Monthly Archives: March 2014

Randomized floodfill

Aside from the more prosaic graph traversals (breadth first, depth first, and the all-encompassing best first), we have a class of randomized traversals that come in useful in roguelikes. The best understood of these we call randomized floodfill.

In its simplest form, imagine a breadth first traversal, your common floodfill. With each node you visit, you push all unvisited neighbors onto the frontier; to visit the next cell, you pop one off the other end of the frontier. If you pick that cell off the frontier at random, you have implemented randomized floodfill.

The simplest class of these is useful for ponds and lakes and other natural formations. Just keep a count of the number of cells you want to visit and stop adding any more to the frontier when you have visited enough (but do be sure to run through the rest of the frontier or you’ll end up with gaps.) A uniform distribution does just fine, but if you experiment with unusual distributions you can get some really exceptional shapes.

If instead of simply pushing neighbors onto the frontier you push edges, you can distinguish between the ways of reaching a cell, if two of its neighbors have already been visited; in this way you can trivially generate labyrinths, for instance.

You can maintain more state than just the number of cells visited so far. You can make some pretty good mountains (although you need to fiddle with the distribution to make great ones) by simply decrementing the height of each new cell you visit. The random order tends to make this work out as a nicely craggy but generally smooth construction.

It’s an open question at the moment whether random visitation can help us solve any of our major pathfinding questions. A best-weighted search, for instance, might fail to find the very best path at times, but it would very probably perform better than A* when the best heuristic isn’t very good. Using randomness to break ties introduces no risk of missing the best solution and might be especially useful for collaborative pathfinding; most possible sets of collaborative moves are indistinguishable each turn from one another, and expanding a node at random is a better bet than always proceeding in the same order.

Give randomized floodfill a try as part of your procedural generation — you’re likely to find that you rarely need anything better than the simplest form.