полный эребор, не круто
11.01.2015, 17:45
Очень похоже на - Марковский процесс принятия решений, это покруче чем A*.
Эту фигню проходят в магистратуре...
Эту фигню проходят в магистратуре...
Это обычный пиоск в глубину, а не алгоритм Ли.
Во-первых, алгоритм Ли основан на поиске в ширину, а на данной картинке при наполовину исследованном лабиринте в самом начале остаются неисследованные пути. При использовании алгоритма Ли так не бывает.
Во-вторых, можно просто внимательно присмотреться к картинке - там на развилке выбирается случайный путь, в случае тупика идёт возврат к последней развилке и выбирается другой путь. Это и называется поиск в глубину.
Во-вторых, можно просто внимательно присмотреться к картинке - там на развилке выбирается случайный путь, в случае тупика идёт возврат к последней развилке и выбирается другой путь. Это и называется поиск в глубину.
Такие штуки алгоритмически проще всего решаются графами, для которых ещё и алгоритмов тьма-тьмущая под любые цели. И кучу готовых реализаций этих алгоритмов на разных языках можно нагуглить.
Недавно вот тоже мучился с хитрожопым поиском по файлу с данными несколько дней. А теперь поиск в сведённом к графу файле и с использованием алгоритма Краскала занимает строчек 50 кода.
Недавно вот тоже мучился с хитрожопым поиском по файлу с данными несколько дней. А теперь поиск в сведённом к графу файле и с использованием алгоритма Краскала занимает строчек 50 кода.
Присмотрись он иногда делает пропускает левые повороты. Это реально поиск в глубину, но в случае развилки (вполне возможно) приоритет обхода определяется эвристикой (скорее всего) или случайно. Во всяком случае приоритет точно не фиксированный (если писать код по тупому обычно получается фиксированный, из-за последовательных условий: если можно вверх - идем вверх. если можно вправо - идем вправо и так далее). В одной из первых развилок он предпочитает шаг влево, шагу вниз, а в следующей уже наоборот, шаг вниз шагу влево.
wallhack
Да, но только для двухмерных лабиринтов, и в худшем случае придется пройти путь, в два раза превышающий длину всех коридоров лабиринта.
Чойто такое припоминаю. Помню целый час по одному лабиринту ходил во тьме и с минимумом монстров (они вродь быстро закончились а вот лабиринт нет) потом плюнул и удалил игру.
А уж если вспомнить лабиринты в майнкрафте то ваще ужос правда там всегда можно забить на подземелье и с помощью кирки пробить путь наверх.
А уж если вспомнить лабиринты в майнкрафте то ваще ужос правда там всегда можно забить на подземелье и с помощью кирки пробить путь наверх.
Тут же метод перебора. Идет до тупика и потом возвращается на развилку и так раз за разом.
В лоб - двойной волновой метод, не оптимально, но надёжно и быстрее этого перебора.
Где то там прячется Минотавр
если долго и пристально смотреть можно видеть разные узоры
я например вижу листву, морских звезд, человеческие уши, мозг, кресты
еще каких-то пауков, пальцы, горы-холмы, животных...
я например вижу листву, морских звезд, человеческие уши, мозг, кресты
еще каких-то пауков, пальцы, горы-холмы, животных...
У меня от этой пикчи видюха свистит. Спасибо, буду разбираться.
Капитан Очевидность поясняет, что заливаются не коридоры, а стены.
дюна на сега тупила как раз из-за таких вещей. можно было построить лабиринт и наблюдать, как падает фпс
Бле... я залип ):
я такие на уроке географии рисовал
