Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (17)


Генерация лабиринтов

Поиск:
 Задача:


    
>> 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 <stdio.h>

#include <conio.h>

#include <stdlib.h>

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<size; y+=2)

  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 ("nnnnnnnnnnnnnnnnnnnnnnn");
  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ачинаем двигаться от этой точки до противоположной стены, попутно ставя в точках пути блоки. Дойдя до противоположной стены на расстояние одного блока останавливаемся. (Кстати не обязательно доходить до конца - можно остановиться и раньше. Это уже тонкости). Повторяем вышеуказанный процесс, пока не останется возможности к добалению новых блоков. Естественно, что на последующих проходах, возможно, придетсе идти уже не до глобальной стены, а до построенных стен.
Сайт: program.rin.ru






Просмотров: 3744

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную