Many of the top sides (currently Revenge Killer 5, Active and its derivative Big Bertha) dodge shots actively, i.e. they look for incoming shots and dodge if they expect a shot to hit. Active dodging seems to be crucial for making a world-class fighter. It's less important for non-combatants but even so Warren is planning to give all his future types at least basic active dodging. This tutorial describes how to do it and how it works.
A basic active dodging procedureEdit
This section uses three operators that were added quite recently: rotate-to, rotate-from, and shot-relative-position. These may not be available on all platforms yet. Also we haven't made a final decision on which is which yet. In this document I look at the perspective of rotating the axes and hence 2 2 1 1 rotate-to is 2.8 0 and 2 2 1 1 rotate-from is 0 2.8. Last I checked the implementation is named based on rotating the vectors and has the two the other way around. Check which is which before using them. If your build doesn't support these look below for alternatives.
One elegant way to interface with the active dodging routines is via a desired-velocity vector variable. The main code sets desired-velocity instead of setting engine-velocity or using seek-location. The main code also calls a dodge-and-move procedure every couple of frames. The dodge-and-move procedure fires the shot sensor. It also sets the engine-velocity to desired-velocity if there are no threatening shots, or to a dodge velocity otherwise. With this interface method cool behaviors such as eating while under fire and dodging as needed happen automatically. Here's an outline of what an active dodging side might look like:
#vector desired-velocity #start do ... food-position position v- 0.08 vs* desired-velocity! time shot-sensor-time - 4 > if dodge-and-move^ shot-found if shot-velocity vnegate angle shot-sensor-focus-direction! 5 shot-sensor-focus-distance! then then ... forever dodge-and-move: fire-shot-sensor sync shot-found if shot-threatens-us and-if ;shot-threatens-us is stand-in for some code dodge-velocity engine-velocity! ;dodge-velocity is also a stand-in else desired-velocity engine-velocity! then engine-max-power engine-power! return
The shot-sensor-focus-direction and shot-sensor-focus-distance are set when a shot is seen so that future shot sensor scans will focus on the area where shots we want to dodge (as opposed to shots that have already missed) are likely to be.
Now we'll discuss how the dodge-and-move procedure works. Let's start off by considering a special case: the shot is always moving straight to the right. In this case it is clear (TODO: draw picture) that the closest the shot will get (assuming we sit still) is simply the y-coordinate of
shot-position position v-, with the sign indicating whether the shot will pass above or below us.
#var miss-coord #var beyond-coord ... shot-relative-position miss-coord! beyond-coord!Actually if beyond-coord is say -0.5 the shot will have hit us before we can dodge so ignore the shot if beyond-coord is greater than say -1. Here's the code for the shot-threatens-us and-ifstandin in the above dodge-and-move with:
beyond-coord -1 < miss-coord abs 2.5 < and and-if
Now that we know if the shot will hit (if we do nothing) how do we dodge? If miss-coord is positive it makes sense to dodge downwards, otherwise it makes sense to dodge upwards, like so:
miss-coord 0 > if 0 -1 else 0 1 then engine-velocity!Here's the complete dodge-and-move routine for this special case of shots moving only directly to the right:
#var miss-coord #var beyond-coord dodge-and-move: fire-shot-sensor sync shot-found if shot-relative-position miss-coord! beyond-coord! beyond-coord -1 < miss-coord abs 2.5 < and and-if miss-coord 0 > if 0 -1 else 0 1 then engine-velocity! else desired-velocity engine-velocity! then engine-max-power engine-power! returnGreat you say but what if the shot isn't going straight to the right? We simply do a change of coordinates to make it so. Think of this as rotating our head so it's moving to the right from the perspective of our tilted head. To do this we convert our position (relative to shot-position) to polar coordinates, subtract "shot-velocity angle" from the angle, and then convert back to rectangular coordinates.
shot-relative-position rect-to-polar shot-velocity angle - polar-to-rect miss-coord! beyond-coord!
The newest version of Grobots has a
rotate-tooperator that does the same thing:
shot-relative-position shot-velocity rotate-to miss-coord! beyond-coord!We can then determine if the shot will miss and if so which way to dodge as before. The final step is to convert the computed dodging velocity, which is in the rotated coordinate system, back to ordinary coordinates so we can set engine-velocity. This is done similarly to converting to these rotated coordinates except that we add shot-velocity angle instead of subtracting it:
miss-coord 0 > if 0 -1 else 0 1 then rect-to-polar shot-velocity angle + polar-to-rect engine-velocity!
The newest version of Grobots has a
rotate-fromoperator to make this easier:
miss-coord 0 > if 0 -1 else 0 1 then shot-velocity rotate-from engine-velocity!
Here's the complete source:
#var miss-coord #var beyond-coord dodge-and-move: fire-shot-sensor sync shot-found if shot-relative-position shot-velocity rotate-to miss-coord! beyond-coord! beyond-coord -1 < miss-coord abs 2.5 < and and-if miss-coord 0 > if 0 -1 else 0 1 then shot-velocity rotate-from engine-velocity! else desired-velocity engine-velocity! then engine-max-power engine-power! return
The following optimized version uses only 26 instructions after the sync until the engine has received its orders. This allows a 13 processor to dodge in two frames (TODO: check for off-by-one errors), allowing even low-CPU cells to take advantage of active dodging. One of the optimizations is moving the setting of engine-power to before the shot sensor firing to reduce the instructions before the engine is operational. Alternatively just set engine-powerto max when the cell starts and then not touch it thereafter. Or with a 14 processor set engine-max-power at the end as in the unoptimized version.
#var miss-coord #var beyond-coord dodge-and-move: engine-power engine-max-power <> if velocity engine-velocity! engine-max-power engine-power! then fire-shot-sensor sync shot-found if shot-relative-position shot-velocity rotate-to miss-coord! -1 < miss-coord abs 2.5 < and and-if 0 miss-coord 0 > -1 1 ifev shot-velocity rotate-from engine-velocity! return else desired-velocity engine-velocity! return then
Active and Revenge Killer versionsEdit
Revenge Killer uses essentially the above except:
- Rather than changing coordinates so that shot-velocity is to the right is makes shot-velocity velocity 0.5 vs* v- point to the right. The purpose of this is to account for our velocity, but we're more likely to slow down than speed up so only count it partially. Without this change it may pick the wrong way to dodge and try to turn around on a dime.
- It uses position shot-position v- instead of shot-position position v-. This is a historical accident of no significance. All it changes is some of the signs are opposite.
- It does the coordinate changes manually instead of using
rotate-from(because those weren't invented yet).
- It ignores shots with zero velocity (explosions?) or large velocity (syphons and force fields).
- It considers the two closest shots instead of just one.
- At the end it adds a bit of desired-velocity into the engine-velocity even when dodging. This helps with range regulation.
Active uses the same general ideas for active dodging but it uses different techniques to change coordinates (described later) instead of the polar coordinates method used above. Active also does a lot of fancy tricks that may improve its decisions a bit but definitely add a lot to CPU requirements.
A demo side with active dodgingEdit
This tutorial ends with code for a demo side with one type, an active dodging gatherer that responds to shots by dodging away from the food and then returning to the food when possible. This is a good starting point for a side; two first things to add are weapons and constructors (to this type or new one(s)).
#side Active dodging demo The purpose of this demo side is demonstrating a simple but reasonably effective active dodging procedure. This side has one type, an active dodging gatherer that responds to shots by dodging away from the food and then returning to the food when possible. To turn this into a real side a good start would be adding weapons and constructors to this type or a new one. This active dodging routine is simpler and shorter than Active 9's. To keep things simple for instructional purposes it looks at the first shot-sensor result only. See Revenge Killer 5 for a similar active dodging routine that uses multiple sensor results. Most of the action occurs in the dodge-and-move procedure at the end of the side's code. ;;shared code #code #const FOOD_CLAIM_BASE 101 #const NUM_FOOD_CLAIMS 300 ;copied from Walled City 2 via Cyclops ;Streamlined version of equivalent from Walled City 2. ;Looks like it should work on any CPU 7 or greater. #var food-hash claim-food: food-position drop world-width / ;stack: between 0 and 1 NUM_FOOD_CLAIMS * floor ;stack: presumably between 0 inclusive and NUM_FOOD_CLAIMS exclusive FOOD_CLAIM_BASE + food-hash! ;staack empty time 100 + ;put on stack for later food-hash sync read time < ClaimExpired& ifg ;valid claim already not ;;drops and then pushes "0" since time+100 != 0. return ClaimExpired: ;stack: time+100 food-hash write 1 return reclaim-food: ;;updates time-stamp of food we've claimed already. time 100 + food-hash write return ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #type Mouse #hardware processor 22 ;dodge in 2 frames energy 500 60 engine 0.12 robot-sensor 12 1 food-sensor 8 3 shot-sensor 9 2 armor 100 eater 1 #code #vector desired-velocity ;input to dodge-and-move #var have-meal 0 #vector meal-position #vector wander-position #const edge-space 4 set-wander-posn: ;this subroutine based in part on eventually 12 0 1 random-int if 0 1 random-int edge-space world-width edge-space - ifev edge-space world-height edge-space - random else edge-space world-width edge-space - random 0 1 random-int edge-space world-height edge-space - ifev then wander-position! return #start set-wander-posn^ do have-meal if eaten not meal-position position radius in-range and and-if 0 have-meal! then have-meal nif 30 periodic-food-sensor and-if food-found if do claim-food^ if food-position meal-position! 1 have-meal! Got-meal& jump then next-food while-loop then then Got-meal: have-meal if meal-position position v- 0.05 vs* desired-velocity! reclaim-food^ else position wander-position 5 in-range set-wander-posn& ifc 0.1 wander-position position v- angle polar-to-rect desired-velocity! then do time shot-sensor-time 5 + > until sync loop dodge-and-move^ shot-found if 4 shot-sensor-focus-distance! shot-velocity vnegate angle shot-sensor-focus-direction! then forever #var miss-coord #var beyond-coord ;Here's a basic dodge and move routine. It takes no arguments on the stack and returns nothing. It input is the vector variable desired-velocity. It sets engine-velocity and engine-power appropriately. ;The user should set desired-velocity to the velocity they would prefer absent any dodging. For example set desired-velocity whenever you would have set engine-velocity (or called seek-location). ;The user is also responsible for setting the shot-sensor-focus to the area where incoming shots are expected. ;See the active dodging tutorial for a detailed description of how this works. dodge-and-move: fire-shot-sensor sync shot-found if ;compute our position in a shifted and rotated coordinated system (axes) where ;the shot is at the origin and the shot is moving along the (new) x axis. ;The new y coordinate miss-coord is clearly the miss distance (positive or negative) if we sit still. ;The new x coordinate beyond-coord is how far the shot is past us (if positive) or yet to travel and still a threat (if negative). shot-relative-position shot-velocity rotate-to miss-coord! beyond-coord! beyond-coord -1 < miss-coord abs 2.5 < and and-if ;only dodge shots that will pass near us but aren't so close there's no hope dodging (also excludes shots that already past us) 0 miss-coord 0 > -1 1 ifev ;dodge velocity (in rotated coords) is on stack. ;Dodge speed is 1, i.e. accelerate as fast as we can ;Now change back to ordinary coordinates: shot-velocity rotate-from engine-velocity! else desired-velocity engine-velocity! then engine-max-power engine-power! return #end
Another way to rotate coordinates: dot and cross productsEdit
(Unlike the rest of this tutorial this section is very drafty so nonsense is likely.)
As mentioned above the side Active that introduced active dodging uses dot and cross products instead of what is described above (which was invented years after Active was). Dot and cross products are used extensively in physics and engineering so what you learn here has relevance far beyond Grobots coding. (One of the reasons why scientists often use dot and cross products rather than the techniques described above is that angles are a lot messier in 3D than in 2D whereas dot and cross products work fine in 3D.)
We'll need a little trigonometry: the definitions of sine, cosine and tangent (i.e. the SOH CAH TOA mnemonic). (These trig operations are also used internally in the built-ins
polar-to-rect, but you don't need to know that to use them so we didn't mention it.)
I don't want to reinvent the wheel, so please read pages 1-6 of Vector Calculus by Matthews now. (Don't let the "calculus" in the name scare you; there's no calculus in those pages.) I will use the notation from that book (i.e. bold italic for vectors) in what follows. If that book doesn't work for you, try reading the first three sections of another introduction. Those two have different definitions of the dot product, but don't worry--the two definitions are equivalent.Recall that the active dodging code uses two built-ins which take two vectors as arguments and return a vector. Here are the implementations discussed previously:
rotate-to: 2swap rect-to-polar 2swap angle - polar-to-rect return rotate-from: 2swap rect-to-polar 2swap angle + polar-to-rect return
Here's an equivalent implementation of
rotate-to: rect'-to-rect: ;v_x v_y x'_axis -> v_x' v_y' unitize x'_axis_unit! v! x'_axis_unit v dot ;computes v_x' x'_axis_unit v cross ;computes v_y'. returnThe grobots engine currently implements
rotate-tothis way and
rotate-fromsimilarly since it's more efficient (no trig).
One could show these implementations are equivalent directly (you'd need some trig including sum and difference formulae) but it's easier and more enlightening to show equivalence (at least at an intuitive level) by the fact that both do the coordinate rotation task.
Here's an alternate implementation of
rotate-from: ;; v_x' v_y' x'_axis -> v_x v_y unitize x'_axis_unit! v_y'! v_x'! x'_axis_unit v_x' vs* ;computes v_x x'_axis_unit negate swap ;this forms the y' axis by rotating x'_axis 90 degrees CCW v_y' vs* v+ ;computes v_y return