Вторник, 16 Августа 2022, 12:14

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Программирование » Общие обсуждения программистов » Поиск пути - как реализовать? (Как оптимизировать)
Поиск пути - как реализовать?
TAPAKAHДата: Четверг, 13 Мая 2010, 12:16 | Сообщение # 1
почетный гость
Сейчас нет на сайте
Есть ли возможность оптимизировать время прокладки пути от а до б для всех юнитов на большой карте?
Какой алгоритм поиска пути предпочли бы вы?
а. Волновой как самый эффективный.
б. А* как самый замороченный
в. Другой

Размышление в слух о поставленой задаче.



Все имеет свое имя и название.
Осмысливая смысл смысла, в смысле смысла смысла смысла, не смысл ли помыслить о немыслимом?
P:OG
Лишь идеи рождают шедевры.
TAPAKAHДата: Четверг, 13 Мая 2010, 13:12 | Сообщение # 2
почетный гость
Сейчас нет на сайте
Quote (QWER56)
в

Краткость сестра таланта.
Поподробнее.


Все имеет свое имя и название.
Осмысливая смысл смысла, в смысле смысла смысла смысла, не смысл ли помыслить о немыслимом?
P:OG
Лишь идеи рождают шедевры.
smittДата: Вторник, 18 Мая 2010, 12:03 | Сообщение # 3
почетный гость
Сейчас нет на сайте
patch engine в помощь

WXZRWДата: Вторник, 18 Мая 2010, 14:41 | Сообщение # 4
Thousand faces conspiration
Сейчас нет на сайте
Quote (TAPAKAH)
Какой алгоритм поиска пути предпочли бы вы?

Navmesh, только не в чистом виде, а гибридный. Упрощенный для текущего патча (локальный поиск) и усложненный для всей карты (глобальный поиск). Правда я не уверен что это подойдет для большого количества ботов.

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

А вообще юзай как у тебя есть, чекпоинты (вообще-то это waypoints), все равно это самый распространенный подход, даже в ХЛ2 нечто подобное да и в других играх.

LucasitoДата: Вторник, 18 Мая 2010, 15:07 | Сообщение # 5
участник
Сейчас нет на сайте
Quote (TAPAKAH)
Какой алгоритм поиска пути предпочли бы вы?

если проходимость клеток не очень часто меняется, то можно сделать по такому алгоритму:
сделать дополнительные 4 матрицы проходимости, которые заполнить слева-направо, сверху-вниз и 2 по диагонали числами по возрастанию станадартным алгоритмом нахождения оптимального пути в лабиринте. Затем идти к цели по какой-либо матрице, только иногда вставляя проверку выбора(в принципе можно каждый ход, но в таком случае персонаж может в некоторых случаях начать дергаться, но идти в нужном направлении), какая матрица сейчас оптимальна для достижения точки. Оптимальность думаю можно выбирать как модуль разности числа в текущей клетке и в клетке назначения. Для какой матрицы будет меньше, ту и выбирать.
Этот алгоритм я сейчас придумал, на практике не применял, но думаю вполне работоспособный.



Скриншоты. Приглашаем бета-тестеров!
Помог? Ставь "+" мне в репу :)
Форум игроделов » Программирование » Общие обсуждения программистов » Поиск пути - как реализовать? (Как оптимизировать)
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2022 Рейтинг