Генерация лабиринта на PHP
Генерация лабиринта на PHP
Рекурсивно-возвратный алгоритм - один из самых простых способов генерации лабиринта на основе двумерного массива. Помимо высокой скорости работы, его плюсы в том, что в созданном лабиринте нет замкнутых областей, а из любой точки лабиринта можно всегда добраться до любой другой. В результате такие задачи, как добраться от входа до точки в центре лабиринта, или наоборот, выбраться из случайного места лабиринта к выходу, расположенному на произвольной стороне, или просто пройти лабиринт от края до края с произвольным расположением входа и выхода, все они гарантированно имеют решение, причем единственное. А кроме того, готовый лабиринт выглядит сбалансированным, без длинных тоннелей, пустых залов, колонн и неоднородных участков.
Алгоритм очень легко реализуется на любом языке программирования. У меня это будет PHP. Единственный недостаток, что при генерации очень больших лабиринтов теоретически может возникнуть превышение лимита вложенности рекурсивных вызовов. На практике, по крайней мере на PHP, мне этого добиться не удалось.
Code (PHP) : Убрать нумерацию
- //-------------------------------------------------------
- // Рекурсивно-возвратный алгоритм генерации лабиринта
- //-------------------------------------------------------
- // Начальные параметры для генерации лабиринта
- $width = 25;
- $height = 18;
- // Инициализация
- $grid=array(array(),array());
- for($y=0; $y<$height; $y++) {
- for($x=0; $x<=$width; $x++) {
- $grid[$y][$x]=0;
- }
- }
- $N=1; $S=2; $E=4; $W=8;
- // Рекурсивная функция создания проходов в лабиринте
- function passage($cx,$cy) {
- global $grid,$width,$height,$N,$S,$E,$W;
- // Клетки для направления движения
- $DX=array($E=>1, $W=>-1, $N=>0, $S=>0);
- $DY=array($E=>0, $W=>0, $N=>-1, $S=>1);
- $OP=array($E=>$W, $W=>$E, $N=>$S, $S=>$N);
- $directions=array($N, $S, $E, $W);
- shuffle($directions);
- foreach($directions as $direction) {
- $nx=$cx+$DX[$direction];
- $ny=$cy+$DY[$direction];
- if ($ny>=0 && $ny<$height && $nx>=0 && $nx<$width && $grid[$ny][$nx]==0) {
- $grid[$cy][$cx] |= $direction;
- $grid[$ny][$nx] |= $OP[$direction];
- passage($nx, $ny);
- }
- }
- }
- passage(0,0);
- // Вывести лабиринт в консоль
- echo ' '.str_repeat('_', ($width*2-1))."\n";
- for($y=0; $y<$height; $y++) {
- echo '|';
- for($x=0; $x<$width; $x++) {
- echo (($grid[$y][$x] & $S) != 0) ? " " : "_";
- if (($grid[$y][$x] & $E) != 0) {
- echo ((($grid[$y][$x] | $grid[$y][$x+1]) & $S) != 0) ? " " : "_";
- }
- else {
- echo '|';
- }
- }
- echo "\n";
- }
Просмотров: 849 | Комментариев: 0
Метки: PHP
Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье
Комментариeв нет
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 35,699 раз
Поблагодарили 35,699 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 360 |
 |
 |