There should be a way to do a precomputation, starting at the last square before the exit and putting a 'signpost' value that points towards the exit. Imagine

There should be a way to do a precomputation, starting at the last square before the exit and putting a 'signpost' value that points towards the exit. Imagine planting a sign that points to the exit in the square adjacent to the exit. Then iterate over all squares reachable from that square and have them point to the square next to the exit and repeat, building flows that all point to some path to the exit until all connected maze tiles have been reached. If you still want randomness, give the people a chance to follow the signpost or move randomly, but bias it towards following the signs the longer they've been in the maze. This should scale pretty well, at the expensive of requiring a one-time recomputation whenever the maze is altered.