Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: [C++] нужно написать генерацию лабиринтов  (Прочитано 42252 раз)
0 Пользователей и 1 Гость смотрят эту тему.
alena
Интересующийся

ru
Offline Offline

« : 28-05-2011 19:29 » 

задача состоит  в построении лабиринтов случайным образом...
не знаю с какой стороны подступиться(
я не представляю какие именно классы должны быть, ну как это все должно быть организовано...кому не сложно,подскажите в общих чертах?
и ещё... это ведь с использованием графики, а разрешается это все рисовать не выходя за пределы консоли...других вариантов, кроме как всякими тирешечками рисовать - никаких??
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 28-05-2011 19:53 » 

Лабиринт допускает циклы?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
alena
Интересующийся

ru
Offline Offline

« Ответ #2 : 28-05-2011 19:58 » 

разрешается все....)) только в рамках консоли
есть алгоритмы краскала и прима как непосредственное построение, разбирала на примере в паскале, не представляю организацию всего этого в классах...
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 28-05-2011 21:29 » 

Графика для данной задачи не обязательна. Псевдографика вполне подойдет.

При чем тут классы? Такое условие в задании?

Расскажи, что знаешь по заданию и что думаешь о решении.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
alena
Интересующийся

ru
Offline Offline

« Ответ #4 : 28-05-2011 21:44 » 

нужно сделать,"использовав" объектно-ориентированное программирование,я не знаю с чего начать...

само задание: напишите программу,которая по исходным данным размера  строит прямоугольный лабиринт, при каждом обращении - новый лабиринт,который должен иметь единственное решение....

в общем, я так думаю,что сам лабиринт - некое подобие двумерного массива, каждый элемент которого - совокупность параметров(информация о соседних клетках, ну вот этих границах), нужно "запоминать", например границу слева и сверху, при этом при вводе размера лабиринта м*н нужно обрабатывать массив размера (м+1)*(н+1), таким образом будет учитываться граница нижняя и правая...что касается самих алгоритмов, в книге Мозгового "Занимательное программирование" они разобраны на пальцах для паскаля,как я уже говорила, алгоритмы Краскала и Прима....
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 29-05-2011 02:20 » 

Elena-ta, А в чем суть того алгоритма? Честно не искал в инете его. Я бы например решал эту задачу при помощи графа. Такое решение само просится.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
alena
Интересующийся

ru
Offline Offline

« Ответ #6 : 29-05-2011 06:10 » 

я не знакома с методом графом,
но вот вкратце алгоритм Прима:
Прима: создается заготовка - лабиринт,в котором все локации(клетки) окружены стенами, каждой клетке ставится в соответствие переменная(может принимать 3 значения:Inside(внутри), Outside(снаружи),Border(на границе)).Получили двумерный массив таких переменных, изначально все они - Outside, выбираем случайную локацию, присваиваем  значение её переменной Inside, а переменным соседних клеток - Border,далее по алгоритму
алгоритм:
Пока переменная хотя бы одной локации равна Border
  выберем случайную локацию, переменная которой равна Border, присвоим ей значение Inside
  изменим на Border переменные соседних локаций,переменные  которых равны Outside
  из всех соседних с текущие локации,переменные которых равны Inside, выберем случайную и разрушим стену между ней и текущей локацией...
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 29-05-2011 06:59 » 

Elena-ta, это задание для зачёта или для чего-то более важного ?
Записан

alena
Интересующийся

ru
Offline Offline

« Ответ #8 : 29-05-2011 07:01 » 

это задание для курсовой...сейчас срочность важна)))а я как всегда все на последний момент оставляю...
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 29-05-2011 09:10 » 

 из всех соседних с текущие локации,переменные которых равны Inside, выберем случайную и разрушим стену между ней и текущей локацией...

1. Критерий соседства?
2. "Разрушим" - это что? Присвоить "Inside"? При этом процедура "изменим на Border переменные соседних локаций,переменные  которых равны Outside" также выполняется?

Добавлено через 2 минуты и 2 секунды:
Сдается мне, данный алгоритм с изъяном. Его результатом всегда будет полный массив Inside. Всему виной - условие "Пока переменная хотя бы одной локации равна Border". Что же тогда будет составлять стены?

Пересмотри условия алгоритма - возможно ты не полностью описала состояния, условия и т.д.

Добавлено через 9 минут и 5 секунд:
Так же думаю, что нужно изменить условие "выберем случайную локацию, переменная которой равна Border, присвоим ей значение Inside".
« Последнее редактирование: 29-05-2011 09:22 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 29-05-2011 10:50 » 

Если совсем тупо, то:

В начале красим все клетки разными цветами (нумеруем от 0 до M*N). Все клетки окружены стенами.

Разрушаем произвольную стену, по обе стороны которой клетки имеют разный цвет.

Соединившиеся проходом области (может быть много клеток) красим в общий цвет (цвет первой или второй области - не важно).

Повторять разрушение и перекрашивание до тех пор, пока все клетки не окажутся одного цвета. Значит из любой клетки существует проход в любую другую, и этот проход единственный - по построению.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #11 : 29-05-2011 22:07 » 

А я маньяк Улыбаюсь Сделал по Димкиному алгоритму

* Labirint.rar (11.41 Кб - загружено 1154 раз.)
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #12 : 30-05-2011 03:09 » 

само задание: напишите программу,которая по исходным данным размера  строит прямоугольный лабиринт, при каждом обращении - новый лабиринт,который должен иметь единственное решение....
Что мы имеем
1) Лабиринт должен быть случаен
2) Лабиринт должен иметь решение
3) Лабиринт должен иметь одно единственнное решение.
Дополнительное спорное условие (которое не оговаривается в задание.
4) У каждой ячейки лабиринта, должна быть разрушена хотя бы одна стена Улыбаюсь (Т.е Из входа в лабиринт можно проложить путь к данной ячейке).

Я лично не представляю, как можно гарантировать 2 и 3 условие в Димкином подходе к рещению Улыбаюсь.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 30-05-2011 03:55 » 

Finch, я не знаю алгоритма Краскала для лабиринтов, но знаю алгоритм Краскала для построения телефонных сетей. Поэтому последний алгоритм (который гарантирует условия 2 и 3) я переиначил для лабиринтов. Алгоритм даёт дерево без циклов (это обеспечивается разрушением стен между разноцветными клетками - для которых гарантированно нет прохода) - это условие единственности. Алгоритм охватывает все клетки - это условие наличия решения, поэтому вход может быть где угодно.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #14 : 30-05-2011 04:10 » 

Finch,

1)  - он у меня псевдослучайный получается, я не нашёл, чем в консоли перемешать рандом (то есть параметр для srand() )

и ещё вопрос, как обеспечить стабильность программы в таком случае, когда нужно ввести число или строку (использую std::cin>>... )  - если напечатать длиннющую строку, то где-то что-то переполняется и программа начинает летать по циклу (у меня меню в виде цикла сделано) . Я даже не смог исключение вызвать, просто дуреет программа и всё
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #15 : 30-05-2011 07:50 » 

1)  - он у меня псевдослучайный получается, я не нашёл, чем в консоли перемешать рандом (то есть параметр для srand() )
Обычно srand(time(NULL)) делают Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #16 : 30-05-2011 08:33 » 

Вад, спасибо
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #17 : 30-05-2011 14:40 » 

Dimka, Я про то, что там может быть теоретически образоваться анклав клеток, которые будут иметь один и тот же цвет и при этом не сообшаться друг с другом.Ты все таки закрашиваеш рандомом лабиринт? Или есть другой алгоритм закраски?
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #18 : 30-05-2011 16:08 » 

Finch, да всё чётко работает. проверено много раз - всё как надо Улыбаюсь Да и по логике тоже всё правильно
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #19 : 30-05-2011 16:21 » 

Finch, не рандомом, каждая клетка изначально имеет уникальный цвет. Для этого достаточно пронумеровать все клетки в некотором порядке - каждый номер будет означать свой цвет.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #20 : 30-05-2011 16:30 » 

и ещё вопрос, как обеспечить стабильность программы в таком случае, когда нужно ввести число или строку (использую std::cin>>... )  - если напечатать длиннющую строку, то где-то что-то переполняется и программа начинает летать по циклу (у меня меню в виде цикла сделано) . Я даже не смог исключение вызвать, просто дуреет программа и всё
а вот про это,, всё ж таки, никто не подскажет? У меня очень очень мало опыта работы с консолью
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 30-05-2011 16:57 » 

Алексей1153++, ну, если очень хочется позволить загонять некорректные данные, то можно сбросить флаги порчи потока, а потом прочитать 1 символ.

Код: (C++)
   
int n; char c;
while(!(std::cin >> n).good()){
  std::cin.clear();
  std::cin.get(c);
  std::cout << "c=" << c << '\t';
}
std::cout << n << std::endl;

>dsd123
c=d   c=s   c=d   n=123
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #22 : 30-05-2011 16:57 » 

Алексей1153++, Загоняеш поток в строку. А потом пытаешся перевести в число, получилось, значит введено было число, поехали дальше. А если не получилось, значит было не число, пытаеш пользователя дальше.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #23 : 30-05-2011 17:23 » 

Вад, оу, интересный примерчик )

Finch, а если строка переполнится ? Улыбаюсь


Кстати, вот обновил с рандомом, перемешивающимся по таймеру



* Labirint.rar (11 Кб - загружено 1481 раз.)
* Labirint_0009.rar (8.93 Кб - загружено 1457 раз.)
* f_4e721475a2216[1].gif (4.85 Кб - загружено 7285 раз.)
« Последнее редактирование: 10-02-2012 02:51 от Алексей1153++ » Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #24 : 30-05-2011 18:05 » 

Алексей1153++, stl::string?
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #25 : 30-05-2011 18:29 » 

Finch, любая. Или он будет автоматом увеличивать буфер, если это std::string ?
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #26 : 30-05-2011 19:34 » 

Леш, попробуй Улыбаюсь
Код:
#include <string>
#include <iostream>

using namespace std;

int main() {
   string str;
   cin >> str;
   cout << str << endl;
   return 0;
}
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #27 : 30-05-2011 19:56 » 

Finch, ага, попробовал, круто )  Мир спасён! ))


Всё, комментарии я написал, исходники пристегнул в ответе #23
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines