Caching bounds of entity clumps

[kostmo]

Somewhat related to #1260, upon loading a map "tile", some up-front analysis could be performed that may facilitate other commands, in particular the path command when used to locate entities.

Take, for example, this procedurally-generated map containing patches of flowers:

Thresholding on a Perlin noise value in the DSL will create contiguous patches of entities. It would be useful to have internal access to the extents of, quantity within, and/or centroid of each patch to facilitate pathfinding.

[kostmo]

Would like to return a hierarchy of nested "blobs", something like findContours.

Ideally we'd be able to use a Haskell implementation of connected component labeling. This is implemented in OpenCV, but the Haskell OpenCV wrapper for this is a bit old. The contours functions might work, though. Underlying the algorithm is union-find, which is discussed here.

Update: The friday package might work.

[byorgey]

Can you elaborate on how this would help with path finding? It sounds cool but I don't yet understand why doing this extra work would be worthwhile.

The big challenge, in my mind, would be the ability to update whatever data structure caches this information whenever more of the map is revealed. Directly using a union-find structure seems like the way to go, as opposed to using a prepackaged solution which assumes that you give it an entire image up front which will never be extended. Also, the module in the friday package you linked to seems to be only for binary images, but presumably we want something that works with blobs of arbitrary entities.

[xsebek]

About how many robots would have to search for paths for this to be a net improvement? 🤔

Let's say that I want to play a normal game where I occasionally collect or plant a forest, would that not lead to a lot of updates that slow the game down? If any robots do automated gardening, that would presumably need to be continuously cached, right?

[byorgey]

I also just remembered that a union-find won't work at all, since it only allows you to connect things but never disconnect them (as could happen e.g. when entities are harvested). In theory one could use something like link/cut trees but that sounds overcomplicated.

[kostmo]

Alternatively, perhaps a quadtree would suffice as a means to locate areas of relatively higher density of a given entity.

I've found implementations in the following packages so far:

• QuadTree - appears limited in capability
• hgeometry - may be a pretty heavyweight package for what we would use

Perhaps rolling our own implementation, specialized to integral coordinates, wouldn't be too hard.

[byorgey]

My previous question still stands:

Can you elaborate on how this would help with path finding? It sounds cool but I don't yet understand why doing this extra work would be worthwhile.