十六进制的星形寻路算法错误
A star pathfinding algorithm bug for hexes
我正在尝试为 2d 六边形 tilemap 实现 A* 寻路算法。我有以下 HexCell class,它使用十六进制索引整数充当数据容器和邻接查找器:
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 class,它使用各自的十六进制单元格邻接列表在十六进制单元格之间进行实际寻路。我使用 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);
}
}
}
}
现在路径总是从瓦片地图原点(在左下角)开始,到用户点击的地方结束。在一些简单的情况下,路径看起来是正确的:
但是,选择更对角的六角形显示出次优路径:
我尝试完全换掉另一种寻路算法并得到完全相同的结果,所以在这一点上我认为在如何为每个十六进制确定邻接方面仍然存在错误。任何关于为什么创建错误路径的见解将不胜感激。
编辑:自第一次发布以来,我重构了几乎所有这些代码以根据索引查找邻接关系,现在改进了路径,因为它不再跳过十六进制,但它仍然比最佳时间长,因此不正确。至少现在我相当确定没有基于正方形的逻辑可能会干扰。
找到了我的问题的解决方案。每个六角形内的邻接逻辑并不像我怀疑的那样正确。由于六边形网格的布局,查找正确的相邻索引需要每隔一行偏移一次。
我正在尝试为 2d 六边形 tilemap 实现 A* 寻路算法。我有以下 HexCell class,它使用十六进制索引整数充当数据容器和邻接查找器:
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 class,它使用各自的十六进制单元格邻接列表在十六进制单元格之间进行实际寻路。我使用 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);
}
}
}
}
现在路径总是从瓦片地图原点(在左下角)开始,到用户点击的地方结束。在一些简单的情况下,路径看起来是正确的:
但是,选择更对角的六角形显示出次优路径:
我尝试完全换掉另一种寻路算法并得到完全相同的结果,所以在这一点上我认为在如何为每个十六进制确定邻接方面仍然存在错误。任何关于为什么创建错误路径的见解将不胜感激。
编辑:自第一次发布以来,我重构了几乎所有这些代码以根据索引查找邻接关系,现在改进了路径,因为它不再跳过十六进制,但它仍然比最佳时间长,因此不正确。至少现在我相当确定没有基于正方形的逻辑可能会干扰。
找到了我的问题的解决方案。每个六角形内的邻接逻辑并不像我怀疑的那样正确。由于六边形网格的布局,查找正确的相邻索引需要每隔一行偏移一次。