Отображение диапазона на гексагональной сетке

Здесь ситуация.

У меня есть гексагональная доска, и юнит на ней, со скоростью или значением перемещения 4. Различная местность имеет разные затраты. Когда я нажимаю на юнит, игра должна показывать мне диапазон хода.

Мое решение состояло в том, чтобы проверять каждый гекс в диапазоне 4, используя A * pathfinding, и если стоимость пути была меньше 4, тогда этот гекс находился в диапазоне. Наконец, игра хорошо показывает мне диапазон этого отряда.

Мой вопрос: есть ли другое решение для поиска диапазона по гекс-сеткам или квадратной сетке, потому что даже если я действительно горжусь тем, что я сделал в своем решении, я думаю, это немного преувеличено? :))

Что заставило меня задать этот вопрос? Я заметил, что когда единичная скорость равна 4, 6 или даже 8, время вычисления диапазона для моего компьютера было действительно хорошим, но когда скорость составляла 10 и более, я заметил, что мне нужно подождать несколько секунд, чтобы вычислить Ну, в реальных играх я не вижу ничего подобного, и мой A * pathfinding довольно хорошо оптимизирован, так что я думаю, что мое решение неверно.

Спасибо за любые ответы.

Вы правы, что A * немного излишне, но ненамного. Вы не должны видеть задержки, как вы. А * на самом деле просто модифицированный алгоритм Диджикстры . Поскольку вы не используете конечную позицию (поскольку ваша конечная позиция просто «насколько вы можете пойти»), использование A * с добавленной эвристикой не требуется. Простого использования Dijikstra или простого поиска в ширину будет достаточно.

Например, Dikikstra будет распространяться равномерно по всем направлениям:

(Простой поиск в ширину будет выглядеть примерно так)

Следите за стоимостью проезда к каждому узлу. Как только узел достиг максимальной стоимости поездки, не обрабатывайте подключенные узлы дальше. (Аналогично тому, где узлы врезаются в стену ниже).

Если вы столкнулись с проблемами производительности только на 10 узлах, вам нужно посмотреть, как вы получаете доступ к узлам. Поиск в ширину должен позволять перемещаться по сотням узлов без заметной задержки (конечно, не за несколько секунд). Рассмотрите возможность хранения простой версии вашего мира в графическом формате для быстрого прохождения.

Амит Патель предоставил отличный ресурс для получения диапазонов на своем сайте . В статье он использует следующий алгоритм для сбора шестигранных плиток в пределах диапазона:

for each -N ≤ Δx ≤ N:
    for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
        Δz = -Δx-Δy
        results.append(H.add(Cube(Δx, Δy, Δz)))

Это создает границы, выровненные по шестнадцатеричной сетке:

Это позволит найти все гексы на определенном расстоянии от центрального гексагона. Если вы хотите рассмотреть препятствия, используйте поиск в ширину из моего другого ответа.

Если кому-то это нужно, вот реализация C # алгоритма Пателя:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }