Hacker News Reader

Comment by DangerousPie | Hacker News Reader

I wonder what simple improvements one could make to the pathfinding algorithm to make it perform better.

I appreciate that a "proper" pathfinding algorithm like A* would not be feasible given the number of guests but maybe taking into account what the guest sees ahead of them would already make it quite a bit more realistic?

You could weight the probabilities for each direction by the square root of the length of the path or something like that. And if you can see the exit set p=0, if you can see the exit set p=1.

I'm sure it would still be easy to fool though - just build very long indents and make sure the entry/exit are not visible until the last moment.

View on HN

With a one-off precomputation you can do a lot. If you store the distance to exit in each cell you can introduce a slight bias towards the exit. Easy to implement but not very realistic since it assumes things the guests can not know.

More realistic would be observing that the entry and exit are on the outer edge and the maze is simply connected, so a trivial left-hand rule [1] will solve the maze in linear time. On its own pretty boring. You could ad some randomness to make it interesting. But would it still have linear expected solving time if you do that?

[1]: https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_fo...

Might also give the guests a slight tendency to get away from each other so they tend to spread all over the maze. That might look nicer to the player. Not too strong though otherwise every guest stays in their own dead end.

Tracking what tiles the guest has been to and disallowing travel in a direction that does not lead to any unvisited tiles while keeping behavior otherwise random would be my preference.

The most efficient way is probably to "cheat" by having all the guests share the path data. Perhaps when a guest enters the maze, she only chooses a winning path 10% of the time, but as she spends more time in the maze she chooses winning paths more frequently, until she is nearly guaranteed to walk right to the exit.

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.

Well, the classic algorithm for solving a planar maze with single entry/exit (on the outside) is to always follow the right wall (or always the left wall). That's what the algorithm in the game was apparently originally modelling, with some randomness thrown in so that not all guests do exactly the same thing.

I assume they are simply talking about fixing the bias.

Instead of randomly picking from the 4 sides, pick one from the set of legal moves.

Reply on news.ycombinator.com