pathfinding for multiple objects?

Game Mechanics Artificial Intelligence
#1

i’ve had a look at path finding for a single unit and its not too difficult to get it round a map with static objects but what i’m having problem with it multiple units. i’ve tried adding units as obsticles on the map but since they move around this approach doesn’t really work well (and pretty processor intense too) couldn’t really find much information on this topic any pointer as to how this would work?

also if you have a squad of units moving them without colliding with each other is tricky too any idea’s how you would tackle such a problem?

thx

#2

You have to treat time as a 4th dimension into your equations, factoring when the two objects will collide in the future if they do. Its complicated to say the least and there isn’t much resources about it on the net…

My guess is to do your own little algorithm :slight_smile:

DP

#3

I was just reading through my old maths books and I stumbled upon “dynamic programming” for networks. It solves path finding problems locally instead of traversing the entire graph…

That lead me to the thought of why not have a radius in which you path find around in? The point you want to go to is the distance between the player and the goal clamped to the radius. Its less costly (less nodes to traverse), more realistic (limited range of sight) and you can probably do cool stuff with that too…

DP

#4

But this could lead to the units to stop at some local minimum, or only move between two points and not reach the target, even if there is a way. And you’ll also have to respect, that objects are moving and that is sometimes wiser to simply wait until they can go, instead of turning immediately. Maybe this could solved by adding some weighted random decisions for the unit, to decide which way it should go. This way it will probably never go the shortes way, but it will reach it’s target some day. It would also make it look more natural.

#5

If thats the case occurs whereby the actual goal hasn’t been reached and there are no valid paths, then increase the search diameter…

Age of Methodology introduces the idea of “uni weights” whereby the units are infact allowed to overlap (very slightly), but the unit with the lesser weight during a collision moves out of the way. I suppose the weight is dynamically calculated by the number of units selected, formation, how hard it is for the unit to move (cannon VS soldier)…etc

You could always treat the local lines that intersect with the current diameter of search as “rays” and collide those rays with the rays from the current target, where a point of collision occurs, then recalculate the path for that “ray” (i.e. put a kink in that ray making it two rays or something…). If there is no way around that (i.e going through a valley or a door way), then recalculate for the rays that are before and after the current ray…etc.

IMO, this looks more natural as you can see the object coming towards you, you know your going to hit it, but you only alter the path of movement until you actually collide with the object! Give the dudes some intelligence, they can clearly see a cannon coming towards them, so move out of the way before the cannon hits you…

DP

#6

Here’s what Paradroidz (http://www.jpct.net/paradroidz) does to deal with this:

The calculations are grid based even if the game is actually presented in 3D. An entity is always located on a grid and has a global and a local target position on the grid. The target positions come from the path calculated by a modified A*-approach with taking only static obstacles into account. The global target position is the destination…it doesn’t really matter in the calculation until it has been reached. The local target position is a position next to the actual position. If it’s reachable, i.e. no other moving entity covers that position OR has it as a target position itself, the entity will move towards the midpoint of that position (in 3D) (with a slight chance to do something completely different to add a random element). If the target position is occupied (or most likely will be in the foreseeable future) by another entity, the next target position will be the exact opposite (compared to where the entity is now) of that position. That way, the entity tries to move out of a collision and resumes to travel its actual path only after it has reached this escape position. If the escape position is occupied too, it chooses a completely different global target.
Because the movement is done in 3D (at least when the entity is visible) and a grid is only a rough approximation of the actual position in 3D, a 3D ellipsoid collision detection acts as the last line of defense. Its outcome may change the grid position of the entity when it forces the entity to cross grid borders, but that doesn’t matter. In the next iteration, it tries to reach its current local target from there.

Edit: That’s how it basically works. There are some special cases that i had to cover, but that’s really quite dependent on the game.
Edit2: Don’t overcomplicate things. Often a simple “hack” can produce results that are “good enough”, but again, this depends on the game.

#7

i have a similar problem. my virtual frog/spaceship/whatever wants to get through a street full of cars/an asteroid field/whatever. i can calculate the position of any object at any moment in time, because the movement is pretty simple. my idea was to use the a*-algorithm, but alter the world after every step. i didn’t try it yet, but it should work. this is pretty similar to brute-forcing a chess game, btw. the “world”, and “other movable objects” are changing their states also.

as for the “but i have 200 units and therefore need a billion years for this calculation”-problem, i’d simply define a leader and let the others follow him.

#8

The real problem that kappa was having was that other moving objects should block other objects without the need to recalculate the path everytime…Im not sure that A* solves that problem

DP

#9

If you have have let’s see 50 units selected, and tell them to go to a place, you shouldn’t calculate the path 50 times in one game-cycle.

Create a queue, and this queue would calculate maybe 1 path every 1-2-3 cycles, spreading out the calculations over 1-2 seconds. The player doesn’t notice it.

Check: http://www.policyalmanac.org/games/aStarTutorial.htm