Blog. Just Blog

Генерация лабиринта на PHP

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Web-мастеру и не только | Автор: ManHunter
Генерация лабиринта на PHP
Генерация лабиринта на PHP

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

Алгоритм очень легко реализуется на любом языке программирования. У меня это будет PHP. Единственный недостаток, что при генерации очень больших лабиринтов теоретически может возникнуть превышение лимита вложенности рекурсивных вызовов. На практике, по крайней мере на PHP, мне этого добиться не удалось.
  1. //-------------------------------------------------------
  2. // Рекурсивно-возвратный алгоритм генерации лабиринта
  3. //-------------------------------------------------------
  4.  
  5. // Начальные параметры для генерации лабиринта
  6. $width  25;
  7. $height 18;
  8.  
  9. // Инициализация
  10. $grid=array(array(),array());
  11. for($y=0$y<$height$y++) {
  12.     for($x=0$x<=$width$x++) {
  13.         $grid[$y][$x]=0;
  14.     }
  15. }
  16. $N=1$S=2$E=4$W=8;
  17.  
  18. // Рекурсивная функция создания проходов в лабиринте
  19. function passage($cx,$cy) {
  20.     global $grid,$width,$height,$N,$S,$E,$W;
  21.  
  22.     // Клетки для направления движения
  23.     $DX=array($E=>1$W=>-1$N=>0$S=>0);
  24.     $DY=array($E=>0$W=>0$N=>-1$S=>1);
  25.     $OP=array($E=>$W$W=>$E$N=>$S$S=>$N);
  26.  
  27.     $directions=array($N$S$E$W);
  28.     shuffle($directions);
  29.  
  30.     foreach($directions as $direction) {
  31.         $nx=$cx+$DX[$direction];
  32.         $ny=$cy+$DY[$direction];
  33.  
  34.         if ($ny>=&& $ny<$height && $nx>=&& $nx<$width && $grid[$ny][$nx]==0) {
  35.             $grid[$cy][$cx] |= $direction;
  36.             $grid[$ny][$nx] |= $OP[$direction];
  37.             passage($nx$ny);
  38.         }
  39.     }
  40. }
  41. passage(0,0);
  42.  
  43. // Вывести лабиринт в консоль
  44. echo ' '.str_repeat('_', ($width*2-1))."\n";
  45. for($y=0$y<$height$y++) {
  46.     echo '|';
  47.     for($x=0$x<$width$x++) {
  48.         echo (($grid[$y][$x] & $S) != 0) ? " " "_";
  49.         if (($grid[$y][$x] & $E) != 0) {
  50.             echo ((($grid[$y][$x] | $grid[$y][$x+1]) & $S) != 0) ? " " "_";
  51.         }
  52.         else {
  53.             echo '|';
  54.         }
  55.     }
  56.     echo "\n";
  57. }
Для более красивого вывода можно использовать символы псевдографики, тогда результат будет как на главной картинке. Вот так можно совершенно бесплатно, без регистрации и SMS, генерировать лабиринты в промышленных масштабах. А то некоторые деятели пытаются срубить на этом денег.

Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 175 | Комментариев: 0

Метки: PHP

Комментарии

Отзывы посетителей сайта о статье
Комментариeв нет

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2022
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 2 (0.0031 сек.) / Память: 5 Mb
Наверх