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

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