I have seen this question come up a few times, but on every instance there has been no reasonable solution. How on earth do you navigate an NPC through unknown terrain. what I mean by unknown, is that the NPC does not have access to the map, it knows its coordinates and has a rough idea of where the goal is. As it moves around, it can see a distance of 2 tiles (in any direction), and from this it can build its own map. The problem I''m having is how to move the NPC towards the goal, while trying to avoid obstacles and monsters. 1. I attempted to overlaying the map with nodes at say every 10 by 10 squares, and moving towards these rather than tring to aim straight for the goal. But if there is no direct path between two nodes, we become stuck. 2. I also tried using A*, and marking the unknown area as passable, but this means recalculating a path every move, or at least every time we see a new part of the map. more of a down and dirty way of doing it, but not very friendly. 3. I could randomly walk around the map, with an influence towards unknown areas, but I havent a clue how to implement this realisticly. I.e. due to the terrain, some areas will never be seen, and we tend to repeatedly circle these areas. It doesnt matter how much of the map I explore, infact the more (towards the goal at least) the better. Any help would be greatly appreciated.

Bear in mind that, without complete information, you can''t guarantee anything. You might end up traversing the whole map and then discovering the penultimate tile is blocked. This has to be taken into account when deciding what is ''reasonable''! I suppose that with a square grid-based system this is unlikely to happen very often though.

I don''t see why using A* would be a problem. You don''t need to recalculate a path every time you see a new tile, only when you see a tile that doesn''t fit your prior expectation (that it is passable). After all, there''s no difference between a visible tile that is passable and an as-yet invisible tile that you expect will be passable.

Depending on the density of your obstacles, you may find it''s easier to fix up broken paths than to totally recalculate new ones. For example, if you have this hypothetical path to the goal and then find out that a single tile on that path is blocked, it may be simpler to do a quick DFS of the nearby tiles to find a quick sub-path round that obstacle that gets you back onto the latter part of the path. This is only a problem if recalculation is slow though, which it may not be.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

funny you should bring this up. i'm dealing with exact same problem. Basically, i'm doing a tile-based TBS game and usually you plot a path from A to B. However, i recently implemented "visibility" of the map and it causes the exact problems you discribed. I got around it by limiting the uncovering the fog of war to a particular type of unit and then sort of cheating:

In a nutshell, the computer knows the map, but the player does not. Therefore, if the player directs a Scout to an "area of the unknown", the Scout will draw an actual path around obstacles to the actual goal. Now, the player will not know why the unit is moving the way it does, but it gives the impression of "exploring the darkness" and such. There might be some times when it looks fake, but for now, that's how i've decided to do it.

BUT, what happens when there is no path to the goal? We need to at least *look* like we are exploring , right? So my Scout units have 2 states: ROAMING and MOVING. If they are moving, it's because you told them too, they have found a path through the fog to the goal (without your really knowing the path of course) and are on an intercept course. if ROAMING, the unit will perform a spiral search from it's standing location and set course to the first/nearest tile that is fogged, therefore, it will at least look like like it's "trying". If though, the path to the original goal is visibly blocked (that is, the player can see that it is blocked since the fog of war has been removed), then you can have the unit report that to the player and perhaps prompt for another location to move to.

To take it further, you can crack into the A* algorithm directly. A* is basically a "blind search" if you will. It moves in the direction that scores the most points (or the least), so you could get rid of the framework and just move in a direction that gets you closer to the goal without really making a path to it. This presents a problem though, in that there is no way to tell your unit "you've already been there" unless of course you keep track of all the places you've explored and don't wish to return to. Though that could lead to a lot of backtracking in more complex terain.

Yet another way would be to do the A* search in "real time". The search normaly creates child nodes, searches the children and creates mre child nodes until it hits the goal, then returns the complete path. You could move along with what the algorithm does as it does it, like instead of getting a whole path and moving along it, have the A* create a set of child nodes with it's current collection (s it normally would) and move to the best node *for that step*, and stop the algorithm there. On the next step, pick up where you left off. Again, this may lead to a lot of backtracking. And if there is no path, you'll be in for a LOT of backtracking and running around in circles :-)

[edited by - leiavoia on March 5, 2004 10:04:02 PM]

Deal with the unknown differently than you deal with the known.

If you''re wandering unexplored territory, what exactly is your goal? you have not specific goal! if you did, the territory would hardly be unknown.

I have an ittybitty TBS remake of a classic, and each player has a worldmap of what they have explored. They take specific action based on what they /know/, like attacking an enemy city, and take umm... unspecific action against what they /don''t/ know. You know... like just sortof... explore it. Forget trying to give them a specific point to travel to, just give them a general area and let loose with some exploration algorithm.

Given the type of game, I can make certain heuristics to determine how it treats the unknown based on what it does know (bits of land there? may be an island! explore that instead of the random sea tiles we have over in the other direction)

no cheating involved.

How far ahead can your character ''see''? If it is more than just a single tile ahead, you might think about using some sort of ''potential functions'' to repel your character away from obstacles when you see them, while keeping him on the general path towards the goal.

Generic potential functions will get you stuck in some cases, the classic case is where obstacles form a U shape, so you will need to add some clauses to help your character find his way out of these circumstances, but in general potential functions can be had on the cheap. Consider if a blocking pattern is found, perhaps reverting to an A* or similar to find the way out of the blocking pattern, back into known space, and add a high repellant to the obstacles that make up the blocking pattern, to be sure you dont explore your way back there.

You might also want to add a little randomness in the characters path. If the character is supposed to look like he is exploring his way to a goal, taking the most direct route might break that illusion.

So consider a random number that represents a degree of rotation, say about 40-50 degrees of fuzziness from the vector between your character''s current position, and the goal position. This will cause your character to explore more of the map while still travelling in the general direction of the goal.

Just some thoughts

Peace

Thanks for all the replies, they have given me a few good ideas on how to solve this problem.

So far, I have added another member to my class, which will tell my exploration function whether we have tried finding a path to an unknown tile yet. I then scan the area around the NPC for an unknown tile, and then find a path towards it. So far this works, and the character really does look like its exploring the map.

The only problem is, due to the size of the map (500X500 tiles), this is a time consuming process. And we will explore the whole map. C-Junkie, that was an excellent point you made about dealing with the unknown. So one of next tasks is to only update the Astar map when a non passable tile has been spotted. Also I should think about adding some sort of heuristic so that we explore towards the goal, rather than to closest unknown tile.

Incidently, if the path to the goal is blocked, there are other NPC''s with different functions, one of which is the ability to remove walls, dig tunnels etc. Also if we havent found the goal, since I know which side of the map its located, I can norrow down the searching until its found.

you mentioned that some charators can build and destroy walls. That is exactly what my game has and it''s real problem for pathfinding. i have worked out a system that has the A* algorithm go through a series of checks. My node class has a reference to the unit agent that it is pathing for, and each of my units of course knows what it is trying to do (build, destroy, move, etc). So the agent has a set of pathing switches it can use to help out the algorithm

for instance, i have a unit that can destroy destroyable block. These blocks would otherwise limit other types of units, but for this particular unit it should ignore barriers. So the algorithm node class, in it''s GenerateChildNodes() function, it does something like this:

if ( node.type != BARRIER || unit->IgnoreBarriers() ) {   AddNodeAsChild();   } 

i have similar checks for other kinds of obstacles, inlcuding going into the unknown areas of the map, over occupied tiles, etc.

maybe that helps.

POMDP: Partially Observable Markov Decision Process

leiavoia, I like your idea, but it would only come into play after you have explored the map. Running this method on an unexplored map would result in a path being found to a goal, in a near perfect straight line. Since you are adding the blocked nodes, Astar will just go over them.

My method sets a limit on how many obstacles you can remove. i.e. when Astar is running, it will add the blocked node with an extremely high movement cost, say 200 - unblocked tiles being 1. This way if there is no path around the obstacle within 200 moves, it will go over it.

The Learning Real Time A* algorithm sounds very interesting, I have been reading up about it since it was mentioned, but I''m still non the wiser. All I can find are papers describing the algorithm, but without some sort of code, my brain goes blank.