Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
56 / 56
100.00% covered (success)
100.00%
2 / 2
 CRAP
100.00% covered (success)
100.00%
1 / 1
MazeGenerator
100.00% covered (success)
100.00%
56 / 56
100.00% covered (success)
100.00%
2 / 2
 29
100.00% covered (success)
100.00%
1 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 random
100.00% covered (success)
100.00%
50 / 50
100.00% covered (success)
100.00%
1 / 1
 25
 render
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 3
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\Maze
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Maze;
16
17/**
18 * Maze generator
19 *
20 * @package phpOMS\Algorithm\Maze
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25class MazeGenerator
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /**
38     * Generate a random maze
39     *
40     * @param int<0, max> $width  Width
41     * @param int<0, max> $height Height
42     *
43     * @return array
44     *
45     * @since 1.0.0
46     */
47    public static function random(int $width, int $height) : array
48    {
49        $n          = $height * $width - 1;
50        $horizontal = \array_fill(0, $height, []);
51        $vertical   = \array_fill(0, $height, []);
52
53        $pos       = [\mt_rand(0, $height) - 1, \mt_rand(0, $width) - 1];
54        $path      = [$pos];
55        $unvisited = [];
56
57        for ($i = 0; $i < $height + 2; ++$i) {
58            $unvisited[] = [];
59
60            for ($j = 0; $j < $width + 1; ++$j) {
61                $unvisited[$i][] = $i > 0 && $i < $height + 1 && $j > 0 && ($i !== $pos[0] + 1 || $j != $pos[1] + 1);
62            }
63        }
64
65        while ($n > 0) {
66            $potential = [
67                [$pos[0] + 1, $pos[1]],
68                [$pos[0], $pos[1] + 1],
69                [$pos[0] - 1, $pos[1]],
70                [$pos[0], $pos[1] - 1],
71            ];
72
73            $neighbors = [];
74
75            for ($i = 0; $i < 4; ++$i) {
76                if ($unvisited[$potential[$i][0] + 1][$potential[$i][1] + 1] ?? false) {
77                    $neighbors[] = $potential[$i];
78                }
79            }
80
81            if (!empty($neighbors)) {
82                --$n;
83
84                $next                                  = $neighbors[\mt_rand(0, \count($neighbors) - 1)];
85                $unvisited[$next[0] + 1][$next[1] + 1] = false;
86
87                if ($next[0] === $pos[0]) {
88                    $horizontal[$next[0]][($next[1] + $pos[1] - 1) / 2] = true;
89                } else {
90                    $vertical[($next[0] + $pos[0] - 1) / 2][$next[1]] = true;
91                }
92
93                $path[] = $next;
94                $pos    = $next;
95            } else {
96                $pos = \array_pop($path);
97
98                if ($pos === null) {
99                    break; // @codeCoverageIgnore
100                }
101            }
102        }
103
104        $maze = [];
105        for ($i = 0; $i < $height * 2 + 1; ++$i) {
106            $line = [];
107
108            if ($i % 2 === 0) {
109                for ($j = 0; $j < $width * 4 + 1; ++$j) {
110                    if ($j % 4 === 0) {
111                        $line[$j] = '+'; // 9
112                    } else {
113                        $line[$j] = $i > 0 && ($vertical[$i / 2 - 1][(int) \floor($j / 4)] ?? false) ? ' ' : '-'; // 9
114                    }
115                }
116            } else {
117                for ($j = 0; $j < $width * 4 + 1; ++$j) { // 2
118                    if ($j % 4 === 0) {
119                        $line[$j] = $j > 0 && ($horizontal[($i - 1) / 2][$j / 4 - 1] ?? false) ? ' ' : '|'; // 0 | 9
120                    } else {
121                        $line[$j] = ' '; // 0
122                    }
123                }
124            }
125
126            if ($i === 0) {
127                $line[1] = $line[2] = $line[3] = ' '; // 0
128            }
129
130            if ($height * 2 - 1 === $i) {
131                $line[4 * $width] = ' '; // 2 - 0
132            }
133
134            $maze[] = $line;
135        }
136
137        return $maze;
138    }
139
140    /**
141     * Render a maze
142     *
143     * @param array<int, int[]> $maze Maze to render
144     *
145     * @return string
146     *
147     * @since 1.0.0
148     */
149    public static function render(array $maze) : string
150    {
151        $rendered = '';
152        foreach ($maze as $row) {
153            foreach ($row as $column) {
154                $rendered .= $column;
155            }
156
157            $rendered .= "\n";
158        }
159
160        return $rendered;
161    }
162}