I have a basic recursive backtracking alghorithm for a maze. It pretty much works but ocasionally leaves some tiles in the corners untouched. This is the recursive function:
void GenerateMaze(Coordinate tilePos)
{
Debug.Log("MazeGen");
tileMap[tilePos.x, tilePos.y].visited = true;
Shuffle<Coordinate>(directions);
foreach(Coordinate d in directions)
{
if (tilePos.x + d.x >= 0 &&
tilePos.x + d.x < mapWidth &&
tilePos.y + d.y >= 0 &&
tilePos.y + d.y < mapHeight)
{
if (!tileMap[tilePos.x + d.x, tilePos.y + d.y].visited)
{
Carve(tilePos, d);
GenerateMaze(new Coordinate(tilePos.x + d.x, tilePos.y + d.y));
}
}
}
}
This is how the Carve method looks like:
private void Carve(Coordinate position, Coordinate direction)
{
if (direction.Equals(new Coordinate(-1, 0)))
{
tileMap[position.x, position.y].west = true;
tileMap[position.x + direction.x, position.y + direction.y].east = true;
}
else if (direction.Equals(new Coordinate(1, 0)))
{
tileMap[position.x, position.y].east = true;
tileMap[position.x + direction.x, position.y + direction.y].west = true;
}
else if (direction.Equals(new Coordinate(0, -1)))
{
tileMap[position.x, position.y].south = true;
tileMap[position.x + direction.x, position.y + direction.y].north = true;
}
else if (direction.Equals(new Coordinate(0, 1)))
{
tileMap[position.x, position.y].north = true;
tileMap[position.x + direction.x, position.y + direction.y].south = true;
}
}
I'm betting on a typo or stupid mistake somewhere but I cannot find it. In my last result tileMap[4,4] stayed untouched without any walls. But the algorithm does backtrack as I often end up with dead ends. It does not happen often and up till now only on the sides.
Below is an example where two tiles on the bottom right have not been carved in too.
Here is another one without walls, this time 3 unconnected tiles in another corner of the maze.
Anyone can find whats wrong?
