Started by Nov 14 2012 05:13 PM

,
2 replies to this topic

Posted 14 November 2012 - 05:13 PM

I'm trying to implement RTS style units movement, where you can click on a point, and all units move into there in a group.

Right I have it almost functional, the units move in a group, and don't intersect each other.

However it seems that the correct method is not stable enough, units will constantly move and bounce around even after reaching the targeting point.

My current algoritm is the following:

1 - Calculate direction vector to target

2 - For each unit find the nearest unit

3 - if they intersect, move this unit a very small bit in the opposite direction

I tried doing the collision test with all other units instead of only the nearest, but the result is similar (all units pushing each other around endlessy). What am I missing?

I guess this problem is somehow similar to a very simple 2D engine, so the solution is probably related to that, but my maths is quite weak

Right I have it almost functional, the units move in a group, and don't intersect each other.

However it seems that the correct method is not stable enough, units will constantly move and bounce around even after reaching the targeting point.

My current algoritm is the following:

1 - Calculate direction vector to target

2 - For each unit find the nearest unit

3 - if they intersect, move this unit a very small bit in the opposite direction

I tried doing the collision test with all other units instead of only the nearest, but the result is similar (all units pushing each other around endlessy). What am I missing?

I guess this problem is somehow similar to a very simple 2D engine, so the solution is probably related to that, but my maths is quite weak

Posted 14 November 2012 - 10:54 PM

The usual Google terms here are going to be things like "flocking," and "potential functions."

There's a ton written on this topic, and there are many variations. Here's a nice, simple approach:

0.) You have a bunch of units -- aka "agents" -- and each has a position vector in 2d. If you have n agents, call their positions x1, x2, ..., xn.

1.) Define an "interagent potential function." This is a scalar-valued function of two agents' positions that's big when the agents are close and small when far away. You typically pick something that looks vaguely bell-curve-ish. Call it*w*. I'll give an example later.

2.) You add up these potentials for all pairs of agents, to define a new function

V(x1, x2, ..., xn) = sum_over_all_ij w(xi, xj)

It's something a lot like "potential energy."

3.) You compute a partial derivative dV/dxi, for each i. This is something a lot like "force."

4.) At each step, you push each agent a little bit against the derivative, i.e.

xi[t+1] = xi[t] - eps*dV/dxi(x1,...,xn)

where 'eps' is a small number.

If you pick a smooth enough*w*, then for sufficiently small "eps," this will converge (if you want to be really fancy, you check to make sure that V has gone down since the last iteration, and, if not, halve "eps" and try again (and so on)).

What you're doing is a lot like a "physics simulation" of "charged particles." The differences are that (1) you're working directly with velocities, not accelerations, and (2) you're not necessarily using 1/r^2 force fields (which give all kinds of nasty divide-by-zero--type problems when agents get too close to each other).

The potential function that I personally like to use I've heard called the "poly6 kernel." As a function of the squared radius between two particles, it is,

w(r^2) = ( r^2 - 1 )^2 if r < 1 and 0 if r >= 1.

I like it because it looks a lot like a Gaussian, because it is exactly zero outside r=1 (so you only need to look at neighbors within that radius), and because you only need r^2 and not r, so you can avoid a square root. But this is just one choice of function; the real key is not what potential you pick, but simply*that* you define your algorithm in terms of a potential. If you do, you get, "for free," good stability properties.

There's a ton written on this topic, and there are many variations. Here's a nice, simple approach:

0.) You have a bunch of units -- aka "agents" -- and each has a position vector in 2d. If you have n agents, call their positions x1, x2, ..., xn.

1.) Define an "interagent potential function." This is a scalar-valued function of two agents' positions that's big when the agents are close and small when far away. You typically pick something that looks vaguely bell-curve-ish. Call it

2.) You add up these potentials for all pairs of agents, to define a new function

V(x1, x2, ..., xn) = sum_over_all_ij w(xi, xj)

It's something a lot like "potential energy."

3.) You compute a partial derivative dV/dxi, for each i. This is something a lot like "force."

4.) At each step, you push each agent a little bit against the derivative, i.e.

xi[t+1] = xi[t] - eps*dV/dxi(x1,...,xn)

where 'eps' is a small number.

If you pick a smooth enough

What you're doing is a lot like a "physics simulation" of "charged particles." The differences are that (1) you're working directly with velocities, not accelerations, and (2) you're not necessarily using 1/r^2 force fields (which give all kinds of nasty divide-by-zero--type problems when agents get too close to each other).

The potential function that I personally like to use I've heard called the "poly6 kernel." As a function of the squared radius between two particles, it is,

w(r^2) = ( r^2 - 1 )^2 if r < 1 and 0 if r >= 1.

I like it because it looks a lot like a Gaussian, because it is exactly zero outside r=1 (so you only need to look at neighbors within that radius), and because you only need r^2 and not r, so you can avoid a square root. But this is just one choice of function; the real key is not what potential you pick, but simply

**Edited by Emergent, 14 November 2012 - 10:54 PM.**

Posted 15 November 2012 - 01:07 PM

Thanks for the reply, very informative but the math is still a bit advanced to me, I'm trying to digest it