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