Breadth First Search Algorithm With Varying Terrain Costs

15 September 2016
Engine: Unity
Language: C#

This is a flipped version of Dijkstra’s Algorithm that I made for a hex tile based battle game I’m working on. Units of troops have fixed movement amounts and each different type of terrain has a cost to enter that tile. Given that, this algorithm figures out every possible spaces a unit can move into using the least amount of movement. These spaces are then highlighted allowing players to get a full picture of their movement options.

The coordinate and neighbor assignment rules and the pseudo code I used as my starting point were based on Red Blob Games Hexagonal Grids page. It’s a great resource for anyone using hexagonal boards for their games that even includes the math involved in aligning hexagons. I cant recommend it more highly!

The Code Explained:

Every tile is assigned an X and Y location value and has a list of all their neighbors. When the player selects a unit, the neighboring hexes are searched through to determine if that tile can be moved into based on the tile’s accessibility and the movement cost to enter the particular terrain. (ex. Hills cost more movement than plains but are still accessible. Units can never enter mountain tiles or tiles occupied by other units.)

A list of neighbors and the remaining movement power the unit would have if entering that tile is made. The neighbors of all those tiles are checked the same way as the initial neighbors, except this time if a more efficient path (a new rout with a lower movement cost) is found the lesser movement power is assigned to that destination tile.

This process repeats until no more tiles can be moved into. In the end, you’re left with a list of possible tiles the unit can move into and how much movement power that would expend. My game uses this information to highlight all possible tiles the unit can move into to give the player a clear visualization of their options for that particular unit. This algorithm can be scaled to account for any number of terrain effects or map sizes.

public static List<Node> TilesTroopCanMoveTo(GameObject Unit){

    int x = (int)Unit.GetComponent<UnitData> ().tileLocation.x;
    int y = (int)Unit.GetComponent<UnitData> ().tileLocation.y;

    List<Node> possibleDestinations;
    possibleDestinations = new List<Node> ();

    List<Node> visited; //the list to see what tiles you already know you can visit. maybe it's useless because of possibleDestinations
    visited = new List<Node> ();

    List<Node> fringe; //this is the boarder of the currently checked tiles
    fringe = new List<Node> ();

    List<float> movementLeft; //when you add nodes to the fringe list you should also add to this array to keep track of the varying movement points you have left
    movementLeft = new List<float> (); //movementLeft must always be the same length as fringe so their values correspond



    float movement = Unit.GetComponent<UnitData>().movement;


    visited.Add (graph [x, y]);
    foreach (Node neighbor in graph [x, y].neighbours) { //visit all your immediate neighbors if you can
        GameObject tileInQuestion = GameObject.Find ("/Map/Tile_" + neighbor.x + "," + neighbor.y);
        if (tileInQuestion.GetComponent<TileData> ().accessable) {
            possibleDestinations.Add (graph [neighbor.x, neighbor.y]);
            visited.Add (graph [neighbor.x, neighbor.y]);
            fringe.Add (graph [neighbor.x, neighbor.y]);
            movementLeft.Add (movement - CostToEnterTile (tileInQuestion));
        }
    }


    //is it checking all neighbors
    int f;
    while (fringe.Count > 0) {
        
        f = fringe.Count;
        while (f > 0) { //for ever tile in the current fringe

            //remove the movementLeft and the fringe after this foreach loop but within the above wile loop
            movement = movementLeft [0]; //movement left in the current fringe

            foreach (Node neighbor in graph [fringe[0].x,fringe[0].y].neighbours) { //for each neighbor to the current fringe tile we're looking at
                GameObject tileInQuestion = GameObject.Find ("/Map/Tile_" + neighbor.x + "," + neighbor.y);
                //check if the neighbor you're looking at is within the fringes

                if (!possibleDestinations.Contains (neighbor)) { //if it's not a possible destination or if it is and it has some un visited node neighbors
                    visited.Add (graph [neighbor.x, neighbor.y]); //this was making it so if you visited somewhere before and couldn't get to it one way you'd never be able to get to it
                    if (tileInQuestion.GetComponent<TileData> ().accessable) {


                        float entranceCost = CostToEnterTile (tileInQuestion);
                        if (!tileInQuestion.GetComponent<TileData> ().occupied) { //if unoccupied
                            if (movementLeft [0] >= entranceCost) {
                                possibleDestinations.Add (graph [neighbor.x, neighbor.y]);

                                fringe.Add (graph [neighbor.x, neighbor.y]);
                                movementLeft.Add (movement - entranceCost);
                            }
                        } else if (tileInQuestion.GetComponent<TileData> ().occupyingArmy == Unit.GetComponent<UnitData> ().army) //if the tile is occupied, ensure that the unit is friendly

                            if (movementLeft [0] >= entranceCost) {
                            possibleDestinations.Add (graph [neighbor.x, neighbor.y]);

                            fringe.Add (graph [neighbor.x, neighbor.y]);
                            movementLeft.Add (movement - entranceCost);
                        }
                    }
                } else if (fringe.Contains (neighbor)) {
                    float entranceCost = CostToEnterTile (tileInQuestion);
                    if (movementLeft [0] >= entranceCost) { //if we can move in to the tile from our current position
                        int index = fringe.IndexOf (neighbor);

                        //only adjust movement cost for repeating ones if the movementLeft is greater. this would mean removing the tile and adding it again
                        if (movementLeft [index] < movementLeft [0] - entranceCost) //if it's easier to get into that fringe tile from this new rout
                            movementLeft [index] = movementLeft [0] - entranceCost;

                    }
                }
            }

            fringe.RemoveAt (0);
            movementLeft.RemoveAt (0);
            f--;
        }
    }
    return possibleDestinations;
}