[comp.lang.misc] help needed with vehicle movement algorithm/code

demon@desire.wright.edu (11/30/90)

	Hi, I need an algorithm (or code) for the following:

given n vehicles (tanks) moving towards m vehicles (tanks)
given x obsticles (buildings, hills, etc.)

a way of moving the tanks towards each other without running into obsticles or
ending up in a dead end.

	Although this is similiar to a maze moving algorithm, the solution is
not the same, as the goals are also moving, and new obsticles are being added.

	The problem I get stuck at is encountering a hill (vehicles can not go
over them, only around).  I could simply pick a direction and go around, but
run the risk of simply circling the hill forever.

	I start with each vehicle at a specific x,y coordinate and move towards
an opposing vehicle (the closest observable).  However, if a hill or building
gets in the way, I need to move around it.  But, which direction is best?  How
about getting trapped in a "canyon" of projecting hills?
	This is for a real time system so speed is critical.  I can't spend all
day doing travelling salesmen routines.

	If anyone has done this type of thing before, let me know!

	I'll take algorithms, code, or suggestions!

	Thanx in advance.

Brett

nagle@well.sf.ca.us (John Nagle) (12/05/90)

     Try this:

	- Simulate an attractive force between the tanks.  The
	  strength of the attractive force is constant, or may
	  increase slightly as the distance decreases.

	- Simulate a repulsive force between tanks and obstacles.
	  This force falls off with an inverse-square law.

	- Compute the force resultant of all these forces on each
	  tank, and move in that direction.

Sometimes a tank will get stuck.  This occurs when every possible move
leads to a worse position, that is, one where the magnitude of the 
sum of the forces is higher.  There are various ways out of this problem,
an interesting one being to inject some noise into the force calculation,
thus adding some randomness to the movement.  Increase the noise level 
slowly until the tank is unstuck.  Note that this may result in panicky
appearing activity.

     This won't solve mazes.  But it will get you around.

					John Nagle