Connected components algorithm
Sean Barrett

stb_connected_components.h

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 will explore the entirety of the map that is reachable from P).

Finding and updating connected components

The traditional algorithm for finding connected components in a graph is to just use depth-first-search; the equivalent on grids is a "flood-fill" algorithm. These techniques work fine, a

Read more

Connected components library.
Sean Barrett

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.93.

Read more

Public Domain
Sean Barrett