Я пытаюсь реализовать алгоритм поиска пути A * для двумерной гексагональной карты тайлов. У меня есть следующий класс HexCell, который действует как контейнер данных и искатель смежности, используя целое число шестнадцатеричного индекса:
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);
}
}
}
}
}
Затем у меня есть класс ExpeditionController, который выполняет фактическое нахождение пути между шестнадцатеричными ячейками, используя их соответствующие списки соседей шестнадцатеричных ячеек. Я использую OnDrawGizmos для рисования сфер для каждого узла в пути:
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);
}
}
}
}
На данный момент путь всегда будет исходить из источника мозаичного изображения (в нижнем левом углу) и заканчиваться там, где пользователь щелкает. В некоторых простых случаях путь выглядит правильным: 
Тем не менее, выбор более диагонального гексагона открывает субоптимальный путь: 
Я попытался полностью поменять алгоритм поиска пути на другой и получил те же самые результаты, так что в этот момент я думаю, что все еще есть ошибка в том, как определяются смежности для каждого гекса. Любое понимание того, почему был создан неправильный путь, будет оценено.
Редактировать: я реорганизовал практически весь этот код, чтобы найти смежность на основе индекса с момента первой публикации, и теперь путь улучшен, так как он не больше пропускает гексы, но все равно длиннее оптимального и поэтому неверно. По крайней мере, теперь я вполне уверен, что нет логики c, основанной на квадрате, которая может мешать.