|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
15.10.2010, 11:47 | #1 |
Форумчанин
Регистрация: 16.08.2008
Сообщений: 276
|
Автоматическая генерация лабиринтов
Доброго времени суток уважаемые эксперты. Натолкнулся на такую проблему:
Пишу n+1 аналог PacMan. Но столкнулся с проблемой генерации лабиринтов. Дело в том, что достопочтенный гугл находит мне варианты генерации лабиринтов, но они очень сложные и запутанные для PacMan. Все исходники, которые я находил юзают заранее созданные уровни (а это не тру). Может кто уже делал нечто подобное, или знает как такое осуществить? Поделитесь опытом. Заранее спасибо
Искусственный интеллект - фигня по сравнению с естественной глупостью
|
15.10.2010, 12:59 | #2 |
Linux C++ Qt ARM
Старожил
Регистрация: 30.11.2008
Сообщений: 3,030
|
есть пара мыслей.
Мысль первая: Делаем "пустой" лабиринт (т.е. без стен) Запоминаем все возможные варианты прохода лабиринта (пустого). Затем определимяся, сколько вариантов проходов лабиринта нам нужно. Постепенно ставим стенки (при этом задаем минимальное кол-во стенок, которое нас интересует) (с помощью ГСЧ). Сгенерировав координаты новой стенки мы ее НЕ ставим, если: а)Стенок уже больше, чем надо (лабиринт уже готов) б)Стенка перегораживает один из маршрутов, в следствии чего число маршрутов становится меньше заданого минимального кол-ва маршрутов прохождения. Если условия "а" или "б" не выполнены, то стенку можно ставить сюда (в сгенерированые координаты) Вариант 2: (ИМХО, более экономичен в плане вычислений и памяти) Разбиваем лабиринт на отдельные зоны. (прямоугольники или квадраты) Генерируем путь из зоны(т.е. ровно столько, сколько вам нужно, т.е. минимум 1) (или пути, если хочется несколько), в которой вход к зоне, в которой выход. Т.е. Фактически мы получим что-то типа графа. А графе это можно представить так(для наглядности) - каждая зона - вершина, проходы между зонами - ребра(дуги). Путь - маршрут из вершины со входом в вершину с выходом. Все, теперь берем у каждых зон отмечаем точки их состыковки с соседними зонами (точнее с теми, в которые/из которых мы можем пройти). Код:
В таком случае будет памяти надо меньше (если вы не переборщите с генерацией подзон вариантом 2) upd. Ой, сори.. не заметил, что это для пакмана. Тогда, как вриант, задать в лабиринте некоторые "узловые" точки (например 4 угла, в которых бонус для врагопоедания) + точки спауна (пакмана и врагов), которые будем соединять описанным мною (см. выше) способом.
Дилетант широкого профиля.
"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс Последний раз редактировалось ROD; 15.10.2010 в 13:07. |
15.10.2010, 13:21 | #3 |
Форумчанин
Регистрация: 16.08.2008
Сообщений: 276
|
Забавно. Мне нравится второй подход. Первый действительно уж очень неэкономичный, да и придется часто пересчитывать пути (а это чревато жесткими тормозами). А что если немного модифицировать Ваш вариант таким образом:
Допустим у Нас имеется какой-то набор стандартных стенок. 1. Разбиваем поле на квадраты (прямоугольники). 2. Переходим на свободный квадрат. Если свободных квадратов нет - алгоритм завершен 3. Проверяем есть ли свободное место для размещения хотя бы одной стенки. Если нет - переходим к пункту 2 4. Пытаемся поместить случайно выбранную стенку (разные типы стенок) с условием: 4.1. Стенка отстоит от соседних ровно на одну клетку 4.2. Если стенку разместить не удалось - переходим к пункту 2 По идее такой алгоритм должен сгенерировать множество областей, которые можно обойти по кругу. Минус в том, что надо делать довольно большое поле, что может быть чревато последствиями. Хотя наверное пункт 1 можно и опустить.
Искусственный интеллект - фигня по сравнению с естественной глупостью
|
15.10.2010, 14:07 | #4 | |
Linux C++ Qt ARM
Старожил
Регистрация: 30.11.2008
Сообщений: 3,030
|
Цитата:
Если так, то да, идея не плохая. (и, похоже, для пакмана она подходит даже больше, чем моя.). Если лабиринт не сильно большой, то резать на куски (как в моем "варианте 2") нет смысла.
Дилетант широкого профиля.
"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс Последний раз редактировалось ROD; 15.10.2010 в 14:09. |
|
15.10.2010, 20:10 | #5 | |
Форумчанин
Регистрация: 16.08.2008
Сообщений: 276
|
Цитата:
Значит решено. Буду пробовать делать такой лабиринт. Ну и тогда еще один небольшой вопросец. Не знаете откуда можно выдрать красивые спрайты привидений?
Искусственный интеллект - фигня по сравнению с естественной глупостью
|
|
15.10.2010, 21:25 | #6 |
Linux C++ Qt ARM
Старожил
Регистрация: 30.11.2008
Сообщений: 3,030
|
http://files.vector-images.com/cd_sa...t_cartoons.gif
http://a1.twimg.com/profile_images/2...art_bigger.png http://4.bp.blogspot.com/_w_bza2cj7x...s320/ghost.gif http://icons.mysitemyway.com/wp-cont...day-ghost1.png http://www.gg-go.com/parade/hallowee...ully-ghost.gif http://1.bp.blogspot.com/_-RlxQV-Vqe...s400/ghost.jpg http://sweetandsaucy.files.wordpress...cookie2452.jpg Гугл вам в помощь.
Дилетант широкого профиля.
"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс |
16.10.2010, 12:28 | #7 |
Форумчанин
Регистрация: 16.08.2008
Сообщений: 276
|
Спасибо за помощь
Искусственный интеллект - фигня по сравнению с естественной глупостью
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
автоматическая загрузка js в IE | world12_tk | JavaScript, Ajax | 3 | 03.06.2011 18:41 |
Автоматическая регистрация | stepennwolf | PHP | 2 | 21.08.2010 20:39 |
Автоматическая группировка | anester | Microsoft Office Excel | 0 | 08.06.2010 14:07 |
Автоматическая группировка | buk | Microsoft Office Excel | 5 | 20.09.2007 13:35 |
Автоматическая авторизация | Novice777 | Работа с сетью в Delphi | 2 | 01.03.2007 16:56 |