Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
В демке на HaxeFlixel если не трогать аттрактор, ограничить область справа и сделать выход из неё в 1 точку по правому краю, то сикеры будут выходить за карту и не возвращаться. :)
«Тепловые карты»? Алгоритм Ли
Ваша правда, добавил правку в статью. Проблема ещё в том, что этот метод описывается сильно разными терминами в разных источниках. На «Алгоритм Ли» я не наткнулся, пока рылся по англоязычным туториалам, связанным с геймдевом, но видел «Heat maps», «Dijkstra maps», «Distance maps», «Wavefront algorithm» и, кажется, «Weighted map».
На геймдевовских русскоязычных сайтах я его чаще всего встречал под названием «Волновой алгоритм».
Волновой алгоритм (я бы сказал просто поиск в ширину), это способ расчета этой самой тепловой карты. Фишка тепловой карты, насколько я понял, в том что она одна считается для целей, а не для тех, кто строит путь. На каждого зомби пускать волну и рассчитывать путь ресурсов не напасёшься, вот тогда мы и переворачиваем ситуацию. Очень элегантно!
Ну потому то это не совсем волновой алгоритм.
Алгоритм Мура-Ли узкоспециализированный и ищет только кратчайший путь на планарном графе. Во время работы этого алгоритму каждой ячейке на карте присваивается стоимость движения из точки А с учетом возможных весов перехода из ячейки в ячейку (в простейшем случае это 1), после чего из точки В (куда нужно придти) восстанавливаем путь последовательно выбирая ячейки с наименьшим весом. Ну да, похоже, но только пока аттрактор один.
Здесь же описан частный случай метода потенциальных полей (Potential Field Method) — при наличии одного аттрактора на графе в контексте поиска пути от А (стартовой позиции агента) до В (положения аттрактора), собственно и получаем этот совсем частный случай — алгоритм Мура-Ли.
Если же аттракторов несколько, если пристувуют еще и силы отталкивания, и если все эти силы будут еще и разные, то тогда агент будет двигаться по градиенту (ну или против градиента как в данном случае), пока не свалиться в локальный минимум, который не всегда находится там же где и целевая точка В (в отличии от волнового алгоритма, где путь находится всегда). Ну и метод потенциальных полей применим не только к решетчатым моделям, а к любым http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.9504&rep=rep1&type=pdf
Алгоритм Мура-Ли узкоспециализированный и ищет только кратчайший путь на планарном графе. Во время работы этого алгоритму каждой ячейке на карте присваивается стоимость движения из точки А с учетом возможных весов перехода из ячейки в ячейку (в простейшем случае это 1), после чего из точки В (куда нужно придти) восстанавливаем путь последовательно выбирая ячейки с наименьшим весом. Ну да, похоже, но только пока аттрактор один.
Здесь же описан частный случай метода потенциальных полей (Potential Field Method) — при наличии одного аттрактора на графе в контексте поиска пути от А (стартовой позиции агента) до В (положения аттрактора), собственно и получаем этот совсем частный случай — алгоритм Мура-Ли.
Если же аттракторов несколько, если пристувуют еще и силы отталкивания, и если все эти силы будут еще и разные, то тогда агент будет двигаться по градиенту (ну или против градиента как в данном случае), пока не свалиться в локальный минимум, который не всегда находится там же где и целевая точка В (в отличии от волнового алгоритма, где путь находится всегда). Ну и метод потенциальных полей применим не только к решетчатым моделям, а к любым http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.9504&rep=rep1&type=pdf
Год назад была неплохая статья по теме: https://habrahabr.ru/post/262181/ (у вас упоминается оригинал, здесь перевод)
Круто, спасибо! Одна из тех тем, что будучи прочитанными кажутся элементарными и интуитивными. Словно и это и раньше знал. Хотя не знал. :) У себя в игре я ничего подобного и не додумался применить, хотя мог бы и испытываю местами проблемы с производительностью.
По поводу видимости игрока для монстра:
— Это элементарно. Сравниваете расстояние (полученое алгоритмом поиска пути) от монстра до игрока с учетом препятствий и без. Если расстояния равны, то монстр видит игрока
— Это элементарно. Сравниваете расстояние (полученое алгоритмом поиска пути) от монстра до игрока с учетом препятствий и без. Если расстояния равны, то монстр видит игрока
Это не совсем верно. Представьте себе карту где можно ходить только по горизонтали и вертикали, непроходимый квадрат на этой карте и монстра с игроком на противоположных углах квадрата. Как то так:
e___
_##_
_##_
___p
Расстояние между ними кратчайшее, а видимости нет.
Предложенный вами метод работает скорей всего только для плоской карты и расстояния определяемого по теореме Пифагора.
e___
_##_
_##_
___p
Расстояние между ними кратчайшее, а видимости нет.
Предложенный вами метод работает скорей всего только для плоской карты и расстояния определяемого по теореме Пифагора.
Кратчайшее расстояние — диагональ, пройти можно только по сторонам. Расстояния не равны — не видят. Вроде работает.
В вашем примере кратчайшее расстояние с учетом препятствий равно 6, кратчайшее расстояние без учета препятствий равно 3. Расстояния не равны — монстр не видит игрока.
Прежде, чем писать критические комментарии, научитесь внимательно читать и думать головой.
Прежде, чем писать критические комментарии, научитесь внимательно читать и думать головой.
Я пронял вашу логику — вы исключаете движение по диагонали.
В этом случае задача бессмыслена, т.к. не имеет решения. Любое расположение препятствия можно считать как «монстр видит игрока» и «монстр не видит игрока».
Даже вот такой пример можно расценивать двояко:
е_
#р
Поэтому ваша задача (с исключением движения по диагонали) изначально абсурда. Так что — думайте головой
В этом случае задача бессмыслена, т.к. не имеет решения. Любое расположение препятствия можно считать как «монстр видит игрока» и «монстр не видит игрока».
Даже вот такой пример можно расценивать двояко:
е_
#р
Поэтому ваша задача (с исключением движения по диагонали) изначально абсурда. Так что — думайте головой
Впредь я буду стараться думать головой!
Рассмотрите следующий пример допуская движения по диагонали:
e_________
__________
_________p
Пример вообще без препятствий. Расстояние между игроком и монстром по прямой короче любого адекватного пути между ними по дискретным клеткам по этому монстр не будет видеть игрока по вашему алгоритму.
В случае же если местность непредставима в виде дискретного графа, то к такой задаче рассматриваемый в статье класс алгоритмов не применим вообще.
Рассмотрите следующий пример допуская движения по диагонали:
e_________
__________
_________p
Пример вообще без препятствий. Расстояние между игроком и монстром по прямой короче любого адекватного пути между ними по дискретным клеткам по этому монстр не будет видеть игрока по вашему алгоритму.
В случае же если местность непредставима в виде дискретного графа, то к такой задаче рассматриваемый в статье класс алгоритмов не применим вообще.
Вы не совсем поняли суть идеи. Брать нужно не прямой отрезок от сикера до аттрактора, а путь, полученный поиском, не учитывающим препятствия.
То есть прогоняется алгоритм два раза: 1) обычный поиск пути, 2) тот же самый поиск пути, только с отключенными препятствиями.
И сравниваются уже их длины.
Если длины одинаковые — препятствия нет, сикеру чтобы достичь аттрактор нужен прямой путь.
Если разница есть — значит сикер должен будет что-то обойти, прежде чем достигнет аттрактора, и значит, что он его не видит.
То есть прогоняется алгоритм два раза: 1) обычный поиск пути, 2) тот же самый поиск пути, только с отключенными препятствиями.
И сравниваются уже их длины.
Если длины одинаковые — препятствия нет, сикеру чтобы достичь аттрактор нужен прямой путь.
Если разница есть — значит сикер должен будет что-то обойти, прежде чем достигнет аттрактора, и значит, что он его не видит.
Может оказаться неоднозначно, если имеется несколько оптимальных путей. Например, вот так:
Существует два оптимальных пути, один из которых проходит через препятствие, другой не проходит. Заслоняет ли стена А от В? Хороший вопрос. Некоторые имплементации линии зрения (кажется, даже классический Брезенхэм) превращают стену в полупрозрачную, то есть А видит B, но не наоборот; если считать, что стена в сечении квадратная со стороной в тайл, то линия из центра A в центр B её пересекает и должна заслонять.
A . . . .
. . . . .
. . # . .
. . . . B
Существует два оптимальных пути, один из которых проходит через препятствие, другой не проходит. Заслоняет ли стена А от В? Хороший вопрос. Некоторые имплементации линии зрения (кажется, даже классический Брезенхэм) превращают стену в полупрозрачную, то есть А видит B, но не наоборот; если считать, что стена в сечении квадратная со стороной в тайл, то линия из центра A в центр B её пересекает и должна заслонять.
Да, контрпример для этой идеи я описал в своем первом комментарии:
e___
_##_
_##_
___p
А предыдущий написал в ответ на предположение что надо сравнивать с прямым расстоянием.
Вообщем если видимость считается не по тем же правилам по которым можно передвигаться, то все весьма нетривиально.
e___
_##_
_##_
___p
А предыдущий написал в ответ на предположение что надо сравнивать с прямым расстоянием.
Вообщем если видимость считается не по тем же правилам по которым можно передвигаться, то все весьма нетривиально.
Может, я скажу полнейшую глупость, но нельзя ли в таком случае иметь две тепловые карты — передвижения и видимости? Карта передвижения строится с учётом только вертикальных и горизонтальных передвижений, а видимости — уже с учётом диагональных ходов. Тогда по карте видимости можно будет определить, видит ли монстр игрока, а передвигаться будет уже по другой карте.
По-моему, это даже не слишком похоже на костыль, потому что и в реальной жизни мы можем видеть что-то, но не иметь возможности добраться до этого объекта по прямой.
В этом случае можно будет использовать «прозрачные» препятствия (окна, ловушки, заборы), сквозь которые монстр может увидеть игрока, но будет вынужден преследовать его по другому пути.
По-моему, это даже не слишком похоже на костыль, потому что и в реальной жизни мы можем видеть что-то, но не иметь возможности добраться до этого объекта по прямой.
В этом случае можно будет использовать «прозрачные» препятствия (окна, ловушки, заборы), сквозь которые монстр может увидеть игрока, но будет вынужден преследовать его по другому пути.
Я уверен, что ваша идея будет работать корректно.
Сложность тут заключается в том, что все рассматриваемые в статье и в коментариях классы алгоритмов основаны на том, что движение транзитивно, тоесть если из А можно попасть в B, а из B в C, то из А можно попасть в C. К сожалению это не верно для видимости по прямой. По этому для построения карт видимости придется применять принципиально более сложные алгоритмы из области геометрии.
Сложность тут заключается в том, что все рассматриваемые в статье и в коментариях классы алгоритмов основаны на том, что движение транзитивно, тоесть если из А можно попасть в B, а из B в C, то из А можно попасть в C. К сожалению это не верно для видимости по прямой. По этому для построения карт видимости придется применять принципиально более сложные алгоритмы из области геометрии.
Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые.
А как вам вариант, если зомби будет запоминать тепловую карту и обновлять её, только заметив игрока? Тогда он прибежит в ту точку где последний раз видел игрока, помоему довольно честно
А почему видимость монстрами игрока не проверять по той же тепловой карте по треш-холду? Причем треш-холд и по прямому расстоянию и по расстоянию траектории доступности. То есть, просто не прибавляем аттрактор к весу рассматриваемого направления, если его значение в рассматриваемой ячейке меньше порогового.
Первое достоинство такого метода очевидно: он быстрый
Насколько я понимаю, это частный случай поиска в ширину, самого ресурсоемкого и затратного метода поиска пути.
В случае одного монстра и одной цели — да, тот же A* был бы быстрее. Но на практике одно построение карты и два десятка обращений к ней получаются быстрее, чем гонять по полноценному A* для каждого противника.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
AI монстров и поиск пути с помощью тепловых карт