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)?

Biased

This is not directly programming related. I think you should better ask this on Math or GameDevelopment – Bumboat

Maybe try generating a maze with just 1 diagonal half of the board, then replicate it for the other team – Largo

@Bumboat thanks for the advice. I actually thought about GameDev stack exchange, but Math never came to my mind. I am a newbie and don't know if asking the same question on another stack exchange site is allowed or frowned upon. what sould I do? – Biased

Actually I don't know exactly either :D You can either delete this question and open a new one there (,copy paste) or (and I think this is the supposed way) you can flag you own question using in need of moderator intervention and ask the moterators kindly to move your question to another community. – Bumboat

I'm voting to close this question as off-topic because is is not directly programming related. – Balfore

Until yesterday I believed to know what is off-topic. Now I am excluded from the review for 6 months because of this question about game development. – Shift

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.

Tristram

thanks for the reply. I now have two resources on symmetric maze, one is Astrolog which define the symmetric maze and one is this article on Algorithms for making more interesting mazes which propose to use a modified version of Prim algorithm to create symmetric mazes. but my question has evolved into this: which one guarantees to create a fair random maze: a symmetric approach or a uniform one? – Biased

You're actually quite right about the problem I raised. for those who are having the same question, you can look into concrete examples to help you understand the situation. Jamis Buck is quite known for his works on maze generation, and his library 'Theseus' is what I used to create symmetric mazes and see for my self how can the symmetry help the problem of a random maze being fair. This library is open source and can be used as a guide for implementing a random symmetrical maze generator. – Biased