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

Question

[Updated my questions at the end] 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)
3. @btilly suggest to use a Symmetric maze to solve the problem of the maze being fair, but now I have to ask which one guarantees to create a fair random maze: a symmetric approach (like the one proposed in this article or a uniform one (like Wilson's algorithm)?

Answer 1

One solution is to build a rotationally symmetric maze. Start from each end, growing, growing the other at the same time. Then when you have filled things, open a wall to a point where the length from one is close to the length from the other.

Now you'll have a maze where both teams have the same length path and very, very fair opportunities.