Advertisement

A* with multiple moving agents

Started by July 31, 2006 04:03 PM
6 comments, last by adam23 18 years, 3 months ago
I am working on an RTS game, and it is going well. I have the A* algorithm implemented with manhattan heuristics. The way I ended up doing it is have one global map that is in a class that each object has a pointer to an object of. The problem comes in when I have a lot of characters on screen. I can detect collision between characters, but what is the normal response to a collision? I thought about several solutions but none seem really reasonable. One solution I thought of is have a flag built into each character called moving. If the character is not moving tell all other characters that node is blocked. If the character starts moving tell all characters the node is not blocked. This would work, but what if multiple enemies are moving and pass through each other, then I thought I could just let one pause and wait for the other to get ahead, but I'm not sure because it depends on the direction the agent is heading. Does anyone know a good resource for managing AI in RTS games or a similar case? Any suggestions or comments would be greatly appreciated. Here is an image of 30+ soldiers rendered with my game engine. RTS
Adamhttp://www.allgamedevelopment.com
Two flags :-)
Moving and Waiting

This is how i did it:
Every tile in the map have a byte telling what unit ocupies this tile. Whenever a unit moves from tile A to tile B, it own tile B. This way, its not possible that to units move into the same tile, and when pathfinding you can easely check what unit is at any tile.

So:
whenever a unit is moving, the moving flag is marked.
whenever a unit tries to walk into a ocupied tile it checks if the blocking unit is moving. If its not moving, it recalc the path, if its moving, we wait, and we mark the wait flag.
The tricky part is what to do if the tile you want to move into is both moving and waiting. To avid deadlocks (two units waiting on each other) you should not just wait. If 10 units are passing trough a tight gapp, the 8 last ones will meet waiting and moving units, so you could have a framecount, max wait for 3 frames, or something like that. As long as you avid deadlocks from a ring of waiting units, and that you asure that one of the units recalcs its path this should work, and would look rather realistic with units waiting and walking around.

not_moving = calc path around
moving = calc path trough
moving and vaiting = calc path around

Also:
reference from tile to unit makes rendering alot easier!
-Anders-Oredsson-Norway-
Advertisement
If one unit is stationary and the other moving, the easiest solution is to have the moving unit avoid the stationary one and return to its track (the path it is following) on the other side of the unit. In real world domains, such as driving, flying and sailing, rules govern which of two moving objects has right of way, or which side you should pass on if coming head on. Create something like this for your units, so that they will not both stand there next to each other, waiting for the other to shift out of their intended path. If both units are moving then work out which has right of way and slow the other down (halt them for enough frames to avoid the collision).

The above though does not account for the case where the stationary unit is waiting to move along the same track because of some other obstacle (so the track is also blocked for the upcoming unit, but it doesn't know it yet), or the case where the unit is following another unit and that front unit slows down for some reason (to avoid a collision, deal with a bottleneck, etc). You either need to slow the unit down, have it avoid the unit/bottleneck or have it communicate with other units or the pathing oracle to find a solution to the problem. My preferred solution is the middle one. Units should communicate with each other using a simple transaction language to resolve dynamic collisions. For example, units could send a signal to a unit that is blocking their path indicating that they are blocking and requesting a status response (which might be, for example, HOLDING or WAITING to signal that they are stationary or waiting for a blockage on their path to clear). The signaling unit can then evaluate a solution, which might include further communication with the waiting unit as to where the bloack is (does it affect this unit) and/or how long it expects to wait.

Of course, you could also solve this problem using an oracle dynamic pathfinder. One suggestion would be to use potential fields around units to affect the velocity of units close by. Thus, a bottleneck would slow all units down that are behind the blockage (and in its vicinity) and speed up units in front of it (think of a flow through a constricted tube and Bernoulli's Equation).

There is a LOT of literature available online regaring the coordinated movement of autonomous agents. You could certainly find many solutions to your problem with a brief search through Google.

Good luck,

Timkin
Thank you for the advice guys. I think I am going to build a messaging system into my game where the soldiers can communicate with each other. I really like this idea. What I may do is build an ID for each character in the game. When a collision occurs, I will send the id, location, message, and direction to both soldiers. That way I can determine if the soldiers are heading in the same direction, which character is in front of the other. All the suggestions are really good, I have been reading the book Programming AI by Example and found some techniques I may use for seperating the soldiers.

Thanks again for all the help :)
Adamhttp://www.allgamedevelopment.com
A messaging system is a good thing to have in your game. There are some very good example of how to impliment a robust messaging system out there. I particularly like the one in "AI Game Programming By Example" by Matt Buckland. Actually, I can strongly reccomend that book to anyone interested in game AI.
Quote: Original post by MidgardSerpent
I particularly like the one in "AI Game Programming By Example" by Matt Buckland. Actually, I can strongly reccomend that book to anyone interested in game AI.


I have to throw my vote behind this fantastic book as well. I recently borrowed it from the library and was *very* impressed with it as a whole. From it's coverage of FSM's all the way through to fuzzy logic systems it's fantastic.

I particularly liked the section on emergent behaviors.
My sig used to be, "God was my co-pilot but we crashed in the mountains and I had to eat him..."
But folks whinned and I had to change it.
Advertisement
I agree, great book!!
"We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the internet, we know this is not true." -- Professor Robert Silensky
I also have to recommend the book highly to anyone that is interested. Matt Buckland writes in a way that is fun and informative at the same time. I have both AI Techniques for Game Programmers, and Programming AI by Example and enjoy them both a lot.

As for the messaging system, I built a very simple one that I am testing in the console window right now, but so far it works really well. I am using std::map to store the message based on the users id.

Let me know what you guys think of this so far.
#ifndef _TELEGRAM_H#define _TELEGRAM_H#include <map>enum MSG{NOMSG, WAITING, HOLDING, ATTACKING, MOVING};class Telegram{public:	int reciever;	int sender;	MSG msg;	float x, y; //Stores the position of the sender};typedef std::pair <int, Telegram> Msg;//There should only be one TelegramSender objectclass TelegramSender{public:	TelegramSender();	~TelegramSender();	//SendMessage takes the senders id and receivers	//id and places the message in map structure	void SendMessage(int sender, int receiver, MSG msg, float centerX, float centerY);	//This function receives the characters id and 	//Sees if there is a message waiting	Telegram GetMessage(int reciever);private:	std::map<int, Telegram> telegrams;};#endif


#include "Telegram.h"TelegramSender::TelegramSender(){}TelegramSender::~TelegramSender(){}void TelegramSender::SendMessage(int sender, int receiver, MSG msg, float centerX, float centerY){	Telegram tmp;	tmp.msg = msg;	tmp.reciever = receiver;	tmp.sender = sender;	tmp.x = centerX;	tmp.y = centerY;	telegrams.insert(Msg(receiver, tmp));}Telegram TelegramSender::GetMessage(int receiver){	std::map<int, Telegram>::iterator iter;	Telegram tmp;	iter = telegrams.find(receiver);	if(iter != telegrams.end())	{		//Save the message and remove it from		//the map		tmp = iter->second;		telegrams.erase(iter);	}	else		tmp.msg = NOMSG;	return tmp;}
Adamhttp://www.allgamedevelopment.com

This topic is closed to new replies.

Advertisement