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

Вот ситуация.

У меня есть гексагональная доска и блок на ней со скоростью или перемещением. 4. Дифференциальная рельеф имеет разную стоимость. Когда я нажимаю на устройство, игра должна показывать мне диапазон перемещения.

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

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

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

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

10 голосов | спросил user23673 6 ThuEurope/Moscow2012-12-06T15:08:27+04:00Europe/Moscow12bEurope/MoscowThu, 06 Dec 2012 15:08:27 +0400 2012, 15:08:27

2 ответа


11

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

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

введите описание изображения здесь

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

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

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

ответил MichaelHouse 6 ThuEurope/Moscow2012-12-06T23:00:46+04:00Europe/Moscow12bEurope/MoscowThu, 06 Dec 2012 23:00:46 +0400 2012, 23:00:46
2

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

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

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

введите описание изображения здесь>> </p>

<p> Это найдет все гексы на определенном расстоянии от центрального гексагона, если вы хотите рассмотреть препятствия, используйте первый поиск по ширине из моего другого ответа. </p></body></html>

ответил MichaelHouse 27 FriEurope/Moscow2013-12-27T02:13:42+04:00Europe/Moscow12bEurope/MoscowFri, 27 Dec 2013 02:13:42 +0400 2013, 02:13:42

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132