Hello everyone, I am currently developing a 3D team-based capture-the-flag game. Path planning is based on a waypoint system. My problem now is finding a way to chase an enemy in an efficient manner. There are two aspects of efficiency that I am concerned about here: 1. Trying to predict the path of the enemy to meet them within the path instead of chasing them based on current location only. How can I predict the waypoints the enemy is likely to follow, assuming that I could estimate their purpose (e.g. taking my flag from my base, taking their flag from ground .. etc)? Do classical prediction and filtering techniques apply here and if not, what techniques should I consider ? 2. Coordinating the path planning of multiple agents to siege a player, rather than making them follow the same path. However I don't think this can be done unless the first problem is solved. Thank you.

Well it really depends on how your maps are laid out. If you have a simple node network and you know the direction in which the enemy is traveling you can make guesses about where they are heading. You could add heuristic weights to the different states of "interest" nodes. For example.

Enemy is on team A

Base occupied by team A and unassaulted by another team: 0
Base occupied by another team: 60
Base that is unoccipied by any team: 80
Base occupied by team A and assaulted by another team: 90

The problem here, of course, is that you are just guessing what the enemy is going for based on what you "think" are his priorities.

You could attempt to learn those priorities: i.e. make a guess, compare to where he really went, adjust weights for that player. But generally FPS games don't last long enough to get a good set of patterns for a given player; and their pattern may change given other conditions (they're on vent and their friend convinces them to suddenly prefer defense over offense, etc).

Discovering intent of a human player is really really hard.

Map design could help you a lot here. If the maps are narrow corridors that offer various routes to go to intersections then you can just head to the nearest intersection towards which the player is traveling.

After that coordination is relatively easy. Just take a different path through the node network to reach the destination. You can reverse-travel the network here. Given a destination node, have group A take a path out of that network and pathfind back to where group A actually is, then mark that out-path owned. For the next group, pick an un-occupied out-path and reverse pathfind back to their origin. I'm glossing over it here b/c i'm lazy but you'll have to intelligently pick out-paths so that the resultant 2 paths chosen are the shortest different paths possible.

-me

Hi, an interesting question. Here is my answer, which was implemented in Starfleet Command II. It's an old game, so you can pick up a copy for cheap, if you want to see it in action.

The problem is in framing the question. So let me ask you about what you are trying to achieve: Does a dog chase a cat by predicting where the cat will be next frame? Does a Cheetah hunt a deer by moving towards a calculated destination? The answer of course is no.

What we are trying to implement here can be described by fighter pilots: The three modes of persuit are Pure Persuit, Lag Persuit, and Lead Persuit.

Pure Persuit is probably most familiar. It involves pointing your nose directly at the target. Heat seaker missiles follow this course. Unfortunately, so do a lot of weak AI opponants. It is also fairly easy to outmaneuver; just turn so that the enemy is sleightly behind you and you will arc around him.

Lag Persuit is what a dog does to a person. He points his nose behind the target, and this changes the way his target is facing fastest. It brings him around to the rear of his opponant.

Lead Persuit is what is what is meant by an "intercept course", and involves pointing your nose in front of your opponant. It's what children playing a game of tag do, and it's probably what you're looking for.

So let's talk about the algorithm a little more. Instead of percieving the universe as a set of coordinates from "above", consider a 'ground-level' view. What you can do is turn to place him at any angle from you. You could turn to put him in your 12:00--dead ahead. What you can watch is what angle he is presenting to you. If you are in his 6:00 he is running straight away from you.

Let's start by saying you are both the same speed. We'll add speed difference in a moment. If he is facing directly at you, or directly away from you, then you should turn to face directly at him. What if he is facing so that you are in his 9:00 or 3:00 -- directly abreast of his run? Then you will have to run in the same direction on a parallel course until something changes. Do that by turning to put him in your 3:00/9:00.

So now we have straight-on, and parallel-course; 0~90 degrees, based on his presentation of 0~90 degrees. these are the two extremes, and the only thing left is to figure out what the middle values should be. It's easy enough for dumb animals, so we should be able to 'get it'. As the target turns more and more away from dead-on, so should you.

Now about that speed difference. If you are moving twice as fast as the target, then cut the angle change in half. Simple, huh?

[Edited by - AngleWyrm on June 16, 2007 2:03:28 AM]

Thanks AngleWyrm,
Your angle monitoring technique is interesting. I think I got the general idea.

However, I think there are 2 assumptions:
* We are in free space (i.e. there are no obstacles).

* This is a death match game. That is, my only purpose is to kill the enemy. I don't need to worry that the enemy may go to my base or their base.

Please correct me if I am wrong.

To answer your question about obstacles, such as mines being dropped from a space ship -- you have to change course to go around them. Like flagging an angle range as avoid. I don't know where that death match thing came from; I was answering a question about "finding a way to chase an enemy in an efficient manner".

The second interesting question posed is "Coordinating the path planning of multiple agents to siege a player". The book "Multi-Agent Systems -- A Modern Approach" is about this subject, and has some interesting stuff. One method is the auction system, and it works in O(2N) time like this:

First unit sees a base to seige, estimates the firepower necessary, and puts up a 'contract' to kill the base. Next unit checks the contracts list, and makes a bid, offering his firepower and time-to-target. Same thing with all units.

On the next pass, the first unit sorts the bidders according to ability, and selects the top guys who can make it happen. He then messages them that they have been selected for the job (making it a binding contract), and marks the contract closed.

On each pass, units check first if they are in a contract, then if the contract needs to be re-evaluated (like if a team member can't make it), and then either work on executing their contract, bidding on another contract, or making a new one.

[Edited by - AngleWyrm on June 16, 2007 3:55:35 AM]

That sounds like a great idea. It makes me want to program a game just to use it.

Quote: Original post by AngleWyrm
... The book "Multi-Agent Systems -- A Modern Approach" is about this subject, and has some interesting stuff.

Could you please give more Information on the book as I can't find it.

Amazon.com: Multiagent Systems - A Modern Approach to Distributed Artificial Intelligence
by Gerhard Weiss, ISBN 0-262-23203-0

There's a pdf on P2P as well, but I'm not sure if that's an official release.

Thanks you.