Build a better robot: Part 1.

Area searching

First cut

The most important initial objective for your robot is to find your opponent ... fast!

The canonical way to do this is a fast sweep around scanning 20 degrees every turn. To implement this I shall use an array of offsets. You may use a for loop or some other algorithm to implement it but array lookups are fast, fast, fast at runtime which is when it counts.

BEGIN
#include "robots.h"
main()
{
  // Search table
  DEGREE search_off[18] = {0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340};
  int    search_idx     = 0;

  // Setup flag to indicate target not seen yet.
  int contact = 0;

  // Misc working variables.
  int    seen_range;

  // Start of search loop.
  while (contact == 0)
  {
    // Have a look...
    seen_range = scan( search_off[ search_idx ], 10 );
    if ( seen_range > 0 )
    {
      // If we saw something scan returns the range.
      printlog("Contact at range %5d bearing %3d +/- 10 degrees", seen_range, search_off[ search_idx ]);
      contact = 1;
    }
    else
    {
      // If we saw nothing check next direction.
      search_idx = ++search_idx % 18;
    }
  }
  contact = drive(0, 0); // Dummy call to anything to allow printlog time to display.
}
END

This is your basic search algorithm. I was, at this point, going to write about how this algorithm was not particularly efficient and back up my comments with some statistics from tests against the hill. However when I ran the tests the demo algorithm had a significant advantage against 46% of opponents and a significant disadvantage against only 38% of opponents. I am now expecting the final algorithm to have a a significant advantage over most of the hill robots.

Improving the efficiency

Now think about the situation where your robot starts way off in a corner. In the worst case the scan spends a lot of time closely examining nearby walls rather than the vast open vistas where your opponent is probably cranking up its first shot. What you would really like to do is perform the scan that will cover the greatest area first then scan other directions in order of decreasing area.

One way of doing this is to locate the corner of the arena furthest from your robot and start scanning in that direction. Slightly less optimal but way faster to do this is to first scan in the direction of the centre of the arena. Then in both cases scan the areas to either side of the initial scan and so on until all 360 degrees are covered or your target is found.

The simplest way to do this is to use the following sequence of scan offsets:

0, +20, -20, +40, -40, +60, -60, +80, -80, +100, -100, +120, -120, +140, -140, +160, -160, +180

A similar but alternative sequence is:

+10, -10, +30, -30, +50, -50, +70, -70, +90, -90, +110, -110, +130, -130, +150, -150, +170, -170

Which of these you choose will depend mostly on the nature of your robot's targeting scan. For this exercise we will use the second option.

BEGIN
#include "robots.h"
main()
{
  // Search table
  DEGREE search_off[18] = {10, -10, 30, -30, 50, -50, 70, -70, 90, -90, 110, -110, 130, -130, 150, -150, 170, -170};
  int    search_idx     = 0;

  // Setup my current location
  int my_x = loc_x();
  int my_y = loc_y();

  // Setup dummy target location pointing at centre of field.
  int seen_x = 5000;
  int seen_y = 5000;

  // Which direction is centre of field
  DEGREE seen_dir = atan2( seen_y - my_y, seen_x - my_x);

  // Setup flag to indicate target not seen yet.
  int contact = 0;

  // Misc working variables
  DEGREE scan_dir = 0;
  int    seen_range;
  
  while (contact == 0)
  {
    scan_dir = seen_dir + search_off[ search_idx ];
    seen_range = scan( scan_dir, 10 );
    if ( seen_range > 0 )
    {
      printlog("Contact at range %5d bearing %3d +/- 10 degrees", seen_range, scan_dir);
      contact = 1;
    }
    else
    {
      search_idx = ++search_idx % 18;
    }
  }
  contact = drive(0, 0); // Dummy call to anything to allow printlog time to display.
}
END

When I sent this algorithm up against the hill it had a significant advantage over 68% of its opponents and a significant disadvantage against only 18%. I expect to see new versions of a number of robots real soon now. 8-)

Things to experiment with.

Try varying the alternation of right and left scan offsets.

Try asymmetrical scan patterns.

Set up a table of asymmetrical scan sequences and index into it depending on your start location in the arena.

If you find that your targets are slipping through your scan pattern try using 20 steps spaced 18 degrees apart rather than the 18 steps spaced 20 degrees apart. My robot minim uses this kind of pattern.

Things to remember.

Indexing into a table is faster that calculating a value.

Initial scans should always be at maximum width.

Try and scan the directions that cover the greatest area first.

Try and scan the directions adjacent to areas you have recently scanned to minimise the chance that your target will move from an unscanned area to one that you have already scanned.