Нужна помощь в изменении моего A * на (шестнадцатеричной) сетке, которая в основном "препятствия", но актер может перепрыгивать X плиток - PullRequest
Новая
       66

Нужна помощь в изменении моего A * на (шестнадцатеричной) сетке, которая в основном "препятствия", но актер может перепрыгивать X плиток

1 голос
/ 19 сентября 2019

Решено! См. Мой собственный ответ.

Я создаю приложение, в котором есть карта на основе гекса.Для перемещения между гексами требуется определенное количество времени, и я пытаюсь реализовать способ нажать на любой действительный гекс и получить оптимальный путь (если возможно) из текущей позиции игроков.

Вотхитрая часть, только несколько из гексов являются допустимыми местами перемещения, поэтому мне нужно найти путь, чтобы можно было пропустить пустые гексы.В зависимости от «досягаемости» игроков им разрешено пропускать недопустимые пробелы.Так что, если игроки достигли, было франц.3, им разрешено перемещаться на 1, 2 или 3 пробела за один «ход», даже если гексы между ними недопустимы (пусто), но им не разрешено «останавливаться» на недопустимых гексах.

Пример:

Example image

До сих пор я реализовал скрипт поиска пути A * с помощью следующих ссылок:

Но я не уверен, как реализовать функцию «Прыжки» или «Прыжки» Iищу.Я специально избегал использования «крайних» затрат, потому что это потребовало бы большого количества изменений в моей текущей реализации, а направление вообще не имеет значения.

Моя версия функции 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);
            }
        }
    }
}

Я просто не знаю, как расширить поиск по другим непроходимым гексам или подобным.Мне нужно, чтобы конечный результат был кратчайшим путем до конечного гекса (если возможно), чтобы отобразить маршрут и пройденное расстояние.Любая помощь приветствуется:)

Редактировать: Хорошо, согласно предложению Рузима, я пытаюсь расширить свою функцию "GetNeighbors", чтобы достичь своей цели.Чтобы получить всех «соседей» в диапазоне максимальной скорости, я пытаюсь реализовать код из раздела «Диапазон движения» руководства по шестигранным сеткам Red Blob Games: 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 для каждого гекса ивернуть те, у которых есть расстояние <=, чтобы "достичь" ..? </p>

1 Ответ

1 голос
/ 20 сентября 2019

Хорошо, поэтому я решил свою проблему (благодаря некоторым указателям из 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

...