Collide avoidance using Goldenstein's Attract/Repel formula

[msafwan]

I found a research paper that describe a formula for collision avoidance algorithm!! I believe the (usage of this) formula is quite straightforward and we can build it now using Spring's current available function (I imagine in LUA). The challenge is just to put the correct input into this formula and use the result for unit steering.

In other word:
This collision avoidance strategy is feasible. The objective is to "port" this formula into Spring sourceCode (or Spring's LUA). Thus the result is a state of the art collision avoidance strategy.
___

First, for details I refer to 2 paper:
http://scholar.google.com/scholar?hl=en ... a=N&tab=ws

http://www.google.com/search?hl=en&q=Sc ... 14bc218727

(both is free for download)

The first paper contain the collision avoidance formulas that uses input in form of "angle toward an obstacle" or "angle toward a target". HERE's MORE ABOUT THE FORMULA:{
First we find the angle of the target and then use:

"F.target=constant*math.sin(agentHeadingAngle - obstacleAngle.with.respec.to.Agent)"

to get a graph shape that describe the max value when agent is heading the right way, and then

"F.obstacle= R*W*D"

to get the heading where it has max value when an agent heading the wrong way.
,
and the value of W and R and D is:

R= ((agentAngle - obstacleAngle.w.r.t.Agent) / subtendedAngleOfObstacle.as.seen.by.agent ) * exponen.to.the.power.of(1- abs(
((agentAngle - obstacleAngle.w.r.t.Agent) / subtendedAngleOfObstacle.as.seen.by.agent )))

W= 1/2(math.tanh('h' (math.cos(agentAngle - obstacleAngle.w.r.t.Agent) - math.cos(2* subtendedAngleOfObstacle.as.seen.by.agent +constant2)))+1)
--- 'h' = 4/(math.cos(2*subtendedAngleOfObstacle.as.seen.by.agent) -math.cos(2*subtendedAngleOfObstacle.as.seen.by.agent +constant3))

D= exponen.to.the.power.of(-distance/constant4).
,
lastly is the velocity:

velocity= (closestObstacleDistance- safetyDistance)/time.to.contact

*next is an algoritmic way to sum both "F.target" and "F.obstacle" in way which yeild correct result* }
The aim is to sum all "F.obstacle" to get the whole graph (perceived by that unit) that'll describe where the unit shouldn't go.

You can sum directly but the author says that it may cause unit to bump into obstacle. The author use some matrix summation to sum all the F.obstacle and use some condition (if else) to set constant (in above equation) to make unit behave appropriately. The first paper tells you everything about collision avoidance.
__

THe second paper tells you about the above IDEAS plus ideas to improve the LOS system; by using somesort of "Delaunay triangulation" to reduce the need to update the unit's environment, and fluid equation to make units flow like water. I'm sure the collision avoidance part is feasible, while the other 2 equations were not quite accessible yet.

The Pseudocode was:

1: for each instant t do
2: for each agent do
3: Calculate ¤êtar and╬ö¤êtar (see Fig. 2);
4: Use (2) to calculate ftar and also Ôêé ftar/Ôêé¤å;
5: Wt = 0, fobs = 0, D fobs = 0;
6: for each Obstacle i do
7: Calculate ¤êobsi and╬ö¤êobsi ;
8: Using (5), (6), (8) and (4) calculate Ri ,
Di , Wi , fobsi and Ôêé fobsi/Ôêé¤å;
9: Wt = Wt +Wi , fobs = fobs+ fobsi and
D fobs = D fobs+Ôêé fobsi/Ôêé¤å;
10: end for
11: Calculate ╬│12 (32), ╬▒2 (33) and ╬▒1 (34) (╬│21
is a constant, here set to 0.05);
12: Using initial value as w = [0, 0], simulate
(21) until it stops at a fixed point;
13: Use (10) to calculate ╦Ö¤å;
14: Use one of the velocity methods to calculate
the forward velocity;
15: Find next position and orientation (¤å) of the
agent through forward integration.
16: end for

[Licho]

I believe its much more complex than that for spring. "Obstacles" in spring are agent themselves which usually have some movement goal themselves and move each frame.
And there are lot's of specialities like
- pushing (units can push different units),
- limits imposed by unit script/animation,
- limits imposed by terrain only to some agents (some units can be pushed to water, other's can't),
- radically different costs of different paths - if you change angle and head uphill you become much slower
- collision impulse/gravity weapons

So I think you would have some pretty hard time integrating this into spring

[msafwan]

Build the collision avoidance on top of existing system.
---
This collision avoidance can be built on LUA, on top of the existing system or (if the core developer wanted to) can be added to the core pathfinding. The objective is to replace the current "move" command (which is queued by core pathfinder) with a periodic command received from this formula. As a result; the core pathfinder calculate less distance while the formula calculate for every distance this unit travel (and when the formula fail, the control is relinguished to the core pathfinder).

[scifi]

Build the collision avoidance on top of existing system.
---
This collision avoidance can be built on LUA, on top of the existing system or (if the core developer wanted to) can be added to the core pathfinding. The objective is to replace the current "move" command (which is queued by core pathfinder) with a periodic command received from this formula. As a result; the core pathfinder calculate less distance while the formula calculate for every distance this unit travel (and when the formula fail, the control is relinguished to the core pathfinder).

interesting ive been reading it and i think its a sound idea.

but behare its a lot of work as licho said.

If you have the time mate you can get it going surely spring could benefict, but you would need to work in stages keep with engine version, get to know the code e.t.c.. witch takes a lot of time.

still its nice to see the excitement, and if you choose to go aloong with this feel free to post in the forums.

[msafwan]

ISSUE 1:
Using this method for a pathfinding of more than 20 units caused a noticeable lag, and the unit move inconsistently.
___

This method is supposed to be faster because it doesn't require any CPU hungry state-space search... it only use fixed equations. The method convert angular information into a graph that interact with other graph to produce another graph that represent the correct course of action. There was some "if else" used but the actual mechanism wasn't clear.

So, I made a full size widget that encapsulate this equations... and the result was not good. The unit like to wander around, got lost (and sometimes get stuck on the edge of map) but finally find their way. This non-precision is not good for battle unless it was for scouting.

This widget has been debugged and now can be used for fun... it also can be used to emulate a brownian motion because a clusters of units will spread and occupy space like gasses.
_____

Instruction:

-Select unit(s) and pressSpaceBar + move_command to order the unit to move using this method.
-Edit any of the widget's CONSTANT to change unit behaviour.
-Press "s" to clear unit list.

-------
ISSUE 2
This widget still use native-pathFinding for a short stroll. This give a smoother movement plus not getting stuck on wall. Spring's unit-movement was different than the one used by the author; in Spring you can't set velocity and/or change direction instantenously.

If the widget is set to provide an instantenous vector and move order (like: "momomomo..momove!"), then the unit will move very slowly... thus unplayable.

It is not know how the unit will move at an ideal control condition. But IMO it is better to just play Spring for fun.

The objective was to play Spring for fun using a brand new collision avoidance strategy but it doesn't work perfectly...