tag:blogger.com,1999:blog-5052387.post5708560722501051108..comments2024-03-17T16:13:55.262-07:00Comments on Blobs in Games: Connected ComponentsAmithttp://www.blogger.com/profile/12159325271882018300noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5052387.post-53677692820248253452023-04-15T07:11:34.642-07:002023-04-15T07:11:34.642-07:00Yes. When it comes to Connected Component, my inst...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.<br /><br />There are also more memory cost in UnionFind. lexnewgatehttps://www.blogger.com/profile/11634461946892053650noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-47545743322280841152023-04-13T08:30:34.351-07:002023-04-13T08:30:34.351-07:00Union Find is indeed useful if you are joining exi...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)#AlgorithmsAmithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5052387.post-28349909239339539542023-04-11T01:51:04.708-07:002023-04-11T01:51:04.708-07:00UnionFind may also be a solution.
https://en.wiki...UnionFind may also be a solution. <br />https://en.wikipedia.org/wiki/Disjoint-set_data_structurelexnewgatehttps://www.blogger.com/profile/11634461946892053650noreply@blogger.com