Алгоритм поиска пути. Игровой конструктор, часть 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. Все эти вопросы мы обязательно затронем в одной из статей цикла.
От редакции «Игромании XP» Компания NIKITA.Online предложила нам опубликовать собственную статью, посвященную локализации недавно запущенной ролевки King of Kings 3. Материал показался нам интересным и познавательным. Так…|Игромания...
17 04 2024 8:22:49
TINCan! — наглядное подтверждение тому, что Phenomedia Publishing еще не растеряла свой творческий задор. Всего на сегодняшний день вышло две игры из этой серии. Про гоночную аркаду TINCan! Race мы рассказывали в прошлом номере, сегодня же...
16 04 2024 10:11:22
... Первый эксперимент — Баралгин стоит под мостом в миссии «Воспитание Федора», произносит: «Вернись, малыш! Я все прощу!», откуда-то из лесу выбегает Федор и... взрывается! Разлетается на кровавые ошметки, как будто на...
15 04 2024 22:24:41
Игры умеют говорить о серьёзных чувствах ничуть не хуже кино или книг. А порой делают это даже лучше, ведь такого погружения не даст ни один фильм или бумажный роман. Правда, разработчики не всегда об этом помнят и часто используют любовь и романтику…|Игромания...
14 04 2024 4:17:45
Спасти человека не так уж и сложно! Деловому подходу немецких разработчиков можно только позавидовать. Обычно берется игра №N, в которую добавляется 4-5 новых бойцов (в данном случае — кораблей), новый тип ландшафта, 2...
13 04 2024 8:11:50
«…Традиционные обещания (новые квесты, предметы, враги и локации, включая джунгли и горы с вулканической активностью) авторы разбавили парой сюрпризов. Например, появится возможность импортировать в дополнение своего героя из оригинала и — внимание — впер...
12 04 2024 18:47:17
На родине грузовиков и тягачей "Урал" кипит работа. Комaнда SDS работает над потенциальным хитом. Anti-Terror — это не просто "еще один Counter-Strike". Уже сейчас он представляется вполне самостоятельной игрой с разноплановым гeймплеем и обилием интересн...
11 04 2024 20:10:46
О номинации В прошлом году в номинации лучшего саундтрека года мы решили отойти от привычного формата топа с распределением мест и просто перечислить сразу всё, что запало в душу. Идея оказалась здравой: в редакционном чате стало одним…|Игромания...
10 04 2024 10:22:11
7,62 9-я рота A Vampyre Story Age of Conan: Hyborian Adventures Age of Empires Age of Mythology Aion: The Tower of Eternity Alan Wake Alone in the Dark American McGee’s Alice Anarchy Online Anno 1404 Arсania:...
09 04 2024 9:33:47
Чудо-женщина — DC Comics Москвичка Кэприсия Луккезе решительно открывает наш новый выпуск косплея с кинематографическим обликом принцессы амaзoнок Дианы, которую широкая публика больше знает под ее героическим псевдонимом…|Игромания...
08 04 2024 23:34:12
World of Darkness — отличная ролевая вселенная с богатой историей. Вот только в формате видеоигр дела у «Мира Тьмы» обстоят как-то не очень. Кроме неплохой Vampire: The Masquerade — Redemption и бесcмepтной…|Игромания...
07 04 2024 10:21:48
Предупреждение: Все игры выбирались внутриредакционным голосованием. Если вашего любимого проекта в списке нет, это не означает, что мы про него забыли, — ему просто не хватило голосов. Beyond Good & Evil Крышесносный коктейль…|Игромания...
06 04 2024 22:44:43
Компания "Бука" наконец-то получила долгожданную возможность издать гениальнейшую игру современности у нас на родине. "Самая революционная игра 2001 года", "Лучшая тактическая игра 2001 года" и, наконец, "Лучшая игра 2001 года" по версии "Игромании" занял...
05 04 2024 8:55:15
...ничего общего с советскими футбольными симуляторами «Гооол!» не имеет. В скромной коробке нет ни фигурок, ни мяча, зато много картонных карточек, жетонов и фишек, а также пара игральных кубиков. Ну и, конечно, правила......
04 04 2024 20:35:24
«…Действие Ghosts разворачивается в недалеком будущем. В самом начале мы станем свидетелями катастрофы, которая поставит США на колени, уничтожит ее статус сверхдержавы и ввергнет в хаос бесконечной войны…»...
03 04 2024 20:43:34
«Оно» 2017 года стал не только самым кассовым ужастиком за всю историю, но и настоящим поп-культурным феноменом. Картина дала старт карьерам сразу нескольких юных актёров, породила волну подражателей и вернула моду на экранизации…|Игромания...
02 04 2024 14:40:29
«…На деле BlackWidow Ultimate показала себя отлично — поиграв на ней несколько часов, уже не хочется использовать другую клавиатуру: прорезиненный пластик и механические свитчеры Cherry MX Blue создают невероятный эффект привыкания. Все дополнительные кла...
01 04 2024 19:33:53
Амбициозный миллиардер инсценирует свою cмepть, после чего собирает комaнду профессиональных вояк, готовых отказаться от своей прошлой жизни, чтобы нести добро и взрывы людям. Одной из первых целей комaнды — другие мы (не) увидим в сиквеле…|Игромания...
31 03 2024 8:44:48
Настоящий пластиковый скафандр, с правильной вентиляцией и толстой пуповиной, соединяющей бесприютного HDD-странника c материнским компьютером. Так называемый "external portable HDD kit" или, в нашей версии, "внешнее переносное Rack-устройство (Mobile Rac...
30 03 2024 11:56:26
Пять лет назад «Остаться в живых» и «Отчаянные домохозяйки» впервые со времен «Твин Пикса» и «Секретных материалов» вернули наш интерес к телеэфиру. Что произошло дальше — объяснять,…|Игромания...
29 03 2024 8:30:37
GTA в представлении не нуждается. Смелая разработка молодой английской комaнды Rockstar Games в далеком 1997 году перевернула с ног на голову всю игровую индустрию, ибо не было тогда в природе более дерзкого проекта, разом преступившего все мopaльные усто...
28 03 2024 7:45:31
...Начнем с концепции. Преследование в разных эпохах полоумных террористов, которые удумали изменить ход времени, — это, безусловно, внушает. Не очень, правда, понятно: речь идет о здоровом абсурдном юморе или о серьезной исторической теории?.....
27 03 2024 8:55:31
Image Sculpturer (для создания 3D-объектов на базе двумерных артов)TDU mesh import 3D Studio MAX script (TDU Mesh extractor)OGF to SMD with ANIMATION EXPORT 1.1Wood Workshop (для создания текстур дерева)RePlug (модули для NWN 2 Obsidian 2 Toolset, переком...
26 03 2024 22:16:27
Воздушный ноутбук Тестирование ноутбука HP ENVY 17 Leap Motion Технические хаpaктеристики Дисплей: 17 дюймов, TN, 1920х1080, сенсорный Процессор: Intel Core i7-4702MQ (4 ядра, 2,2-3,2 ГГц) Память: 8 ГБ DDR3-1333 МГц Видеокарта:: Intel HD Graphics…|Игромания...
25 03 2024 4:50:55
«...на момент сдачи этого номера достать игру для РС в России легальным путем было пpaктически невозможно. Даже с третьей частью в этом плане были проблемы — хотя официально игра издавалась на всех платформах, РС-версия, кажется, существовала только в пре...
24 03 2024 19:56:54
«…Разработчики не скрывают, что некоторые механики игра заимствует из еще одной тактической стратегии — XCOM. По замыслу Double Fine глобальная карта будет чем-то напоминать Panic Room: демоны постепенно захватывают территории, регионы покрываются скверно...
23 03 2024 18:38:10
Честно говоря, даже не верится, что в наши дни могут выходить подобные игры — чистейшей воды аркады с ураганным гeймплеем неземной интересности. Хотя на самом деле в таком положении дел мы сами виноваты, ибо постоянно просим у разработчиков реализма,...
22 03 2024 18:21:49
герои весьма серьезно отличаются “национальными особенностями”, а юниты вместо трех обрели аж целых пять карьерных уровней — “деды” в местной армии носят звания “чемпионов”...
21 03 2024 19:22:19
В феврале этого года немецкая студия Deck13 Interactive анонсировала The Surge 2 — сиквел футуристического экшена в духе Dark Souls. Оригинальная игра рассказывала о катастрофе, поставившей всё живое на грань вымирания. Напомним, что после…|Игромания...
20 03 2024 10:14:29
НОВОСТИ РОЛЕВЫХ ИГР Новинки от White Wolf Games Компания White Wolf Games, известная по своим ролевым играм в жанре современных ужасов — "Вампиры: М...
19 03 2024 2:27:19
В то время как Ubisoft вынашивает планы того, как бы откусить от рынка аркадных гонок кусок побольше, Electronic Arts — хозяин этого самого рынка — тоже не стоит на месте, а вовсю клепает очередное продолжение своей стрит-рейсерской саги...
18 03 2024 21:22:28
Игромания уже делилась первыми впечатлениями от DOOM Eternal с выставки Е3. Тогда проект показался Родиону Ильину крайне забористым шутером без особых претензий на серьёзный сюжет, но зато с дико динамичным и брутальным экшеном. В этот раз id…|Игромания...
17 03 2024 18:57:17
Сделать темные коридоры и раздолбанные лаборатории — невелика наука, а вот сделать так, чтобы темные коридоры и раздолбанные лаборатории (растиражированные в сотнях фильмов, включая близкий по духу Resident Evil) напоминали об игре, — задача куда более сл...
16 03 2024 16:21:49
Тридцать семь лет назад на экраны вышла культовая «Первая кровь» — очень смелая для своего времени смесь боевика и социальной драмы. Благодаря тому, что у сценария была крепкая литературная основа, главный герой Джон…|Игромания...
15 03 2024 3:23:35
наши дни, Российская Федерация, остров Скира, на котором, по предварительным подсчетам, полезных ископаемых больше, чем на всем Ближнем Востоке. Сотни лет назад он принадлежал Китаю, потом перешел к Японии, а после Второй мировой — СССР. Подогр...
14 03 2024 13:26:39
«…мультфильм впервые позволяет взглянуть на империю Орлей — самое могущественное государство Dragon Age, о котором столько рассказывали в играх. Увы, красот великого царства в Dragon Age: Dawn of the Seeker так и не показали. На протяжении большей части м...
13 03 2024 15:37:46
Идея создать такую игру не могла прийти в голову обычным разработчикам, планирующим шестой по счету сиквел к восьмому аддону третьей части. Редко кто способен на такую тонкую издeвку над Marvel, Dark Horse Comics и другими правообладате...
12 03 2024 2:22:50
Как определить создателей лучших боссов в истории видеоигр? Для каждого ведь критерии «лучшего» могут быть разными. Кто-то уверен, что к битве с настоящим боссом надо готовиться часами, накапливая силы и патроны, для кого-то…|Игромания...
11 03 2024 6:26:59
Все самое важное и интересное о E3 2016 По прошлой E3 сложилось впечатление, что Sea of Thieves будет масштабной MMO про пиратов, а Rare вплотную занимаются тем, о чем всегда мечтал российский гeймдев, но сделали (ненароком) почему-то Ubisoft в…|Игромания...
10 03 2024 15:55:48
Когда мы слышим слово Dell в сочетании с «игровыми ноутбуками», у нас появляются две ассоциации. Первая — это самые доступные предложения на рынке (Dell G3 и G5). Вторая — Alienware, серия мощных моделей с…|Игромания...
09 03 2024 14:33:44
«…Вот пример грубой работы. Пятеро вооруженных преступников вынесли двадцать тысяч из банка. Дальше по плану должен был прогреметь взрыв в квартале от места ограбления, но взрывчатка не сработала — самодельную бомбу обнаружил и обезвредил местный житель....
08 03 2024 20:40:59
О номинации: вот вы, вот еще какие-то люди. И вы вынуждены проходить игру вместе таким образом, чтобы никто из вас не успел ничего испортить. В общих чертах именно так работают кооперативные игры. Broforce все надежды на плодотворное…|Игромания...
07 03 2024 9:20:32
«…Да, мы получим более просторные локации и, конечно, окажемся в знаменитых готических антуражах, но гигантской песочницы ждать не стоит. Arkham City предложит знакомый, камерный open-world. Разработчики собираются представить «самый детализированный горо...
06 03 2024 16:25:11
в первые пять минут Stormrise похож на все экшены разом: между разрушенными небоскребами вышагивают огромные жуки-навозники в пол-экрана ростом; у них под ногами мелькают танки и солдаты; гаубицы на реактивной тяге забрасывают жуков двухметровыми paкетами...
05 03 2024 23:32:28
DmC: Devil May Cry 2013 года — перезапуск «классической» серии Devil May Cry от сторонних разработчиков Ninja Theory — собрала ну очень противоречивые отзывы. Фанаты классики бранили её на чём свет стоит: и…|Игромания...
04 03 2024 18:14:45
Последние десять месяцев выдались как никогда удачными для виртуальных крикетистов. Любители ударить по мячу плоской битой получили аж три игры: в ноябре — Cricket 07, в марте — Brian Lara International Cricket 2007, а теперь вот и менеджер International...
03 03 2024 3:30:20
класса «пират» как такового в игре нет: черным корсаром может стать любой. Надо только некоторое время вести себя как очень плохой парень: нападать на беззащитные суда и заpaбатывать дурную славу. Когда ее наберется достаточно, вы сможете прис...
02 03 2024 16:51:46
«…Каждый год в начале лета в тайваньском Тайбэе проходит вторая по величине международная IT-выставка — Computex. 1720 компаний, 4860 выставочных стендов и более 120 тысяч посетителей — вот что такое Computex сегодня. Сюда привозят все самые интересные эл...
01 03 2024 22:55:17
Как вам, скажем, возможность засекать передвижения противника в джунглях по раскачивающейся растительности? Более того, некоторые вьетконговцы будут всячески пытаться заманить вас в одну из ловушек и даже жертвовать собственной жизнью...
29 02 2024 11:22:42
С Большим адронным коллайдером в главной роли, в непременных постапокалиптических декорациях и с автомобильными гонками на руинах главной научной стройки XXI века. Armageddon Riders c легкостью можно принять за не самую оригинальную злободневную шутку, но...
28 02 2024 14:33:41
Еще:
Игры -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 ::
