| server2009 | Дата: Воскресенье, 22.11.2009, 12:34 | Сообщение # 1 |
 Admin
Группа: Администраторы
Сообщений: 18
Статус: Offline
| Все мы играли в компьютерные игры. Кто-нибудь задумывался, как объекты управляемые пользователям движутся по карте?
Суть алгоритмов поиска кратчайшего пути:
Давайте попробуем разобраться на примере типовой стратегии. Чтобы игрок двигался по карте рациональным путем от начальной позиции к конечной, используются алгоритмы поиска кратчайшего пути.
Мы остановимся на "Волновом" алгоритме, он или его модификации чаще всего используется в играх. И так, мы указали координату куда следует направить персонажа, компьютер начинает поиск пути.
Принцип работы подобных алгоритмов очень прост, есть различные места на карте, которые можно классифицировать по типу:
- непроходимые части (их мы исключаем из пути сразу)
- проходимые, но с большими затратами по скорости или другим факторам, их мы будем использовать только в крайнем случае
- наилучшие участки (пешеходные дороги или что-то в этом роде), их мы будим использовать наиболее часто
Для этого в массиве должны содержаться данные с "ценой" прохождения участка.
Разберем для начала более простой вариант реализации:
На двумерной клетчатой карте (матрице), состоящей из "проходимых" и "непроходимых" клеток, обозначена клетка старта и клетка финиша.
Цель алгоритма - проложить кратчайший путь от клетки старта к клетке финиша, если это возможно.
- От финиша во все направления распространяется волна, причем каждая пройденная волной клетка, помечается как "пройденная".
- Волна, в свою очередь, не может проходить через клетки помеченные как "пройденные" или "непроходимые".
- Волна движется, пока не достигнет точки старта или пока не останется не пройденных клеток.
- Если волна прошла все доступные клетки, но так и не достигла клетки старта, значит путь от старта до финиша проложить невозможно.
- После достижения волной старта, от старта прокладывается путь до финиша и сохраняется в массиве.
|
| |
| |
| server2009 | Дата: Воскресенье, 22.11.2009, 12:34 | Сообщение # 2 |
|
Admin
Группа: Администраторы
Сообщений: 18
Статус: Offline
| Пример реализации прикреплен к сообщению:
|
| |
| |
