Artificial Intelligence: Last-Known-Pursuit method
Submitted:|| 6th February, 2006
This is an explanation of a relatively simple method to make enemies chase you a bit more intelligently.
It's *not* designed to be used on its own, rather in conjuction with other methods.
I'll be using the term 'Routine' quite commonly in this article; 'Idle Routine', 'Chase Routine', 'Pursuit Routine', etc.
These names are kind of irrelevant. A routine is basically a set of events that you've chosen to occur under certain conditions.
So for example, if you've told your enemy to wander around aimlessly if he can't see the player, then that's your Idle Routine. If you've told him to run with guns blazing if he sees the player, that's your Chase Routine. And so on.
Suppose you have a system that checks if enemies can see you (perhaps it fires bullets from the player to each enemy on-screen and checks if there are obstacles in the way).
If the enemy can see you, he runs at you.
what if you go out of view? Hide behind a wall, turn a corner, etc?
The enemy can no longer see you, so on comes the Idle Routine, and our vicious trained killer of an enemy starts wandering around aimlessly again.
Anyone who's seen it knows how bad it looks in-game. It's just not fun being chased by an enemy who'll lose interest when you turn the corner. It'd be like playing Hide and Seek with an Ephrian Eskimo who can't find 'Seek' in his English-For-Igloo-Dwellers dictionary.
It's just not realistic, and it's hardly 'intelligent'. But what can we do? Is there an easier way to make enemies chase you?
The comforting answer is: Yup.
The idea that springs into most people's heads at this point is 'Pathfinding!'
While that's a nice idea, and something that could possibly be incorporated into the game, it's a bit ambitious for our situation. Remember, all that's happened is the player's gone around the corner! It's not like he's the opposite end of a complex maze or something. A pathfinding routine is kind of overkill don't you think?
We need to rethink what we're trying to achieve.
When chasing someone, a fundamental key is:
You need to see your opponent in order to chase him (kind of obvious, but that's what AI is about). Otherwise you don't know where you've got to run to (you lose your target).
If our enemy has lost his direct line of sight with the player, we need to get that line of sight back. Once that's happened, the original 'chase' routine can continue.
The principle behind LKP is that enemies remember where they saw you last. They store your X and Y location in a couple of alterable values that we'll call LK-X and LK-Y.
When they can see you, these two values are constantly updated, but not used. All the while they can see you, the enemy can generally just run in your direction shooting like crazy. We'll call this your standard 'Chase Routine'. No matter how simple or complicated you choose to make it, the 'Chase Routine' will only happen when the enemy can see you.
But lo! You turn the corner and vanish!
'Chase Routine' is now obsolete, as they can no longer see you. The conditions that operated Chase Routine are no longer true, so the enemies will stop chasing.
We now need a new routine - we'll call it 'Pursuit Routine'. We'll set a flag on and keep that flag on for a few seconds (let's say 10). The count-down can be held in another alterable value (let's call it LK-CD). When the count-down ends, the flag will be switched off, 'Pursuit Routine' will end, and the enemy can finally resume his 'Idle Routine'.
But while the flag is ON, and 'Pursuit Routine' is still alive and kicking, our enemies can use the Last-Known coordinates (in LK-X and LK-Y) as their target.
Now, instead of chasing the player, they run for the x/y position where they last saw him.
This is very logical. The player can't have vanished, and it's extremely likely that if they run to where they last saw him, he will still be visible from that position. (They might just see him running down the corridor, for example)
Seeing him again, even for a moment, will trigger 'Chase Routine', and that updates the LK-X and LK-Y coordinates.
Do you see how this works now?
The two routines - Chase and Pursuit - kind of look out for each other. It's a partnership. Chase provides the Last-Known coordinates that Pursuit needs. Then when Chase can no longer run, Pursuit does its best to bring the enemy into a position where he can start Chase routine again.
The Bigger Picture
Last-Known-Pursuit is not in itself a decent AI system. But when added onto an existing system, LKP is incredibly handy indeed.
Of course, it's still quite easy to fool. The enemy can only follow if they see you turn the corner. If you turn one corner, then another before they see you, they'll have no choice but to give up.
This is where, if you wished, a complex PathFinding routine could be useful. So you'd have Chase Routine, Pursuit Routine, and maybe a Search Routine. But that's the subject of another article altogether.
Potential for Growth
LKP also has potential for growth. I'm working on a few ideas for simple situations which would expand the routine:
1. Recording a secondary set of coordinates a moment after the first, to get the player's general direction (handy for crossroads where the player could have taken more than one turning)
2. Some system of nodes to sit in corners and cross-roads. So if a player vanishes down a corridor, then turns another corner, the enemy won't see the player, but they will see the node. The node tells them 'There's only one direction you can go this way, so even though you can't see the player, he must have turned left here'. As a result, the enemy moves towards the node, and perhaps spots another node from that position which also says "he must have gone left here, as there's no other possible direction". That way, he follows the path.
I'll probably post an example at some point.
Best Article WriterRegistered