STB libraries » Blog

Connected components algorithm

Sean Barrett  — 3 years, 6 months ago

stb_connected_components.h (stbcc) finds the connected components on a large 2D grid, and tracks those connected components as the grid is updated. This is trickier than you might think.

stbcc has many possible uses, but it was inspired in particular by a comment by the programmer of Dwarf Fortress that they kept a separate data structure that could efficiently answer the question of whether any given point Q on the map was reachable from some other point P, and they used this to prevent degenerate slowness in pathfinding from P to Q (which, if Q is unreachable, typically ...
Read More →

Connected components library.

Sean Barrett  — 3 years, 6 months ago
Last weekend I wrote a new library, stb_connected_components.h, which solves a problem a friend of mine was having, but which is also generally useful.

I wrote the initial version entirely on a 5.5 hour twitch stream. This includes about 45 minutes creating some test data and a reference solution, and some time at the end optimizing things.

There were additional updates to the library since the initial version, one to reduce memory by a factor of 10 in the 1024x1024 case, and some which fix some degenerate cases to have better performance. It's currently at version 0 ...
Read More →

Public Domain

C Sean Barrett  — 3 years, 7 months ago