#c# #php #algorithm
Вопрос:
В настоящее время я работаю над проектом, в котором используется алгоритм Эллера для создания лабиринтов. Я нашел идеальный рабочий пример этого алгоритма, написанный на C# . Но проблема в том, что моя среда программирования основана на PHP. Поэтому я попытался преобразовать код C# в PHP, но пока безрезультатно.
PHP — код в настоящее время выполняется нормально, но результат преобразованного кода не совпадает с результатом C#. Так что, должно быть, что-то не так с преобразованием, но я не могу понять, что именно.
Результат, который я сейчас получаю (неразрешимый лабиринт): Изображение текущего
Результат, который я ожидал получить (идеально сгенерированный лабиринт): Ожидаемая картинка
Проект, который я пытаюсь преобразовать, это: https://github.com/SebastianEd/EllersAlgorithm
Это файловая структура, которая у меня сейчас есть:
- index.php (Частично на основе Program.cs)
require('Maze.php');
$width = 5;
$height = 5;
$maze = new Maze();
$maze->GenerateMaze($width, $height);
$maze = $maze->TranslateMaze();
for ($y = 0; $y < $height * 2 2; $y ) {
for ($x = 0; $x < $width * 2 2; $x ) {
echo $maze[$y][$x];
}
echo '<br>';
}
- Maze.php (на основе Eller.cs)
<?php
class Set
{
public $Cells;
}
class Cell
{
public $Set;
public $HasRightWall;
public $HasBottomWall;
}
class Maze
{
private const MaxBias = 64;
private const Bias = 32;
private const Wall = "xx";
private const Path = "....";
private $width;
private $height;
private $sets;
private $row;
private $maze;
public function ReturnMaze()
{
return $this->maze;
}
public function GenerateMaze(int $width, int $height)
{
$this->width = $width;
$this->height = $height;
$this->maze = Array();
$this->sets = [];
$this->row = [];
for ($i = 0;$i < $this->width;$i )
{
$this->row[] = new Cell();
}
// This is the section where the algorithm finally executes after all the preperations.
for ($x = 0;$x < $this->height;$x )
{
// Handles the last row which is a special case.
if ($x === $this->height - 1)
{
// Every cell that has no set, will have its own unique set.
$this->InitSets();
// In the last row every cell will have a bottom wall
foreach ($this->row as $cell)
{
$cell->HasBottomWall = true;
}
// Create right walls
for ($i = 0;$i < count($this->row) - 1;$i )
{
// Delete all rows that divide different sets
if ($this->row[$i]->Set !== $this->row[$i 1]->Set)
{
$this->row[$i]->HasRightWall = false;
}
else
{
$this->row[$i]->HasRightWall = true;
}
}
// The last cell in a row always has to have a right wall because that's where the border of the maze is.
$this->row[count($this->row) - 1]->HasRightWall = true;
// Stores the row in the maze.
$this->WriteRowIntoMaze($x);
// End the loop because the last row has already been done.
continue;
}
// Every cell that has no set, will have its own unique set.
$this->InitSets();
// If there are multiple cells with the same set place a wall between them.
// Otherwise you will get "holes" in your maze. Just remove this code-segment and generate some mazes to see it!
for ($i = 0;$i < count($this->row) - 1;$i )
{
if ($this->row[$i]->Set === $this->row[$i 1]->Set)
{
$this->row[$i]->HasRightWall = true;
}
}
// Create the right walls.
$this->CreateRightWalls();
// Create bottom walls. (NOTE: Each set need at least one cell without a bottom wall.)
$this->CreateDownWalls();
// Stores the row in the maze.
$this->WriteRowIntoMaze($x);
// Prepare the next row.
$this->PrepareNextRow();
}
}
/// <summary>
/// Returns a random bool and is used to define if a right wall should be created or not.
/// </summary>
private function CreateWall():
bool
{
$x = rand(0, self::MaxBias 1);
if ($x > self::Bias)
{
return true;
}
return false;
}
/// <summary>
/// This will define foreach cell in a row if it has a right wall or not.
/// </summary>
private function CreateRightWalls()
{
// i is the left cell(lc) and i 1 is the right cell(rc) => | lc | rc |
for ($i = 0;$i < count($this->row) - 1;$i )
{
// Randomly create a wall.
if ($this->CreateWall())
{
$this->row[$i]->HasRightWall = true;
}
else if ($this->row[$i]->Set === $this->row[$i 1]->Set)
{
// If the left and the right cell have the same set there needs to be a right wall to not create loops in the maze.
$this->row[$i]->HasRightWall = true;
}
else
{
// Merge cells to the same set.
unset($this->row[$i 1]
->Set
->Cells[array_search($this->row[$i 1], $this->row[$i 1]
->Set->Cells, true) ]);
$this->row[$i 1]
->Set->Cells = array_values($this->row[$i 1]
->Set
->Cells);
$this->row[$i]
->Set
->Cells[] = $this->row[$i 1];
$this->row[$i 1] = $this->row[$i];
}
}
// The last cell in a row always has to have a right wall because that's where the border of the maze is.
$this->row[count($this->row) - 1]->HasRightWall = true;
}
/// <summary>
/// This will define foreach cell in a row if it has a bottom wall or not.
/// </summary>
private function CreateDownWalls()
{
// NOTE: Every set needs to have at least one path downwards.
foreach ($this->sets as $set)
{
// Check if the set is used by any cells. (NOTE: There can be sets without any cells due to merging the sets of different cells.)
if (count($set->Cells) > 0)
{
// The cellIndices store the information which cells of a set should NOT have bottom walls.
$cellIndices = [];
// If a set only has one cell it must not have a bottom wall!
if (count($set->Cells) === 1)
{
$cellIndices[] = 0;
}
else
{
// Randomly choose how many paths you want to have downwards. (NOTE: Each set needs at least one path downwards!)
$downPaths = rand(1, count($set->Cells) 1);
// Randomly choose which cells of the set should have the downPaths.
for ($i = 0;$i < $downPaths;$i )
{
do
{
$index = rand(0, count($set->Cells));
}
while (in_array($index, $cellIndices));
$cellIndices[] = $index;
}
}
// Add bottom walls.
for ($k = 0;$k < count($set->Cells);$k )
{
if (!in_array($k, $cellIndices))
{
$set->Cells[$k]->HasBottomWall = true;
}
else
{
$set->Cells[$k]->HasBottomWall = false;
}
}
}
else
{
// Remove empty sets to clean up a little bit.
unset($this->sets[array_search($set, $this->sets, true) ]);
$this->sets = array_values($this->sets);
}
}
}
/// <summary>
/// Prepares a new row.
/// </summary>
private function PrepareNextRow()
{
foreach ($this->row as $cell)
{
// Remove all right walls for the next row.
$cell->HasRightWall = false;
// If a cell in the previous row had a down wall the cell beneathe must not have a down wall nor a set.
if ($cell->HasBottomWall)
{
unset($cell
->Set
->Cells[array_search($cell, $cell
->Set->Cells, true) ]);
$cell
->Set->Cells = array_values($cell
->Set
->Cells);
$cell->Set = null;
$cell->HasBottomWall = false;
}
}
}
/// <summary>
/// For the algorithm to work you need to make a unique set for each cell where the set is empty.
/// </summary>
private function InitSets()
{
foreach ($this->row as $cell)
{
if ($cell->Set === null)
{
$set = new Set(); // Create a new set...
$cell->Set = $set; // ...and assign it to the cell
$set->Cells[] = $cell; // Add the cell to the set.
$this->sets[] = $set; // Add the set into the list of sets.
}
}
}
/// <summary>
/// Eller's algorithm always loads only one row into memory. So you need to store every row before you move on to the next one.
/// You could also print every row before moving on to the next row, but then you can't access the whole maze! (Or simply doing both :P)
/// </summary>
/// <param name="h">
/// 'h' stands for height and tells the how many rows this is.
/// </param>
private function WriteRowIntoMaze(int $h)
{
for ($i = 0;$i < count($this->row);$i )
{
// You need to store a new object into the arrays cell, because otherwise it will only store
// the reference to the rows cell and it will be overridden after the next step in the loop
$cell = new Cell();
$cell->HasBottomWall = $this->row[$i]->HasBottomWall;
$cell->HasRightWall = $this->row[$i]->HasRightWall;
if (!isset($this->maze[$i]))
{
$this->maze[$i] = Array();
}
$this->maze[$i][$h] = $cell;
}
}
public function TranslateMaze()
{
$mazeTranslation = Array();
for ($i = 0;$i < $this->height 1;$i )
{
$y = $i - 1;
for ($j = 0;$j < $this->width 1;$j )
{
$x = $j - 1;
if ($i === 0)
{
$mazeTranslation[$i * 2][$j * 2] = self::Wall; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Wall; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Wall; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Wall; // This is the bottom right block
continue;
}
if ($j === 0)
{
$mazeTranslation[$i * 2][$j * 2] = self::Wall; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Wall; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Wall; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Wall; // This is the bottom right block
continue;
}
if ($this->maze[$x][$y]->HasRightWall amp;amp; $this->maze[$x][$y]->HasBottomWall)
{
$mazeTranslation[$i * 2][$j * 2] = self::Path; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Wall; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Wall; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Wall; // This is the bottom right block
// Fills corners to look nicer. (Remove this section and run the code to see what I mean.)
if ($i > 1)
{
$mazeTranslation[$i * 2 - 1][$j * 2 1] = self::Wall;
}
// Fills corners to look nicer. (Remove this section and run the code to see what I mean.)
if ($j > 1)
{
$mazeTranslation[$i * 2 1][$j * 2 - 1] = self::Wall;
}
}
else if ($this->maze[$x][$y]->HasRightWall amp;amp; !$this->maze[$x][$y]->HasBottomWall)
{
$mazeTranslation[$i * 2][$j * 2] = self::Path; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Wall; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Path; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Wall; // This is the bottom right block
// Fills corners to look nicer. (Remove this section and run the code to see what I mean.)
if ($i > 1)
{
$mazeTranslation[$i * 2 - 1][$j * 2 1] = self::Wall;
}
}
else if ($x >= 0 amp;amp; $y >= 0 amp;amp; !$this->maze[$x][$y]->HasRightWall amp;amp; $this->maze[$x][$y]->HasBottomWall)
{
$mazeTranslation[$i * 2][$j * 2] = self::Path; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Path; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Wall; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Wall; // This is the bottom right block
// Extends bottom walls to look nicer. (Remove this section and run the code to see what I mean.)
if ($j > 1)
{
$mazeTranslation[$i * 2 1][$j * 2 - 1] = self::Wall;
}
}
else
{
$mazeTranslation[$i * 2][$j * 2] = self::Path; // This is the top left block
$mazeTranslation[$i * 2][$j * 2 1] = self::Path; // This is the top right block
$mazeTranslation[$i * 2 1][$j * 2] = self::Path; // This is the bottom left block
$mazeTranslation[$i * 2 1][$j * 2 1] = self::Path; // This is the bottom right block
}
}
}
// Return the translated maze.
return $mazeTranslation;
}
}
Кто — нибудь знает, что вызывает проблему с генерацией?