How can I adapt "random walk" generation to very large maps?

Question

The random (or drunkard's) walk is a great, simple algorithm that can generate very organic-looking maps, such as this:

Unfortunately it seems to have poor scalability, making it unsuitable for generating large maps in a reasonable amount of time. For example, a test I performed looking at how many iterations are required to generate a desired range for a 1D random walk yielded what looked like quadratic complexity:

Range | Iterations
------+-----------
10    | 81
100   | 7309
1000  | 585352
10000 | 30656784

For higher-dimension walks I imagine this would be even worse.

How can improve the efficiency of random walk, whilst preserving the overall look of the result, for large maps? I'm hoping for a solution with sub-quadratic complexity.

Answer 1

"Divide and conquer" is a good first step towards reducing the complexity of any such algorithm.

Use some heuristics based on your previous metrics gathering to define some number n based on the size of the map to be generated, where n indicates how many independent random walks to run in parallel. Choose n random starting locations, possibly weighted towards the center of the map to avoid the likely-hood of smashing up against the borders, and run the walks.

If you keep track of the walks only as a set of coordinate pairs you can, once the walks are complete, attach them all to eachother. There are several ways you could go about this. Two I can think of offhand are to:

• compute the bounding regions of the walk (possibly breaking a walk into multiple regions if it's total bounding region is too long in one dimension or another), consider them "rooms" and attach them using one of several typical techniques for connection rooms in Roguelike games.

• select random points within the walks, pairwise, and translate the results of one walk into the frame of the other walk at that point. Optionally rotate the translating walk by some amount.

As Nathan suggested in the comments, a hierarchical approach is also a good place to explore: use a walk that consumes chunks of your grid to define a rough layout, and after each chunk is consumed start a smaller, fine-grained walk within that chunk.

Answer 2

Your observation is perfectly accurate. The dependence of the map size of a random walk on the number of iterations is well known to have a power of 1/2, i.e., R~N^(1/2), and R is usually called the radius of gyration.

You could try a self-avoiding random walk, which grows "faster" R~N^(3/(d+2)), i.e., in two-dimensional d=2 it will grow with a power of 3/4. This will still take more than linear-time, but I believe this is unreachable (Best case is a 1d-linear chain, visiting every point once will still take linear time). The results will differ, because (as the name suggests), a point will only be visited once. But if your goal is simply an organic looking map, you can probably recreate a similar look by additional means. As suggested, you work out a hierarchical approach. First a self-avoiding random walk on a course grid, then replacing each point with a dense, filled structure.