# Global Game Jam: Pathfinding

Along with fog of war, another challenge I tackled for our 2021 Global Game Jam submission was pathfinding.

There are a slew of Unity Asset Store packages that provide pathfinding. Like this one that has been around for eternity. If you have more complex requirements than I did — say, continuous rather than grid-based movement1 — it’s worth your time to evaluate these. A basic A* implementation was all I needed though, so I went the DIY route instead of the drudgery of integrating a third party solution.

A* is a tried and true classic, the kind of algorithm you study in computer science class. The Wikipedia article is a good overview, but give Red Blobs Games’ Introduction to the A* Algorithm a read for an even better explanation.

Here’s my version, a line-by-line translation of the Wikipedia pseudocode:2

``````List<T> FindShortestPath<T>(
T start,
T goal,
Func<T, int> getCostEstimate,
Func<T, T, int> getEdgeWeight,
Func<T, IEnumerable<T>> getNeighbors) where T : IEquatable<T>
{
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
var openSet = new HashSet<T> {start};

// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start to n currently known.
var cameFrom = new Dictionary<T, T>();

// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
var gScore = new Dictionary<T, int>();
gScore[start] = 0;

// For node n, fScore[n] = gScore[n] + getCostEstimate(n).
// fScore[n] represents our current best guess as to how short a path from start to finish can be if it goes through n.
var fScore = new Dictionary<T, int>();
fScore[start] = getCostEstimate(start);

while (openSet.Count > 0)
{
// Find the node in openSet with the lowest fScore value.
// This operation can occur in O(1) time if openSet is a min-heap or a priority queue.
var current = openSet
.OrderBy(position => fScore.TryGetValue(position, out var fValue) ? fValue : int.MaxValue)
.First();

if (current.Equals(goal))
{
return ReconstructPath(cameFrom, current);
}

openSet.Remove(current);
var neighbors = getNeighbors(current);

foreach (var neighbor in neighbors)
{
// tentativeGScore is the distance from start to the neighbor through current.
var tentativeGScore = gScore[current]+ getEdgeWeight(current, neighbor);
var neighborGScore = gScore.TryGetValue(neighbor, out var gValue) ? gValue : int.MaxValue;

if (tentativeGScore < neighborGScore)
{
// This path to neighbor is better than any previous one. Record it!
cameFrom[neighbor] = current;
gScore[neighbor] = tentativeGScore;
fScore[neighbor] = gScore[neighbor] + getCostEstimate(neighbor);

if (!openSet.Contains(neighbor))
{
}
}
}
}

// Open set is empty but goal was never reached.
return null;
}

List<T> ReconstructPath<T>(Dictionary<T, T> cameFrom, T current)
{
var totalPath = new List<T> {current};

while (cameFrom.ContainsKey(current))
{
current = cameFrom[current];
totalPath.Insert(0, current);
}

}
``````

To use it you pass five arguments. `start` is where you begin and `goal` is where you want to end up. `getEdgeWeight` determines how expensive it is to travel from a node to its neighbour. Our game only had one ground tile type so we returned a constant of `1`, but you might want to make some terrain (e.g. mud) slower to traverse.

`getNeighbours` is self-explanatory: given a node, return a list of nodes adjacent to it. `getCostEstimate` is a heuristic function that returns how expensive it is to travel from a given node to the goal. For a grid, this can simply be horizontal + vertical distance. Our calling function wound up looking like this:

``````List<Vector3Int> GetPathFromEnemyToPlayer(Transform enemy, Transform player)
{
var start = Vector3Int.RoundToInt(enemy.position);
var goal = Vector3Int.RoundToInt(player.position);
int getCostEstimate(Vector3Int position) => Mathf.Abs(goal.x - position.x) + Mathf.Abs(goal.z - position.z);
int getEdgeWeight(Vector3Int current, Vector3Int neighbour) => 1;