|
Название: Алгоритм решения уровней для игры Sokoban Отправлено: Miriel от Октябрь 05, 2005, 11:30 Игрушка Sokoban - это довольно известная игра...там есть лабиринт и нужно передвинуть ящики с начальных позиций на заданные конечные позиции...двигать можно только вперед и только 1 ящик...
Фактически есть задача, как создать новый уровень пользователю : для этого либо нужно - как-то пробовать решить уровень - либо от обратного, т.е. когда все ящики стоят на своих местах делать движение по рандому чтоли...но только рандом плохо работает В инете есть редакторы, которые решают уровни (не все)...но вот алгоритма описывающего как они это делают я не нашел :( [/i] Название: Алгоритм решения уровней для игры Sokoban Отправлено: D_K от Октябрь 05, 2005, 18:46 Intelligent sokoban (http://cs.joensuu.fi/pages/mozgovoy/homepage/projects/windows/isokoban.rar).
Название: Алгоритм решения уровней для игры Sokoban Отправлено: Miriel от Октябрь 06, 2005, 09:31 Цитата: "D_K" Intelligent sokoban (http://cs.joensuu.fi/pages/mozgovoy/homepage/projects/windows/isokoban.rar). Там плохой алгоритм для решения...решает очень плохо уровни и только примитивные : пример : xxxxx x xxxxx x x x x x b b x xffxbxbxx xfsb x xff xxx xxxxxx ('a point' by takaken) нифига ета прога не решит (памяти не хватает или переполняется чего-нить) Вот есть лучше : http://prdownloads.sourceforge.net/jsokoapplet/JSokoApplet_1.06.zip?download Зато ето без исходников :( В принципе solver может быть и не нужен...нужно как-нить просто и качественно делать уровни (автоматически или/и полуавтоматически), ну или solver для уровней Название: Алгоритм решения уровней для игры Sokoban Отправлено: D_K от Октябрь 06, 2005, 22:53 Алгоритм - A*, IDA*. Вообщем, копать в сторону AI :)
Название: Алгоритм решения уровней для игры Sokoban Отправлено: Miriel от Октябрь 07, 2005, 07:21 Вот это мне и не нравится ИИ...придется думать
2 алгоритма 1 - фактич. поиск в ширину 2 - A* :roll: Название: Алгоритм решения уровней для игры Sokoban Отправлено: D_K от Октябрь 07, 2005, 17:33 Сама задача, на мой (и не только) взгляд представляется очень нетривиальной. Методики с эвристиками, похоже, очень грубы: далеко не всегда эвристика, например, на минимальное число перемещений может оптимально (или в принципе) решить предложенный уровень. Но: другой способ сейчас не изобретён (насколько мне известно состояние дел). Если вам удастся - попробуйте сообщить в комитет по нобелевским премиям (только Вам понадобится как-то интегрировать эту идею с идеями экономики или, возможно, медицины) :)
А на данный момент эти простые рычаги (вроде эвристик и A*) дают возможность решать хотя бы некоторые уровни (пусть и не идеально). Название: Алгоритм решения уровней для игры Sokoban Отправлено: Miriel от Октябрь 17, 2005, 11:32 Цитата: "D_K" Intelligent sokoban (http://cs.joensuu.fi/pages/mozgovoy/homepage/projects/windows/isokoban.rar). Спасибо это очень помогло...сделать хоть что-то работающее :) Название: Алгоритм решения уровней для игры Sokoban Отправлено: D_K от Октябрь 17, 2005, 12:09 Пожалуйста. Успехов!
|