Pathfinding shouldn’t care about the map

Back to posting on the blog… after a long while. Lack of time is the only issue that stops me from publishing the piling up stuff I want to share. But, as I am wrapping up the last couple of courses for my Master’s degree right now I hope to find a little bit of extra time to write.

One of those last projects I am doing is for the “Game Programming” course. This one will give me a chance to improve my XNA library of reusable classes and components that I hope to use in a real game someday.
In short, this project will be a small strategy game where some human knights battle monsters (not sure what kind yet) such as orcs (that’s new 🙂 ). It’s an excuse to implement some of the basic game AI techniques such as: procedural generation, pathfinding, finite state machines and maybe, time permitting, some emotional computing.

A few days ago I was working on the pathfinding part and, as usual, I first search online to see what is already out there, so I came across THIS very nice implementation by Roy Triesscheijn. It is quite well done, but what I started thinking about was “how to make this even more generic?”. And the answer was: duh… generics. So, in order to make it work with both 2D and 3D nodes I would pass the type of the node position as a generic type. I further reduced the implementation by merging the original World class into the PathFinder and making the PathFinder non static.

This is the code for the node class:

    public class PathNode<PositionType> : Runestone.Interfaces.IMinHeapNode
    {
        private PositionType position;
        private double cost;
        private double pathCost;
        private Runestone.Interfaces.IMinHeapNode next;
        private Runestone.Interfaces.IMinHeapNode nextList;

        public PositionType Position { get { return position; } set { position = value; } }
        public double Cost { get { return cost; } set { cost = value; } }
        public double PathCost { get { return pathCost; } set { pathCost = value; } }
        public Runestone.Interfaces.IMinHeapNode Next { get { return next; } set { next = value; } }
        public Runestone.Interfaces.IMinHeapNode NextList { get { return nextList; } set { nextList = value; } }

        public PathNode(PositionType position, double cost, double pathCost, 
            Runestone.Interfaces.IMinHeapNode next)
        {
            this.position = position;
            this.cost = cost;
            this.pathCost = pathCost;
            this.next = next;
        }
    }

this is pretty straight-forward and looks like any normal linked list node with the position that is basically the content of the node being generic. This means you can use for the position any class you want such as Point or Vector2 for 2D maps or Vector3 for 3D maps. You can even create your own class such as Point3.

Then the code for the PathFinder class, which becomes a non static abstract class is:

    public abstract class PathFinder<PositionType>
    {
        protected PositionType size;
        protected bool[] isBlocked;

        public PathFinder(PositionType theSize)
        {
            this.size = theSize;
            this.isBlocked = new bool[this.GetPositionIndex(size)];
        }

        protected abstract int GetPositionIndex(PositionType pos);

        protected abstract double GetSquaredDistance(PositionType start, PositionType end);

        protected abstract PositionType[] GetSurrounding(PositionType center);

        public void SetBlocked(PositionType pos, bool value)
        {
            this.isBlocked[this.GetPositionIndex(pos)] = value;
        }
        public void SetBlocked(PositionType pos) { this.SetBlocked(pos, true); }

        /// <summary>
        /// Method that switfly finds the best path from start to end.
        /// </summary>
        /// <returns>The starting breadcrumb traversable via .next to the end or null if there is no path</returns>        
        public PathNode<PositionType> FindPath(PositionType start, PositionType end)
        {
            //note we just flip start and end here so you don't have to.            
            return FindPathReversed(end, start);
        }

        /// <summary>
        /// Method that switfly finds the best path from start to end. Doesn't reverse outcome
        /// </summary>
        /// <returns>The end breadcrumb where each .next is a step back)</returns>
        private PathNode<PositionType> FindPathReversed(PositionType start, PositionType end)
        {
            PathNode<PositionType> startNode = new PathNode<PositionType>(start, 0, 0, null);

            Runestone.Util.MinHeap<PathNode<PositionType>> openList = new Util.MinHeap<PathNode<PositionType>>();
            openList.Add(startNode);

            bool[] brWorld = new bool[this.GetPositionIndex(size)];
            brWorld[this.GetPositionIndex(start)] = true;

            while (openList.HasNext())
            {
                PathNode<PositionType> current = openList.ExtractFirst();

                if (this.GetSquaredDistance(current.Position, end) <= 3)
                    return new PathNode<PositionType>(end, current.PathCost + 1, current.Cost + 1, current);

                PositionType[] surrounding = this.GetSurrounding(current.Position);
                for (int i = 0; i < surrounding.Length; i++)
                {
                    PositionType tmp = surrounding&#91;i&#93;;
                    int brWorldIdx = this.GetPositionIndex(tmp);

                    if (this.PositionIsFree(brWorldIdx) && brWorld&#91;brWorldIdx&#93; == false)
                    {
                        brWorld&#91;brWorldIdx&#93; = true;
                        double pathCost = current.PathCost + this.GetSquaredDistance(current.Position, tmp);
                        double cost = pathCost + this.GetSquaredDistance(tmp, end);
                        PathNode<PositionType> node = new PathNode<PositionType>(tmp, cost, pathCost, current);
                        openList.Add(node);
                    }
                }
            }
            return null; //no path found
        }

        private bool PositionIsFree(PositionType pos)
        {
            return this.PositionIsFree(this.GetPositionIndex(pos));
        }

        private bool PositionIsFree(int index)
        {
            return !this.isBlocked[index];
        }
    }

This uses the same generic to specify which type of positioning it is using. The idea is, based on the specific needs of the map, to have a path finder class that inherits from this one and implements the needed abstract methods:

  • GetPositionIndex: gets a position and returns the int index for it. This is used because the blocked array is a 1-dimensional array and all positions need to be mapped to an index in that array. Needless to say, each specific position needs to be mapped to a single specific index.
  • GetSquaredDistance: calculates the distance between 2 positions
  • GetSurrounding: returns all possible next steps based on the current position

And these two classes are the very portable part of it. Now on the specific side, a child path finder needs to be implemented, and it looks like this (this is the one I am using for a simple 2D tile based map):

    public class PathFinderGrid2D : Runestone.AI.Pathfinding.PathFinder<Point>
    {
        public PathFinderGrid2D(Point size) : base(size) { }

        protected override int GetPositionIndex(Point pos)
        {
            return pos.Y * this.size.Y + pos.X;
        }

        protected override double GetSquaredDistance(Point start, Point end)
        {
            int x = start.X - end.X;
            int y = start.Y - end.Y;
            return x * x + y * y;
        }

        protected override Point[] GetSurrounding(Point center)
        {
            List<Point> ret = new List<Point>();
            for (int x = center.X - 1; x <= center.X + 1; x++)
                for (int y = center.Y - 1; y <= center.Y + 1; y++)
                    if ((x != center.X || y != center.Y) && x >= 0 && x < size.X && y >= 0 && y <= size.Y)
                        ret.Add(new Point(x, y));
            return ret.ToArray();
        }
    }
&#91;/csharp&#93;
and it implements the 3 methods mentioned before. As you can see, these are very specific to the application and thus, they need to be separated from the generic part. I think the code here is pretty self explanatory and a version for a 3D map would be very similar.

Now for the usage. This is the way I am using this class into my 2D map class:
&#91;csharp&#93;
// of course it needs to be declared
private PathFinderGrid2D pathFinder;
...
// and initialized
this.pathFinder = new PathFinderGrid2D(new Point(width, height));
...
// then, every time an obstacle is added to the map we need to inform the path finder
this.pathFinder.SetBlocked(new Point(i, j));
...
// and to find the path between 2 points I use the following method
public List<Point> GetPath(Point start, Point end)
{
    Runestone.AI.Pathfinding.PathNode<Point> root = this.pathFinder.FindPath(start, end);
    List<Point> path = new List<Point>();
    while (root != null)
    {
        path.Add(root.Position);
        root = (Runestone.AI.Pathfinding.PathNode<Point>)root.Next;
    }
    return path;
}

that’s it. There is one change needed that I thought of: if you want to use it with sparse nodes instead of a simple grid, then the way it specifies the size needs to change. Right now the size is just a position but in case of a graph that would not work. I don’t need that right now so I can’t be bothered to come up with a solution for the moment. If you do, let me know.