5
\$\begingroup\$

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 3

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:

uneven closest cell for each team

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
\$\endgroup\$
  • 1
    \$\begingroup\$ In case I never finish writing my full answer: 1. It's not fair for many reasons. 2. Uniform helps but isn't a silver bullet. Since no maze-carving algorithm I'm aware of is designed with competitive fairness in mind, I'd recommend just making the maze (and treasure placement) symmetrical. \$\endgroup\$ – Chris Mills-Price Sep 11 '18 at 6:41
  • \$\begingroup\$ @ChrisMills-Price Short and precise! thanks. I have this article on how to make symmetric mazes, but it's more like an idea than an algorithm or an approach. Could you please guide me on how to make a symmetrical maze? \$\endgroup\$ – Mahdad Baghani Sep 11 '18 at 8:03
  • \$\begingroup\$ Hello and welcome to Game Development! On stack exchange sites, once an issue is "solved" it's enough to mark the preferred answer as accepted: there is no need to update the title to reflect this. \$\endgroup\$ – Alexandre Vaillancourt Sep 11 '18 at 14:10
  • \$\begingroup\$ @AlexandreVaillancourt thanks for your advice. I will definitely do that should I post another question. \$\endgroup\$ – Mahdad Baghani Sep 11 '18 at 18:47
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your time. Actually I want a symmetric maze, cause the answers I got shows that uniform algorithms like wilson's would not help the problem as much as symmetry. but in my opinion, a perfect maze in the case of a multiplayer game, would limit the gameplay, meaning each team is either on the right path or not. A non-perfect maze would enable stealth gameplay in which players can sneak behind the other player using cycles in the maze ( players can only see their rivals if the rivals are in their line of sight). could you elaborate more on how to create a symmetric maze? \$\endgroup\$ – Mahdad Baghani Sep 11 '18 at 8:08
  • \$\begingroup\$ 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. I myself am still looking through Theseus code to find how Jamis Buck has actually done it. \$\endgroup\$ – Mahdad Baghani Sep 11 '18 at 14:02
  • 1
    \$\begingroup\$ My initial thought about creating a symmetrical maze is just creating half the maze you need and then flip it and the starting position to the other side and potentially flip it once more over the other axis. Should not be hard to implement. \$\endgroup\$ – Madmenyo Sep 13 '18 at 8:57
  • \$\begingroup\$ I actually ended up porting Theseus library by Jamis Buck for C# to use it for my game in unity. I will open source the ported library as soon as it is finished. \$\endgroup\$ – Mahdad Baghani Sep 14 '18 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.