Do they have the POWER?

Question

I'm working on a city building simulation game, and I have reached the point where I need to check whether tiles are connected to a power source. I decided on a flood fill for this, since it seemed simple enough to implement. For reference, I used this flood fill algorithm, and I also found this question on code review about flood fill in java. My code is largely similar to the code in those links, but it is slightly different because I am not filling an image with color but rather marking tiles connected to power plants as isPowered.

I know that recursion is dangerous, and the efficiency of the code may be suspect. With the map mostly filled up, this method gets called a couple of thousand times per cycle. With just a snaky path, about 200 times.

Here is an example to show that the algorithm is working:

The visible tiles are powered.

Here is the code:

private void calculatePower() {
    for (Tile tile : this.tilesForSort) {
        tile.hasBeenSearched = false;
    }
    for (Tile tile : this.tilesForSort) {
        if (tile.getBuildingType() == IsoTileType.POWER) {
            this.powerFill(tile.getPosition().x, tile.getPosition().y);
        }
    }
}
public void powerFill(int x, int y) {

    if (this.isNotInsideGrid(x, y)) {
        return;
    }

    Tile tile = this.levelData[x][y];

    if (tile.hasBeenSearched || tile.zoneType.getLevel() < 1) {
        return;
    }

    tile.isPowered = true;
    tile.hasBeenSearched = true;

    this.powerFill(x - 1, y);
    this.powerFill(x + 1, y);
    this.powerFill(x, y - 1);
    this.powerFill(x, y + 1);
}
private boolean isNotInsideGrid (int x, int y) {
    return x < 0 || y < 0 || x >= World.WORLD_WIDTH || y >= World.WORLD_HEIGHT;
}

Answer 1

It seems that Tile is a key element in your game model. On the other hand, a field like Tile.hasBeenSearched sounds something technical, not something that belongs to conceptual model. You probably don't wake up in the morning thinking, "hm, it will be nice to give the Tile class a hasBeenSearched attribute". This field is an implementation detail of the flood-fill algorithm, and I don't think it fits well into Tile. It will be better to use a Set<Tile> searched. This field could be encapsulated within a FloodFiller class, that takes tilesForSort and returns a collection of tiles for which the caller can set isPowered to true. The advantage of this approach will be that you can reuse FloodFiller for other purposes, say, to actually flood your city.

---

This call is a bit tedious, with the duplicated tile.getPosition():

powerFill(tile.getPosition().x, tile.getPosition().y);

It would be good to create a helper powerFill(tile.getPosition()) that forwards to powerFill(int, int).

---

The name isNotInsideGrid is a bit clumsy. How about isOutsideGrid ?

---

Perhaps something like this might work well:

public class FloodFill {
    interface World {
        Set<Position> getEligibleNeighbors(Position position);
    }

    interface Position {
    }

    public static Set<Position> floodFill(World world, Position start) {
        Set<Position> searched = new HashSet<>();
        floodFill(world, searched, start);
        return searched;
    }

    private static void floodFill(World world, Set<Position> searched, Position position) {

        if (searched.contains(position)) {
            return;
        }

        searched.add(position);

        for (Position neighbor : world.getEligibleNeighbors(position)) {
            floodFill(world, searched, neighbor);
        }
    }
}

The idea is:

• It is the responsibility of the World implementation to return the valid neighbors of a position that are eligible for filling:

  • x +- 1, y +- 1, or whatever coordinate system you use
  • Excluding positions outside of the world's boundary
  • Excluding positions where zoneType.getLevel() < 1
  • Any other custom logic you might need

• The FloodFill class doesn't need to know anything else about the world, and doesn't need to know what "filling" really means

This gives you the flexibility to reuse the flood fill logic to other purposes, without polluting the rest of your game model with specific knowledge catering to the flood fill process.

Answer 2

Incremental vs full search

For a one time power check, the flood fill algorithm you are using is fine. But I would imagine that every time you lay down a new tile, you'd have to update the powered status of your tiles. For example, you might lay down a tile that connects a powered region to a previously unpowered region, thereby causing that whole region to become powered.

Your current algorithm isn't very good for that, because it pretty much starts over from scratch every time, looking for power plants and flood filling from there. You could modify the algorithm to start from any point (such as a newly added tile position). That way, if you add a new tile and it is connected to a powered tile, you could just start a new flood fill from that tile. Removing a tile would require a full search though.

Connectivity between arbitrary tiles

There is another way to check for power which might benefit you more later on. You could use a "union find" or "disjoint set" data structure. This basically makes each tile belong to a connected set. Incrementally adding a tile is close to \$O(1)\$, and checking tiles for connectivity is \$O(1)\$. However, removing a tile is slow and requires a rescan of all tiles connected to the removed tile.

This could help later on, because once you start adding things like roads, water lines, etc, you might want to know whether certain tiles are connected to certain other tiles, not just whether they are "on" or "off". You can use multiple union-find sets to keep track of connectivity by power/road/train/water/sewage/etc.