Optimal multiplayer maze generation algorithm

Question

I'm working on a simple multiplayer game in which 2-4 players are placed at separate entrypoints in a maze and need to reach a goal point. Generating a maze in general is very easy, but in this case the goal of the game is to reach the goal before everyone else and I don't want the generation algorithm to drastically favor one player over others.

So I'm looking for a maze generation algorithm where the optimal path for each player from the startpoint to the goal is no more than 10% more steps than the average path. This way the players are on more or less an equal playing field. Can anyone think up such an algorithm?

(I've got one idea as it stands, but it's not well thought out and seems far less than optimal -- I'll post it as an answer.)

Answer 1

The easiest solution I can come up with is to randomly generate an entire maze like normal, then randomly pick the goal point and player startpoints. Once this is done, calculate the shortest path from each startpoint to the goal. Find the average and start 'smoothing' (remove/move barriers -- don't know how this will work) the paths that are significantly above it, until all of the paths are within the proper margin. In addition, it could be possible to take the ones that are significantly below the average and insert additional barriers.

Answer 2

What about first selecting the position of the players and goal and an equal length path and afterwards build a maze respecting the defined paths? If the paths do not intersect this should easily work, I presume

Answer 3

I would approach this by setting the goal and each player's entry point, then generating paths of similar length for each of them to the goal. Then I would start adding false branches along these paths, being careful to avoid linking to other player's paths, or having a branch connect back to the path. So essentially every branch is a dead end.

This way, you guarantee the paths are similar in length. However it won't allow players to interact with each other. You can however put this in, by creating links between branches such that branch entry points on either path are at a similar distance away from the goal. And on this branch you can branch off more dead ends for fun and profit :-)

Answer 4

An alternative to freespace's answer would be to generate a random maze, then assign each cell a value representing the number of moves to reach the end of the maze (you can do both at once if you decide that you're starting at the 'end'). Then pick a distance (perhaps the highest one with n points at that distance?) and place the players at squares with that value.

Answer 5

Pick your exit point somewhere in the middle

Start your N paths from there, adding 1 to each path per loop, until they are as long as you want them to be.

There are your N start points, and they are all the same length.

Add additional branches off of the lines, until the maze is full.