c#unity-game-enginepath-findinga-star
A star pathfinding algorithm bug for hexes
I'm attempting to implement the A* pathfinding algorithm for a 2d hexagonal tilemap. I've got the following HexCell class that acts as a data container and adjacency finder using a hex index integer:
namespace Expedition
{
using System;
using System.Collections.Generic;
using UnityEngine;
public class HexCell
{
public List<HexCell> AdjacencyList = new List<HexCell>();
public Vector3 Position;
public HexCell Parent;
public float f = 0;
public float g = 0;
public float h = 0;
private int index;
private enum HexDirection { Northeast, East, Southeast, Southwest, West, Northwest };
public HexCell(int index, Vector3 position)
{
this.index = index;
Position = position;
}
// Reset references to valid adjacent hexes relative to this hex cell
public void RefreshAdjacencyList()
{
AdjacencyList.Clear();
var directions = Enum.GetValues(typeof(HexDirection));
HexCell adjacentCell;
int gridMaxX = ExpeditionController.gridMaxX;
int gridMaxY = ExpeditionController.gridMaxY;
int targetIndex;
foreach (HexDirection dir in directions)
{
targetIndex = -1;
switch (dir)
{
case HexDirection.Northeast:
// Not on right and not on top
if (index - ((index / gridMaxX) * gridMaxX) != gridMaxX - 1 && index / gridMaxX != gridMaxY - 1)
{
targetIndex = index + gridMaxX;
}
break;
case HexDirection.East:
// Not on right
if (index - ((index / gridMaxX) * gridMaxX) != gridMaxX - 1)
{
targetIndex = index + 1;
}
break;
case HexDirection.Southeast:
// Not on right and not on bottom
if (index - ((index / gridMaxX) * gridMaxX) != gridMaxX - 1 && index / gridMaxX != 0)
{
targetIndex = index - gridMaxX + 1;
}
break;
case HexDirection.Southwest:
// Not on left and not on bottom
if (index % (gridMaxX) != 0 && index / gridMaxX != 0)
{
targetIndex = index - gridMaxX - 1;
}
break;
case HexDirection.West:
// Not on left
if (index % (gridMaxX) != 0)
{
targetIndex = index - 1;
}
break;
case HexDirection.Northwest:
// Not on left and not on top
if (index % (gridMaxX) != 0 && index / gridMaxX != gridMaxY - 1)
{
targetIndex = index + gridMaxX - 1;
}
break;
}
if (targetIndex != -1)
{
adjacentCell = ExpeditionController.Instance.Cells[targetIndex];
AdjacencyList.Add(adjacentCell);
}
}
}
}
}
Then I've got this ExpeditionController class that does the actual pathfinding between hex cells using their respective lists of hex cell adjacencies. I use OnDrawGizmos to draw spheres for each node in the path:
namespace Expedition
{
using Common;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Tilemaps;
public class ExpeditionController : StateMachine
{
public static ExpeditionController Instance;
public GameObject HexCellHighlightPrefab;
public Dictionary<int, HexCell> Cells { get; private set; } = new Dictionary<int, HexCell>();
[HideInInspector] public static int gridMaxX = 13;
[HideInInspector] public static int gridMaxY = 21;
public TileBase tilebaseTest;
private const float worldmapVerticalOffset = 100f;
private Dictionary<Vector3Int, GameObject> cellHighlightObjects = new Dictionary<Vector3Int, GameObject>();
private HexCell selectedHex;
private Stack<HexCell> path = new Stack<HexCell>();
// These will change based on player position later, for now they're static at the origin:
private float playerF = 0;
private float playerG = 0;
private float playerH = 0;
[SerializeField] private GameObject worldMap;
[SerializeField] private Camera mainCamera;
[SerializeField] private GameObject minimapParent;
[SerializeField] private RenderTexture minimapRawImageRenderTexture;
private Camera worldMinimapCamera;
private Grid grid;
private Tilemap tilemap;
private const float hexDimension = 0.8660254f;
private void Awake()
{
Instance = this;
}
private void Start()
{
var bottomPanel = Instantiate(GameManager.Instance.BottomPanelPrefab);
bottomPanel.GetComponent<RectTransform>().SetParent(GameManager.Instance.Canvas.transform, false);
worldMap = Instantiate(GameManager.Instance.WorldMapPrefab);
worldMinimapCamera = worldMap.GetComponentInChildren<Camera>();
grid = worldMap.GetComponent<Grid>();
tilemap = grid.GetComponentInChildren<Tilemap>();
BuildMap();
foreach (var hexCell in Cells.Values)
{
hexCell.RefreshAdjacencyList();
}
ChangeState<TravelState>();
}
public void ToggleWorldMapVisibility()
{
if (mainCamera.gameObject.activeInHierarchy)
{
// Hide world map and show travel view
minimapParent.SetActive(false);
worldMinimapCamera.targetTexture = null;
mainCamera.gameObject.SetActive(false);
}
else
{
minimapParent.SetActive(true);
worldMinimapCamera.targetTexture = minimapRawImageRenderTexture;
mainCamera.gameObject.SetActive(true);
}
}
public void RegisterCellHighlightObject(Vector3 position, GameObject go)
{
var intPos = Vector3Int.RoundToInt(position);
if (!cellHighlightObjects.ContainsKey(intPos))
{
cellHighlightObjects.Add(intPos, go);
}
}
public void OnClick(Vector3 clickPosition)
{
if (worldMinimapCamera != null && grid != null)
{
Vector3 mouseWorldPos = worldMinimapCamera.ScreenToWorldPoint(clickPosition);
Vector3Int coordinate = grid.WorldToCell(mouseWorldPos);
var index = ConvertPositionToHexCellIndex(coordinate);
// Debug.Log("Index: " + index);
tilemap.SetTile(coordinate, tilebaseTest);
// Activate the corresponding highlight object for the tile
cellHighlightObjects[coordinate].SetActive(!cellHighlightObjects[coordinate].activeInHierarchy);
if (Cells.ContainsKey(index))
{
selectedHex = Cells[index];
if (selectedHex != null)
{
// Debug.Log("selected hex at " + selectedHex.Position);
DeterminePathToHexCell(selectedHex);
}
}
}
}
private void BuildMap()
{
float xCalc;
int index = 0;
for (float y = 0; y < gridMaxY; y++)
{
for (float x = 0; x < gridMaxX; x++)
{
if ((int) y % 2 == 0)
{
xCalc = x * hexDimension;
}
else
{
xCalc = (x * hexDimension) + (hexDimension / 2);
}
var hexCoordinate = new Vector3(xCalc, y * 0.75f, 0);
// Debug.Log("creating tile at index " + index);
Cells.Add(index, new HexCell(index, hexCoordinate));
index++;
tilemap.SetTile(new Vector3Int((int)x, (int)y, 0), tilebaseTest);
}
}
}
private HexCell FindLowestF(List<HexCell> list)
{
HexCell lowest = list[0];
foreach (HexCell t in list)
{
if (t.f < lowest.f)
{
lowest = t;
}
}
list.Remove(lowest);
return lowest;
}
private void DeterminePathToHexCell(HexCell target)
{
var openList = new List<HexCell>();
var closedList = new List<HexCell>(); // When the target tile is added to the closed list, we are done
openList.Add(Cells[0]);
var currentCellPos = Cells[0].Position;
var targetCellPos = selectedHex.Position;
playerH = Vector3.Distance(currentCellPos, targetCellPos);
playerF = playerH;
// If openList count is ever 0, that means we've not found the shortest path
while (openList.Count > 0)
{
HexCell lowestFCell = FindLowestF(openList);
closedList.Add(lowestFCell);
if (lowestFCell == target)
{
// Path found
BuildPathAndStartMoving(lowestFCell);
return;
}
foreach (HexCell cell in lowestFCell.AdjacencyList)
{
var tilePos = cell.Position;
var cPos = lowestFCell.Position;
// Add this later:
//if (cell.unit != unit && cell != target && cell.unit != null)
//{
// // Don't allow movement through occupied tiles (unless its the moving unit or the target unit)
// closedList.Add(cell);
//}
if (closedList.Contains(cell))
{
// Do nothing, already processed
}
else if (openList.Contains(cell))
{
float tempG = lowestFCell.g + Vector3.Distance(tilePos, cPos);
if (tempG < cell.g)
{
cell.Parent = lowestFCell;
cell.g = tempG;
cell.f = cell.g + cell.h;
}
}
else
{
cell.Parent = lowestFCell;
cell.g = lowestFCell.g + Vector3.Distance(tilePos, cPos);
cell.h = Vector3.Distance(tilePos, targetCellPos);
cell.f = cell.g + cell.h;
openList.Add(cell);
}
}
}
Debug.Log("Path not found");
}
private void BuildPathAndStartMoving(HexCell cell)
{
path.Clear();
// Start at the end tile
HexCell next = cell;
while (next != null)
{
path.Push(next);
next = next.Parent;
}
// StartMoving();
}
private int ConvertPositionToHexCellIndex(Vector3 position)
{
int xIndex = (int)position.x;
int yIndex = (int)position.y * gridMaxX;
var index = xIndex + yIndex;
if (index < 0 || index > gridMaxY * gridMaxX)
{
return -1;
}
return index;
}
private void OnDrawGizmos()
{
// Mark all hex centers for easier coordinate validation
Gizmos.color = Color.white;
foreach (var hc in Cells.Values)
{
// The map is currently 100 units above everything else in the scene and has a z value of 8, change this later
Gizmos.DrawSphere(hc.Position + new Vector3(0, 100, 8), 0.1f);
}
// Mark all nodes in the path
Gizmos.color = Color.blue;
foreach (var hc in path)
{
//Debug.Log("path" + hc.Position);
Gizmos.DrawSphere(hc.Position + new Vector3(0, 100, 8), 0.1f);
}
// Mark the selected (clicked) hex
if (selectedHex != null)
{
Gizmos.color = Color.red;
Gizmos.DrawSphere(selectedHex.Position + new Vector3(0, 100f, 8), 0.1f);
}
}
}
}
For now the path will always originate from the tilemap origin (in the lower-left corner) and end wherever the user clicks. In some simple cases the path looks correct:
However, selecting a more diagonal hex reveals a suboptimal path:
I tried completely swapping out the pathfinding algorithm for another one and got the exact same results, so at this point I think there is still a bug in how adjacencies are determined for each hex. Any insight as to why the incorrect path is created would be appreciated.
Edit: I refactored just about all of this code to find adjacencies based on index since first posting, and the path is now improved in that it no longer skips hexes, but it's still longer than optimal and therefore incorrect. At least now I'm fairly certain there is no square-based logic that may be interfering.
Solution
Found the solution to my problem. The adjacency logic within each hex was not quite right as I suspected. Finding correct adjacent indices requires an offset on every other row due to the layout of the hexagonal grid.