Sub-optimal pathing

This topic is 4967 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm working on an open-source bots addition/modification for the FPS game Return to Castle Wolfenstein (forums at ubersoldat.3.forumer.com). The bots use waypoints for their primary navigation, and I've implemented A* as a pathfinding mechanism along these waypoints/paths. As a design issue, though, I would prefer that the bots not always take the shortest waypoint-path to reach their destination (ie, there are usually multiple possible paths between any two given waypoints, but A* will always find the shortest). I have been playing with the pathfinding to try to create more varied paths, but I would welcome any suggestions about ways to possibly implement this. Some of my ideas so far: -Tweak the A* heuristic by a random amount each time a new path must be calculated (I realize this can lead to no path being found) -Only let the A* algorithm run for a specific amount of time and then stop it, *before* it has found a full path, and just returning the best path it has created so far (with how the waypoints are placed, this would likely still be on a valid path to the goal) -Pathfind randomly (at least not A*) from the goal a certain distance in any direction (still along waypoint paths), and then try to construct an A* path to that waypoint (and then on to the goal) And a perhaps less realistic option - use a genetic algorithm to evolve a path to the goal, but only allow it to run for a specified, relatively small number of generations. I realize genetic algorithms aren't generally considered great for real-time pathing with modern computers, but even only allowing the the algorithm to run for a few hundred generations (which is fast enough to be unnoticed) still generates at least a good start to a valid path, if not the whole path. And given the random starting state of the population, this virtually guarantees varied paths. I'm in the process of testing this now (a big thanks to fups for his excellent book), and so far it seems to work better than I had expected. The main issue I have is determining a valid crossover operator for order-dependent pathing. If anyone has any ideas or suggestions about these or any other methods to create varying paths, I would really appreciate your help :)

Share on other sites
Generate the shortest path, remove a random waypoint from it (or link from one waypoint to another, as long as it's part of this path) and generate a new path around it. repeat as needed.

Share on other sites
Find the shortest path,
find all other paths longer then the shortest path and shorter then the shortest path * x

make x small

pick one randomly

Share on other sites
Quote:
 Original post by TeamWhore-Tweak the A* heuristic by a random amount each time a new path must be calculated (I realize this can lead to no path being found)

I'm not sure that would allow the algorithm to keep working. You could slightly randomise the cost for entering each waypoint. In fact if you did this with some sort of predictable noise-generator that deterministically modified the original cost of each waypoint by 50-150% (for example), it would work well.

Quote:
 -Only let the A* algorithm run for a specific amount of time and then stop it, *before* it has found a full path, and just returning the best path it has created so far (with how the waypoints are placed, this would likely still be on a valid path to the goal)

I don't know how random this is likely to look though. Maybe try it, but it wouldn't be the solution I'd attempt.

Quote:
 -Pathfind randomly (at least not A*) from the goal a certain distance in any direction (still along waypoint paths), and then try to construct an A* path to that waypoint (and then on to the goal)

That'll give you a path that looks wobbly along the first half and then direct along the second half; probably not good enough.

Apart from the use of procedural noise I mentioned above, I concur with C-Junkie in that fuzzifying the best path is another useful approach.

Share on other sites
Create a semi-random cost map over your area, which puts false costs on to transitions between locations. Ideally make it lie about simple routines and truthful about more obscure ones. For example, make the main paths in your dungeon higher cost than the back alleys...

Then just use unmodified A* to find the "best" path using these false costs, and it will do what you want?

Mark

Share on other sites
I would add noise to the function responible for estimating the distance to the destination. Actually I'd multiply the noise, so that it gets more random the farther away it is.

Share on other sites
You could design a simple exploration function, that records the number of paths chosen and every mod Y number of paths you instead use chosen a random path of the possible paths.

Share on other sites
If you just need a random choice in situations when there are multiple "good enough" alternative paths from A to B, it suffices to:
- detect (or manually mark) the bottleneck waypoint identifying each unique path from A to B (for example, for a room with multiple doors, you mark the waypoints representing each of the doors as 'bottleneck').
- before each A* search, add a random visiting cost component for each of the bottleneck nodes

This way, the you'll get logical variations in the paths instead of really random variations (such as zigzagging through a room where a straight line path would be the only sensible option).

Unreal Tournament implements something along these lines:
http://wiki.beyondunreal.com/wiki/AlternatePath
although it seems in UT some paths are forced to visit a bottlenekc waypoint / alternatepath node, which may cause troubles.

William

Share on other sites
Hi,

Why not use some other algorithm? you could try a modified depth first search and then take the first path to the goal.

Share on other sites
Hi everyone, thanks for all the help so far. I'll work on adding these ideas in, and hopefully I can get it to work.

ray_intellect - part of what I'm asking for is ideas for other algorithms to use; I just mention A* a lot because that's what I have in place currently. I'm not committed to using it, it's just what I've thought about the most so far. I'm fairly new to pathfinding/AI programming, so I figure more experienced people will have better and more plausible ideas that what I would come up with. There is also *so* much information about pathfinding available, that I decided it would be better to ask for help, rather than the guess-and-pray method (which I use too much to be good) :)

Share on other sites
Interestingly, a recent search just turned up a previous thread on this topic, which I actually started. Maybe some of the responses there might be useful too.

http://www.gamedev.net/community/forums/topic.asp?topic_id=150182

Share on other sites
Consider a CS map Assualt

if you created a new waypoint time called - Path Important and you placed one in the vent,backdoor,front door and then code the bots as not 2 be allowed to go past a Path Important waypoint if it hasnt passed another one..

For Exanmple The bot goes in the vents gets to the hostages (For Rescue) finds no one there(he leaves them(Random AI)) goes on but instead of going back through the roof he goes out the back door.

Then you can create sub-Important Paths,eg there are 2 ways to get to the vents and if say by the time he is on top of the roof a friend gives a call at the backdoor he is not allowed to use the ladder he came by instead he uses another....

MM im tired

Share on other sites
Hi,

If I understand your problem correctly, you don't want the bot to always use the same path in the situation because it lets the bot's path get predictable by the player if he recognizes the pattern in the bots path-choosing. My suggestion would be to think about it like a human player perhaps would. A human would think: if i walk the same route again, my movement gets predictable, so it would be a disadvantage for me. So if i choose a certain path this time, i'll try to avoid using it next time.
You can model this within A* by increasing the cost for a certain path after using it, so that it will get more improbable the more you use it, eventually leading to another decision. The only problem is that your costfunction isn't just dependent on location anymore then but also dependant on startlocation and destination. But i found the idea interesting. I hope it is useful for you.

Thies Heidecke

Share on other sites
Quote:
 Original post by h3idiHi,If I understand your problem correctly, you don't want the bot to always use the same path in the situation because it lets the bot's path get predictable by the player if he recognizes the pattern in the bots path-choosing. My suggestion would be to think about it like a human player perhaps would. A human would think: if i walk the same route again, my movement gets predictable, so it would be a disadvantage for me. So if i choose a certain path this time, i'll try to avoid using it next time.You can model this within A* by increasing the cost for a certain path after using it, so that it will get more improbable the more you use it, eventually leading to another decision. The only problem is that your costfunction isn't just dependent on location anymore then but also dependant on startlocation and destination. But i found the idea interesting. I hope it is useful for you.Thies Heidecke

That actually makes a lot of sense. What are the motivations for a bot to choose a sub-optimal path? In this case, Thies suggests that the bot will actively try and avoid a path that has already been taken. In whatever case, the avoiding of a certain path should be part of a higher-level decision made by the bot --> then, modifying your A* algortihm might involve sending the algortihm a list of paths that you want to avoid.

Alternatively, you might be trying to simulate a situation where the bot doesnt always take an optimal path 'just' to reduce the effect of the program being a simulation. In this case, what you're trying to model is a world that is non-fully observable --> i dont know exactly how this could represented (maybe some weights across pathnodes are unknown?)

Share on other sites
You could achieve this by identifying nodes on previous paths and avoiding these nodes in further search... that is, penalise paths through these nodes. Once a bot has travelled through all nodes, they are equally penalised and thus the penalty is mitigated. You might also want to permit the penalty to degrade over time, so that if a node is not used in a while, it becomes an acceptable waypoint on a path.

Timkin

Share on other sites
If you use a cost function that does not discriminate between meaningful and meaningless path variations, you'll end up with with silly paths (in addition to some useful variations).

For example:
%%%%%%%%%%%% A %%%%%%%%%%%%%%      %%%%%%%%%%%% B %%%%%%%%%%%%%%       %%%%%%%%%%%% C %%%%%%%%%%%%%%%%%%%%%%%%%% A . %%%%%%%%%%%%      %%%%%%%%%%%% a B %%%%%%%%%%%%       %%%%%%%%%%%% a C %%%%%%%%%%%%%%%%%%%%% . A % . . %%%%%%%%%      %%%%%%%%% . a % B . %%%%%%%%%       %%%%%%%%% . . % C . %%%%%%%%%%%%%%%%%% . A % . . %%%%%%%%%      %%%%%%%%% . a % B . %%%%%%%%%       %%%%%%%%% . . % C . %%%%%%%%%%%%%%%%%% . A % . . %%%%%%%%%      %%%%%%%%% . a % B . %%%%%%%%%       %%%%%%%%% . . % C . %%%%%%%%%%%%%%%%%%%%% A . %%%%%%%%%%%%      %%%%%%%%%%%% a B %%%%%%%%%%%%       %%%%%%%%%%%% a C %%%%%%%%%%%%%%%%%%%%%% . A %%%%%%%%%%%%%%      %%%%%%%%%% B a %%%%%%%%%%%%%%       %%%%%%%%%% . C %%%%%%%%%%%%%%%%%%%%%%%%%% A . %%%%%%%%%%%%      %%%%%%%%%%%% a B %%%%%%%%%%%%       %%%%%%%%%%%% C . %%%%%%%%%%%%%%%%%%%%%% . A %%%%%%%%%%%%%%      %%%%%%%%%% B a %%%%%%%%%%%%%%       %%%%%%%%%% . C %%%%%%%%%%%%%%%%%%%%%%%%%% A . %%%%%%%%%%%%      %%%%%%%%%%%% a B %%%%%%%%%%%%       %%%%%%%%%%%% C . %%%%%%%%%%%%%%%%%%%%%% . A %%%%%%%%%%%%%%      %%%%%%%%%% B a %%%%%%%%%%%%%%       %%%%%%%%%% . C %%%%%%%%%%%%%%%%%%%%%%%%%% A . %%%%%%%%%%%%      %%%%%%%%%%%% a B %%%%%%%%%%%%       %%%%%%%%%%%% C . %%%%%%%%%%%%%%%%%%%%%% . A %%%%%%%%%%%%%%      %%%%%%%%%% B a %%%%%%%%%%%%%%       %%%%%%%%%% . C %%%%%%%%%%%%%%        1st path A                   2nd path B, zigzagging               2nd path C, avoiding	                             to avoid all 'a' marks             just two 'a' marks placed				                                          at junction locations

When you arbitrarily mark waypoints as being visited (for example all waypoints in path A above), you may end up with paths that simply look unrealistic (the lower part of part B, where it zigzags along diagonal connections between waypoints).
By first identifying those waypoints where path variation would be meaningful (doors, portals, paths into/from junctions), and solely marking those waypoints as visited, you'll end up without the silly and unrealistic variation (path C above).

Share on other sites
No one suggested arbitrarily marking waypoints as having been visited. I suggested penalising waypoints that have been visited. Obviously, if you use a large, naive penalty, you'll get ridiculous paths like the ones in your example. A little thought about the idea (rather than simply assuming the worst case implementation) shows that a small, incremental penalty proportional to the local density of the waypoint space would give a reasonable result.

Timkin

Share on other sites
Timkim,

I used 'arbitrarily' to refer to the lack of discrimination between meaningless variation and meaningful variation in the paths. Perhaps 'uniformly' would have been better.

Meaningful variation in games such as RtCW typically occurs when paths visit different entrances and branches at junctions.
Taking detours (such as the zigzagging in the example I sketched) in an empty room with only one entrance and one exit just to avoid the beaten path through that featureless room is meaningless variation: a player won't be able to explain that movement as smart.

Reducing the penalty for visited notes simply reduces the probability of the AI picking a variation (equally for both the best-case and worst-case variations).

My point is that a heuristic not explicitly reflecting the required type of variation is unlikely to accomplish that effect without (hard to control) side-effects.
And once the type of variation is reflected (as in the Unreal Tournament example mentioned earlier), getting just the required variation isn't that hard.

William

Share on other sites
Quote:
 Original post by WilliamvanderSterrenReducing the penalty for visited notes simply reduces the probability of the AI picking a variation (equally for both the best-case and worst-case variations).

Not if the penalties are correlated with the waypoint density. In which case, if one were to choose the obvious positive correlation of a higher penality for a higher density, then the probability of choosing a different route would scale with the number of available routes. One must also (obviously) choose penalty levels that do not overly influence the path costs, which would create undesirable paths like the one depicted in your middle picture above.

Obviously, my suggestion is a purely automatic method for influencing path selection and as such will not perform optimally under all circumstances... however it is fairly easy to implement and requires no specialised analysis of the map. Ultimately, this presents a tradeoff which must be evaluated and decided upon.

I'm not suggesting your method is not appropriate... merely that I offered an alternative.

Cheers,

Timkin

Share on other sites
You don't say why you want random path selection in your first post, but I presume (as someone else pointed out) its to make the bot feel more human and reduce other players ability to predict the bots movement. However i'm not sure this is an ideal strategy to use, it may add randomness, but doesn't really add much more to the bot.

Anyway being a rather dedicated player of RTCW or rather RTCW:ET I have built up a great deal of experience in the game. Yet there are many times when I use exactly the same path over and over, and conversely times when I deliberately do the opposite of what I'd normally do. What might be a better improvement is to examine why and when players take the same path and when they do something different.

Some reasons as to why I choose the same path or deliberately choose a different one, regardless of what path is optimal.

a. There is no better path
b. Another more optimal path is too well defended (i've died taking that path to many times)
c. I have to get to an objective quickly
d. Its about time I tried a different route (don't want to become predictable - o.k so some randomness might be useful)
e. I'm low on health (look for medic)
f. I saw via the spectate mode whilst waiting to reswpan the enemy at a specific location
g. i'm low on ammo (look for field op)
h. Another path is underfire (artilery etc)
i. Certain objectives have been met, so a specific waypoint may no longer be within the gameplay area
j. I've noticed many team members die at a specifc point in the map

This isn't a comprehensive list but i think it shows two areas that would help make the bot more bleievable/success without the need for just adding randomness into the mix.

The first is to take on board the bots current status in terms of health and ammo supply as when you're low its better to run away and find a fieldop/medic than anything else. Importantly taking the most secure route to whichever player the bot needs. This brings me onto the second point which is to use influence mapping to take into account the danger level of a particalur route.

The influence map would be a combination of good practice (i.e. from game playing expereince you rarely want to move to a certain waypoint as its normally underfire) argumented by what the bot can see (enemy men placement, number, and where), although if you could access all the game data (cheating) this would be far easier.

The influence map is team not bot based, so it shouldn't get bogged down when adding more bots. Once calculated it can be overlaid onto the waypoints, adding or subtracting from their cost.

I would start off just by tagging the number of enemy players seen around a waypoint and possibly the length of time they have been there. If you can access it then data on where artilery is being fired and perhaps more importantly if other team members/bots have died there recently. Roll this up into some value and update over time to give an influence map, which as I said can be used to modify the cost of a specific waypoint.

This should introduce more randomness into the bots movement without it actually being random.

Of course there are many other factors that could be considered, but I'll leave that for you to come up with ;)

Just thought of something else, as RTCW is a squad based coop game and not flat out fragger, play is sligtly different. Use of cover and caution is a good method to stay alive longer, and so perhaps you should take this into account.

At its simplist i'm thinking that you could add several special waypoints types. For example a 'hide point' denotes an area where the bot is safe from typical (forward) enemy fire. Another would be View point as most maps have prime locations from which to view areas of the game level. The one important aspect is that these nodes should be dead ends and not through ways

In normal AI game play these nodes are ignored they are only considered if the bot has decided to hide or get a better overview of the battle etc.

[Edited by - noisecrime on July 15, 2004 8:23:18 AM]

Share on other sites
Well the main reason I want to have the bots choose different paths is basically so that they'll be less predictable and at least seem a *little* random, as people have said. I realize that in many cases things like that wouldn't seem realistic (especially if the 'new' path the bot chose went far, far out of the way). But on most maps, there are multiple ways to get from one location to another, and usually more than one is fairly valid. For RTCW players - a simple example is beach, and creating a path for an allied bot to the objective. Assuming the bot starts from the bunker flag, he can reach the upper base in 2 'normal' ways - via axis spawn to radio room, or up the stairs to the back stairway. If he goes the back stairway, he can then get to the warroom via the ducts (which is actually the 'shortest path' if you don't account for crouching being slower), or through the basement. This leaves 3 valid paths to reach the same goal, and it is much more interesting to play against these bots if they don't *always* go down the back stairs and through the ducts. If you're playing against 10 bots, and all 10 go the exact same way, every single time, it can get pretty boring, not to mention easy. That being said, I don't want totally random paths - like there's no reason at all for a bot to leave the bunker and go on to the beach and run around there for a while.

A lot of the factors mentioned for path selection are actually part of the goal selection I use for the bots - eg, one bot's longterm goal may be to steal the objective, but if he's low on health, he'll look for a medic if one isn't way out of the way, even if the medic isn't on a direct path to the objective. I'm working on including some of the other concepts into a factor of how likely a bot is to even search for a sub-optimal path (eg, if time is short and the bot is on offense, shorter paths are better, etc), and I will probably add some kind of influence mapping, though I'll try to do it without having the bots 'cheat' :)

Again, thank you to everyone for all the help and suggestions. I'm trying out a lot of these methods to see how well they perform in various situations, and I am sure that I will be able to use a lot of what is mentioned here to create something suitable. You have all given me a lot of good ideas and a better understanding of pathfinding in general. Thanks :)

Share on other sites
The optimum path every time is not going to give a human player the challenge they want. There are logical reasons for variation. The "self safety" version which prefers to move in a direction but does it by going from landmark to landmark to get some cover as they move. The "swarming berserker" is the opposite and seeks the straightest line which can give the fastest speed only avoiding terrain which might slow it. The "flanking movement", the "assassin backattack", the "get close then pause for buddies". Really irritating would be the "scout/decoy" which moves into a line of site, then drops back abit and circles closer until a new line of site, then circles the other direction. So the bot will still get to the same target but its the positions inbetween which will be arrived at differently.