Sorceress

Procedural generation strategies

May 3rd, 2016
240
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Procedural generation strategies
  2. --------------------------------
  3.  
  4. Before deciding what algorithm to use, you need to remember that there probably isn't a perfect algorithm. There rarely is. So whatever you choose it will have advantages and disadvantages. You have to think in terms of trade-offs.
  5.  
  6. Typical trade-offs are:
  7. Run-time;
  8. Memory usage;
  9. Quality of solution;
  10. Variety of solutions;
  11. Work time (To design+write your algorithm).
  12.  
  13. --------------------------------
  14. [1] Generate a random solution.
  15.  
  16. - Predictable fast run-time.
  17. - The solution could be good or bad. Expect bad.
  18.  
  19. --------------------------------
  20. [2] Generate random solutions over and over, until you find one "good enough" that passes some tolerance.
  21.  
  22. - It will find a good solution, providing the search terminates.
  23. - Unpredictable run-time. May not terminate at all if the tolerance is set too high.
  24.  
  25. --------------------------------
  26. [3] Generate a fixed number of random solutions, and pick the best of those.
  27.  
  28. - Predictable run-time. Could be fast or slow, depending on the number chosen.
  29. - Not guaranteed to find a good solution every time. It might even be a terrible solution some times.
  30.  
  31. --------------------------------
  32. [4] Generate a random solution, then iteratively modify it to get better solutions.
  33.  
  34. - Should be fast.
  35. - May find a "local maximum", whereby your modifications won't improve it, because the much better solutions are too different from what you ended up with.
  36.  
  37. --------------------------------
  38. [5] Solve the problem on paper, and hand-pick solutions you like.
  39.  
  40. - Very fast run-time, as the computer is just picking a random thing from a list.
  41. - Potentially good solutions, because you've hand-picked them.
  42. - Lacks variation, as the solutions are limited to the few you've chosen.
  43. - Depending on the nature of the problem, it could use a lot of memory to store all these picked solution. It might be a lot of work.
  44.  
  45.  
  46. [...]
RAW Paste Data