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?
(reload the page to see a new map)
After implementing it, my feeling is that the randomness would be fine for a small map, but it isn’t enough for a large map. I generally don’t like these types of results. It means the number of tiles in each region affects the map boundaries too much. I’d much rather have something that’s independent of resolution.
However, the nice thing about this approach is that it’s simple and fast. It can be combined with obstacles like mountains or rivers (see the last example on this page).
Another idea: use Dijkstra’s Algorithm, with a priority queue, but use 2D noise for the cost function (instead of height, as people often do). I haven’t implemented this, but I think it has a better chance of being resolution-independent, because the noise function doesn’t depend on the resolution.