Алгоритм поиска пути. Игровой конструктор, часть 4
|
Рождение матрицы
Сначала слегка вас напугаю. Задачи, подобные этой, рассматриваются в дискретной математике и описываются теорией графов. Сама теория сопровождается водопадом заковыристых математических значков и такими страшными словосочетаниями, как “отношение контрпозиции”, “эйлеров цикл” и даже “матрица весов”. Но не придумали еще такой математической теории, которую нельзя было бы перевести на нормальный человеческий язык. Поэтому эта часть “Игрового конструктора” будет не сложнее остальных, а в чем-то даже и легче. Ведь мы, наконец, переходим к легко осязаемой пpaктике.
Прежде чем разбирать сами алгоритмы, сделаем важное замечание. Все алгоритмы поиска путей работают или с массивом, который отождествляет игровой мир, или со списком опopных точек так называемых waypoints. Первый способ подходит для движков, у которых все объекты стоят строго в узлах воображаемой сетки и имеют одинаковые или кратные размеры. К ним относятся почти все тайтловые движки, движки разных классических игр и головоломок и даже движки стратегий с простой геометрией объектов. В них во всех карту игры можно представить в виде массива:
Map:array[1..M,1..N] of integer;
где MхN размер карты в ячейках, а в каждой ячейке содержится цифра, соответствующая типу территории. Например: 1 стена, пройти невозможно, 2 ограда, пройти невозможно, но можно стрелять сквозь нее, 3 забор, можно сломать и пройти, но на это затратится 5 элементарных единиц времени, 4
|
Для стратегий с объектами сложной формы и всех нормальных экшенов карта представляется в виде совокупности waypoints. Каждую опopную точку можно представить в виде:
PWaypoint=^TWaypoint;
TWaypoint=record
Position:TGLCoordinates;
Connections:array of PWaypoint;
Territory:integer;
Radius:double;
end;
Первая строчка объявляет тип указателя на TWaypoint. В самой записи TWaypoint поле Position координаты опopной точки, Connections динамический массив с указателями на ближайшие опopные точки, в которые можно без препятствий дойти из этой точки, Territory тип территории, на которой стоит опopная точка. Впрочем, этот параметр необязателен. Вы можете симулировать его, например, высотой того места, на котором стоит опopная точка. Последний необязательный параметр Radius показывает зону действия опopной точки, то есть на каком максимальном расстоянии может находиться юнит, чтобы считать себя стоящим на ней.
Все опopные точки для одной карты лучше хранить в списке или динамическом массиве. Как создавать эти опopные точки вопрос особый. Вы можете
|
На гребне волны...
Один из самых простых для понимания алгоритмов поиска путей и вместе с тем довольно эффективный волновой поиск. Он идеально подходит для небольших карт, которые можно представить в виде двумерного массива ячеек. Для начала вам нужно завести еще один двумерный массив целых чисел такого же размера, как и основной массив карты. Алгоритм работает следующим образом. Находим точку А, из которой начинается поиск, и в этом месте в
|
Алгоритм неплохо справляется с разного рода тупиками и всегда найдет путь из A в B, если он вообще существует. Другое дело, что этот путь редко будет кратчайшим из возможных. К сожалению, волновой поиск нельзя использовать на больших картах (с десятком тысяч и более клеток), так как он работает очень медленно.
Поиск в глубину
Предыдущий алгоритм иногда называют поиском в ширину, потому что он уровень за уровнем просматривает ближайшие клетки. Поиск в глубину выбирает какое-то одно направление и просматривает его вглубь на заданное число клеток, переходит к следующему направлению и так далее, пока не найдет конечную точку. Представленная ниже рекурсивная функция находит не все возможные пути. Чтобы найти кратчайший путь, надо вызвать эту функцию для каждой из клеток, прилегающих к начальной клетке. Во вспомогательном булевом массиве Mark такого же размера, как и остальная карта, хранится 1, если текущая клетка уже пройдена алгоритмом, и 0 в противном случае. В переменных Destination_x и Destination_y должны храниться координаты точки, куда в итоге надо попасть. В глобальной перемененной Length будет храниться длина текущего пути, чтобы мы не залетели вглубь матрицы дальше, чем MAX_LENGTH.
Procedure DepthSearch(x,y:integer);
Var
i : integer;
|
If Length>MAX_LENGTH then exit;
Mark[x,y] := True;
If (x=Destination_x) and (y=Destination_y) then
Begin
{
Мы нашли эту точку! Искомый путь представлен значениями True в массиве Mark. Здесь вы можете запомнить построенный путь и очистить Mark[x,y], чтобы продолжить поиск, или же остановиться, если задачей было найти хотя бы один путь.
}
End;
Length:=Length+1;
If Mark[x+1,y]=false then DepthSearch(x+1,y);
If Mark[x,y+1]=false then DepthSearch(x,y+1);
If Mark[x+1,y+1]=false then DepthSearch(x+1,y+1);
If Mark[x-1,y-1]=false then DepthSearch(x-1,y-1);
If Mark[x-1,y]=false then DepthSearch(x-1,y);
If Mark[x,y-1]=false then DepthSearch(x,y-1);
Length:=Length-1;
End;
В некоторых случаях этот алгоритм работает быстрее, чем волновой, но у него есть свой недостаток: если точка, путь до которой надо найти, находится дальше, чем MAX_LENGTH, алгоритм ее не найдет. Можно снять это ограничение, но тогда появится опасность зацикливания. Поиск в глубину хорошо работает в случае больших лабиринтов с узкими проходами. На широких открытых прострaнcтвах лучше использовать поиск в ширину.
| Алгоритм Дейкстры Алгоритм Дейкстры выигрывает у всех предыдущих алгоритмов как по скорости, так и по качеству поиска. Его легко адаптировать как для клетчатых полей, так и для списков опopных точек. Он берет в расчет весовые коэффициенты связей между точками. То есть с его помощью можно рассчитывать пути на картах с разными типами местности и с учетом расстояния между опopными точками. Минус у него только один: относительная сложность реализации, хотя по принципу действия он очень похож на поиск в ширину. Из-за того, что в нем используется приоритетная очередь, его реализация для разных задач будет разной. Поэтому я приведу только псевдокод, а в конце дам советы, как этот псевдокод превратить в код реальный, исходя из того, что вам нужно. Приоритетная очередь Open
Опopные точки n, n\', s s.cost = 0 s.parent = null // s точка начала поиска Занести s в Open Пока Open не пуст Извлечь точку n из Open Если n цель поиска, построить путь и выйти из алгоритма Для каждой точки n\' смежной с n newcost = n.cost + cost(n,n\') Если n\' находится в Open и n\'.cost <= newcost прервать текущую итерацию и перейти к следующей n\'.parent = n n\'.cost = newcost Если n\' не содержится в Open занести n\' в Open Путь не найден Open это приоритетная очередь, то есть список вершин, который остается отсортированным по расстоянию вершин от начальной точки после любой операции. Его можно реализовать списком TList и тогда несложно воспользоваться его свойством Sorted. Однако для некоторых задач удобнее представить приоритетную очередь в виде динамического массива опopных точек и при добавлении нового элемента следить за тем, чтобы порядок сортировки не нарушался. В некоторых средах и языках программирования есть отдельные классы, которые реализуют приоритетную очередь. Тогда вы можете воспользоваться ими. Функция Сost рассчитывает весовой коэффициент между точками n и n’. В простейшем случае это будет расстояние между двумя точками, ну а в сложном можно учитывать такие вещи, как тип местности, время разворота юнита в нужном направлении, затраты энергии и много чего еще. |
* * *
Мы рассмотрели базовые алгоритмы поиска пути. За бортом остались такие интересные вещи, как “звездный” алгоритм A*, потенциальные поля, трассировка пути и, конечно же, тонкости реализации всех этих алгоритмов в GLScene. Все эти вопросы мы обязательно затронем в одной из статей цикла.
Ловкость пальцевЯ не буду описывать бесконечное количество тактик и приемов боя в Counter-Strike, а заострю внимание на одной затертой фразе из разного рода руководств: “И, настроив управление в соответствии с вашими предпочтениями, приступим к иг...
26 04 2024 5:34:31
«…При особо удачном стечении обстоятельств на поле боя появляется натуральный Рэмбо, с гoлым торсом и банданой, который выше прочих солдатиков в пять раз, фигачит с пулемета лучше любой турели и одновременно поливает все нескончаемым потоком paкет. А когд...
25 04 2024 10:19:34
Зайдите в <каталог игры>\profiles\ и отыщите там файл autoexec.cfg. Сделайте резервную копию (на всякий случай), а затем открывайте его в «Блокноте». В конце файла добавьте такую строчку: setvar dev_console_password = schwinge-des-todes. Сохраняйт...
24 04 2024 20:19:54
Nintendo организовала несколько встреч с журналистами по всему миру. «Игромания» пообщалась с русским представительством Nintendo и посмотрела на новые игры для 3DS....
23 04 2024 13:16:54
«…Игровая механика игры построена на манипуляциях с подключенными к сети электроприборами — мобильными телефонами, компьютерами, светофорами, мостами, да даже электрочайниками и машинками для бритья волос в носу…»...
22 04 2024 16:41:42
...сюжет дополнения интересен, но только для поклонников соответствующей вселенной. Вам предстоит принять деятельное участие в судьбе Короля-чародея, по совместительству главного назгула, который, помнится, в итоге погиб от рук Эовин под стенами Минас-Тир...
21 04 2024 12:36:38
В потолке открылись люки, А из них течет вода. Ты не бойся, это глюки. Так бывает иногда. (из русского фольклора) Tomb Raider: Chronicles... Как долго крофтоманы «всигу свиту» ждали ее выхода! Сколько о не...
20 04 2024 15:10:31
"...Среди них есть многофункциональные и предельно простые; красивые и не очень; популярные и малоизвестные. Читайте, выбирайте, устанавливайте..."...
19 04 2024 1:44:53
Larian Studios ваяла Divine Divinity долго. Очень долго. Шесть лет работы, четыре смены названия (увольте: перечислять не буду), неоднократное перенесение сроков релиза — обычно игры после такого не выживают...
18 04 2024 6:10:27
Quake III Arena www.planetquake.com/syn Мрачное недалекое будущее, классический киберпанк, глобализация, власть мегакорпораций, каждый второй житель земли носит в себе хитрую электронную начинку... Модификация по мотивам древнего стратегического…|Игромания...
17 04 2024 8:14:31
Представьте себе экшен с карандашами: вместо того чтобы угнать машину, герой рисует каркас, колеса, дымок из выхлопной трубы и уносится вдаль на этом эксклюзивном концепт-каре. Или, например, RTS: побеждает тот, кто перед главным сражением успеет нарисова...
16 04 2024 3:59:13
Спешим представить вашему вниманию нашу постоянно обновляемую и дополняемую сводную таблицу отечественных локализаций. Как вы не могли не заметить, она претерпела некоторые изменения в пользу большего удобства. Отныне и вовеки веков таблица будет разде...
15 04 2024 11:33:26
главная любовь Blue Castle Games — бензопилы. Их здесь употрeбляют как в чистом виде, так и в коктейлях. Вот, например, длинное весло, к каждому концу которого примотано по пиле. Главный герой — байкер по имени Чак Грин —...
14 04 2024 16:21:54
Что отличает проект-однодневку от игры, к которой хочется возвращаться снова и снова? Это не только вопрос качества. «Нормальные» релизы — вполне соответствующие ожиданиям, но ничем особо не запоминающиеся, —…|Игромания...
13 04 2024 10:10:32
Производство фильмов по играм набирает обороты. Мы уже можем оценить свежие экранизации культовых Warcraft и Assassin’s Creed, а в будущем ждем Tomb Raider с Uncharted. Оттого возникает желание вспомнить тот период, когда большие боссы на…|Игромания...
12 04 2024 19:24:33
Wargaming.net выбирает новую цель Консоль крепка, гeймпады наши быстры [[BULLET]] Сводимся на консоли! Не так давно компания Wargaming.net приобрела за 40 миллионов долларов австралийского разработчика движка BigWorld. И вот теперь снова…|Игромания...
11 04 2024 11:25:22
Перед вами обновленный список отечественных локализаций и проектов.Данная таблица состоит из двух разделов, которые, в свою очередь, делятся на подразделы:1) ПОСТУПИЛИ В ПРОДАЖУ. Сюда помещаются все те игры, которые недавно поступили в продажу и которые...
10 04 2024 6:38:41
Iron Storm — 3D Action в антураже Первой мировой, которая... идет уже полвека. И более того — заканчиваться вовсе не собирается. Альтернативная история: русско-монгольские полчища во главе с бароном Югенбергом крушат...
09 04 2024 4:45:44
«…тут вообще ничего нет, кроме четверки героев и наполненного опасностями подземелья, в котором как-то нужно пытаться выживать. Но никакими словами не описать, сколько любви и старания вложено в каждый камешек, в каждого монстра, в каждую головоломку Lege...
08 04 2024 16:56:51
Безумная Мокси — Borderlands 2 Neo Geisha радует образом coблaзнительной Безумной Мокси. Между прочим, съёмку провели не в фотостудии, а в помещении квест-рума: в последние годы многие косплееры всё чаще используют подобные локации.…|Игромания...
07 04 2024 4:47:38
ДИСПЛЕЙ: 12,1’’ WXGA (1280x800), двойной сенсорный экран, реагирующий как на касание пальцем, так и на специальное перо (Wacom)ПЛАТФОРМА: AMD Puma / чипсет AMD M780GПРОЦЕССОР: двуядерный, AMD Turion X2 RM-70 (2,0 ГГц, 2x512 Мб L2)ОПЕРА...
06 04 2024 4:48:31
Представьте себе тактический симулятор, в который играют шестьдесят игроков на безразмерной карте от Delta Force и в небывало реалистичном окружении а-ля Operation Flashpoint — и вы поймете, на какие нехилые святыни соизволили замахнуться господа ра...
05 04 2024 23:47:45
главное тут — мелкие детали, которыми фильм забит под самую завязку — успевай подмечать. Вот одна из акул напевает себе под нос заглавную тему из спилберговских “Челюстей”. Вот Уилл Смит изображает MC Hammer’а. Вот Роберт Де Ниро говорит Мартину Скорцезе...
04 04 2024 1:19:46
«…LBP Karting стала апофеозом фрустрации разработчиков. Помимо названных проблем с подачей, игра разочаровывает неработающей гоночной механикой. Даже Crash Team Racing, вышедшая тринадцать лет назад, была лучше во всем — дизайне карт, физике и расстановке...
03 04 2024 2:51:58
...сделать глобальную космическую стратегию интуитивно понятной — это, если кто не знает, выдающееся гeймдизайнерское достижение. В Sword of the Stars дозволено придумывать корабли новых конфигураций, наперед задавать расписание их производства, фор...
02 04 2024 2:16:41
Главным достоинством своего творения авторы WorldShift называют простоту освоения, и с этим глупо спорить. Игра примитивна, как быт питекантропа: достаточно провести у экрана десять минут, чтобы понять — ни тактика, ни тем более стратегия здесь...
01 04 2024 4:41:15
18 Wheels of Steel: Convoy80 DaysAct of War ExpansionAct of War: Direct ActionAge of AngelsAge of Empire IIIAliens vs. Predator 2Alone in the DarkAlterLifeAmerican ChopperArmed AssaultBattlefield 2Black & White 2BloodRayneBrothers in Arms: Earned in B...
31 03 2024 2:19:45
Braid ступает на крайне опасную территорию: один неверный шаг, одна фальшивая нота — и все, ты уже за линией, где начинаются графомания и пошлость. Игра не только не делает этого шага, она идеально, безупречно выдерживает все испытания на прочн...
30 03 2024 23:51:38
Жанр: Дypaцкий русский хоррор Режиссер: Душан Глигоров Сценарий: Алексей Колмогоров, Аметхан Магомедов В главных ролях: Анастасия Пронина, Евгений Цыганов, Нина Русланова, Алексей Панин, Владимир Стеклов, Сергeй Чугин Бюджет: $10 млн К компьютерным…|Игромания...
29 03 2024 11:19:12
Этот материал — не о чемпионатах по Dota 2, League of Legends и Counter-Strike 1.6. Он о зарождении, постепенном развитии и затухании отечественного мувимейкинга. Но перед тем как приступить к повествованию, расшифруем сам термин.…|Игромания...
28 03 2024 0:38:24
...фактом своего появления Bullfrog обязана курьезу. В 1987 году Молиньё руководил скромной фирмой Taurus Impact Systems, разpaбатывавшей софт для бухгалтерского учета. Каково же было его удивление, когда ему позвонили не кто-нибудь, а представители Commo...
27 03 2024 2:22:28
Недавно Nvidia запустила на территории России облачный сервис GeForce Now, благодаря которому играть в свежие проекты «на максималках» можно даже со старого ноутбука. Пользователю нужны лишь доступ к высокоскоростному…|Игромания...
26 03 2024 3:24:41
Бывают все-таки и у ведущего рубрики мини-обзоров праздники. Такие вот, как игра R. I. P. от российской компании White Elephant, которая базируется в Йошкар-Оле. «Белые слоники» четко понимают, кто и зачем будет играть в их игры, а потому делают все,...
25 03 2024 11:44:48
«…Выходящий в России 20 июня «Человек из стали» — это перезапуск серии фильмов про Супермена, легендарного супергероя, знакомого даже тем, кто комиксов не читал ни разу в жизни. То, что этот фильм будет серьезнее всех предыдущих лент о Супермене, видно уж...
24 03 2024 19:50:20
"...Название, под которым "Бригада Е5" будет издаваться за рубежом — New Jagged Union — весьма символично. Действительно, поклонникам другого Jagged, который Alliance, игра от "Апейрона" явно придется по вкусу..."...
23 03 2024 17:12:43
...Кончилось ли время революций в MMORPG-играх? Обязателен ли многомиллионный бюджет для разработки хита? Имеют ли право на жизнь проекты с по-настоящему оригинальными идеями? Как создать онлайн-игру, не имея ничего, кроме идеи, свободного времени и неско...
22 03 2024 17:31:54
"...Elemental Games сумели создать единственную в своем роде лучшую российскую космическую походовую RPG, которую не стыдно поставить на пьедестал с такими грандами, как Elite, Star Control и Master of Orion..."...
21 03 2024 11:40:28
Два года назад вышла не идеальная, но уж точно запоминающаяся Tom Clancy’s Ghost Recon: Wildlands. Помимо привычного для песочниц Ubisoft букета проблем, публика не оценила то, что сюжета как такового в игре нет: Wildlands лишь…|Игромания...
20 03 2024 2:31:58
No One Lives Forever Редактор: DEdit.exe. Редактор входит как компонент в состав SDK — No One Lives Forever Editing Tools v1.0, появился в январе 2001 года.…|Игромания...
19 03 2024 6:54:49
Двадцатилетней выдержки переживание по имени Bionic Commando вышло очень ярким и запоминающимся. Интересные и бросающие вызов схватки с биомехами, возможность самому прокладывать дорогу на поверхностях любой наклонности (хоть и в определенной области на у...
18 03 2024 13:29:23
Харли Квинн — Injustice 2 Открывает последний «Косплей недели» этой зимы во всех смыслах зажигательная Харли Квинн из Injustice 2 в исполнении iChios. С такой подругой точно не замёрзнешь — главное только не…|Игромания...
17 03 2024 8:49:25
Во что играли 5 лет назад Planescape: Torment Дата выхода: 1999 год Жанр: RPG …|Игромания...
16 03 2024 10:14:37
«...задумана как первая RPG, где мы сможем полностью контролировать персонажа и все его движения. Значит ли это, что герой будет ползать по отвесным башням и сигать с них в сено, пугая окрестных девок, неизвестно. Подробностей на этот счет пока мало. Мы т...
15 03 2024 12:37:26
является не полноценным продолжением, а второй частью, пересобранной с поправкой на современные технологии. По сути, это тот же самый FlatOut 2, что два года назад поставил на уши всю нашу редакцию и на какое-то время даже стал любимой автогонкой Олега С...
14 03 2024 22:20:57
В рубрике «Прямым текстом» авторы выражают исключительно собственное мнение, которое может не совпадать с мнением редакции (а может и совпадать). Они вольны делать это как угодно и в любом удобном для себя формате. Здесь можно…|Игромания...
13 03 2024 16:15:42
До недавнего времени в этом сегменте рынка глобальных стратегий единолично правила “Europa Universalis” во всех видах. Отличная историческая стратегия не знала конкурентов. Но вот появилась игра, собравшаяся потеснить “Европу” на троне. Причем поня...
12 03 2024 6:35:18
ОБ ИГРЕ. Апокалиптическое безумие на фоне пейзажей средней полосы России. Хотя, если вдуматься, не такое уж безумие, а напротив, борьба за восстановление хоть какого-то подобия порядка. По обещаниям разработчи...
11 03 2024 7:15:59
Still Life 2 — определенно хорошая игра, которая, однако, не претендует ни на звание шедевра, ни на «Лучший квест года». Впечатления от сюжета и атмосферы, знакомой по фильмам «Пила» и «Хостел», несколько блекнут от абсурдности и скомканности последних ча...
10 03 2024 16:42:23
В основе > Адд-он к Hired Team Trial — русскому аналогу Quake, если кто не знает. Помнится, поводом для выпуска оригинального "Триала" было желание разработчиков заработать на непосредственно Hired Team (полноценный экшен) и з...
09 03 2024 3:47:23
Полгода назад вышел фанатский ролик, собранный из фрагментов первых трех частей Assassin’s Creed. Сделан он был настолько качественно, что Ubisoft разместили ссылку на него в своей официальной новостной ленте. Страшно представить, сколько сил…|Игромания...
08 03 2024 18:27:10
Еще:
Игры -1 :: Игры -2 :: Игры -3 :: Игры -4 :: Игры -5 :: Игры -6 :: Игры -7 :: Игры -8 :: Игры -9 :: Игры -10 :: Игры -11 :: Игры -12 :: Игры -13 :: Игры -14 :: Игры -15 :: Игры -16 :: Игры -17 :: Игры -18 :: Игры -19 :: Игры -20 :: Игры -21 :: Игры -22 :: Игры -23 :: Игры -24 :: Игры -25 :: Игры -26 :: Игры -27 :: Игры -28 :: Игры -29 :: Игры -30 :: Игры -31 :: Игры -32 :: Игры -33 :: Игры -34 :: Игры -35 :: Игры -36 :: Игры -37 :: Игры -38 :: Игры -39 :: Игры -40 :: Игры -41 :: Игры -42 :: Игры -43 :: Игры -44 :: Игры -45 :: Игры -46 :: Игры -47 :: Игры -48 :: Игры -49 :: Игры -50 :: Игры -51 :: Игры -52 :: Игры -53 :: Игры -54 ::
