需要帮助在（十六进制）网格上修改我的 A*，该网格主要是 "obstacles"，但演员可以跳过 X 个方块

Question

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

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

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

示例：

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

但我不确定如何实现我正在寻找的 "Skipping" 或 "Jumping" 功能。我特别避免使用 "edge" 成本，因为它需要对我当前的实现进行大量更改，而方向根本不重要。

我在第三篇参考中的A*函数版本link:

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" 函数以实现我的目标。为了让所有 "neighbors" 都在最大速度范围内，我正在尝试实现 Red Blob Games 的 hexgrid 指南的 "Movement range" 部分中的代码：https://www.redblobgames.com/grids/hexagons/#range（第二个代码片段）

从 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 和 return 那些距离 <= 到 "reach"..?

Answer 1

好吧，我最终解决了我的问题（感谢 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;
}

哦，还有，这是我用来将寻路数据转换为对象形式的有用数据的方法，我称之为 "Journey":

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);
}

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

需要帮助在（十六进制）网格上修改我的 A*，该网格主要是 "obstacles"，但演员可以跳过 X 个方块

Need help modifying my A* on a (hex) grid that's mostly "obstacles", but the actor can jump over X tiles

c#

a-star

path-finding

hexagonal-tiles

unity3d