1
\$\begingroup\$

I have a grid where objects can be placed down by the player. Each object that gets placed down is added to a dictionary where the key is the grid position.

Each object that gets placed down either gets added to a new zone, or added to an existing zone if any of the neighbors are in an existing zone. If there are multiple zones, then it just picks the first one it finds and adds it.

The issue I am struggling with is how to handle splitting up zones if an object is removed from the grid.

enter image description here enter image description here enter image description here

In the first image I have 2 zones.

In the second image, I add a new object to the grid, because that tile contains 2 neighbor tiles that are in a zone, it merges the 2 zones into one.

In the third image, I remove an object from the grid, which removes it from the zone, and in this case it creates 2 new zones (but could be more depending on neighbors). This is where I am struggling to work out the best way to efficiently do this.

  • I have a grid array that holds all objects placed on the grid.
  • A zone contains a list of tiles that are in that zone.
  • Each tile in a zone also gets a zone id.

What would be a fast efficient way of splitting up a zone into multiple zones?

I thought about checking all the tiles in the zone by checking its neighbors, but thought that it could be quite slow, as a zone can grow to be very big over time (zones can auto merge as well). Also wouldn't there be a chance of an endless loop?

\$\endgroup\$
  • \$\begingroup\$ You can do a first coarse test locally: if the removed tile's eight neighbours are still connected after removal, there's nothing to do. \$\endgroup\$ – Quentin Feb 15 '18 at 18:01
  • 1
    \$\begingroup\$ This looks like a pretty conventional depth-first-search problem, which should be blazingly fast up to many thousands of elements unless your lookups are especially slow. You might be prematurely optimizing here. \$\endgroup\$ – DMGregory Feb 15 '18 at 19:36
1
\$\begingroup\$

Unfortunately there is no tidy way to do this. Anytime you delete a node that was touching more than 1 other node in the grid you will have the opportunity to split the zone into 4 or more child zones. There is no way of knowing if that split occurs unless you use some sort of flood-fill algorithm to reassign zones.

I would create a stack of points containing each filled node that touches the deleted space. Create a new zone for each of those points. Expand that stack with a flood-fill algorithm, merging zones as they meet. Create a temporary array of bits the size of your grid to track which nodes have already been checked. Below is an example:

Depth-First Example of Zone determination

Using a stack for this results in Depth-First searching. That means that the zones will grow one at a time while the rest remain a single node, so merging is as simple as reassigning one node. If you solely want checking, then just push one node and run until all the other nodes have been touched. If all the surrounding nodes are reached then the zone hasn't been split. If the stack runs out before they are reached then the zone has been split. In that case you could leave the original zone alone and run the above algorithm with just the nodes that weren't reached.

In the example above nodes in Zone 2 are reassigned back to Zone 1 after the whole process is completed. This may not be required by your program.

This may seem inefficient, but it should be quite fast if your data is stored normally. Don't try to optimize too much prematurely.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.