Форум программистов, компьютерный форум, киберфорум
Наши страницы
Программирование игр
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
6ireee
0 / 0 / 0
Регистрация: 31.01.2018
Сообщений: 9
1

Тонкости реализации волнового алгоритма в RTS

21.09.2018, 21:57. Просмотров 946. Ответов 4

Разрабатываю RTS, подобие Dune 2 и KKnD. Есть квадратное поле, разбитое на ячейки (двухмерный массив), каждая из которых является либо проходимой, либо нет. По этому полю необходимо найти кратчайший путь от выбранного игроком юнита до указанной точки, либо до ближайшей к ней незанятой точке. Для поиска задействовал волновой алгоритм.
Проблема в следующем: если указанная точка свободна, путь строится без проблем - чем меньше расстояние до неё, тем быстрее, если в указанной точке стоит вражеский или дружественный юнит, путь тоже можно построить, но что делать, если этот юнит будет вплотную окружён со всех сторон другими юнитами? Ведь на карте их позиции являются непроходимыми, и они будут препятствовать распространению волны. Необходимо найти ближайшую к указанной цели ячейку, до которой можно добраться, но как именно это реализовать?
Перепробовал массу вариантов.
Если юнит вражеский, можно задавать в качестве целей все свободные ячейки в пределах определённого радиуса (к примеру, радиуса стрельбы), и найти путь хотя бы к одной из них (примерно так советуют в этой статье), но что делать, если указанный вражеский юнит окружает настолько много других юнитов, что ближайшая свободная ячейка карты будет за пределами этого радиуса? Да, атаковать из этой ячейки будет нельзя, но ведь нужно до неё хотя бы добраться, а там уже действовать по ситуации...
Можно дождаться, когда волновой алгоритм обойдёт всю карту, а потом перебрать все ячейки и выбрать ту из помеченных волной ячеек, чья стоимость движения будет минимальной, и чьё расстояние (Манхэттанское или же реальное) до целевой ячейки также будет минимальным, но ведь такой перебор займёт немалое время. Кроме того, необходимо дождаться, пока алгоритм обойдёт всю карту, и только потом проверять, а как быть, если выбранный юнит и целевая ячейка расположены не в противоположных углах карты, а достаточно близко, к примеру на расстоянии 5-7 ячеек?..
Можно тупо построить путь, вообще не учитывая юниты как препятствия, а потом просто последовательно двигаться по нему и
при любом столкновении с юнитами включать алгоритм обхода (к примеру, обход по правилу правой/левой руки) но вот пути при этом получаются далеко не кратчайшими, а если вражеские юниты ещё и загородили какой-нибудь проход между скалами, где построен кратчайший путь, то вообще кошмар...

Как решить подобную проблему? Ведь во множестве RTS это успешно решено... Или же нужно идти вообще другим путём?
Буду очень признателен за дельный совет...
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.09.2018, 21:57
Ответы с готовыми решениями:

Нужен совет в реализации волнового алгоритма
program E; uses crt; const a:array of byte = ((0, 0, 1, 0, 0, 0, 0, 0, 0, 0), ...

Применимость волнового алгоритма.
Случай таков: 1. Карта трёхмерная. 2. Карта существует не в виде растра проходимости, а в виде...

Реализация волнового алгоритма
Делаю игру Пакман В Игре имеются следующие классы Map.h #ifndef MAP_H #define MAP_H ...

Реализация волнового алгоритма в С++ и вывод на экран
Есть у меня такая задачка: составить программу, которая создаст квадратный лабиринт со сторойной...

Исправить ошибку в коде волнового алгоритма
вот код программы #include using namespace std; int plov(int n,int i,int j,int k,char***...

4
Бард
153 / 102 / 58
Регистрация: 12.07.2018
Сообщений: 256
22.09.2018, 12:49 2
Лучший ответ Сообщение было отмечено 6ireee как решение

Решение

Цитата Сообщение от 6ireee Посмотреть сообщение
Можно дождаться, когда волновой алгоритм обойдёт всю карту, а потом перебрать все ячейки и выбрать ту из помеченных волной ячеек, чья стоимость движения будет минимальной, и чьё расстояние (Манхэттанское или же реальное) до целевой ячейки также будет минимальным
Перебирать ячейки после окончания волнового алгоритма не нужно. Надо в расчёте волны при попадании в проходимую ячейку вычислять расстояние от неё до целевой ячейки и сравнивать полученное значение с имеющимся на данный момент минимальным расстоянием. В этом случае в конце волны автоматически будет получена ближайшая к цели доступная ячейка и путь до неё.
Для предотвращения больших вычислений путей в одном игровом цикле, следует разнести вычисления путей для разных юнитов по ряду последовательных игровых циклов.
В качестве оптимизации можно также не вычислять точное реальное расстояние, а брать просто сумму квадратов (без извлечения корня), т.к. это значение требуется только для сравнения по условию "меньше".
1
HappyCodingDays
4 / 5 / 0
Регистрация: 23.09.2018
Сообщений: 31
02.10.2018, 11:07 3
Или же нужно идти вообще другим путём?
я бы пошел другим путем
скачал бы с гита Recast & Detour https://github.com/recastnavigation/recastnavigation
и начал с разбираться как на нем делают управление толпой юнитов
0
6ireee
0 / 0 / 0
Регистрация: 31.01.2018
Сообщений: 9
11.01.2019, 00:36  [ТС] 4
Цитата Сообщение от Бард Посмотреть сообщение
Надо в расчёте волны при попадании в проходимую ячейку вычислять расстояние от неё до целевой ячейки и сравнивать полученное значение с имеющимся на данный момент минимальным расстоянием.
Об этом я как-то не подумал :) Попробую реализовать.
Цитата Сообщение от Бард Посмотреть сообщение
В качестве оптимизации можно также не вычислять точное реальное расстояние, а брать просто сумму квадратов (без извлечения корня)
Ну, эту фишку очень активно использую.
0
Дмитррр
39 / 23 / 3
Регистрация: 27.03.2016
Сообщений: 108
11.01.2019, 11:14 5
Я бы вообще в начале проверил если ли путь до указанной точки. Если пути нет, то никуда не надо двигать юниты.
Что игрок должен подумать об игре, когда он послал унит в одну точку, а тот припёрся в ближайшую к ней, но с другой стороны от стены или горы например? Ты не угадаешь, куда игроку нужно было двигать юнит. Пусть сам думает и приказывает более точно.
Исключение можно сделать только для союзных юнитов - пусть становится рядом.
0
11.01.2019, 11:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2019, 11:14

Реализация волнового алгоритма поиска пути в лабиринте
Люди прошу помощи бьюсь над этой фигнёй уже 3 недели. На форуме впервые прошу не ругать за...

Визуальный редактор массивов для обратного волнового алгоритма
Обратный волновой алгоритм - способ инициализации типа объекта. Разработан в качестве процедуры...

Нужне совет по реализации алгоритма
a1, (a1+a2), (a1+a2+a3), ... , (a1+a2+...aN)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru