Discovering path through unknown territory

Question

Let's say all the AI knows about it's surroundings is a pixel-map that it has which clearly shows walkable terrain and obstacles. I want the AI to be able to traverse this terrain until it finds an exit point.

There are some restrictions:

• There is always a way to the exit in the entire map that the AI walks around in, but there may be dead ends. The path to the exit is always pretty random, meaning that if you stand at crossroads, nothing indicates which direction would be the right one to go.

• It doesn't matter if the AI reaches a dead end, but it has to be able walk back out of it to a previously not inspected location and continue its search there.

• Initially, the AI starts out knowing only the starting area of the whole map. As it walks around, new points will be added to the pixel-map as the AI corresponding to the AIs range of sight (think of it like the AI is clearing the fog of war)
• The problem is in 2D space. All I have is the pixel map.
• There are no paths in the pixel map which are "too narrow". The AI fits through everything.
• The AI does not know where the endpoint is (it is hidden in the map)
• The AI traverses the terrain in real time
• It shouldn't be a brute force solution. E.g. it would be possible to simply find a path to each pixel in the pixel map that is yet undiscovered (with A*, for example), which will lead to the AI discovering new pixels. This could be repeated until the end is reached.
• The path doesn't have to be the shortest path (this is impossible without knowing the entire map beforehand), but when movements within the visible area are calculated, the shortest and from a human standpoint most logical path should be taken (e.g. if you can see a way out of your room into a hallway, you would obviously go there instead of exploring the corner of your current room).

What kind of approaches to solve this problem are there?

Answer 1

Since finding the exit is the first goal, then the process will have two phases: clearing fog, then finding a path.

When clearing fog, the goal should be to clear it as efficiently as possible. A simple way to do this is to pick the next step that will clear the most fog, or pick the next step that will take you toward the nearest fog if no immediate fog is available to clear. More complex algorithms will depend on the type of terrain... a hedge maze has a different optimal exploration method than a wargame hex map with fields, forests, and rivers.

When the exit is found, then just path to it, with the obvious 'fogged terrain has a moderate cost that gets updated to the real cost once explored'. The fog cost can be adjusted to whatever level you desire... very high costs will have the AI take long backtracks to follow explored paths to the exit, while lower costs encourage the AI to attempt to find new shorter routes. Which is better depends on your terrain generator.

Answer 2

You may want to look at a game called Brouge. It's an open source game and is has an "auto explore" feature. From what I can tell, essentially the algorithm is:

1. Pick a random direction and start going
2. Continue exploring, choosing random directions at intersections
3. Once you've reached a dead end, path towards the nearest "fog of war"
4. Loop to 2 until exit is discovered.

In Brouge, I believe the character will keep exploring until all the fog of war is gone, but you'd cut out early. It's worth downloading and watching it work so you can get a better idea.

There's also some other links on the RogueBasin that might be helpful. They don't describe your exact problem, but they'd be useful to break parts of them off and use those in your solution.

How to create an anticipating wall-following pathfinder

Answer 3

Generate waypoints from a god perspective and let the AI have a collection of waypoints it knows of (add them as the AI discovers them). Now whenever the AI has reached its temporary goal score all the reachable Waypoints by a few factors like distance and probability that it doesn't lead to already discovered area (if the path goes to the left and you already discovered a large area to the left it's likely that it will lead there, for example). Having that score you can now go to the waypoint with the highest score. This can be repeated till the AI has found the exit.