Поиск пути

Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками.

В играх

Поиск пути в контексте компьютерных игр касается пути, на котором движущийся объект ищет путь вокруг препятствий. Наиболее часто задача поиска пути возникает в стратегиях реального времени, в которых игрок даёт задание игровым юнитам (единицам) двигаться через игровой уровень, который содержит препятствия. Кроме стратегий, задача поиска пути, так или иначе, в той или иной мере встречается в большинстве современных игровых жанров. Так как игры становятся всё сложнее, то поиск пути также эволюционирует и развивается вместе с ними.

Стратегии реального времени обычно содержат большие территории с открытым ландшафтом, в которых поиск пути обычно является простой задачей. Однако в большинстве случаев по карте перемещается не один юнит, а несколько, что создаёт потребность в различных и намного более сложных алгоритмах поиска пути для избежания пробок в узких областях игрового ландшафта. В стратегиях игровой уровень делится на тайлы (англ. tiles), которые действуют как узлы (англ. nodes) в алгоритме поиска пути.

В жанре 3D-шутеров используются намного более ограниченные пространства, которые не так легко разделить на узлы. Здесь взамен узлов используются так называемые waypoints (англ. waypoints; дословно — рус. точки пути). Waypoints — это нерегулярные и вручную установленные узлы, которые содержат информацию о том, к каким другим узлам возможно добраться от данного.

Алгоритмы

По своей сути алгоритм поиска пути ищет на графе, начиная с одной (стартовой) точки и исследуя смежные узлы до тех пор, пока не будет достигнут узел назначения (конечный узел). Кроме того, в алгоритмы поиска пути в большинстве случаев заложена также цель найти самый короткий путь. Некоторые методы поиска на графе, такие как поиск в ширину, могут найти путь, если дано достаточно времени. Другие методы, которые «исследуют» граф, могут достичь точки назначения намного быстрее. Здесь можно привести аналогию с человеком, идущим через комнату. Человек может перед началом пути заранее исследовать все характеристики и препятствия в пространстве, вычислить оптимальный маршрут и только тогда начать непосредственное движение. В другом случае человек может сразу пойти в приблизительном или предполагаемом направлении цели и потом, уже во время пути, делать корректировки своего движения для избегания столкновений с препятствиями.

К самым известным и популярным алгоритмам поиска пути относятся такие алгоритмы:

• Алгоритм поиска A*
• Алгоритм Дейкстры
• Волновой алгоритм
• Маршрутные алгоритмы
• Навигационная сетка (Navmesh)
• Иерархические алгоритмы
• Обход препятствий
• Разделяй и властвуй
• Алгоритм поворота Креша

См. также

• Игровой искусственный интеллект

Внешние ссылки

Англоязычные

• Amit. [theory.stanford.edu/~amitp/GameProgramming/ Amit’s A* Pages] (англ.). theory.stanford.edu. Проверено 1 мая 2010. [www.webcitation.org/66fdZRVrC Архивировано из первоисточника 4 апреля 2012].
• [sourceforge.net/projects/argorha/ Argorha pathfinding] (англ.). SourceForge.net. Проверено 1 мая 2010. [www.webcitation.org/66fdcNUGn Архивировано из первоисточника 4 апреля 2012].
• PaulT. [www.ai-blog.net/archives/000152.html Fixing Pathfinding Once and For All] (англ.). www.ai-blog.net (26 июля 2008 года). Проверено 1 мая 2010. [www.webcitation.org/66fddNvU9 Архивировано из первоисточника 4 апреля 2012].

Русскоязычные

• Bryan Stout (оригинальная статья) Maxim Kamensky (перевод). [pmg.org.ru/ai/stout.htm Алгоритмы поиска пути]. pmg.org.ru (5 декабря 2000 года). Проверено 22 июля 2009. [www.webcitation.org/66fdejfBT Архивировано из первоисточника 4 апреля 2012].
• Patrick Lester (автор), Morpher (перевод). [www.policyalmanac.org/games/aStarTutorial_rus.htm Алгоритм A* для новичков]. policyalmanac.org (26 июля 2004 года). Проверено 1 мая 2010. [www.webcitation.org/66fdfaHVe Архивировано из первоисточника 4 апреля 2012].
• George Judkin. [www.delphikingdom.com/asp/viewitem.asp?catalogid=1127 Алгоритм поиска пути на карте] (англ.). Королевство Delphi (28 марта 2005 года). Проверено 22 июля 2009. [www.webcitation.org/66fdg4GA3 Архивировано из первоисточника 4 апреля 2012].
• John Christian Lonningdal (оригинальная статья) Анисимов С.Ю. (перевод). [www.iskint.ru/?xid=games-poisk_puti Поиск пути: описание волнового алгоритма и других]. www.iskint.ru (декабрь 1996 года). Проверено 22 июля 2009. [www.webcitation.org/66fdgxhSb Архивировано из первоисточника 4 апреля 2012].
• [www.iskint.ru/?xid=games-poisk_puti_src Поиск пути: исходные коды программ]. www.iskint.ru. Проверено 22 июля 2009. [www.webcitation.org/66fdi0d6r Архивировано из первоисточника 4 апреля 2012].
• Алексей Седов «onimod_land». [www.uraldev.ru/articles/id/2 Алгоритм построения пути в стратегической игре] 2. UralDev (7 сентября 2006 года). Проверено 3 апреля 2010. [www.webcitation.org/66fdj0MOI Архивировано из первоисточника 4 апреля 2012].

Отрывок, характеризующий Поиск пути

– Всё от воспитания зависит, – сказала гостья.
– Да, ваша правда, – продолжала графиня. – До сих пор я была, слава Богу, другом своих детей и пользуюсь полным их доверием, – говорила графиня, повторяя заблуждение многих родителей, полагающих, что у детей их нет тайн от них. – Я знаю, что я всегда буду первою confidente [поверенной] моих дочерей, и что Николенька, по своему пылкому характеру, ежели будет шалить (мальчику нельзя без этого), то всё не так, как эти петербургские господа.
– Да, славные, славные ребята, – подтвердил граф, всегда разрешавший запутанные для него вопросы тем, что всё находил славным. – Вот подите, захотел в гусары! Да вот что вы хотите, ma chere!
– Какое милое существо ваша меньшая, – сказала гостья. – Порох!
– Да, порох, – сказал граф. – В меня пошла! И какой голос: хоть и моя дочь, а я правду скажу, певица будет, Саломони другая. Мы взяли итальянца ее учить.
– Не рано ли? Говорят, вредно для голоса учиться в эту пору.
– О, нет, какой рано! – сказал граф. – Как же наши матери выходили в двенадцать тринадцать лет замуж?
– Уж она и теперь влюблена в Бориса! Какова? – сказала графиня, тихо улыбаясь, глядя на мать Бориса, и, видимо отвечая на мысль, всегда ее занимавшую, продолжала. – Ну, вот видите, держи я ее строго, запрещай я ей… Бог знает, что бы они делали потихоньку (графиня разумела: они целовались бы), а теперь я знаю каждое ее слово. Она сама вечером прибежит и всё мне расскажет. Может быть, я балую ее; но, право, это, кажется, лучше. Я старшую держала строго.
– Да, меня совсем иначе воспитывали, – сказала старшая, красивая графиня Вера, улыбаясь.
Но улыбка не украсила лица Веры, как это обыкновенно бывает; напротив, лицо ее стало неестественно и оттого неприятно.
Старшая, Вера, была хороша, была неглупа, училась прекрасно, была хорошо воспитана, голос у нее был приятный, то, что она сказала, было справедливо и уместно; но, странное дело, все, и гостья и графиня, оглянулись на нее, как будто удивились, зачем она это сказала, и почувствовали неловкость.
– Всегда с старшими детьми мудрят, хотят сделать что нибудь необыкновенное, – сказала гостья.
– Что греха таить, ma chere! Графинюшка мудрила с Верой, – сказал граф. – Ну, да что ж! всё таки славная вышла, – прибавил он, одобрительно подмигивая Вере.
Гостьи встали и уехали, обещаясь приехать к обеду.
– Что за манера! Уж сидели, сидели! – сказала графиня, проводя гостей.


Когда Наташа вышла из гостиной и побежала, она добежала только до цветочной. В этой комнате она остановилась, прислушиваясь к говору в гостиной и ожидая выхода Бориса. Она уже начинала приходить в нетерпение и, топнув ножкой, сбиралась было заплакать оттого, что он не сейчас шел, когда заслышались не тихие, не быстрые, приличные шаги молодого человека.
Наташа быстро бросилась между кадок цветов и спряталась.
Борис остановился посереди комнаты, оглянулся, смахнул рукой соринки с рукава мундира и подошел к зеркалу, рассматривая свое красивое лицо. Наташа, притихнув, выглядывала из своей засады, ожидая, что он будет делать. Он постоял несколько времени перед зеркалом, улыбнулся и пошел к выходной двери. Наташа хотела его окликнуть, но потом раздумала. «Пускай ищет», сказала она себе. Только что Борис вышел, как из другой двери вышла раскрасневшаяся Соня, сквозь слезы что то злобно шепчущая. Наташа удержалась от своего первого движения выбежать к ней и осталась в своей засаде, как под шапкой невидимкой, высматривая, что делалось на свете. Она испытывала особое новое наслаждение. Соня шептала что то и оглядывалась на дверь гостиной. Из двери вышел Николай.
– Соня! Что с тобой? Можно ли это? – сказал Николай, подбегая к ней.
– Ничего, ничего, оставьте меня! – Соня зарыдала.
– Нет, я знаю что.
– Ну знаете, и прекрасно, и подите к ней.
– Соооня! Одно слово! Можно ли так мучить меня и себя из за фантазии? – говорил Николай, взяв ее за руку.
Соня не вырывала у него руки и перестала плакать.
Наташа, не шевелясь и не дыша, блестящими главами смотрела из своей засады. «Что теперь будет»? думала она.
– Соня! Мне весь мир не нужен! Ты одна для меня всё, – говорил Николай. – Я докажу тебе.
– Я не люблю, когда ты так говоришь.
– Ну не буду, ну прости, Соня! – Он притянул ее к себе и поцеловал.
«Ах, как хорошо!» подумала Наташа, и когда Соня с Николаем вышли из комнаты, она пошла за ними и вызвала к себе Бориса.
– Борис, подите сюда, – сказала она с значительным и хитрым видом. – Мне нужно сказать вам одну вещь. Сюда, сюда, – сказала она и привела его в цветочную на то место между кадок, где она была спрятана. Борис, улыбаясь, шел за нею.
– Какая же это одна вещь ? – спросил он.
Она смутилась, оглянулась вокруг себя и, увидев брошенную на кадке свою куклу, взяла ее в руки.
– Поцелуйте куклу, – сказала она.
Борис внимательным, ласковым взглядом смотрел в ее оживленное лицо и ничего не отвечал.
– Не хотите? Ну, так подите сюда, – сказала она и глубже ушла в цветы и бросила куклу. – Ближе, ближе! – шептала она. Она поймала руками офицера за обшлага, и в покрасневшем лице ее видны были торжественность и страх.
– А меня хотите поцеловать? – прошептала она чуть слышно, исподлобья глядя на него, улыбаясь и чуть не плача от волненья.
Борис покраснел.
– Какая вы смешная! – проговорил он, нагибаясь к ней, еще более краснея, но ничего не предпринимая и выжидая.
Она вдруг вскочила на кадку, так что стала выше его, обняла его обеими руками, так что тонкие голые ручки согнулись выше его шеи и, откинув движением головы волосы назад, поцеловала его в самые губы.
Она проскользнула между горшками на другую сторону цветов и, опустив голову, остановилась.
– Наташа, – сказал он, – вы знаете, что я люблю вас, но…
– Вы влюблены в меня? – перебила его Наташа.
– Да, влюблен, но, пожалуйста, не будем делать того, что сейчас… Еще четыре года… Тогда я буду просить вашей руки.