Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Игры, и все с ними связанное /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Генерация лабиринтов - Программирование от RIN.RU
Генерация лабиринтов

Задача:


Hужен алгоритм генерации лабиринта в виде прямоугольника MxN. Он должен иметь один вход и один выход, должен иметь одно решение, т.е. от входа к выходу должен быть один путь. В лабиринте не должно быть изолированных "комнат". Любая "комната" должна соединятся с "главным" путем.


Решение:


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


Если лимит M и N небольшой, можно сделать рекурсиями. Устанавливаем точку входа. Сначала генерится основной ход. Движемся по клеточкам, "прогрызая" "ходы" в "камне", изменяя вектор движения случайно по или против часовой стрелке, в завасимости от значения случайного числа, и с проверкой касания края (если коснулись, то ставим выход). С каждым шагом запоминаем координаты "прогрызенной точки" и увеличиваем уровень рекурсии. Итак, предположим, выход достигнут. Когда достигаем выхода, начинаем понижение уровня рекурсии с восстановлением координат вышеупомянутой точки, и в зависимости от случайности (например 50%) по тому-же алгоритму генерируем боковой ход. Тогда, при создании основного хода, концом генерации у нас служило достижение края лабиринта.


При генерации боковых ходов концом процесса можно сделать лимит на уровень рекурсии - например только 50 клеточек, но вообщем это на собственное усмотрение. Кончаем генерацию бокового хода, понижаем уровень рекурсии основного хода, восстанавливаем координаты, и рассчитываем вероятность создания нового бокового хода. Если надо, то создаем его. А потом снова возвращаемся к основному ходу.


Все эти ходы будут петлять, пересекаться друг с другом, и пр., в результате путь найти будет весьма сложно. Конечно, против священной силы "волнового метода нахождения пути", или композитных "методов излома вектора движения" поможет только перекрытие главного выхода :))))


Hедостатком такого метода является рекурсия, которая, при больших лабиринтах, кушает память в больших количествах.


Стaвить cтeны блoкaми, пpoвepяя пpoxoдимocть лaбиpинтa (в чacтнocти вoзмoжнocть зaпoлнeния BCEX пуcтыx ячeeк нaчинaя oт тoчки выxoдa), вpoдe ничeгo cлoжнoгo нeт.


FullFill - на сколько плотно заполнять лабиринт (делать ли холлы).


WallShort- на сколько короткие должны быть стены 0 - одни колонны.



#include
#include
#include
const int size = 20;
const int fullfill = 100; // in %
const int wallshort= 50; // in %
char m[size+1][size+1];
// Random generator
int r[2][size/2*size/2];
int h; // How many number in array;
void initrandom ()
{
int j=0;
for (int y=2; y for (int x=2; x< size; x+=2)
{
r[0][j] = x; r[1][j] = y; j++;
}
h=j-1;
}
int getrandom(int &x, int &y)
{
int i = random (h);
x = r[0][i]; y = r[1][i];
r[0][i] = r[0][h]; r[1][i] = r[1][h];
return h--;
}
// View labirint on screen
void view()
{
for (int y=0; y<=size; y++)
for (int x=0; x<=size; x++)
{
gotoxy (x*2+1,y+1);
if (m[y][x]==0) cprintf ("..");
if (m[y][x]==1) cprintf ("__");
}
}
int main(void)
{
printf ("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\");
printf ("Labirint generator");
// Clear labirint
for (int c = 0; c < size*size; c++) ((char *)m)[c] = 0;
// Make border
for (int i = 0; i <= size; i++)
{
m[0][i] = 1; m[size][i] = 1;
m[i][0] = 1; m[i][size] = 1;
}
view ();
initrandom();
int startx, starty;
while (getrandom (startx, starty))
{
if (m[starty][startx]==1) continue;
if (random (100) > fullfill) continue;
int sx=0,sy=0;
do
{
sx=random (3)-1;
sy=random (3)-1;
} while (sx==0 && sy==0 || sx!=0 && sy!=0); //sx==0 and sy==0
while (m[starty][startx]==0)
{
if (random (100) > wallshort)
{m[starty][startx] = 1; break;}
m[starty][startx] = 1;
startx +=sx; starty+=sy;
m[starty][startx] = 1;
startx +=sx; starty+=sy;
}
}
view();
return 0;
}


Представьте себе прямоугольник (N x M) составленный из блоков, где N и M - нечетные и больше или равны 5. Выбираем точку на любой стене прямоугольника, отстоящую от других стен, как минимум на 1 блок. (Hапример в прямоугольнике пять на пять единственные точки удовлетворяющие этому условию - это середины сторон). Hачинаем двигаться от этой точки до противоположной стены, попутно ставя в точках пути блоки. Дойдя до противоположной стены на расстояние одного блока останавливаемся. (Кстати не обязательно доходить до конца - можно остановиться и раньше. Это уже тонкости). Повторяем вышеуказанный процесс, пока не останется возможности к добалению новых блоков. Естественно, что на последующих проходах, возможно, придетсе идти уже не до глобальной стены, а до построенных стен.




 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Ubiquiti UniFi Switch Enterprise XG 24 сюда