How can I shorten the length of time spent on finding a path using my A* pathfinding code?

Question

I am working on a game where the player and enemies move between discreet tiles, with only orthagonal movement (like pokemon). The game also runs on a turn system, so the player makes a move input, then the enemies calculate their paths and begin moving simultaneously with the player to the first node in their path. My enemies calculate their paths one after another and set move points at the position they intend to travel to. This lets enemies check if there is already a move point where they are trying to pathfind to, in which case they'll choose an alternate adjacent point to move to. After all the paths are calculated the enemies move simultaneously. I also implemented enemy aggro, so only enemies within the bounds of the camera path to the player. The rest path to a random adjacent node to keep the paths short. My problem is I've been playtesting with 20 enemies on a reasonably small grid (56x28) and it takes 130 ms or so to calculate the paths of all the enemies. This results in some pretty undesirable movement, since the player's control is locked until all enemies have finished moving. The player noticeably pauses for the enemies to finish moving in between taking steps.

I've posted the relevant sections of my code below, does anyone see a glaring issue with how I'm approaching this? I've adapted a pathfinding tutorial series by Sebastian Lague on YouTube to fit my game. I also looked at the A* Pathfinding Project by Aron Granburg, but stayed away from it because it looked much more complicated to adapt to my specific project. If anyone is familiar with the A* pathfinding project, is it highly optimized to the point where it might be worth it to scrap what I have and try to use that instead?

Also relevant: I changed my fixed timestep in my unity project settings to 0.001 from 0.02. Since I had to include a WaitForFixedUpdate to make sure enemies were accurately checking for collision this sped up the enemy turns quite a bit, and it doesn't seem to have created significant overhead.

Also also relevant (maybe): Performance differs when I have the scene view open. In this case enemy pathfinding takes ~ 255 ms rather than the ~130 ms when the game view is maximized.

Edit: Thanks for all the useful info everyone! I’m going through and implementing several suggestions to fine tune everything, but I found the major source of the problem. In turn system.cs I had a waitforfixedupdate, which I assumed would add an option extra 1 ms per enemy that was pathfinding. This was necessary because the physics 2D overlap circles I used to check collision weren’t always giving me accurate results otherwise. Well, turns out my computer wasn’t managing to keep up with the 0.001s fixed timestep interval and the waitforfixedupdates were adding more wait time than intended. I stumbled across Physics.synctransforms and used that where I had the fixed update, then set my fixed timestep back to the default 0.02s. Worked like a charm, collision checks are all working correctly and the pathfinding went from taking 130ms to about 40ms.

From TurnSystem.cs:

        public IEnumerator EnemyTurn(bool playerTookMoveAction)
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

            playerController.LockControl(true);

            sw.Start();
            WaitForFixedUpdate wait = new WaitForFixedUpdate();  
            for (int i = 0; i < enemies.Count; i++)
            {
                if (enemies[i].GetTookFightAction()) continue;
                yield return StartCoroutine(enemies[i].SetMovePoint());
                yield return wait;
            }

            sw.Stop();
            print("Elapsed Time: " + sw.ElapsedMilliseconds/1000f);

            for (int i = 0; i < enemies.Count; i++)
            {
                if (enemies[i].GetTookFightAction()) continue;
                StartCoroutine(enemies[i].TakeStep());
            }
            
            while(enemiesFinishedAction < enemies.Count)
            {
                yield return null;
            }
            enemiesFinishedAction = 0;

            for (int i = 0; i < enemies.Count; i++)
            {
                enemies[i].SetAggro();
            }

            StartCoroutine(playerController.UnlockControlAfterMovement());
            OnReadyToSpawn();
        }

        public void AddEnemy(EnemyAIController enemy)
        {
            enemies.Add(enemy);
        }

        public void RemoveEnemy(EnemyAIController enemy)
        {
            enemies.Remove(enemy);
        }

        public void EnemyFinishedAction()
        {
            enemiesFinishedAction++;
        }

From EnemyAIController.cs:

        public void OnPathFound(Vector2[] newPath, bool pathSuccessful)
        {
            if (pathSuccessful && newPath.Length > 0)
            {
                path = newPath;
            }
        }

        public IEnumerator SetMovePoint()
        {
            if (!isLocked)
            {
                if (isAggroed) 
                {
                    target = playerMovePoint.position;
                }
                else
                {
                    target = GetRandomAdjacentTarget();
                }
                yield return PathRequestManager.RequestPath(transform.position, target, OnPathFound);
                if (path != null && !Physics2D.OverlapCircle(path[0], 0.3f, collisionLayer))
                {
                    movePoint.position = path[0];
                }
                else
                {
                    movePoint.position = GetAlternateWaypoint();
                }
            }
            else yield return null; 
        }

        protected Vector2 GetRandomAdjacentTarget()
        {
            float random = UnityEngine.Random.Range(0,4);
            if (random == 0) return new Vector2 (transform.position.x, transform.position.y - 2);
            if (random == 1) return new Vector2 (transform.position.x - 2, transform.position.y);
            if (random == 2) return new Vector2 (transform.position.x, transform.position.y + 2);
            if (random == 3) return new Vector2 (transform.position.x + 2, transform.position.y);
            return transform.position;
        }

        protected Vector2 GetAlternateWaypoint()
        {
            if (path != null && path[0] != null && path[0] != (Vector2)movePoint.position)
            {
                if(path[0].x != movePoint.position.x)
                {
                    if (target.y > movePoint.position.y && !Physics2D.OverlapCircle(new Vector2(movePoint.position.x, movePoint.position.y + 1), 0.3f, collisionLayer))
                    {
                        return new Vector2(movePoint.position.x, movePoint.position.y + 1);
                    }
                    else if (target.y <= movePoint.position.y && !Physics2D.OverlapCircle(new Vector2(movePoint.position.x, movePoint.position.y - 1), 0.3f, collisionLayer))
                    {
                        return new Vector2(movePoint.position.x, movePoint.position.y - 1);
                    }
                }
                else if (path[0].y != movePoint.position.y)
                {
                    if (target.x > movePoint.position.x && !Physics2D.OverlapCircle(new Vector2(movePoint.position.x + 1, movePoint.position.y), 0.3f, collisionLayer))
                    {
                        return new Vector2(movePoint.position.x + 1, movePoint.position.y);
                    }
                    else if (target.x <= movePoint.position.x && !Physics2D.OverlapCircle(new Vector2(movePoint.position.x - 1, movePoint.position.y), 0.3f, collisionLayer))
                    {
                        return new Vector2(movePoint.position.x - 1, movePoint.position.y);
                    }
                }
            }
            return movePoint.position;
        }

From PathRequestManager.cs:

public class PathRequestManager : MonoBehaviour
    {
        Queue<PathRequest> pathRequestQueue = new Queue<PathRequest>();
        PathRequest currentPathRequest;

        static PathRequestManager instance;
        Pathfinding pathfinding;

        bool isProcessingPath;

        private void Awake() 
        {
            instance = this;
            pathfinding = GetComponent<Pathfinding>();
        }

        public static IEnumerator RequestPath(Vector2 pathStart, Vector2 pathEnd, Action<Vector2[], bool> callback)  //does this need to be static?
        {
            PathRequest newRequest = new PathRequest(pathStart, pathEnd, callback);
            instance.pathRequestQueue.Enqueue(newRequest);
            instance.TryProcessNext();
            yield return null;
        }
        private void TryProcessNext()
        {
            if (!isProcessingPath && pathRequestQueue.Count > 0)
            {
                currentPathRequest = pathRequestQueue.Dequeue();
                isProcessingPath = true;
                pathfinding.StartFindPath(currentPathRequest.pathStart, currentPathRequest.pathEnd);
            }
        }

        public void FinishedProcessingPath(Vector2[] path, bool success)
        {
            currentPathRequest.callback(path, success);
            isProcessingPath = false;
            TryProcessNext();
        }

        struct PathRequest
        {
            public Vector2 pathStart;
            public Vector2 pathEnd;
            public Action<Vector2[], bool> callback;

            public PathRequest(Vector2 _start, Vector2 _end, Action<Vector2[], bool> _callback)
            {
                pathStart = _start;
                pathEnd = _end;
                callback = _callback;
            }
        }
    }

From Pathfinding.cs:

    public class Pathfinding : MonoBehaviour
    {
        PathRequestManager requestManager;
        AStarGrid grid;

        private void Awake() 
        {
            requestManager = GetComponent<PathRequestManager>();
            grid = GetComponent<AStarGrid>();
        }

        public void StartFindPath(Vector2 startPos, Vector2 targetPos)
        {
            StartCoroutine(FindPath(startPos, targetPos));
        }

        IEnumerator FindPath(Vector2 startPos, Vector2 targetPos)
        {
            Vector2[] waypoints = new Vector2[0];
            bool pathSuccess = false;

            Node startNode = grid.NodeFromWorldPoint(startPos);
            Node targetNode = grid.NodeFromWorldPoint(targetPos);

            if(startNode.walkable && targetNode.walkable)
            {
                Heap<Node> openSet = new Heap<Node>(grid.MaxSize);
                HashSet<Node> closedSet = new HashSet<Node>();
                openSet.Add(startNode);

                while (openSet.Count > 0)
                {
                    Node currentNode = openSet.RemoveFirst();
                    closedSet.Add(currentNode);

                    if (currentNode == targetNode)//found the path
                    {
                        pathSuccess = true;
                        break;
                    }

                    foreach(Node neighbor in grid.GetNeighbors(currentNode))
                    {
                        if(!neighbor.walkable || closedSet.Contains(neighbor)) continue;
                        int newMovementCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
                        if (newMovementCostToNeighbor < neighbor.gCost || !openSet.Contains(neighbor))
                        {
                            neighbor.gCost = newMovementCostToNeighbor;
                            neighbor.hCost = GetDistance(neighbor, targetNode);
                            neighbor.parent = currentNode;

                            if (!openSet.Contains(neighbor))
                            {
                                openSet.Add(neighbor);
                            }
                            else
                            {
                                openSet.UpdateItem(neighbor);
                            }
                        }
                    }
                }
            }
            yield return null;
            if (pathSuccess)
            {
                waypoints = RetracePath(startNode, targetNode);
            }
            requestManager.FinishedProcessingPath(waypoints, pathSuccess);
        }

        Vector2[] RetracePath(Node startNode, Node endNode)
        {
            List<Node> path = new List<Node>();
            Node currentNode = endNode;

            while(currentNode != startNode)
            {
                path.Add(currentNode);
                currentNode = currentNode.parent;
            }
            Vector2[] waypoints = SimplifyPath(path);
            // Array.Reverse(waypoints);
            return waypoints;
        }

        Vector2[] SimplifyPath(List<Node> path)//I simplified this section of code since I just needed the first waypoint of the path returned, this did help performance
        {
            List<Vector2> waypoints = new List<Vector2>();
            // Vector2 directionOld = Vector2.zero;

            for(int i = Mathf.Max(path.Count - 1, 0); i < path.Count; i ++)
            // for(int i = 1; i < path.Count; i ++)
            {
                // Vector2 directionNew = new Vector2(path[i-1].gridX - path[i].gridX, path[i-1].gridY - path[i].gridY);
                // if(directionNew != directionOld)
                // {

                    waypoints.Add(path[i].worldPosition);
                // }
                // directionOld = directionNew;
            }
            return waypoints.ToArray();
        }

        int GetDistance(Node nodeA, Node nodeB)
        {
            int distanceX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
            int distanceY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

            return distanceX + distanceY;
        }
    }

From node.cs:

    public class Node : IHeapItem<Node>
    {
        public bool walkable;
        public Vector2 worldPosition;
        public int gridX;
        public int gridY;

        public int gCost;
        public int hCost;
        public Node parent;
        int heapIndex;

        public Node( bool _walkable, Vector2 _worldPos, int _gridX, int _gridY) 
        {
            walkable = _walkable;
            worldPosition = _worldPos;
            gridX = _gridX;
            gridY = _gridY;
        }

        public int fCost
        {
            get 
            {
                return gCost + hCost;
            }
        }

        public int HeapIndex
        {
            get
            {
                return heapIndex;
            }
            set
            {
                heapIndex = value;
            }
        }

        public int CompareTo(Node nodeToCompare)
        {
            int compare = fCost.CompareTo(nodeToCompare.fCost);
            if (compare == 0)
            {
                compare = hCost.CompareTo(nodeToCompare.hCost);
            }
            return -compare;
        }
    }

From Heap.cs

    public class Heap<T> where T : IHeapItem<T> {
        
        T[] items;
        int currentItemCount;
        
        public Heap(int maxHeapSize) {
            items = new T[maxHeapSize];
        }
        
        public void Add(T item) {
            item.HeapIndex = currentItemCount;
            items[currentItemCount] = item;
            SortUp(item);
            currentItemCount++;
        }

        public T RemoveFirst() {
            T firstItem = items[0];
            currentItemCount--;
            items[0] = items[currentItemCount];
            items[0].HeapIndex = 0;
            SortDown(items[0]);
            return firstItem;
        }

        public void UpdateItem(T item) {
            SortUp(item);
        }

        public int Count {
            get {
                return currentItemCount;
            }
        }

        public bool Contains(T item) {
            return Equals(items[item.HeapIndex], item);
        }

        void SortDown(T item) {
            while (true) {
                int childIndexLeft = item.HeapIndex * 2 + 1;
                int childIndexRight = item.HeapIndex * 2 + 2;
                int swapIndex = 0;

                if (childIndexLeft < currentItemCount) {
                    swapIndex = childIndexLeft;

                    if (childIndexRight < currentItemCount) {
                        if (items[childIndexLeft].CompareTo(items[childIndexRight]) < 0) {
                            swapIndex = childIndexRight;
                        }
                    }

                    if (item.CompareTo(items[swapIndex]) < 0) {
                        Swap (item,items[swapIndex]);
                    }
                    else {
                        return;
                    }

                }
                else {
                    return;
                }

            }
        }
        
        void SortUp(T item) {
            int parentIndex = (item.HeapIndex-1)/2;
            
            while (true) {
                T parentItem = items[parentIndex];
                if (item.CompareTo(parentItem) > 0) {
                    Swap (item,parentItem);
                }
                else {
                    break;
                }

                parentIndex = (item.HeapIndex-1)/2;
            }
        }
        
        void Swap(T itemA, T itemB) {
            items[itemA.HeapIndex] = itemB;
            items[itemB.HeapIndex] = itemA;
            int itemAIndex = itemA.HeapIndex;
            itemA.HeapIndex = itemB.HeapIndex;
            itemB.HeapIndex = itemAIndex;
        }
        
        
        
    }

    public interface IHeapItem<T> : IComparable<T> {
        int HeapIndex {
            get;
            set;
        }
    }

From AStarGrid.cs

    public class AStarGrid : MonoBehaviour
    {
        public bool displayGridGizmos;
        public LayerMask unwalkableMask;
        public Vector2 gridWorldSize;
        public float nodeRadius;
        Node[,] grid;

        float nodeDiameter;
        int gridSizeX, gridSizeY;

        private void Awake() 
        {
            nodeDiameter = nodeRadius *2;
            gridSizeX = Mathf.RoundToInt(gridWorldSize.x/nodeDiameter);
            gridSizeY = Mathf.RoundToInt(gridWorldSize.y/nodeDiameter);
            CreateGrid();
        }

        public int MaxSize
        {
            get
            {
                return gridSizeX * gridSizeY;
            }
        }

        private void CreateGrid()
        {
            grid = new Node[gridSizeX, gridSizeY];
            Vector2 worldBottomLeft = (Vector2)transform.position - Vector2.right * gridWorldSize.x/2 - Vector2.up * gridWorldSize.y/2;

            for (int x = 0; x < gridSizeX; x++)
            {
                for (int y = 0; y < gridSizeY; y++)
                {
                    Vector2 worldPoint = worldBottomLeft + Vector2.right * (x * nodeDiameter + nodeRadius) + Vector2.up * (y * nodeDiameter + nodeRadius);
                    bool walkable = (Physics2D.OverlapCircle(worldPoint,nodeRadius,unwalkableMask) == null);
                    grid[x,y] = new Node (walkable, worldPoint, x, y);
                }
            }
        }

        public List<Node> GetNeighbors(Node node)
        {
            List<Node> neighbors = new List<Node>();

            for (int x = -1; x <= 1; x++)
            {
                for (int y = -1; y <= 1; y++)
                {
                    if (x == 0 && y == 0 || Mathf.Abs(x) + Mathf.Abs(y) == 2) continue;

                    int checkX = node.gridX + x;
                    int checkY = node.gridY + y;

                    if(checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)// if checkX and checkY are on the grid
                    {
                        neighbors.Add(grid[checkX, checkY]);
                    }
                }
            }

            return neighbors;
        }

        public Node NodeFromWorldPoint(Vector2 worldPosition)
        {
            float percentX = worldPosition.x / gridWorldSize.x + 0.5f;
            float percentY = worldPosition.y / gridWorldSize.y + 0.5f;

            int x = Mathf.FloorToInt(Mathf.Clamp((gridSizeX) * percentX, 0, gridSizeX - 1));
            int y = Mathf.FloorToInt(Mathf.Clamp((gridSizeY) * percentY, 0, gridSizeY - 1));
            
            return grid[x,y];
        }

        public List<Node> path;
        void OnDrawGizmos() 
        {
        Gizmos.DrawWireCube(transform.position,new Vector2(gridWorldSize.x,gridWorldSize.y));
        if (grid != null && displayGridGizmos) {
            foreach (Node n in grid) {
                Gizmos.color = Color.red;
                if (n.walkable)
                    Gizmos.color = Color.white;

                Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter-.8f));
            }
        }
        }
    }

Answer 1

Let's start with some general C# optimization advice:

Avoid heap allocations in your hot path. That means anywhere you have new Foo(...) where Foo is a reference type (that's any class, including any collections like arrays, lists, sets, heaps, etc).

• If you're going to finish your work with this one, then make another one for the next job (eg. your open / closed set collections), just keep a persistent one and re-use it, calling Clear() or the equivalent before each new use.

  Fun fact: YieldInstructions like WaitForFixedUpdate can be reused this way. You don't need to allocate a new one every time you want to yield. You can even store a single one as a static readonly variable for all your yields to reference.

• If you're returning a collection of results, definitely don't create a new zero-capacity array then replace it like you're doing with waypoints = new Vector2[0] - that's a completely useless heap allocation. Just let the variable be null in the event that no waypoints are provided, and handle the null case in the code that consumes it.

  You can even get rid of the allocation for the returned collection in SimplifyWaypoints and similar methods, by following the pattern used by Unity's own NonAlloc methods: accept a list or array as one of the method parameters, and store your results there (and if using an array, return the number of items so the caller knows how much of the buffer is the new data). That lets the caller re-use one collection instead of allocating new ones.

• When using variable-sized collections (List, HashSet, Heap, etc.), pre-size them for the capacity you're likely to need. Under the hood, these data structures allocate a small buffer of memory for starters, and when you add more items than they have room for, they allocate a new, larger buffer and move their contents over to that. By telling them how much space you expect them to need up-front, by passing a number to the constructor, you avoid doing these shuffles in the middle of your work. (Re-using your containers helps here too - you pay the resizing cost early on, but once the structure has "warmed up" it doesn't need resizing again on the next use)

• Where you can, use value types instead of reference types. These don't require a separate heap allocation if used as temporaries inside a method, and they piggyback on the parent's allocation when stored as member variables or placed inside a collection (provided the type of the storage location matches - that you're not casting them to an interface that would cause boxing). These can also be faster to access, since they're stored directly in the parent container's memory, rather than storing just a pointer that needs to be chased. When doing lots of iterations, this can improve cache locality.

  Instead of a class for Node, can you make it a struct? You can use a "Structure of Arrays" approach to unpack your node class into multiple arrays that store stuff about the nodes. Your open set could just store Vector2Int coordinates for each node (or your own custom version that uses short or sbyte for compactness), and then you can use those coordinates to look up or compute the cost / position / etc. when needed.

Now let's look at algorithmic improvements specific to the pathfinding problem:

• When you have many agents pathfinding toward the same goal, it can be faster to reverse the problem: pathfind from the goal (player) to the agent (enemy).

  This lets you re-use data from the previous pathfinding attempt. After agent 1 has finished their A* search, your node grid contains exactly correct path distances to the player from every tile along agent 1's path, and many adjacent tiles evaluated along the way. If agent 2 is somewhat near agent 1, or their shortest paths converge along the way, then their A* search will want to look at many of the same tiles, where it can find the right answer already recorded, with no re-computation or heuristic guessing.

• If you have many enemies all over the map, so that you're probably going to search the majority of the tiles anyway, then you can use a simpler algorithm: just do a breadth-first search of walkable tiles out from the player's position, and record the search depth at each tile (if all tiles have the same traversal cost - if not, use Dijkstra's algorithm instead). This produces what's called a distance field. Agents can then find a path to the player from anywhere just by "rolling down-hill" - checking the distance values at their adjacent tiles, and moving into whichever one has the lower number.

  This might initially look like a pessimization because it involves iterating every tile on the map, but it visits each tile only once, and the code executed per node is much simpler, so this tends to be a net win when your agent counts are large and your map is small.

• Since you only want enemies to pathfind to the player when they're within the camera bounds, generate a distance field as above but windowed to just those bounds plus a few tiles' margin. Now the most expensive part - writing a value for every reachable tile - is cut down to just writing a value for every reachable tile on-screen (or very nearly).

• If agents are off-screen, does it matter whether they're following a path toward a randomly-chosen goal? Will the player be able to tell, when they get close to the agent, that it got to where it is by following a path? If not, you might be able to massively simplify the behaviour of off-screen agents: just have them do a random walk. Each time they want to move a tile, pick an adjacent walkable tile at random (possibly excluding tiles outside the agent's designated "wander zone").

  When the player encounters the agent, they'll find it on some random tile near its start point, just like with the more expensive path-finding approach, and now that it's on screen it will start using goal-following behaviour so it doesn't look random anymore.

Lastly (and this should probably be your last resort), you can use threads to do the pathfinding work in the background - especially for off-screen enemies. This keeps it from blocking the main thread, and lets you continue working on your pathfinding even while the engine is doing other work, or even compute paths for multiple agents in parallel rather than sequentially. But multithreading can significantly increase the complexity of your code and introduce new opportunities for bugs, so you should try to exhaust other options first. For just a few thousand nodes, there's no reason you shouldn't be able to get a result quickly on a single thread.

Answer 2

Consider using a grid-optimized pathfinding algorithm

A* is the canonical pathfinding algorithm. It's great for general purpose pathfinding on a graph.

It looks like your terrain is a 2D grid specifically. If that terrain is not deformed or modified during play, then there are more specialized algorithms available.

Either of the following algorithms (if implemented well) will likely result in very significant speed-improvements over well-implemented A*, however, they both require some pre-processing of the map, are not terribly well documented online. I recommend following DMGregory's answer first and then only pursuing these algorithmic improvements if you still need the speed (and have time to spare).

Jump Point Search

Jump Point Search is an algorithm that reduces the grid to a set of key vertices, such as the narrowest possible corners when making turns. A short paper that describes the algorithm can be found here.

Pruning

During pathfinding, pre-emptively prune (meaning: do not add to the open list) potential options based on the direction from which the current node was entered. When leaving a node x that was reached from node p, do not consider moving to any node n if

• A path exists from p to n that is shorter than {p, x, n} - for example, a path that moves northeast then south to arrive at a square immediately east of where it started would not be considered, because a path that moves east directly would be shorter.
• A path exists from p to n that is of the same length as {p, x, n}, but makes diagonal moves earlier. For example, moving east and then northeast would not be considered, because a path that moves northeast and then east would be preferred.

You can detect these short paths necessary for pruning without doing any actual pathfinding. For example, If you have just made a non-diagonal move, you can moves in any other direction unless you've just passed a wall (because otherwise, a path would exist with earlier diagonals). From a diagonal move, you only need to consider moves in the same direction, or its two adjacent non-diagonal moves, again, unless you pass a wall.

If you pass a wall - meaning that p was adjacent to a wall in some direction, but x has empty space in that direction, and that direction is at most 90-degrees off from the direction of travel - you need to consider movement in that direction (and any intervening diagonals) as well.

The JPS algorithm authors refer to nodes reached by continuing movement in the same direction as "natural successors" and nodes that must also be considered due to passing a wall as "forced successors."

Jumping

When pathfinding, you can move multiple steps in the same direction, so long as:

• You do not jump over any nodes that have forced successors
• When moving diagonally, you do not jump over any nodes from which you could jump non-diagonally to a node with forced neighbors.

Precomputation and Caching

The successors of a node from a given direction do not change unless the map itself does. It is therefore possible to trade memory for speed by precomputing the jump points for every node in the graph in every driection. This can either be done before publishing and saved as part of the map data, computed during load-time on the client, or lazy-evaluated (but then stored) when pathfinding is actually performed.

Goal Bounding

Goal Bounding is another grid-based optimization on top of A* (compatible with JPS). For goal bounding, preprocess the map by the following algorithm. A more detailed explanation of this algorithm (as applied to nav-meshes) can be found here.

• During load-time, run Dijkstra's Algorithm on the map to find the shortest path from each node to every other node.
• If your map is small enough that have enough memory to save the output of Dijkstra's Algorithm, use that instead. Goal Bounding is an optimization to save space.
• For each node, for each neighbor, calculate the bounding box that contains all of the shortest paths which move in that direction. (This should be a fixed size of 4 rectangles per node, since you only allow movements in the cardinal directions)
• During runtime, when doing pathfinding, discard all candidate paths that attempt to move in a direction where the goal is outside the bounds for that direction.

Answer 3

Your grid (56x28) has 1568 spaces in it.

For each location, all you need is the direction to go in. That is 2 bits.

1568^2 * 2 bits is only 615k.

So: use a lookup table. At Table[Index(x,y)][Index(a,b)] it tells you which direction (NESW) is the shortest distance from x,y to a,b.

Building a complete graph of shortest paths in a 56x28 world isn't hard. And now lookup is instant. The memory requirements are modest.

You can get fancier if you really want to. But in this case, don't bother.