A* Pathfinding in Unreal (C++)

This snippet is from my C++ Unreal Project Showdown. It shows my implementation of the A* pathfinding algorithm to find the optimal path from one Hex tile to another. I use unordered_map for storing the Hex objects and a Priority Queue to sort tiles by their cost.

This functionality is exposed to the project’s Blueprints and is used in gameplay for unit movement.

// A* Pathfinding
std::unordered_map<Hex, Hex> AMapManager::FindPath(Hex start, Hex goal)
{
  // The optimal path.
  std::unordered_map<Hex, Hex> cameFrom = { {start, start} };
  // The cost to reach each hex
  std::unordered_map<Hex, int> costSoFar = { {start, 0} };

  // A sorted queue of hexes (cheapest in front) of all available tiles you can move to.
  PriorityQueue<Hex> availableMoves;
  availableMoves.put(start, 0); // Add the starting tile with 0 cost.

  // While we still have nodes to search
  while (!availableMoves.empty())
  {
    // Get the next cheapest tile.
    auto current = availableMoves.get();

    // If it is the goal, we are done.
    if (current == goal)
    break;

    // Cycle through the current hex's neighbors
    for (int i = 0; i < 6; ++i)
    {
      // Get the neighbor
      auto neighbor = current.neighbor(current, i);

      // Calculate its cost
      int neighborCost = costSoFar[current] + GetHexCost(FVector(neighbor.q, neighbor.r, neighbor.s));

      // If the neighbor is not already available, OR
      // If the neighbor is available but we found a cheaper path to it
      if (!costSoFar.count(neighbor) || neighborCost < costSoFar[neighbor])
      {
        // Set the cost for the neighbor to the calculated cost
        costSoFar[neighbor] = neighborCost;

        // Its priority is its cost + its distance to the goal
        int priority = neighborCost + neighbor.distance(neighbor, goal);

        // Add the neighbor to the available moves
        availableMoves.put(neighbor, priority);

        // Add the current hex to the optimal path
        cameFrom[neighbor] = current;
      }
    }
  }

  // Return the optimal path
  return cameFrom;
}