How to randomly create a fair maze for a multiplayer game?

Question

I am creating a 2d multiplayer RTS game which happens inside a maze. I have used Growing Tree algorithm to randomly generate the maze. I thought that the maze would be fair for each team as long as each team's shortest path to solving the maze is equal to the other team. I made sure of that by making a rule in my game which dictates that each team start point is the other team's finish point and vice versa, so the shortest path would always be equal for both teams. but in practice, I noticed something else.

this question sprang up on me when I was trying to make the resulting perfect maze to a non-perfect maze using this solution, specifically @tobias-k answer.

if you already have a maze with a single path form start to goal, use this variant:

• Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away from both the start and the goal.

• Subdivide the maze by putting all cells that are closer to the start into the start set and all cells that are closer to the goal into the goal set.

• Remove a wall between the two regions to add an additional path from start to goal.

The generated paths might have (maybe even substantial) parts in common, but they should be unique loop-free paths from start to goal. Here's an illustration of the first case:

the result of seperating the maze according to each cell distance from start or end point

However, when I use BFS to calculate all distances from my start and finish point, and before removing a wall to create a non-perfect maze, I mostly get something like this:

in this picture, 336 cells are closer to team Red start point and only 105 are closer to Team Blue start point. Even removing a wall (or more than just one wall) between these two sections does not help the situation.

My game is about collecting the treasures that are randomly spread throughout the maze and getting out before the other team exits the maze, this resulting mazes are totally unfair because it gives one team the higher chance of reaching more treasures in the maze sooner compared to the other team.

so my qustions are:

1. Does the mentioned results of growing tree maze generator means that the maze is not fair for a multiplayer game (for simplicity lets just imagine the game happens between two players)?
2. Do I need to change my maze generator to something that produces a uniform texture, like Wilson's or Aldous-Broder Algorithm? (this is based on algorithms introduced by Astrolog

Answer 1

Interesting question, a really simple solution would be to create half a maze and mirroring it. If you don't want a perfect symmetrical maze then I don't have a solid solution for you but I have some thoughts about the steps to take to make it fair for both teams. First creating the perfect maze.

• Carving out the maze step by step for both the red team and the blue team simultaneously should fix the issue of more/less cells closer and thus having more options to choose from for one team making it harder to solve. There are still cases where one team has no more room of carving out walls because the other team has "cut off" an area. You could implement a "switching" patter where the team without cells left can "steal" cells from the other team.

• Another much simpler approach would be to randomly pick a common end point for both teams then have both teams walk away from it randomly but in a different pattern. If you use an equal amount of steps in a perfect maze this should also give an equal amount. Team could end up very close together but you can have a check for this in place and regenerate if necessary.

However, when you start from a imperfect maze or randomly remove walls the problem will get a lot harder to solve. So once you have placed the teams fairly in the perfect maze you could do the following.

• You should not carve into the other teams area unless both cells have the same amount of distance from there starting point.

• Second you should carve only into similar patterns otherwise one player would get a bigger loop, making it unfair.

This should be possible with the growing tree maze algorithm, I mostly used recursive backtracking for my mazes and mostly based my experience on that.