Occasionally someone will ask me how to implement Connected Components, which is useful for several things, including
- determining whether there's a path between two points; if there isn't, you can skip running pathfinding
- finding the islands/continents on a procedurally generated map
It's actually a clever use of Breadth First Search. Every time the queue is empty, you find an unvisited node and put it into the queue, and then run the loop some more. When you have no more unvisited nodes, you're done.
I've told people about it but I hadn't implemented it before. So I implemented a demo. I wanted to reuse the generic search diagram I wrote for my pathfinding pages, but that algorithm didn't implement the variant of Breadth First Search I needed. The solution was to use a trick that my Diagram class allows, but that I had forgotten about. The diagrams are implemented in layers (see the diagrams halfway down on this page). The trick is that a layer can calculate things too. It's not limited to drawing things. So I implemented layer that calculated the modified Breadth First Search, and then wrote the data back into the diagram so that subsequent layers could visualize it.
A reader had asked about connecting these islands together. This can also be done with Breadth First Search. The idea is to put all land locations into the starting points. Then as we use the search algorithm to visit the water tiles, as soon as we find a connection between water tiles emanating from two different islands, that tells us not only the meeting point, but also the path to connect the two islands. I implemented this demo too.
I added it to my "distance to any" page, which is poorly named. It originally started out as a single demo for a single use of Breadth First Search, but over time I've expanded it to include several demos that share an idea: that you can start with multiple start points.
While I was updating that page, I decided to change the sample code to highlight the places where it differs from regular Breadth First Search:
Take a look at the new section of the page.
Labels: pathfinding
UnionFind may also be a solution.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Union Find is indeed useful if you are joining existing regions together, or if you are adding tiles afterwards. For this particular problem since all the tiles and regions are already available at the beginning, I think it's simpler to use flood fill (BFS/DFS) on each region. Then we'll have all the tiles connected before the next region is started. There's a bit of discussion over on wikipedia https://en.wikipedia.org/wiki/Component_(graph_theory)#Algorithms
Yes. When it comes to Connected Component, my instinctive thought is UnionFind. But I didn't realize that FloodFill is actually a better way to handle it.Since there is no need joining clusters.
There are also more memory cost in UnionFind.
Post a Comment