==============================================================================
The World of a C++Robot Richard Rognlie <rrognlie@gamerz.net>
==============================================================================

One of the problems people have been having with the C++Robots combat simulator has been a misunderstanding of the robot's eye view of the arena and the way the robots actually work. Here's the scoop:

The arena is 10k units wide by 10k units high. (100 units = 1 meter). The
arena is surrounded by a forcefield through which robots may not pass. It
acts like a wall for robots, but cannon shots pass right through (as do
explosion effects).

Directions are specified in degrees (not radians like the "normal" C math
functions). 0 is due east. 90 due north. 180 due west. 270 due south. All
functions that use directions work in modulo 360, so the directions -45, 315,
695, etc. are all equivalent.

( 0,9999)                         (9999,9999)
+------------------------------------------+
|                      90                  |
|                      |                   |
|               180 ---+--- 0,360          |
|                      |                   |
|                     270                  |
+------------------------------------------+
( 0, 0)                             (9999, 0)

Each C++Robot is really a simulated Sun SPARC. When a C++Robot is received,
it is compiled by the GNU C++ compiler down to Sun SPARC object code. The
simulator loads each C++Robot into memory, and randomly positions the robot in
the arena. The simulator then begins executing the C++Robots in 100 CPU cycle
timeslices. Each timeslice simulates 1 second. This is a *really* slow
SPARC! A 2 player bout that fights to a draw simulates 30 minutes of
C++Robots activity, but, in reality, takes about 3 minutes of real time.

If during the execution of a robot's timeslice, it encounters a call to
drive(), scan() or cannon(), the call is immediately executed, but any
remaining CPU cycles left in that robot's current timeslice are lost.
Therefore, an average call to scan() takes ~50 CPU cycles. [Assuming random
distribution of scan() invocation times...]

Once all robots have completed their timeslices, the simulator updates their
positions in the arena and checks to see if any cannon shots have exploded,
etc. This means that the result of scan() is already out of date when your
robot continues execution. [scan() returns a result based on the other
robot's position during the previous timeslice, your timeslice then gets
suspended, and when it resumes, it is a new timeslice. The other robot may
have moved up to 100 units. Plus your robot may have moved up to 100 units,
as well.]

This execution loop continues until one robot is destroyed (or both are
destroyed simultaneously) or time runs out.

==============================================================================
C++Robots Strategies Richard Rognlie <rrognlie@gamerz.net>
==============================================================================

There are as many C++Robot strategies are there are C++Robots! Some robots
can be very simple, others quite complex. It all depends on your robot's
goal.

My robot, tracker, has been quite successful with very little modification
since the creation of the C++Robots hill. Its algorithm was originally:
1) Scan for a target. Move towards and shoot at any target found.
2) If you lose the target, back up the scan a few degrees and start
over again.
This algorithm worked quite well for the first few weeks of the hill, but he
was slowly replaced by other smarter robots. By tweaking his scan arc, he
bounced back up the hill temporarily, but eventually slid off again. *sigh!*

It was time to update the algorithm again. Apparently, the problem was that
the tracker would move towards his opponents and they would lock on him as
well. This wouldn't do! So, I adopted (stole) the movement algorithm from
susan_unit (one of the early leader's of the C++Robots hill). And that was to
move about in a box pattern. So, tracker's movement routines are independent
of its targeting routines. The current algorithm is:
1) Move around the arena in a box pattern. Full speed. staying
about 2000 units inside from the wall.
2) Scan for a target, and shoot it. If you had seen a target, and
have lost sight, back up the scan a bit and continue scanning.


==============================================================================
The Strategy Behind Crawl Morten Piil <blikror@inet.uni-c.dk>
==============================================================================

The current C++Robots King of the Hill (All Hail the King!) writes:

1. Don't move, it spoils your aim, and it's more difficult to keep track of
the opponent.

2. Move! Crawl grew out of "Aim" my previous 'bot witch didn't move,
Aim/Crawl actually got a bit better after I started to creep forward
against robots too far away to shoot. I had a lot of ties in my score,
crawling slowly forward reduced these ties and converted them into wins!

3. Adjust the scanning angle according to the distance of the enemy, I use a
formula:
ScanArg = 5730/d + 1;
where d is the distance of the enemy. This is derived from beeing able to
keep up with a robot traveling at full speed at 90 degrees across my line
of sight.

4. If his angular position doesn't change, I actually decrease my scanning
angle to get a better shot (at the possibility of losing track of the
'bot.)

5. Remember his last position, and use this information to estimate where he
will be at impact time of own shot. For estimation I use a polar
coordinate system, and linear extrapolation.
d = d1 + (d1-d2) * dt / (t1-t2);
v = v1 + (v1-v2) * dt / (t1-t2);
where d is the distance, v is the angle, t is the time, 1 refers to last
position, 2 to the one before, and dt is the time from the last
observation till impact of the shell (see 8). Polar extrapolation is
inaccurate at close distances, and I've noticed that Chris Fodor uses the
absolute coordinates for his extrapolation, but the calculations are a bit
more complicated and use too much time to fit in a single cycle of the
simulator (for me at least).

6. Keep cannon as many cannon shots in the air as possible. Cannon shot
travel at approx. 100 m/s. I use an algorithm that says above d=5200
units I fire one shot. above 4000 I fire 2 shots, below 4000 I fire 3
shots. The 'bot Rikke (by John Schmidt, not me!) uses an array to keep
track of his shots, so he can keep exactly 3 shots in the air at all times
(when he has track of the enemy 'bot).

7. You can actually harm a bot that's 7399 units away, at impact time, but
you must use 7000 as the argument to cannon (otherwise Richard's combat
engine doesn't fire !)

8. KNOW YOUR WORLD, When I started to play this game, I had a mental image of
the world these 'bots live in, you probably has one as well, and so does
Richard Rognlie. These images were *NOT* the same. I requested a copy of
the source code for the combat engine from Richard. (Interesting reading
BTW!) I had this notion of a smooth running time where a robot would be
moving constantly forward within the timeslices of the simulator, because
of this I had a routine for calculating the (relative) impact time of a
cannon shot:
dt = calctime + d/10 + time() - t1;
where calctime was the time it took to calculate the new position (later),
d/10 was the flight time (in clockcycles) for the cannonshot, and time() -
t1 was the time from now till my last observation of the enemy.

Now Richard has a different point of view: Robots only move and
cannonshots only land between timeslices. This means that when you see a
robot with scan() the information is already one timeslice old. When you
fire a cannon shot it *MAY* travel up to 150 meters in 0.01 seconds thats
15,000 m/s, not 100 m/s. After this I changed my robot to calculate in
whole timeslices, and used Richards formula for finding the impact time of
a cannon() shot:
dt=((d+500)/1000); if (!dt) dt=1; dt+=t++;
Thats when Chris Fodors "susan_unit" stopped being number one. So check
your world against Richard's you may be suprised.

9. Use the trace facility, i.e.
c++robots challenge your_bot's_name bot_on_hill's_name
to run your robot against a bot on the hill. Observe the timing of your
calls to scan, cannon and drive. Check that they fit in your timeslice,
and use your timeslice. Don't waste CPU cycles (crawl actually uses up to
98-99 % of the slice in the tight places.

10. Check that all your cannon shots go off.

==============================================================================
C++Robots Insights Chris Fodor <cfodor@ra.megatek.com>
==============================================================================

Try to put external commands near the end of 100 cycles (so that you don't
lose to many instructions).

Staying on the move by limitting turning makes you a harder target.
(Actually, it makes it easier for "trackers". Zigzagging makes it harder for
"trackers".)

The way my best bot has worked is to stay on the diagonal, and use actual
geometry to predict the position of the enemy bot when the bullet reaches it
and fire at that position.

My second best bot (daisy) worked by chasing the robot and assuming that it
was behind the other robot when it fired. (i.e., both traveling at 100)

==============================================================================
C++Robots Tradeoffs James B. Reed <jbreed@doink.b23b.ingr.com>
==============================================================================

When I wrote my robots, I found that I could get a pretty good grip on
the different strategies by issuing challenges and paying attention to
what the other robot did. After observing and thinking about it awhile,
several tradeoffs and basic considerations became apparent.

1. Moving targets may be harder to locate and hit.

2. Targets that change direction and/or speed may be even harder to hit.

3. It's easier to aim when you're sitting still or at least moving
consistently.

4. If you don't understand polar coordinates, you'll have a hard time
targetting accurately.

5. Every calculation takes some amount of time, so performing more
calculations for more accurate targetting means you'll get to shoot less
often.

6. It's easy to know the distance to the target, the scan resolution
specifies the uncertainity in direction. That uncertainity can be quite
large for a distant target.

7. Luck in the starting position can affect the outcome (I assume that's why
the robots face each other 5 times).

By empasizing different considerations, you can devise different strategies.

For example, pointnshoot emphasizes point 2 by changing direction every time
it detects that it's been hit. That makes it a more challenging target to
track, but it also makes it more difficult for pointnshoot to track its
opponent.

hereicome emphasizes point 6 by driving straight toward the target as soon as
it's located. That reduces the uncertainity by reducing the distance. It
also emphasizes point 5 by keeping its calculations to a minimum so it can
shoot more often.

I know that there are some robots that spend a lot of effort in locating the
target and shooting accurately. A well implemented intelligent robot is more
likely to place high up on the chart, but they can still get beat on occasion
by a fast-but-stupid robot.