This stackoverflow question made me want to experiment. The difference between depth first search and breadth first search is that depth first uses a stack and breadth first uses a queue. What if I use neither, and choose randomly? Would I get organic-looking output?
After implementing it, my feeling is that the number of tiles in each region affects the map boundaries too much. The shapes are more interesting with lower resolution, but I don’t want to change the map resolution to change the shapes. I’d much rather control the shapes independent of map resolution.
However, the nice thing about this approach is that it’s simple and fast.
Variants to try:
- Use an irregular grid like voronoi for the expansion, then rasterize to tiles, so that the shapes will be independent of the tile resolution
- Use Dijkstra’s Algorithm, but use 2D noise for the cost function (instead of height, as people often do)
- Mark mountains and rivers as natural barriers that discourage expansion (see the last example on this page)
Source code: randomized-fill.js