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

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

Quote:Original post by h3idi
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

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?)

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

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).

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

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

Quote:Original post by WilliamvanderSterren
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).

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

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]