Hexagonal grid: Path-finding using A* algorithm

Preparations

As usual let’s start with things you should know before following this guide. Firstly, as this entry is continuation of “Hexagonal grid” article series, you should know about the things explained in Generating the grid article. Also, even I will explain some of the implementation details, you should know how A* search algorithm works. Next you should read “Hexagon grids: coordinate systems and distance calculations” article by Chris Schetter to know what I mean by squiggly axis and straight axis coordinate systems. Finally, you should read “Path Finding Using A* in C# 3.0” article series by Eric Lippert because we’ll be using his generic path finding implementation. Oh, and one more thing I would like to mention before we move on with the tutorial: this tutorial will be in many ways similar to Patrick Lea’s “Unity, hexagons and path-finding” with few key differences – I will use straight axis coordinate system, because of which things like distance calculations and neighbor tile coordinate calculations will be different, also I will use slightly different ways to represent pathfindng results, determine origin and destination tiles and I will take into account ground dimensions.

The model layer

If some of you are not familiar with “model layer” terminology, model layer groups classes which are usually used for data representation. Classes here should be simple enough to understand without any explanation for any average C# coder.

using System;

//struct holding x and y coordinates
public struct Point
{
    public int X, Y;

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
}

using System;
//abstract class implemented by Tile class
public abstract class GridObject
{
    public Point Location;
    public int X { get { return Location.X; } }
    public int Y { get { return Location.Y; } }

    public GridObject(Point location)
    {
        Location = location;
    }

    public GridObject(int x, int y): this(new Point(x, y)) {}

    public override string ToString()
    {
        return string.Format("({0}, {1})", X, Y);
    }
}

using System.Collections;
//interface that should be implemented by grid nodes used in E. Lippert's generic path finding implementation
public interface IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

using System.Collections;
using System;
using System.Linq;
using UnityEngine;
//Basic skeleton of Tile class which will be used as grid node
public class Tile: GridObject, IHasNeighbours<Tile>
{
    public bool Passable;

    public Tile(int x, int y)
        : base(x, y)
    {
        Passable = true;
    }

    public IEnumerable AllNeighbours { get; set; }
    public IEnumerable Neighbours
    {
        get { return AllNeighbours.Where(o => o.Passable); }
    }
}

The last class is not complete and we will return to it a bit later.

Generic A* algorithm implementation

For generic A* implementation we’ll be using the code kindly provided by Eric Lippert and I will only add few comments to the actual path finding algorithm implementation and none to the data classes which are easy to understand once written but might not be so easy to come up with.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class Path: IEnumerable
{
//this comment should be replaced by code from http://goo.gl/oJ6Hd
}

 

using System;
using System.Collections.Generic;
using System.Linq;

class PriorityQueue
{
//this comment should be replaced by code from http://goo.gl/ugzP6
}

using System;
using System.Collections.Generic;
using System.Linq;

public static class PathFinder
{
    //distance f-ion should return distance between two adjacent nodes
    //estimate should return distance between any node and destination node
    public static Path<Node> FindPath<Node>(
        Node start,
        Node destination,
        Func distance,
        Func estimate)
        where Node: IHasNeighbours
    {
        //set of already checked nodes
        var closed = new HashSet();
        //queued nodes in open set
        var queue = new PriorityQueue>();
        queue.Enqueue(0, new Path(start));

        while (!queue.IsEmpty)
        {
            var path = queue.Dequeue();

            if (closed.Contains(path.LastStep))
                continue;
            if (path.LastStep.Equals(destination))
                return path;

            closed.Add(path.LastStep);

            foreach (Node n in path.LastStep.Neighbours)
            {
                double d = distance(path.LastStep, n);
                //new step added without modifying current path
                var newPath = path.AddStep(n, d);
                queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
            }
        }

        return null;
    }
}

Interacting with the grid

The result of the previous tutorial is nothing more than just a plain grid represantation which can not be interacted with in any way. This time let’s make it look better and react to some mouse actions. For that to happen we will need to introduce new TileBehavior class which will be used with hex tile prefab and modify our GridManager class from the last section in Generating the grid tutorial plus add a couple new hex tile materials to our project. The first new material should use white texture with some other color representing hex tile outline and the second one should be completely transparent except hex tile outlines plus the shader used in both cases should be “Transparent/Diffuse”. If you are using hex tile model which I linked to in the previous tutorial, you can find textures for it here. After you have created two new materials, let’s modify a bit our GridManager class.

public class GridManager: MonoBehaviour
{
    //selectedTile stores the tile mouse cursor is hovering on
    public Tile selectedTile = null;
    //TB of the tile which is the start of the path
    public TileBehaviour originTileTB = null;
    //TB of the tile which is the end of the path
    public TileBehaviour destTileTB = null;

    public static GridManager instance = null;

    void Awake()
    {
        instance = this;
    }
    //some of the omitted code from the original goes here
    void createGrid()
    {
        Vector2 gridSize = calcGridSize();
        GameObject hexGridGO = new GameObject("HexGrid");

        for (float y = 0; y < gridSize.y; y++)
        {
            float sizeX = gridSize.x;
            //if the offset row sticks up, reduce the number of hexes in a row
            if (y % 2 != 0 && (gridSize.x + 0.5) * hexWidth > groundWidth)
                sizeX--;
            for (float x = 0; x < sizeX; x++)
            {
                GameObject hex = (GameObject)Instantiate(Hex);
                Vector2 gridPos = new Vector2(x, y);
                hex.transform.position = calcWorldCoord(gridPos);
                hex.transform.parent = hexGridGO.transform;
                //TileBehabiour object is retrieved
                var tb = (TileBehaviour)hex.GetComponent("TileBehaviour");
                //y / 2 is subtracted from x because we are using straight axis coordinate system
                tb.tile = new Tile((int)x - (int)(y / 2), (int)y);
            }
        }
    }
    //following method will be implemented a bit later
    public void generateAndShowPath() {}
//the rest of the omitted code goes here

We’ll come back to GridManager once again once we’ll be showing the path but for now, let’s leave it and take a look at our TileBehaviour class.

using UnityEngine;
using System.Collections;

public class TileBehaviour: MonoBehaviour
{
    public Tile tile;
    //After attaching this script to hex tile prefab don't forget to initialize following materials with the ones we created earlier
    public Material OpaqueMaterial;
    public Material defaultMaterial;
    //Slightly transparent orange
    Color orange = new Color(255f / 255f, 127f / 255f, 0, 127f/255f);

    void changeColor(Color color)
    {
        //If transparency is not set already, set it to default value
        if (color.a == 1)
            color.a = 130f / 255f;
        renderer.material = OpaqueMaterial;
        renderer.material.color = color;
    }

    //IMPORTANT: for methods like OnMouseEnter, OnMouseExit and so on to work, collider (Component -> Physics -> Mesh Collider) should be attached to the prefab
    void OnMouseEnter()
    {
        GridManager.instance.selectedTile = tile;
        //when mouse is over some tile, the tile is passable and the current tile is neither destination nor origin tile, change color to orange
        if (tile.Passable && this != GridManager.instance.destTileTB
            && this != GridManager.instance.originTileTB)
        {
            changeColor(orange);
        }
    }

    //changes back to fully transparent material when mouse cursor is no longer hovering over the tile
    void OnMouseExit()
    {
        GridManager.instance.selectedTile = null;
        if (tile.Passable && this != GridManager.instance.destTileTB
            && this != GridManager.instance.originTileTB)
        {
            this.renderer.material = defaultMaterial;
            this.renderer.material.color = Color.white;
        }
    }
    //called every frame when mouse cursor is on this tile
    void OnMouseOver()
    {
        //if player right-clicks on the tile, toggle passable variable and change the color accordingly
        if (Input.GetMouseButtonUp(1))
        {
            if (this == GridManager.instance.destTileTB ||
                this == GridManager.instance.originTileTB)
                return;
            tile.Passable = !tile.Passable;
            if (!tile.Passable)
                changeColor(Color.gray);
            else
                changeColor(orange);

            GridManager.instance.generateAndShowPath();
        }
        //if user left-clicks the tile
        if (Input.GetMouseButtonUp(0))
        {
            tile.Passable = true;

            TileBehaviour originTileTB = GridManager.instance.originTileTB;
            //if user clicks on origin tile or origin tile is not assigned yet
            if (this == originTileTB || originTileTB == null)
                originTileChanged();
            else
                destTileChanged();

            GridManager.instance.generateAndShowPath();
        }
    }

    void originTileChanged()
    {
        var originTileTB = GridManager.instance.originTileTB;
        //deselect origin tile if user clicks on current origin tile
        if (this == originTileTB)
        {
            GridManager.instance.originTileTB = null;
            renderer.material = defaultMaterial;
            return;
        }
        //if origin tile is not specified already mark this tile as origin
        GridManager.instance.originTileTB = this;
        changeColor(Color.red);
    }

    void destTileChanged()
    {
        var destTile = GridManager.instance.destTileTB;
        //deselect destination tile if user clicks on current destination tile
        if (this == destTile)
        {
            GridManager.instance.destTileTB = null;
            renderer.material.color = orange;
            return;
        }
        //if there was other tile marked as destination, change its material to default (fully transparent) one
        if (destTile != null)
            destTile.renderer.material = defaultMaterial;
        GridManager.instance.destTileTB = this;
        changeColor(Color.blue);
    }
}

Now, after you attach collider (Component -> Physics -> Mesh collider) and TileBehaviour script, instantiate opaque and default materials with the materials we created earlier and finally start the game you should be able to select origin and destination tiles plus tile color should change but nothing more will happen. We need to actually generate the path and show it.

Generating and showing the path

Finally we come to the last part of this tutorial where we actually generate and show the path. To do just that we’ll need to modify our GridManager once again.

//Some part of the code covered before is omitted
    //Line should be initialised to some 3d object that can fit nicely in the center of a hex tile and will be used to indicate the path. For example, it can be just a simple small sphere with some material attached to it. Initialise the variable using inspector pane.
    public GameObject Line;
    //List to hold "Lines" indicating the path
    List<GameObject> path;

    void Start()
    {
        setSizes();
        createGrid();
        generateAndShowPath();
    }

    void createGrid()
    {
        Vector2 gridSize = calcGridSize();
        GameObject hexGridGO = new GameObject("HexGrid");
        //board is used to store tile locations
        Dictionary<Point, Tile> board = new Dictionary<Point, Tile>();

        for (float y = 0; y < gridSize.y; y++)
        {
            float sizeX = gridSize.x;
            //if the offset row sticks up, reduce the number of hexes in a row
            if (y % 2 != 0 && (gridSize.x + 0.5) * hexWidth > groundWidth)
                sizeX--;
            for (float x = 0; x < sizeX; x++)
            {
                GameObject hex = (GameObject)Instantiate(Hex);
                Vector2 gridPos = new Vector2(x, y);
                hex.transform.position = calcWorldCoord(gridPos);
                hex.transform.parent = hexGridGO.transform;
                var tb = (TileBehaviour)hex.GetComponent("TileBehaviour");
                //y / 2 is subtracted from x because we are using straight axis coordinate system
                tb.tile = new Tile((int)x - (int)(y / 2), (int)y);
                board.Add(tb.tile.Location, tb.tile);
            }
        }
        //variable to indicate if all rows have the same number of hexes in them
        //this is checked by comparing width of the first hex row plus half of the hexWidth with groundWidth
        bool equalLineLengths = (gridSize.x + 0.5) * hexWidth <= groundWidth;
        //Neighboring tile coordinates of all the tiles are calculated
        foreach(Tile tile in board.Values)
            tile.FindNeighbours(board, gridSize, equalLineLengths);
    }
    //Distance between destination tile and some other tile in the grid
    double calcDistance(Tile tile)
    {
        Tile destTile = destTileTB.tile;
        //Formula used here can be found in Chris Schetter's article
        float deltaX = Mathf.Abs(destTile.X - tile.X);
        float deltaY = Mathf.Abs(destTile.Y - tile.Y);
        int z1 = -(tile.X + tile.Y);
        int z2 = -(destTile.X + destTile.Y);
        float deltaZ = Mathf.Abs(z2 - z1);

        return Mathf.Max(deltaX, deltaY, deltaZ);
    }

    private void DrawPath(IEnumerable<Tile> path)
    {
        if (this.path == null)
            this.path = new List<GameObject>();
        //Destroy game objects which used to indicate the path
        this.path.ForEach(Destroy);
        this.path.Clear();

        //Lines game object is used to hold all the "Line" game objects indicating the path
        GameObject lines = GameObject.Find("Lines");
        if (lines == null)
            lines = new GameObject("Lines");
        foreach (Tile tile in path)
        {
            var line = (GameObject)Instantiate(Line);
            //calcWorldCoord method uses squiggly axis coordinates so we add y / 2 to convert x coordinate from straight axis coordinate system
            Vector2 gridPos = new Vector2(tile.X + tile.Y / 2, tile.Y);
            line.transform.position = calcWorldCoord(gridPos);
            this.path.Add(line);
            line.transform.parent = lines.transform;
        }
    }

    public void generateAndShowPath()
    {
        //Don't do anything if origin or destination is not defined yet
        if (originTileTB == null || destTileTB == null)
        {
            DrawPath(new List<Tile>());
            return;
        }
        //We assume that the distance between any two adjacent tiles is 1
        //If you want to have some mountains, rivers, dirt roads or something else which might slow down the player you should replace the function with something that suits better your needs
        Func<Tile, Tile, double> distance = (node1, node2) => 1;

        var path = PathFinder.FindPath(originTileTB.tile, destTileTB.tile, 
            distance, calcDistance);
        DrawPath(path);
    }
//Part of the code omitted

The last piece of the puzzle – FindNeighbours method implementation in the Tile class

public class Tile: GridObject, IHasNeighbours<Tile>
{
//Some previously covered code omitted

    //change of coordinates when moving in any direction
    public static List<Point> NeighbourShift
    {
        get
        {
            return new List<Point>
                {
                    new Point(0, 1),
                    new Point(1, 0),
                    new Point(1, -1),
                    new Point(0, -1),
                    new Point(-1, 0),
                    new Point(-1, 1),
                };
        }
    }

    public void FindNeighbours(Dictionary<Point, Tile> Board,
        Vector2 BoardSize, bool EqualLineLengths)
    {
        List<Tile> neighbours = new List<Tile>();

        foreach (Point point in NeighbourShift)
        {
            int neighbourX = X + point.X;
            int neighbourY = Y + point.Y;
            //x coordinate offset specific to straight axis coordinates
            int xOffset = neighbourY / 2;

            //If every second hexagon row has less hexagons than the first one, just skip the last one when we come to it
            if (neighbourY % 2 != 0 && !EqualLineLengths &&
                neighbourX + xOffset == BoardSize.x - 1)
                continue;
            //Check to determine if currently processed coordinate is still inside the board limits
            if (neighbourX >= 0 - xOffset &&
                neighbourX < (int)BoardSize.x - xOffset &&
                neighbourY >= 0 && neighbourY < (int)BoardSize.y)
                neighbours.Add(Board[new Point(neighbourX, neighbourY)]);
        }

        AllNeighbours = neighbours;
    }
}

At long last, initialize Line game object defined in GridManager class with some 3d object that fits inside your hexagon tile and push “play” to see everything’s working as expected 🙂

Small update: in case something doesn’t work for you, take a look at a working example code at github.