[C++] нужно написать генерацию лабиринтов

[alena]

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

[Dale]

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

[alena]

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

[RXL]

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

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

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

[alena]

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

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

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

[Finch]

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

[alena]

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

[Алексей++]

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

[alena]

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

[RXL]

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

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

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

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

Добавлено через 9 минут и 5 секунд:
Так же думаю, что нужно изменить условие "выберем случайную локацию, переменная которой равна Border, присвоим ей значение Inside".

[Dimka]

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

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

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

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

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

[Алексей++]

А я маньяк Сделал по Димкиному алгоритму

[Finch]

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

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

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

[Dimka]

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

[Алексей++]

Finch,

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

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

[Вад]

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

Обычно srand(time(NULL)) делают

[Алексей++]

Вад, спасибо

[Finch]

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

[Алексей++]

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

[Dimka]

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

[Алексей++]

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

а вот про это,, всё ж таки, никто не подскажет? У меня очень очень мало опыта работы с консолью

[Вад]

Алексей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]

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

[Алексей++]

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

Finch, а если строка переполнится ?


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

[Finch]

Алексей1153++, stl::string?

[Алексей++]

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

[Finch]

Леш, попробуй

Код:

#include <string>
#include <iostream>

using namespace std;

int main() {
   string str;
   cin >> str;
   cout << str << endl;
   return 0;
}

[Алексей++]

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


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