Anonymous user
Maze generation: Difference between revisions
Added PHP solution
(Added an implementation written in BASIC (QB64)) |
(Added PHP solution) |
||
Line 4,568:
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|PHP}}==
Code inspired by the D and Python solutions. Could have been done procedurally or fully OO (with cells as class too). A debug flag has been provided to allow following the inner workings. Works on PHP > 5.6.
<lang php><?php
class Maze
{
protected $width;
protected $heigth;
protected $grid;
protected $path;
protected $horWalls;
protected $vertWalls;
protected $dirs;
protected $isDebug;
public function __construct($x, $y, $debug = false)
{
$this->width = $x;
$this->height = $y;
$this->path = [];
$this->dirs = [ [0, -1], [0, 1], [-1, 0], [1, 0]]; // array of coordinates of N,S,W,E
$this->horWalls = []; // list of removed horizontal walls (---+)
$this->vertWalls = [];// list of removed vertical walls (|)
$this->isDebug = $debug; // debug flag
}
private function generate()
{
$this->initMaze(); // init the stack and an unvisited grid
// start from a random cell and then proceed recursively
$this->walk(mt_rand(0, $this->width-1), mt_rand(0, $this->height-1));
}
/**
* Actually prints the Maze, on stdOut. Put in a separate method to allow extensibility
* For simplicity sake doors are positioned on the north wall and east wall
*/
public function printOut()
{
$this->log("Horizontal walls: %s", json_encode($this->horWalls));
$this->log("Vertical walls: %s", json_encode($this->vertWalls));
$northDoor = mt_rand(0,$this->width-1);
$eastDoor = mt_rand(0, $this->height-1);
$str = '+';
for ($i=0;$i<$this->width;$i++) {
$str .= ($northDoor == $i) ? ' +' : '---+';
}
$str .= PHP_EOL;
for ($i=0; $i<$this->height; $i++) {
for ($j=0; $j<$this->width; $j++) {
$str .= (!empty($this->vertWalls[$j][$i]) ? $this->vertWalls[$j][$i] : '| ');
}
$str .= ($i == $eastDoor ? ' ' : '|').PHP_EOL.'+';
for ($j=0; $j<$this->width; $j++) {
$str .= (!empty($this->horWalls[$j][$i]) ? $this->horWalls[$j][$i] : '---+');
}
$str .= PHP_EOL;
}
echo $str;
}
/**
* Logs to stdOut if debug flag is enabled
*/
private function log(...$params)
{
if ($this->isDebug) {
echo vsprintf(array_shift($params), $params).PHP_EOL;
}
}
private function walk($x, $y)
{
$this->log('Entering cell %d,%d', $x, $y);
// mark current cell as visited
$this->grid[$x][$y] = true;
// add cell to path
$this->path[] = [$x, $y];
// get list of all neighbors
$neighbors = $this->getNeighbors($x, $y);
$this->log("Valid neighbors: %s", json_encode($neighbors));
if(empty($neighbors)) {
// Dead end, we need now to backtrack, if there's still any cell left to be visited
$this->log("Start backtracking along path: %s", json_encode($this->path));
array_pop($this->path);
if (!empty($this->path)) {
$next = array_pop($this->path);
return $this->walk($next[0], $next[1]);
}
} else {
// randomize neighbors, as per request
shuffle($neighbors);
foreach ($neighbors as $n) {
$nextX = $n[0];
$nextY = $n[1];
if ($nextX == $x) {
$wallY = max($nextY, $y);
$this->log("New cell is on the same column (%d,%d), removing %d, (%d-1) horizontal wall", $nextX, $nextY, $x, $wallY);
$this->horWalls[$x][min($nextY, $y)] = " +";
}
if ($nextY == $y) {
$wallX = max($nextX, $x);
$this->log("New cell is on the same row (%d,%d), removing %d,%d vertical wall", $nextX, $nextY, $wallX, $y);
$this->vertWalls[$wallX][$y] = " ";
}
return $this->walk($nextX, $nextY);
}
}
}
/**
* Initialzie an empty grid of $width * $height dimensions
*/
private function initMaze()
{
for ($i=0;$i<$this->width;$i++) {
for ($j = 0;$j<$this->height;$j++) {
$this->grid[$i][$j] = false;
}
}
}
/**
* @param int $x
* @param int $y
* @return array
*/
private function getNeighbors($x, $y)
{
$neighbors = [];
foreach ($this->dirs as $dir) {
$nextX = $dir[0] + $x;
$nextY = $dir[1] + $y;
if (($nextX >= 0 && $nextX < $this->width && $nextY >= 0 && $nextY < $this->height) && !$this->grid[$nextX][$nextY]) {
$neighbors[] = [$nextX, $nextY];
}
}
return $neighbors;
}
}
$maze = new Maze(10,10);
$maze->generate();
$maze->printOut();</lang>
{{out}}
<pre>
+---+ +---+---+---+---+---+---+---+---+
| |
+---+---+---+---+---+---+---+ +---+ +
| | | | |
+ +---+---+ + + +---+---+ +---+
| | | | | | | |
+ + + +---+---+ +---+ + + +
| | | | | | |
+ +---+ + +---+ + +---+---+ +
| | | | | | |
+---+---+---+ + +---+ + + + +
| | | | |
+ +---+---+---+---+ +---+---+---+---+
| | |
+---+ + +---+---+---+---+---+ + +
| | | | | |
+ +---+ + + + + +---+---+ +
| | | | | | | | |
+ + +---+---+ + + + + +---+
| | | |
+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|PicoLisp}}==
| |||