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.

About these ads

39 Responses to Hexagonal grid: Path-finding using A* algorithm

  1. Patrick says:

    Nice work on the tutorial. I’m glad people have found my tutorial (http://ledpup.blogspot.com.au/2011/06/unity-hexagons-and-path-finding.html) and are taking it in a different direction. I’ll have to look closely at your next tutorial – moving animated characters. Looks really useful.

    • hakimio says:

      It wasn’t easy to find it, but it was really helpful. Thanks for creating it :)

      At this point my tutorials cover just some basic stuff and my code might look “a bit” ugly, so I doubt you’ll find anything really interesting here though.

  2. bfreese says:

    Great read. I am having problems with the Findpath function. Is the way you have used the constraint an older way of doing that? How can you use a constraint on a non-generic? I think I could get it to work with a few modifications but wanted to check to see if this was a typo first
    .

  3. bfreese says:

    Great read and thanks for posting this. So far only one question. In the find path function you use a constraint but this function is not a generic. Should this work? The compiler (basic monodevelop) does not seem to like this. thanks!

  4. bfreese says:

    A few other issues have come up as I have gone through the code:

    In the GridManager “calcGridSize” is never declared as a function.

    “groundWidth” is also never declared in the same class.

    I am still a bit unsure about your syntax for the FindPath parameters. The two func params I think are not correct. I am trying to figure out how the syntax should work. It looks like the compiler is looking for a type, but this should be a generic? I have tried passing it in several different ways but I have yet to find a way that works.

    Thanks!

  5. bfreese says:

    “Func distance” I think this is the correct syntax for handling that Func param. I also think “estimate” is never actually used anywhere or declared as a Func in the Grid manager class.

  6. hakimio says:

    @bfreese
    First, keep in mind that this is not stand-alone tutorial, but continuation of the previous one. That’s why some of the methods are missing.

    Now, I don’t really understand what’s the other problem, but here are few suggestions:
    * Use pastebin for pasting code
    * Take a look at my sandbox to see a working example. You can find it in github -> https://github.com/hakimio/KR . You’ll find there a lot of unrelated code, so you’ll have to dig up the code you are looking for.
    * As I mentioned in the “Preparations” section, Patrick Lea created a similar tutorial and he has included the source code -> http://ledpup.blogspot.com/2011/06/unity-hexagons-and-path-finding.html

  7. Teonnyn says:

    Small update needed, apparently IEnumerable is in System.Collections, not System.Collections.Generic;

  8. Hector says:

    Hello, thanks for all the tutorial serie, really have been very helpful.
    I just have to say, I don’t like the path it finds, I’ll prefer to take a more straight route, when possible. Is there any way, I can set a comparison, that if the there are more than one possible choice for next step, it takes the one that is closer to the destination using (x2-x1) + (y2 – y1) ?? If it can be possible, where in the code can I add it?

    Thanks in advantage

    • Hector says:

      Ok, I did, just calculated the distance from the tile being checked, to the line between origin and destination, and added that to the distance. That way it would keep moving as close to the straight line as possible. Of course, this can be problematic with obstacles, but still have to check it, I think that the algorithm would change on time.

      • hakimio says:

        If you want your game character (or whatever you are moving along the path) to “cut corners”, see “Moving animated character in the grid” post. In that post speedmodifier is compared with ‘0.95’ (“if (speedModifier > 0.95f)”) replace “0.95” with a smaller value and see if it helps.

    • tomas says:

      Unless your distance calculation function returns incorrect results or you have some invisible obstacles you should always get the shortest route the way it is implemented now.

      • Hector says:

        Yes, of course it gets the shortest route. But, what I wanted to add, is that the players goes in straight line, as long as it’s possible. Due to Hex tiles disposition, the shortest route, usually won’t be the shortest route in real world, that’s why adding this idea, it would take not only the shortest route, but also a route that is closer to real Cartesian coordinates of real world.

        Thanks a lot for this tutorial, it’s helping me a lot. By the way, is recommended not to use generics, and anything of System namespace, like Func if you are developing for iOS platform.

        Kind Regards, Hector

  9. Flash427 says:

    I’m receiving the error of
    Assets/Grid/Scripts/Tile.cs(6,32): error CS0308: The non-generic type `IHasNeighbours’ cannot be used with the type arguments

    do you have any suggestions to get around this?
    ps this is VERY helpful, thank you very much

    Thank you!

    • hakimio says:

      Stupid wordpress messing up my code… It should be:
      public interface IHasNeighbours<N>
      {
      IEnumerable<N> Neighbours { get; }
      }

      • Flash427 says:

        Thank you that makes sense. I changed that and ran into some issues with IEnumerable. I back tracked a bit to try and figure it out and I’m at the part right before you finally edit the GridManager and Tile. I’m getting 2 errors of

        Assets/Grid/Scripts/IHasNeighbours.cs(5,5): error CS0308: The non-generic type `System.Collections.IEnumerable’ cannot be used with the type arguments

        Assets/Grid/Scripts/PathFinder.cs(15,21): error CS0246: The type or namespace name `IHasNeighbours’ could not be found. Are you missing a using directive or an assembly reference?

        The changes I made were to Path where it is now
        class Path : IEnumerable

        Thanks!

      • hakimio says:

        Try to replace “using System.Collections;” with “using System.Collections.Generic;”.
        You can also try checking a working example at https://github.com/hakimio/KR .

      • helbo says:

        Struggling with the same:

        Assets/Scripts/Arena/PathFinder.cs(10,53): error CS0246: The type or namespace name `IHasNeighbours’ could not be found. Are you missing a using directive or an assembly reference?

        It’s the line: public static Path FindPath(Node start,Node destination,Func distance,Func estimate) where Node: IHasNeighbours

        That gives the error, tried looking at your finished example but you’re much further there and it looked very different obviously.

      • hakimio says:

        You can find “public interface IHasNeighbours” in this blog post. Maybe you missed it.

      • Kelbirk says:

        I’m having the same problem with IHasNeighbours going unrecognized. I’ve got the interface set up in its own file, but Pathfinder apparently isn’t finding it (pun intended).

        using System.Collections.Generic;
        public interface IHasNeighbours {
        IEnumerable Neighbours { get; }
        }

        I don’t get it.

      • hakimio says:

        Things to check:
        * You missed “<N>”
        * You put them in different namespaces and don’t have “using”
        * There is a typo somewhere

        Also, if it helps you can check my code here -> https://github.com/hakimio/KR/tree/master/Project/Assets/Scripts/Arena

  10. mike says:

    I’m trying to wrap my head around this stuff currently, not going too bad, but i was wondering, where do you set the cost to move onto each tile? for instance if i want to set the cost to 1 per tile and then have a unit have 3 movement, they can move 3 tiles per turn kind of thing?

  11. Kaoru says:

    Hai, i am just starting on unity, and i don’t know how to follow this, could you please made video with your latest post, or just post the full source code and/or the application? Thank you.

  12. Fuhans Puji Saputra says:

    Hai, why my character is not moving?

    Here is the link of the image:

    Anyway, thank you for the tutorial, it is help me a lot!

  13. Njits4 says:

    Hi,
    Nice tutorial but I’m stuck with the Tilebehaviour.

    I get this error :” NullReferenceException: Object reference not set to an instance of an object.”
    from GridManager.instance.selectedTile = tile.

    It can’t acces the Gridmanager script.

    In the script Gridmanager : “public static GridManager instance = null;”

    Would mean alot if I get it fixed, thank you.

  14. Hello,
    This is my third time trying to get trough this tutorial, still no luck. I believe I have followed all the steps correctly, but I am getting the same error some of the people above had.

    Assets/Scripts/PathFind/PathFinder.cs(17,29): error CS0246: The type or namespace name `IHasNeighbours’ could not be found. Are you missing a using directive or an assembly reference?

    in the Unity editor and in MonoDevelop;

    Assets\Scripts\PathFind\PathFinder.cs(15,15): Error CS0305: Using the generic type ‘PathFind.IHasNeighbours’ requires ‘1’ type arguments (CS0305) (Assembly-CSharp)

    I have shared my project folder via dropbox, would you mind taking a look to see what I did wrong please?

    https://www.dropbox.com/sh/yuoemj52c0571ik/olNPnRP43g

    Thanks.

  15. Byron says:

    Nice tutorial, I’ve been toying with making a turn based tactics game in Unity for a while using a square grid (because the maths is initially easier), and it just never felt right, so thank you.

    NB: If you plan on updating this sometime may I suggest being a bit more explicit with the generics and integer division as these were the main areas where things got a little fuzzy (at 1:00 in the morning mind you). All working in the end though :)

  16. […] Path Finding sur une grille hexa (EN) […]

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: