Dijkstra 在六角网格上的算法效率低下，C#，Unity3D

Question

我正在尝试使用 3D HexGrid 地图创建回合制策略游戏，我已经实现了 dijkstra 的算法，但它运行没有 100% 有效，我无法弄清楚原因。我也尝试过实现 A* 但不得不停止，因为我不知道如何正确地实现它，所以任何帮助也将不胜感激。

我的单元将它的 GameObject 和它的目标 Vector3 传递给生成路径函数，图表列表中的每个节点都填充了它的 x、y、z 和它的所有邻居。

移动时效率低下；在奇数 Z 平面上时在 -X 方向上或在偶数 Z 平面上时在 +X 方向上进行额外的步骤，如屏幕截图所示。另一个低效率是，当在 Z 平面上移动时，通常会采取额外的步骤，因为代码似乎更喜欢在接近 Z 平面之前尽可能长时间地保持其 X 值相同。这导致该单位在开始 Z 轴移动时距离目标更远 1 格，而不是它开始时负向移动 1 X。

我将添加我的路径生成代码、邻居生成代码和我的节点 class 代码以及低效发生位置的屏幕截图，因为我知道我的解释最多不清楚。邻居代码确保最高的相邻瓦片是存储为邻居的瓦片（它还必须搜索类型，因为我有多种瓦片类型。

提前非常感谢您，感谢任何能够提供帮助或深入了解问题所在的人。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;
using System.IO;
using System;
using System.Linq;

public class UnitMasterScript : MonoBehaviour {

//  private int Number_of_neighbours = 6;
private int Number_of_neighbours = 6;
private GameObject[] Neighbours;
Node[,,] graph;

public bool MapMakerDone = false;

void Update()
{
    if (MapMakerDone == true)
    {
        // Wait for MapMaker to change MapMakerDone to true then allow rest of script to run

        GameObject Map = GameObject.Find("MapMaker");
        int WidthVal = Map.GetComponent<MapMakerFromFile>().WidthVal;
        int HeightVal = Map.GetComponent<MapMakerFromFile>().HeightVal;
        int DepthVal = Map.GetComponent<MapMakerFromFile>().DepthVal;

        // Graph of node generation code
        // Code to find which hex is to each side of this hex
        // Need to find hex to left, right, ul, ur, ll, lr
        // Need to find hex at the top of the stack adjacent
        // 0:L 1:R 2:UL 3:UR 4:LL 5:LR
        graph = new Node[WidthVal, HeightVal, DepthVal];

        for (int x = 0; x < WidthVal; x++)
        {
            for (int y = 0; y < HeightVal; y++)
            {
                for (int z = 0; z < DepthVal; z++)
                {
                    graph[x, y, z] = new Node();

                    graph[x, y, z].x = x;
                    graph[x, y, z].y = y;
                    graph[x, y, z].z = z;
                }
            }
        }

        for (int x = 0; x < WidthVal; x++)
        {
            for (int y = 0; y < HeightVal; y++)
            {
                for (int z = 0; z < DepthVal; z++)
                {

                    // Set up the x and y for the neighbour as the source so it can be used
                    int neighbourX = x;
                    int neighbourY = 0; // must always start from 0 to ensure a downstep isn't missed
                    int neighbourZ = z;
                    int neighbourType = 0;
                    int correct_type = 0;

                    GameObject Hex_Present_checker = null;
                    // First needs to check if there even is a tile at this coordinate location
                    for (neighbourType = 0; neighbourType < 5; neighbourType++)
                    {
                        Hex_Present_checker = GameObject.Find("Hex_" + x + "_" + y + "_" + z + "_" + neighbourType);
                        if (Hex_Present_checker != null)
                        {
                            correct_type = neighbourType;
                        }
                        Hex_Present_checker = null;
                    }

                    if (correct_type != 0)
                    {
                        neighbourType = correct_type;
                        // int Number_of_neighbours = 6;
                        // GameObject[] Neighbours;
                        Neighbours = new GameObject[Number_of_neighbours];

                        // For each value of each tile in neighbours find what the tile coordinates are in XYZ 
                        for (int q = 0; q < Number_of_neighbours; q++)
                        {
                            // Finds X and Z values of the neighbours
                            if (q < 2)
                            {
                                if (q == 0) { neighbourX = x + 1; }
                                if (q == 1) { neighbourX = x - 1; }
                            }
                            if (z % 2 == 1)
                            {
                                if (q == 2) { neighbourX = x; neighbourZ = z + 1; }
                                if (q == 3) { neighbourX = x + 1; neighbourZ = z + 1; }
                                if (q == 4) { neighbourX = x; neighbourZ = z - 1; }
                                if (q == 5) { neighbourX = x + 1; neighbourZ = z - 1; }
                            }
                            else
                            {
                                if (q == 2) { neighbourX = x - 1; neighbourZ = z + 1; }
                                if (q == 3) { neighbourX = x; neighbourZ = z + 1; }
                                if (q == 4) { neighbourX = x - 1; neighbourZ = z - 1; }
                                if (q == 5) { neighbourX = x; neighbourZ = z - 1; }
                            }
                            // Checks for the highest tile for the XZ coordinate and gets its Y value
                            GameObject potential_highest_ring;
                            int highest_Y = 0;
                            int correct_neighbour_type = 0;
                            for (neighbourY = 0; neighbourY < HeightVal; neighbourY++)
                            {
                                for (neighbourType = 0; neighbourType < 5; neighbourType++)
                                {
                                    potential_highest_ring = null;
                                    potential_highest_ring = GameObject.Find("Hex_" + neighbourX + "_" + neighbourY + "_" + neighbourZ + "_" + neighbourType);
                                    if (potential_highest_ring != null)
                                    {
                                        highest_Y = neighbourY;
                                        correct_neighbour_type = neighbourType;
                                    }
                                }
                            }
                            // Need to check if there is a neighbour at the given coordinates
                            // Debug.Log("Hex_" + neighbourX + "_" + highest_Y + "_" + neighbourZ + "_" + neighbourType);
                            Neighbours[q] = GameObject.Find("Hex_" + neighbourX + "_" + highest_Y + "_" + neighbourZ + "_" + correct_neighbour_type);
                            // While there is a neighbour in the neighbours array
                            // add it's coordinates to the graph node as a part of its neighbours sublist
                            if (Neighbours[q] != null)
                            {
                                graph[x, y, z].neighbours.Add(graph[neighbourX, highest_Y, neighbourZ]);
                            }
                        }
                    }
                }
            }
        }
        MapMakerDone = false;
    }
}

// List<Node> currentPath = null;


public List<Node> GeneratePathTo(GameObject SelectedUnit, Vector3 targetVec)
{
    // Dijkstra's Algorithm Implementation
    Dictionary<Node, float> dist = new Dictionary<Node, float>();
    Dictionary<Node, Node> prev = new Dictionary<Node, Node>();

    List<Node> unvisited = new List<Node>();


    Node source = graph[
        SelectedUnit.GetComponent<UnitBasicScript>().HexX,
        SelectedUnit.GetComponent<UnitBasicScript>().HexY,
        SelectedUnit.GetComponent<UnitBasicScript>().HexZ];


    // TargetNode float to int conversion
    int targetVecXInt = (int)targetVec.x;
    int targetVecYInt = (int)targetVec.y;
    int targetVecZInt = (int)targetVec.z;
    Node targetNode = graph[
        targetVecXInt,
        targetVecYInt,
        targetVecZInt];

    // Debug.Log(targetVecXInt + "_" + targetVecYInt + "_" + targetVecZInt);


    dist[source] = 0;
    prev[source] = null;


    // Initialise everything to have infinity distance since no other 
information available
    // Some nodes might not eb erachable therefore infinity is reasonable
    foreach (Node v in graph)
    {
        if (v != source)
        {
            dist[v] = Mathf.Infinity;
            prev[v] = null;
        }

        unvisited.Add(v);
    }

    while (unvisited.Count > 0)
    {
        // u is unvisited node with shortest distance
        Node u = null;
        foreach (Node possibleU in unvisited)
        {
            if (u == null || dist[possibleU] < dist[u])
            {
                u = possibleU;
            }
        }

        unvisited.Remove(u);


        if (u == targetNode)
        {
            break;
        }


        foreach (Node v in u.neighbours)
        {
            float alt = dist[u] + u.Distanceto(v);
            if (alt < dist[v])
            {
                dist[v] = alt;
                prev[v] = u;
            }
        }
    }

    if (prev[targetNode] == null)
    {
        // No route to target
        return null;
    }

    List<Node> currentPath = new List<Node>();

    Node curr = targetNode;

    while (prev[curr] != null)
    {
        currentPath.Add(curr);
        curr = prev[curr];
    }

    currentPath.Reverse();
    return currentPath;
} // End of generate path function

public class Node
{

    public int x = 0;
    public int y = 0;
    public int z = 0;

    public List<Node> neighbours;

    public Node()
    {
        neighbours = new List<Node>();
    }

    public float Distanceto(Node n)
    {
        if (n == null)
        {
            Debug.Log("Error");
        }

        return Vector2.Distance(
            new Vector3(x, y, z),
            new Vector3(n.x, n.y, n.z));
    }
}
}

代码到此结束，我知道 monobehaviour 中的所有内容都必须缩进，它在我的代码中，但是在复制到 Whosebug 中时它丢失了缩进。接下来是显示单元采取的错误路径的图片。

https://imgur.com/a/wEChdq3

如果需要任何其他信息，请告诉我，我将非常乐意提供。再次感谢您！

Answer 1

您使用的是 List 而不是优先级队列，后者效率极低。此外，由于您的网格具有简单的启发式算法，因此您应该考虑使用 A*，这样速度会快得多。

Answer 2

尽管我仍然没有解决所有明显的低效率问题，但我已经解决了算法实现的问题。我得到的是瓷砖网格坐标之间的距离，它没有考虑到在六角网格上，对角线移动与水平移动具有完全相同的距离成本。因此，解决方案是在节点网格坐标转换为世界坐标后获取距离，因为这将确保相邻图块之间的所有距离相等。

如果有人遇到同样的问题，希望这对您有所帮助！

Dijkstra 在六角网格上的算法效率低下，C#，Unity3D

Dijkstra's Algorithm Ineffeciencies on a Hex Grid, C#, Unity3D

c#

unity3d

path-finding