Grobots - Documentation - Vector Algebra, Shot-Leading, Friendly Fire and Active Dodging

Vectors are quantities with a direction and a magnitude. Grobots uses them to represent positions, velocities, and other important things.

If you have no clue about vectors, try this introduction. But remember that it's about 3-dimensional vectors, and Grobots only uses 2-dimensional ones. There's also a Wikipedia article about vectors. It's rather technical, so you might want to read only representation of a vector through cross product. Pay particular attention to the pretty pictures for the dot and cross products.

Many grobots quantities are well modeled by (2-dimensional) vectors. Positions of robots are vectors, measured from the lower-left corner of the world. Velocities are the rate of change of position.

The Vector Operators

Doing vector math with only scalar operations is prohibitively tedious. Fortunately Grobots includes a bunch of vector operators.

In two dimensions, vectors can be represented in two forms. In the rectangular approach, distances east and north of the origin are stored. It is often convenient to instead use the length of the vector and its angle relative to the x-axis. This is a polar coordinate system. In Grobots, rect-to-polar and polar-to-rect convert between polar and rectangular coordinates.

You can add, subtract, and negate vectors with v+ and v-, and vnegate. vs* and vs/ multiply and divide vectors by scalars - not other vectors.

norm angle unitize

dot project cross

dist and in-range are conveniences that could be easily defined in terms of v- and norm.

Don't forget the stack manipulation operators. Many of them (2drop, 2swap, 2dup, 2over) operate on two items together, which often means a vector. rot and rrot can swap a vector with a scalar. drop, nip, over, and dup are convenient for getting the x- and y-components of vectors.

Fun Things To Do With Vectors

Shot Leading

Consider the problem of having one's shots hit where a target is going to be when the shot arrives, rather than where the target is when the shot is fired. The general technique is to calculate how long it will take the shot to hit (distance / speed), multiply the target's velocity by this time to determine how far they will move in that amount of time, and add this to their current position to determine where they will be. Then, subtract the robot's current position to compute the target position relative to the robot (instead of lower-left corner of world), and fire.

fire-robot-sensor sync
robot-found if
  robot-velocity ;line 3
    robot-distance grenades-speed / vs*   ;line 4
    robot-position v+   ;line 5
    position v- rect-to-polar fire-grenade    ;line 6
then

The above code was modified from gunner 3, a stationary cell. If the firer is moving, the firer's velocity is added to the projectile's normal velocity - shots are "thrown". To anticipate this, add "velocity v-" to the end of line 3. The reasoning behind this is that from the perspective of the firer, the target is moving at "robot-velocity velocity v-" relative to the firer.

The time to intercept used above is not perfectly accurate, as it assumes the distance to the intercept point is the same as the distance to the robot *now*. Usually, the robots are moving slowly enough relative to the shots that this is not a problem, but sometimes rapidly closing targets confuse this. To remedy this deficiency, a better estimate of TTI is needed. One approach that seems to work well is to calculate TTI, calculate distance to a preliminary intercept point using the just-calculated TTI, and then use the distance to that intercept point to calculate a new, better TTI.

Avoiding Friendly Fire

In order to avoid hitting allies with a blaster, one must determine if an ally is going to ever intersect the blaster. Steps:

  1. Do standard shot-leading, but instead of firing, record where you will be firing in a variable.
  2. Predict the velocity of the shot relative to the ground by adding your velocity relative to the ground to the shot's velocity relative to you.
  3. Fire the robot sensor looking for allies. For each ally, check to see if it's in line of fire. If any are, abort firing. For each ally:
    1. To determine if the ally is between the firer and the target, compute the relative position of the ally and take the dot product with a vector of length 1 pointing in the direction the shot will go in. It turns out that this construction produces the component of the relative position vector parallel to the shot's velocity, which can then be compared to 0 and target-distance. A negative value indicates the ally is behind the firer; greater than target-distance suggests the ally is behind the target.
    2. If the ally is between us and the target, we need to figure out the distance the shot would miss the center of the all by. To do so, compute the velocity of the shot relative to the ally, and then compute the component of the ally's position relative to the firer perpendicular to the closing velocity. It turns out that taking the cross product of the unitized closing velocity with the relative position does the trick. If the shot will miss by less than the sum of the shot and ally's radii, it will actually hit, so don't fire.
  4. If no one is in the way, fire using previously recorded vector to intercept point.
#var target-distance
#var target-delta
#var expected-shot-velocity
0 robot-sensor-sees-friends!
1 robot-sensor-sees-enemies!
0 robot-sensor-focus-distance!
fire-robot-sensor sync
robot-found if
  robot-distance target-distance!
  ;Do shot-leading to predict firing path
  robot-position position v- 
  robot-velocity velocity v-
  robot-distance blaster-speed / vs* v+
  target-delta!
      
  blaster-speed target-delta angle polar-to-rect velocity v+ expected-shot-velocity!
      
  ;look for friends in line of fire
  1 robot-sensor-sees-friends!
  0 robot-sensor-sees-enemies!
  target-delta 0.5 vs* rect-to-polar robot-sensor-focus-direction! robot-sensor-focus-distance!
  fire-robot-sensor sync
  robot-found if
    do
      robot-position position v- expected-shot-velocity unitize dot dup 
        0 > swap target-distance < and if ;if the friend is between us and the enemy
          robot-position position v-
          expected-shot-velocity robot-velocity v- unitize
          ;stack: vector to ally, shots expected closing velocity
          cross abs
          ;stack: ally distance from line of fire
          robot-radius 0.3 + < no-shoot& ifg
        then
      next-robot while-loop
    then ;friends
  target-delta angle fire-blaster
No-Shoot:
then ;enemies found

The method of determining if the ally will intersect the shot's path while it's active (as opposed to before it's fired or after it hits) is primitive, and might fail if the ally is moving rapidly. But it seems to work just fine in practice.

Active Dodging

Active 5 has a complicated multilayered movement algorithm that allows it to eat during combat, leaving the food just long enough to dodge incoming shots. Active dodging does not need to be nearly this complicated.

#const Flee-angle 1.5 ;angle between shot velocity and fleeing.
#const MIN_MISS_DIST 2.5
#const flee-speed 0.1
#const ASSUMED_ROBOT_SLOWDOWN_FACTOR 0.4
#const DODGE_OVERKILL_FACTOR 1.2
#var miss
#vector dv
#vector assumed-robot-velocity
#vector go-dir

;Dodge has inputs:
;-desired-velocity, the desired medium-term engine velocity
;-speed-slop, the amount the velocity can differ before engine is used
;Dodge then sets engine-velocity and power to avoid shots.
Dodge-and-move:
	;do as much computation as possible before firing shot sensor to get up-to-date info
	
	velocity ASSUMED_ROBOT_SLOWDOWN_FACTOR vs*
	2dup desired-velocity dist 0.05 <= if
		2drop desired-velocity
	else
		2dup
		desired-velocity v- unitize -0.05 vs* v+ ;expected velocity
	then
	assumed-robot-velocity!
	
	assumed-robot-velocity rect-to-polar shot-sensor-focus-direction!
	3 * shot-sensor-focus-distance!
	
	fire-shot-sensor sync
	shot-found Obey-User& nifg
	shot-process-loop:
		shot-velocity norm if
			shot-velocity assumed-robot-velocity v- dv!
			dv shot-position position v- dot
			0 < and-if
		else
			next-shot shot-process-loop& obey-user& ifeg				
		then
	dv unitize
	shot-position position v-
	cross miss!
	;positive means the shot will miss to our right (when facing the incoming shot)
	dv angle
	miss 0 > Flee-angle Flee-angle negate ifev -
	dup 1 swap polar-to-rect go-dir!
	MIN_MISS_DIST miss abs - 0 max ;dist to move
	shot-distance 3 max / shot-velocity norm * DODGE_OVERKILL_FACTOR * ;this line: flee speed
	swap polar-to-rect
	assumed-robot-velocity v+ 2dup ;2 copies of engine-vel on stack
	desired-velocity v- go-dir dot ;negative if desired deviation from calculated is ok
	0 < if
		2drop Obey-User& jump
	then

	engine-velocity!
	engine-max-power engine-power!
	return
	Obey-User:
	desired-velocity engine-velocity!
	velocity desired-velocity v- norm speed-slop < 0 engine-max-power ifev engine-power!
	return

Grobots by Devon Schudy (dschudy@yahoo.com) and Warren Schudy (wschudy@wpi.edu)