Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > разработка игр, графический дизайн и моделирование > Gamedev - cоздание игр: Unity, OpenGL, DirectX
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.10.2010, 11:47   #1
Impuls1989
Форумчанин
 
Аватар для Impuls1989
 
Регистрация: 16.08.2008
Сообщений: 276
По умолчанию Автоматическая генерация лабиринтов

Доброго времени суток уважаемые эксперты. Натолкнулся на такую проблему:
Пишу n+1 аналог PacMan. Но столкнулся с проблемой генерации лабиринтов. Дело в том, что достопочтенный гугл находит мне варианты генерации лабиринтов, но они очень сложные и запутанные для PacMan. Все исходники, которые я находил юзают заранее созданные уровни (а это не тру). Может кто уже делал нечто подобное, или знает как такое осуществить? Поделитесь опытом.
Заранее спасибо
Искусственный интеллект - фигня по сравнению с естественной глупостью
Impuls1989 вне форума Ответить с цитированием
Старый 15.10.2010, 12:59   #2
ROD
Linux C++ Qt ARM
Старожил
 
Аватар для ROD
 
Регистрация: 30.11.2008
Сообщений: 3,030
По умолчанию

есть пара мыслей.

Мысль первая:

Делаем "пустой" лабиринт (т.е. без стен)
Запоминаем все возможные варианты прохода лабиринта (пустого).
Затем определимяся, сколько вариантов проходов лабиринта нам нужно.
Постепенно ставим стенки (при этом задаем минимальное кол-во стенок, которое нас интересует) (с помощью ГСЧ).
Сгенерировав координаты новой стенки мы ее НЕ ставим, если:
а)Стенок уже больше, чем надо (лабиринт уже готов)
б)Стенка перегораживает один из маршрутов, в следствии чего число маршрутов становится меньше заданого минимального кол-ва маршрутов прохождения.
Если условия "а" или "б" не выполнены, то стенку можно ставить сюда (в сгенерированые координаты)

Вариант 2: (ИМХО, более экономичен в плане вычислений и памяти)
Разбиваем лабиринт на отдельные зоны. (прямоугольники или квадраты)
Генерируем путь из зоны(т.е. ровно столько, сколько вам нужно, т.е. минимум 1) (или пути, если хочется несколько), в которой вход к зоне, в которой выход. Т.е. Фактически мы получим что-то типа графа. А графе это можно представить так(для наглядности) - каждая зона - вершина, проходы между зонами - ребра(дуги). Путь - маршрут из вершины со входом в вершину с выходом.

Все, теперь берем у каждых зон отмечаем точки их состыковки с соседними зонами (точнее с теми, в которые/из которых мы можем пройти).
Код:
##||##
##||##
# - стена
|| - место состыковки (проход)
зоны выделены разными цветами
Все. Теперь отдельно генерируем лабиринт каждой зоны, как отдельно взятого лабиринта (пологая что нам нужно соединить места состыковки и/или входа/выхода) используя как вариант 2, так и вариант 1.

В таком случае будет памяти надо меньше (если вы не переборщите с генерацией подзон вариантом 2)


upd.

Ой, сори.. не заметил, что это для пакмана.

Тогда, как вриант, задать в лабиринте некоторые "узловые" точки (например 4 угла, в которых бонус для врагопоедания) + точки спауна (пакмана и врагов), которые будем соединять описанным мною (см. выше) способом.
Дилетант широкого профиля.

"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс

Последний раз редактировалось ROD; 15.10.2010 в 13:07.
ROD вне форума Ответить с цитированием
Старый 15.10.2010, 13:21   #3
Impuls1989
Форумчанин
 
Аватар для Impuls1989
 
Регистрация: 16.08.2008
Сообщений: 276
По умолчанию

Забавно. Мне нравится второй подход. Первый действительно уж очень неэкономичный, да и придется часто пересчитывать пути (а это чревато жесткими тормозами). А что если немного модифицировать Ваш вариант таким образом:
Допустим у Нас имеется какой-то набор стандартных стенок.
1. Разбиваем поле на квадраты (прямоугольники).
2. Переходим на свободный квадрат. Если свободных квадратов нет - алгоритм завершен
3. Проверяем есть ли свободное место для размещения хотя бы одной стенки. Если нет - переходим к пункту 2
4. Пытаемся поместить случайно выбранную стенку (разные типы стенок) с условием:
4.1. Стенка отстоит от соседних ровно на одну клетку
4.2. Если стенку разместить не удалось - переходим к пункту 2
По идее такой алгоритм должен сгенерировать множество областей, которые можно обойти по кругу. Минус в том, что надо делать довольно большое поле, что может быть чревато последствиями.
Хотя наверное пункт 1 можно и опустить.
Искусственный интеллект - фигня по сравнению с естественной глупостью
Impuls1989 вне форума Ответить с цитированием
Старый 15.10.2010, 14:07   #4
ROD
Linux C++ Qt ARM
Старожил
 
Аватар для ROD
 
Регистрация: 30.11.2008
Сообщений: 3,030
По умолчанию

Цитата:
разные типы стенок
Это заранее заготовленные (или сгенерированные до генерации карты) составные блоки? (типа как тетрамино )

Если так, то да, идея не плохая. (и, похоже, для пакмана она подходит даже больше, чем моя.).

Если лабиринт не сильно большой, то резать на куски (как в моем "варианте 2") нет смысла.
Дилетант широкого профиля.

"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс

Последний раз редактировалось ROD; 15.10.2010 в 14:09.
ROD вне форума Ответить с цитированием
Старый 15.10.2010, 20:10   #5
Impuls1989
Форумчанин
 
Аватар для Impuls1989
 
Регистрация: 16.08.2008
Сообщений: 276
По умолчанию

Цитата:
Сообщение от ROD Посмотреть сообщение
Это заранее заготовленные (или сгенерированные до генерации карты) составные блоки? (типа как тетрамино )
Да именно так.
Значит решено. Буду пробовать делать такой лабиринт.
Ну и тогда еще один небольшой вопросец. Не знаете откуда можно выдрать красивые спрайты привидений?
Искусственный интеллект - фигня по сравнению с естественной глупостью
Impuls1989 вне форума Ответить с цитированием
Старый 15.10.2010, 21:25   #6
ROD
Linux C++ Qt ARM
Старожил
 
Аватар для ROD
 
Регистрация: 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

Гугл вам в помощь.
Дилетант широкого профиля.

"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс
ROD вне форума Ответить с цитированием
Старый 16.10.2010, 12:28   #7
Impuls1989
Форумчанин
 
Аватар для Impuls1989
 
Регистрация: 16.08.2008
Сообщений: 276
По умолчанию

Спасибо за помощь
Искусственный интеллект - фигня по сравнению с естественной глупостью
Impuls1989 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
автоматическая загрузка 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