Avoiding Expensive A*

The most expensive A* searches are the ones that cannot be reached. It’s a paradox when using A* based path-finding algorithms. You want to know the most optimal path. At the same time, you also want to know if a certain position  is reachable before you execute it. Fortunately, there is such a way.

Advertisements

The most expensive A* searches are the ones that cannot be reached. It’s a paradox when using A* based path-finding algorithms. You want to know the most optimal path. At the same time, you also want to know if a certain position  is reachable before you execute it. Fortunately, there is such a way.

I don’t know the exact term for this. It’s called many names, “flood fill”, “seed fill”, or “connection labeling”. The concept is to “label” connected tiles. Label here simply means setting a unique int value for a set of connected tiles. Before invoking A*, you can simply compare the labels of the start and destination tile. If they are the same, then it means they are reachable and A* can proceed. If not, then they are unreachable and you can entirely skip expensive search. That’s pretty neat for something as simple as comparing integers.

ConnectionLabeling
Here’s an example from our current game Academia. 2 tiles can’t reach the 4 tiles.

This is the flood filler algorithm that I’ve used:

Queue disconnectedQueue;
Queue connectedQueue;

int currentLabel = 1;

// startingTile could be anything from random tile 
// or a tile that has recently been updated. Any tile in a map works.
connectedQueue.Enqueue(startingTile);

while(connectedQueue.Count > 0 || disconnectedQueue.Count > 0) {
    ProcessConnectedQueue();
    ProcessDisconnectedQueue();
}

void ProcessConnectedQueue() {
    while(connectedQueue.Count > 0) {
        Tile tile = connectedQueue.Dequeue();
        if(tile is already labeled) {
            continue;
        }

        bool hasBlocker = tile.HasBlocker; // Whether or not it blocks movement

        // Label the tile
        if(hasBlocker) {
            tile.Label = 0; // Assign zero for blockers
        }

        // Add each neighbor
        foreach(Tile neighbor in tile) {
            AddToQueue(neighbor, hasBlocker);
        }
    }
}

// Identify an unlabeled tile and add it to the connectedQueue for processing
void ProcessDisconnectedQueue() {
    while(disconnectedQueue.Count > 0) {
        Tile tile = disconnectedQueue.Dequeue();
        if(tile is already labeled) {
            // We are not interested in labeled tiles
            continue;
        }

        if(!tile.HasBlocker) {
            // Update the label if the next tile to process is not a blocker
            ++currentLabel;
        }

        connectedQueue.Enqueue(tile);
        break;
    }
}

void AddToQueue(Tile tile, bool hasBlocker) {
    if(tile is already labeled) {
        // No need to add to queue since it was already labeled
        return;
    }

    if(tile.HasBlocker == hasBlocker) {
        // Has the same blocker value. They are connected.
        connectedQueue.Enqueue(tile);
    } else {
        // Not the same blocker value. They are disjoint.
        disconnectedQueue.Enqueue(tile);
    }
}

The tile labels are updated every time a tile becomes a blocker like when a wall is built on it. Our implementation of the algorithm runs in multiple frames so that the game wouldn’t slow down whenever something is built. We process X number of tiles per frame. I’m still adjusting the right number.

What do you think? Let me know how you can make the flood algorithm run faster.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s