============================================================================== The World of a C++Robot Richard Rognlie ============================================================================== 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 ============================================================================== 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 ============================================================================== 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 being able to keep up with a robot travelling 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 that's 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++; That's when Chris Fodors "susan_unit" stopped being number one. So check your world against Richard's you may be surprised. 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 ============================================================================== 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 limiting 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 travelling at 100) ============================================================================== C++Robots Tradeoffs James B. Reed ============================================================================== 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 targeting accurately. 5. Every calculation takes some amount of time, so performing more calculations for more accurate targeting means you'll get to shoot less often. 6. It's easy to know the distance to the target, the scan resolution specifies the uncertainty in direction. That uncertainty 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 emphasizing 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 uncertainty 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.