hi.

im searching for some algorithm or way of implementation of automatic falnking that is made for NPC. for example npc instead of searching for nearest path, it igonres it and finds a way to backdoor.

can you give me some good refrence to make that?

Here is how I would do this:

I would simply use A* pathfinding, but when in flank mode, simply add a high cost for all the sections around the player in front of them in an arc. Project a chord from the players position like a sight cone and make the pathfinding cost of this incredibly high, and your npc will find a route around and behind the player, avoiding their line of sight.

You should update the high cost cone periodically in case the player is moving or turning.

Another approach (slightly more complex) is to mark up your world space.

In an offline preprocessing pass, take note of locations that act as good cover or otherwise viable shooting positions. Store off a cone or frustum that approximates the field of fire that can be achieved from each general firing position.

These positions can be linked together by examining your navmesh or other locomotion data, and making a graph of how the points are connected to each other. Store this graph as well in an offline pass.

Last, at runtime, when you need a cover position, do a breadth-first search of the firing position graph starting at the nearest location to your current position as an NPC AI. If you want to encourage movement, automatically forbid the use of the closest point. Otherwise, you can score the candidates easily using the navmesh distance from your current location to the candidate firing position. The scores can be arbitrarily rich as well, if you decide you want to do things like estimate the danger of taking a given path.

This can work a bit better than merely biasing your A* costs, because it allows the AI to make intelligent-looking decisions *and* intelligent-looking mistakes. The cone-of-death cost approach works, but it makes it very hard to pin down an AI and kill them. It also can lead to artifacts like strobing, where a rapidly twitching player can force an NPC to run back and forth through open space.

The Killzone guys have some presentations that you might find useful. http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

I would simply use A* pathfinding, but when in flank mode, simply add a high cost for all the sections around the player in front of them in an arc. Project a chord from the players position like a sight cone and make the pathfinding cost of this incredibly high, and your npc will find a route around and behind the player, avoiding their line of sight.

^^This. A* is guaranteed to find the absolute shortest path if your "cost" estimates are based on distance, and are admissible... but, even with a completely random heuristic, A* will eventually find a path to the target.

That's no fun for an AI that's supposed to be human-like though - humans never take the "absolute best" option! The "cost" of each node should be based on many factors besides distance-to-target, which will result in more human-like decision making.

You can combine A* very well with ApochPiQ's pre-processing approach. Ahead of time, rank each node according to many different metrics: e.g. how 'open' is the area, how many other nodes can you see from here, is the node on a high-traffic path, or is it off in a corner, etc... The more different measurements you can make on the nodes, the more interesting you can make your AI movement styles.

You can these use this data to adjust the A* "cost" of the nodes based on what the AI is trying to do.

e.g. If it's in stealth mode, then increase the cost of "open area" nodes, so that it prefers more hidden routes. If it's in combat, decrease the cost of nodes that are next to cover objects, so it will try to find paths that give the best cover while moving. If it's in a hurry, then just use the plain distance heuristic. If it's got a sniper rifle, decrease the cost of nodes that can see a lot of other nodes, so they'll prefer getting into places that are good for "overwatch". If it's a coward, decrease the cost of nodes that have friendly units nearby. If they're meant to be smart, increase the cost of nodes where friendly units have previously died... And for flanking, you can use braindigitalis' suggestion of temporarily increasing the costs of the nodes in front of the player. I wouldn't continually update this info as the player looks around, as that's magical knowledge for the NPC (they should only update these costs if they actually see the player change where they're looking).

You should even be able to do this "on the fly", that is, without having to explicitly modify/tweak and store a lot of node weights.

Just multiply every weight with a number derived from the dot product of the target's forward vector (or whatever the AI knows is the target's forward vector) and the NPC's look-at-target vector (both normalized). Standing in front of the target will give a dot product of -1, standing on the side yields zero, and standing right behind it will give +1.

So, multiplying by e.g. 1.01 + dot(player_fwd, npc_target_vec) will adjust weights directly in front of the player to 1/100 their normal value, and let the weighting gradually become "indifferent" on the side, and increase the weights up to two-fold directly behind the player (I've chosen 1.01 instead of 1.0 because otherwise nodes that are exactly in front of the player would be impossible to cross, the weight multiplier would be zero).