时间戳

首页 > 解决方案 > 需要帮助在（十六进制）网格上修改我的 A*，该网格主要是“障碍物”，但演员可以跳过 X 块

c# - 需要帮助在（十六进制）网格上修改我的 A*，该网格主要是“障碍物”，但演员可以跳过 X 块

问题描述

解决了！看我自己的答案。

我正在创建一个应用程序，其中有一个基于十六进制的地图。在六角形之间移动需要一定的时间，我正在尝试实现一种方法来按下任何有效的六角形并从玩家当前位置获得最佳路径（如果可能）。

棘手的部分来了，只有几个格子是有效的旅行位置，所以我需要我的路径查找能够跳过空的格子。根据玩家“达到”的程度，他们可以跳过其他无效的空格。因此，如果玩家到达是 f ex。3，允许他们在一次“移动”中移动 1、2 或 3 个空格，即使中间的十六进制无效（空），但不允许他们在无效的十六进制上“停止”。

例子：

示例图片

到目前为止，我已经在这些参考资料的帮助下实现了一个 A* 寻路脚本：

但我不确定如何实现我正在寻找的“跳过”或“跳跃”功能。我特别避免使用“边缘”成本，因为它需要对我当前的实现进行大量更改，而且方向根本无关紧要。

我在第三个参考链接中的 A* 函数版本：

public void AStarSearch(MapHex startHex, MapHex goalHex)
{
    if (goalHex.empty)
    {
        Debug.Log("Goal empty.");
        return;
    }
    SimplePriorityQueue<MapHex> frontier = 
        new SimplePriorityQueue<MapHex>();

    frontier.Enqueue(startHex, 0);
    cameFrom.Add(startHex, startHex);
    costSoFar.Add(startHex, 0);

    while (frontier.Count > 0)
    {
        MapHex current = frontier.Dequeue();

        if (current.Equals(goalHex)) break;

        foreach (MapHex neighbor in GetNeighbors(current))
        {
            float newCost = costSoFar[current] + 1;
            if (!costSoFar.ContainsKey(neighbor) || 
                newCost < costSoFar[neighbor])
            {
                if (costSoFar.ContainsKey(neighbor))
                {
                    costSoFar.Remove(neighbor);
                    cameFrom.Remove(neighbor);
                }

                costSoFar.Add(neighbor, newCost);
                cameFrom.Add(neighbor, current);
                float priority = newCost +
                    HexHeuristicDistance(neighbor, goalHex);
                frontier.Enqueue(neighbor, priority);
            }
        }
    }
}

我只是不知道如何将搜索扩展到其他无法通过的十六进制或类似内容。我需要最终输出是到末端十六进制的最短路线（如果有可能），以显示路线和行驶距离。任何帮助表示赞赏:)

编辑： 好的，根据 Ruzihm 的建议，我正在尝试扩展我的“GetNeighbors”功能以实现我的目标。为了让所有“邻居”都在最大速度范围内，我正在尝试实现 Red Blob Games hexgrid 指南的“运动范围”部分的代码：https ://www.redblobgames.com/grids/hexagons/#范围（第二个代码片段）

从 python 转换被证明是一个挑战，我似乎创造了一个效率低下的怪物，它可能会也可能不会起作用：

public IEnumerable<MapHex> GetNeighbors(MapHex hex, int distanceOffset)
{
    if (distanceOffset == 0)
    {
        foreach (Vector2 dir in oddQDirections)
        {
            MapHex next = allMapHexes.Find(item => item.coordinate == new Vector2(hex.coordinate.x + dir.x, hex.coordinate.y + dir.y));
            if (next != null)
            {
                yield return next;
            }
        }
    }
    else
    {
        List<MapHex> neighbors = new List<MapHex>();
        List<MapHex> closeHexesX = new List<MapHex>();
        Vector3 hexCubeCoord = OddQToCube(hex.coordinate);

        foreach (MapHex closeHex in allMapHexes.FindAll(item => !item.empty && -(distanceOffset + 1) <= -OddQToCube(item.coordinate).x && -OddQToCube(item.coordinate).x <= distanceOffset + 1))
        {
            closeHexesX.Add(closeHex);
        }
        foreach (MapHex closeHex in closeHexesX.FindAll(item => Mathf.Max(-(distanceOffset + 1), -OddQToCube(item.coordinate).x - (distanceOffset + 1)) <= -OddQToCube(item.coordinate).y && -OddQToCube(item.coordinate).x <= Mathf.Min((distanceOffset + 1), -OddQToCube(item.coordinate).x + (distanceOffset + 1))))
        {
            Vector3 cubeCoord = OddQToCube(closeHex.coordinate);
            cubeCoord.z = -cubeCoord.x - cubeCoord.y;
            neighbors.Add(closeHexesX.Find(item => item.coordinate == CubeToOddQ(hexCubeCoord + cubeCoord)));
        }
    }
}

也许我最好只为每个十六进制运行 GetDistance 并将距离 <= 的那些返回“到达”..？

标签： c#unity3dpath-findinga-starhexagonal-tiles

解决方案

好的，所以我最终通过简单地检查每个寻路节点的范围内所有有效的十六进制来解决我的问题（感谢Ruzihm的一些指针让我重新思考我的问题）。我不确定这是最快的方法，但我已经有一个有效十六进制列表，所以我没有遍历每个循环的所有空十六进制，它似乎足够快。

这是我最终使用每个路径查找循环的“GetNeighbours”代码：

public List<MapHex> GetNeighborsInRange(MapHex hex, int distance)
{
    List<MapHex> neighbors = new List<MapHex>();
    if (distance == 0)
    {
        foreach (Vector2 dir in oddQDirections)
        {
            MapHex next = allMapHexes.Find(item => item.coordinate == new Vector2(hex.coordinate.x + dir.x, hex.coordinate.y + dir.y));
            if (next != null)
            {
                neighbors.Add(next);
            }
        }
    }
    else
    {
        foreach (MapHex closeHex in nonEmptyMapHexes)
        {
            if (HexHeuristicDistance(hex, closeHex) <= distance)
            {
                neighbors.Add(closeHex);
            }
        }
    }

    return neighbors;
}

哦，还有，这是我用来将寻路数据转换为有用数据的方法，我称之为“旅程”的对象形式：

public Journey GetLatestPath()
{
    if (cameFrom == null || cameFrom.Count == 0 || costSoFar == null || costSoFar.Count == 0)
    {
        //Trying to run this before running an A* search.
        return null;
    }

    int pathTravelTime = 0;
    List<MapHex> path = new List<MapHex>();
    MapHex current = aStarLatestGoal;

    while (!current.Equals(aStarLatestStart))
    {
        if (!cameFrom.ContainsKey(current))
        {
            //A* was unable to find a valid path.
            return null;
        }
        path.Add(current);
        current = cameFrom[current];
        pathTravelTime += HexHeuristicDistance(current, path[path.Count - 1]);
    }
    path.Reverse();

    return new Journey(path, aStarLatestStart, pathTravelTime);
}

如果您使用的是立方体或轴向六角网格，请查看此问题以获取“获取所有范围内”的可能解决方案：https ://gamedev.stackexchange.com/questions/116035/finding-cells-within-range-on -hexagonal-grid?rq=1

推荐阅读