Farewell, ROAM aervice

The ROAM auto-flying system has closed. I did still use it every once in a while. It was a good thing in it's day.

Farewell, ROAM service, and best wishes for whatever kind of afterlife a subscription superfast autopiloting system goes to.

They should open source it.

I mumbled a bit about Wet Ikon in Cristiano's thread here:
/140/4a/108651/1.html#post1054481

As for open sourcing, I don't remember where I left the most recent version of the pathfinding code, but this is the first version.

The outline of the pathfinder that it was built in C. We start with a text file of the sim topology.

I wrote a sim_gen utility that would translate that code into more C code. That code would be compiled into a pathfinder executable directly.

The theory was that since map updates were fairly infrequent, we could compile a binary designed only to solve routing problems on a single fixed topology. So while map updates were slightly more expensive, our implementation would be rewarded with lightning fast pathfinding solutions.

The pathfinder for the first generation of ROAM was fairly simple - it was just a simple breadth-first-search algorithm. Any 1st year computer science student worth their weight in salt should be able to do it.

Later on, we went to a more slightly more sophisticated modified A* algorithm (maybe a 2nd year student would be needed ). I believe the only real modification we made was to weight it to favour straight paths over nearly-equivalent path costs with more turns.

Functionally, it was equivalent to the 1st implementation, but it was faster on more extreme cases. The real gain was that it allowed us to express deeper topological information, such as routing around problem and void sims.

Map Data:

Pretanic Isles,251904,255232
The Zone,252160,256000
Bitrate City,252672,255488
Kymeera,252672,256000
Centre Ville,252672,257536
Le Cadre,252672,258048
Transylvania,252672,258560
LaLa Land,252928,257024
Montmartre,252928,257536
Gypsy Moon,253184,253952
Nowall,253184,254976
GNO ILAND,253184,255488
Galleria City,253184,256512
SimCast,253184,258816
Asim Zahra,253440,254464
Galleria Skywalk,253440,256512
Telador Isle,253696,255488
Shomat,253696,258560
JAVA,253952,254208
Cape Destiny,254208,258560
Amaterasu,254464,254720
Luna,254464,256000
Sistiana,254464,256256
Barcola,254464,256512
Krittannia,254464,258048
Kumori,254720,254720
Grignano,254720,256256
Miramare,254720,256512
Fuchsia,254720,257792
FairChang Island,254976,254720
Gibson,254976,256000
Bonifacio,254976,256256
Dore,254976,256512
DarkWood,254976,256768
Celadon,254976,257792
Fame,255232,255488
Balance,255232,255744
Oak Grove,255232,256000
Morris,255232,256256
Ahern,255232,256512
Cayman,255232,257024
Brown,255232,257792
Argent,255232,258048
Fortuna,255488,255488
Bethel,255488,255744
Rizal|Sports,255488,256256
Lusk,255488,256512
Aqua,255488,257536
Green,255488,257792
Bisque,255488,258048
Cordova(Sandbox),255744,255232
Georgean,255744,255488
Brilliant,255744,255744
Tehama,255744,256256
Perry,255744,256512
Kissling,255744,256768
Gray,255744,257280
Blue,255744,257536
Mauve,255744,257792
Chartreuse,255744,258048
Abbotts,256000,255232
Da Boom,256000,256000
Freelon,256000,256256
Clara,256000,256512
Boardman,256000,256768
Tan,256000,257024
Plum,256000,257280
Lime,256000,257536
Mocha,256000,257792
Crimson,256000,258048
Cowell,256256,255232
Stinson,256256,255488
Immaculate,256256,255744
Ritch,256256,256000
Minna,256256,256256
Varney,256256,256512
De Haro,256256,256768
Mesede,256256,257024
Sage,256256,257280
Rose,256256,257536
Olive,256256,257792
Indigo,256256,258048
Albion,256512,254976
Noyo,256512,255232
Rodeo,256512,255488
Zoe,256512,256000
Natoma,256512,256256
Stillman,256512,256512
Tilitr,256512,256768
Solang,256512,257024
Rua,256512,257280
Teal,256512,257536
Slate,256512,257792
Magenta,256512,258048
Mavericks,256768,254720
Pomponio,256768,254976
Davenport,256768,255232
Clementina,256768,256000
Taber,256768,256256
Miru,256768,257024
Marawa,256768,257280
Hina,256768,257536
Maroon,256768,258048
Kelham,257024,254720
Palomarian,257024,254976
Bodega,257024,255232
Welsh,257024,256256
Vaoetere,257024,256768
Vari,257024,257024
Riiki,257024,257280
Papa,257024,257536
Hikuelo,257024,257792
Periwinkle,257024,258048
Deimos,257280,254720
Myrtle,257280,254976
Bolinas,257280,255232
Jessie,257280,256000
Clyde,257280,256256
Rausch,257280,256512
Marunogere,257280,256768
Quat,257280,257024
Ambat,257280,257280
Aluluei,257280,257536
Umber,257280,257792
Purple,257280,258048
Io,257536,254464
Metis,257536,254720
BonnyDoon,257536,254976
Hooper,257536,255232
Gerstle,257536,255488
Stanford,257536,256000
Hawthorne,257536,256256
Paikea,257536,256768
Nakaa,257536,257024
Tawhaki,257536,257280
Sido,257536,257536
Callisto,257792,254208
Ganymede,257792,254464
Europa,257792,254720
Phobos,257792,254976
Montara,257792,255232
Jenner,257792,255488
Federal,257792,256000
Shipley,257792,256256
Akea,257792,256768
Ku,257792,257024
Kane,257792,257280
Palulop,257792,257536
Avalon,257792,258048
Chamonix,258048,253952
Pandora,258048,254208
Atlas,258048,254464
Leda,258048,254720
Limantour,258048,255232
Gualala,258048,255488
Seacliff,258048,255744
Kiha,258048,256256
Kanaloa,258048,256768
Manua,258048,257024
Milu,258048,257280
Cortina,258304,253952
Mimas,258304,254208
Janus,258304,254464
Epimetheus,258304,254720
Baker,258304,254976
Muir,258304,255232
Amida,258304,255488
Mooaleo,258304,256256
Lie,258304,256512
Apukohai,258304,256768
Puea,258304,257024
Hiaka,258304,257280
Isere,258560,252672
Arosa,258560,252928
Kanin,258560,253184
Seefeld,258560,253440
Grindlewald,258560,253696
Davos,258560,253952
Tethys,258560,254208
Enceladus,258560,254464
Kaminari,258560,254976
Yamato,258560,255232
Gama,258560,255488
Fudo,258560,255744
Baku,258560,256000
Koleamoku,258560,256256
Ukanipo,258560,256512
Mahulu,258560,256768
Alua,258560,257024
Olopue,258560,257280
Verbier,258816,252672
Livigno,258816,252928
Bydalen,258816,253184
Anton,258816,253440
Kitzbuhel,258816,253696
Garmisch,258816,253952
Arlberg,258816,254208
Hachiman,258816,255232
Raiden,258816,255488
Daikoku,258816,255744
Kojin,258816,256000
Uzume,258816,256256
Kuula,258816,256512
Uli,258816,256768
Laka,258816,257024
Mokualii,258816,257280
Maui,258816,257536
Orelle,259072,252672
Ayas,259072,252928
Voss,259072,253184
Zermatt,259072,253440
Inari,259072,255232
Funadama,259072,255488
Benten,259072,255744
Hotei,259072,256000
Dosojin,259072,256256
Ebisu,259072,256512
Poliahu,259072,256768
Kaili,259072,257024
Ainu,259072,257280
Meribel,259328,252672
Oberstdorf,259328,252928
Wengen,259328,253184
Moritz,259328,253440
Yabune,259328,256256
Shaka,259328,256512
Butsu,259328,256768
Jarawa,259328,257280
Innu,259328,257536
Wichi,259328,257792
Degar,259328,258048
Awa,259328,258304
Valmorel,259584,252928
Toggenburg,259584,253184
Rogla,259584,253440
Shoki,259584,256512
Shinda,259584,256768
Yora,259584,257280
Semang,259584,257536
Nuba,259584,257792
Penan,259584,258048
Ordino,259840,252928
Anzere,259840,253184
Jizo,259840,256512
Kishijoten,259840,256768
Fujin,259840,257024
Kamba,259840,257280
Embu,259840,257536
Tupi,259840,257792
Sakai,259840,258048
Isora,260096,256768
Uba,260096,257024
Tenjin,260096,257280
Sedig,260096,257792
Atis,260096,258048
Tofalar,260096,258304
Kama,260096,258560
Kafiri,260352,257024
Luo,260352,257280
Dari,260352,258048
Davvi,260352,258304
Voti,260352,258560
Shona,260608,256768
Dacia,260608,257024
Tharu,260608,257280
Igbo,260608,257536
Lozi,260608,257792
Sami,260608,258048
Dusun,260608,258304
Wolof,260608,258560
Urdu,260608,258816
Tuvan,260864,257280
Furu,260864,257792
Zuni,260864,258048
Batak,260864,258304
Zazi,261120,258304

sim_gen

// Fran wuz here
// The input file format is 1 entry per line, no empty lines
//      [sim name], [getregioncorner.x], [getregioncorner.y]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Defines
// ********************************************************************************************
#define MAX_SIMS 4096                          // Maximum number of sims (at least double
                                               // the # of sims is a good for performance)

#define BUF_SIZE 4096                          // Buffer size, used for misc things
#define HASH_JUMP 137                          // Should be coprime with MAX_SIMS

const char * const leader = 
"#ifndef SIM_MAP_H\n"
"#define SIM_MAP_H\n"
"\n"
"#define MAX_SIMS %d\n"
"#define HASH_JUMP %d\n"
"struct sim_node {\n"
"   int x;\n"
"   int y;\n"
"   int neighbor[4];  // north, east, south, west\n"
"   char *name;\n"
"};\n"
"\n"
"const sim_node sim[] = {\n";
const char * const midpoint =
"\n};\n"
"\n"
"struct simNameMap {\n"
"   char *name;\n"
"   int index;\n"
"};\n"
"\n"
"const simNameMap simNameHash[%d] = {\n"
;
const char * const trailer =
"\n};\n"
"\n"
"#endif // SIM_MAP_H\n";

// Helper junk
// ********************************************************************************************

#ifdef __CYGWIN__
// cygwin doesn't implement getline. This code borrowed and fixed from the myLibC project
ssize_t getdelim(char **lineptr, size_t *n, int delimiter, FILE *fp) {
   char *p;
   int i;
   int N = 256;

   if (*lineptr)
      N = *n;
   else {
      *n = N;
      *lineptr = (char*)malloc(*n);
   }

   for(p = *lineptr, i = 0;;i++, p++) {
      *p = fgetc(fp);
      if (feof(fp)) break;

      if (*p == delimiter) {
         p++;
         break;
      }

      if ((unsigned)i >= *n) {
         (*n) += N;
         *lineptr = (char*)realloc(*lineptr, *n);
         p = *lineptr + i;
      }
   }
   *p = 0;
   if ( !i && feof(fp) )
      return EOF;
   return i;
}

ssize_t getline(char **lineptr, size_t *n, FILE *stream) {
   return getdelim( lineptr, n, '\n', stream );
}
#endif // __CYGWIN__

// Data structures
// ********************************************************************************************

struct sim_node {
   char *name;
   int x;
   int y;
   int neighbor[4];  // north, east, south, west
};

struct simNameMap {
   char *name;
   int index;
};

// Globals
// ********************************************************************************************
sim_node sim[MAX_SIMS];
int num_sims = 0;
simNameMap simNameHash[MAX_SIMS];

// Code
// ********************************************************************************************

// Warning, return code only valid until stringify is called again
char *stringify( char *s ) {
   static char buf[BUF_SIZE];
   if ( !s )
      return "0";
   else {
      sprintf( buf, "\"%s\"", s );
      return buf;
   }
} // char *stringify( char *s )

// For alphabetically ordering the sims
// Why am I sorting? I don't know either.
int sim_name_compar( const void *s, const void *t ) {
   return strcmp( ((const sim_node*)s)->name, ((const sim_node*)t)->name );
}

// returns 0 if successful, 1 otherwise
int read_sims( char *simFile ) {
   char s_buff[ BUF_SIZE ];
   char *buffer  = s_buff;
   size_t len = BUF_SIZE;
   int nReturnVal = 0;
   FILE *f = NULL;

   f = fopen( simFile, "r" );
   if ( !f ) { 
      fprintf( stderr, "Can't open file '%s'\n", simFile );
      nReturnVal = 1;
      goto cleanup;
   }

   // Grab the input file
   while ( getline(&buffer, &len, f) != EOF ) {
      char *endName, *endX, *endY;

      endName = strchr( buffer, ',' );
      if ( !endName ) {
         fprintf( stderr, "Malformed entry '%s'\n", buffer );
         nReturnVal = 1;
         goto cleanup;
      }

      sim[num_sims].name = (char *) malloc( endName - buffer + 1 );
      if ( !sim[num_sims].name ) {
         fprintf( stderr, "Out of Memory\n" );
         nReturnVal = 1;
         goto cleanup;
      }
      strncpy( sim[num_sims].name, buffer, endName - buffer );

      sim[num_sims].x = strtol( endName+1, &endX, 0 );
      if ( !endX || *endX != ',' ) {
         fprintf( stderr, "Malformed entry '%s'\n", buffer );
         nReturnVal = 1;
         goto cleanup;
      }

      sim[num_sims].y = strtol( endX+1, &endY, 0 );
      if ( !endY ) {
         fprintf( stderr, "Malformed entry '%s'\n", buffer );
         nReturnVal = 1;
         goto cleanup;
      }

      num_sims++;
   } // while file left to read

   qsort( sim, num_sims, sizeof(*sim), sim_name_compar );

 cleanup:
   if ( f )
      fclose( f );
   return nReturnVal;
} // int read_sims( char *simFile )


void findAdjacencies() {
   // Slow ass O(n2) algorithm to find adjacencies
   for ( int i=0; i<num_sims; i++ ) {
      for ( int j=0; j<4; j++ )
         sim.neighbor[j] = -1;

      for ( int k=0; k<num_sims; k++ ) {    // North
         if ( sim[k].x == sim.x && sim[k].y == sim.y + 256 ) {
            sim.neighbor[0] = k;
            break;
         }
      }
      for ( int k=0; k<num_sims; k++ ) {    // East
         if ( sim[k].x == sim.x+256 && sim[k].y == sim.y ) {
            sim.neighbor[1] = k;
            break;
         }
      }
      for ( int k=0; k<num_sims; k++ ) {    // South
         if ( sim[k].x == sim.x && sim[k].y == sim.y - 256 ) {
            sim.neighbor[2] = k;
            break;
         }
      }
      for ( int k=0; k<num_sims; k++ ) {    // West
         if ( sim[k].x == sim.x-256 && sim[k].y == sim.y ) {
            sim.neighbor[3] = k;
            break;
         }
      }
   }
} // void findAdjacencies()


// Returns a 24-bit hash
int hash( char *s ) {
   int hash = 0;
   do {
      // A convenient prime slightly greater than 2^24
      hash = ( hash*257 ^ hash*3 ^ *s ) % 16777289;
   } while( *(++s) );

   hash &= 0xffffff;
   return hash;
}

// Returns # of collisions
int hashInsert( char *name, int index ) {
   int pos = hash( name ) % MAX_SIMS;
   int collisions = 0;

   while ( simNameHash[pos].name ) {
      pos = (pos + HASH_JUMP) % MAX_SIMS;
      collisions++;
      if ( collisions >= MAX_SIMS ) {
         fprintf( stderr, "Redefine MAX_SIMS to be a larger number\n" );
         exit(1);
      }
   }
   
   simNameHash[pos].name  = name;
   simNameHash[pos].index = index;

   return collisions;
}

void makeHashMap() {
   int collisions = 0;;

   for (int i=0; i<MAX_SIMS; i++) {
      simNameHash.name  = 0;
      simNameHash.index = -1;
   }

   for (int i=0; i<num_sims; i++) {
      collisions += hashInsert( sim.name, i );
   }

   fprintf( stderr, "%d hash collisions\n", collisions );
} // void makeHashMap()


int main( int argc, char*argv[] ) {
   int nReturnVal = 0;

   if ( argc != 2 ) {
      fprintf( stderr, "Usage: %s [sim data file]\n", argv[0] );
      nReturnVal = 1;
      goto cleanup;
   }

   nReturnVal = read_sims( argv[1] );

   findAdjacencies();

   makeHashMap();

   printf( leader, MAX_SIMS, HASH_JUMP );

   // Print out the list of all the sims, with adjacencies
   printf( "   /*%4d */    {%6d,%6d, {%4d,%4d,%4d,%4d}, \"%s\"}", 0, sim[0].x, sim[0].y,
           sim[0].neighbor[0], sim[0].neighbor[1], sim[0].neighbor[2], sim[0].neighbor[3],
           sim[0].name );
   for ( int i=1; i<num_sims; i++ ) {
      printf( ",\n   /*%4d */    {%6d,%6d, {%4d,%4d,%4d,%4d}, \"%s\"}", i, sim.x, sim.y,
              sim.neighbor[0], sim.neighbor[1], sim.neighbor[2], sim.neighbor[3],
              sim.name );
   }

   printf( midpoint, MAX_SIMS );

   // Now print out the hash table to index names
   printf( "{ %s, %d }", stringify(simNameHash[0].name), simNameHash[0].index );

   for( int i=1; i<MAX_SIMS; i++ ) {
      printf( ",\n{ %s, %d }", stringify(simNameHash.name), simNameHash.index );
   }

   printf( trailer );

 cleanup:
   return nReturnVal;
} // int main

pathfinder

// Fran wuz here
#include <stdio.h>
#include <string.h>
#include "sim_map.h"

// Constants
// ********************************************************************************************
const char * const cardinals[] = { "North", "East", "South", "West", "Start" };

// Data structures
// ********************************************************************************************
struct pathList {
   int length;
   int sim[MAX_SIMS];
   unsigned char direction[MAX_SIMS];
};

// Code
// ********************************************************************************************

// Finds the path between 2 sims, breadth first search
int search( int src, int dst, pathList *path ) {
   bool traversed[MAX_SIMS];
   int  from[MAX_SIMS];
   int  direction[MAX_SIMS];
   int  buf1[MAX_SIMS];
   int  buf2[MAX_SIMS];
   int *curr           = buf1;                 // List of nodes in current breadth
   int *next           = buf2;                 // list of nodes in next breadth
   int *tmp;
   int  numCurBreadth = 1;
   int  numNextBreadth = 0;
   int  iterations = 1;

   if ( src == dst ) {                         // that was easy
      path->sim[0] = src;
      path->length = 0;
      return 1;
   }

   bzero( traversed, sizeof(traversed) );      // Initialize
   traversed[src] = true;
   curr[0] = src;
   numCurBreadth = 1;
   direction[src] = 4;

   while ( numCurBreadth ) {
      for ( int i=0; i<numCurBreadth; i++ ) {
         for ( int j=0; j<4; j++ ) {
            if ( sim[curr].neighbor[j] != -1 && !traversed[sim[curr].neighbor[j]] ) {

               // Set traversal information
               traversed[sim[curr].neighbor[j]] = true;
               from[sim[curr].neighbor[j]] = curr;
               direction[sim[curr].neighbor[j]] = j;
               next[numNextBreadth++] = sim[curr].neighbor[j];

               if ( sim[curr].neighbor[j] == dst ) {
                  int curNode = dst;
                  path->length = iterations;
                  while ( iterations >= 0 ) {
                     path->direction[iterations] = direction[curNode];
                     path->sim[iterations--] = curNode;
                     curNode = from[curNode];
                  }
                  return 1;
               } // if we found a solution
            } // if we haven't traversed this sim before
         } // for all neighbors
      } // for all nodes in current breadth

      tmp = curr;                              // Make the next breadth the current
      curr = next;                             // Swap pointers & stuff
      next = tmp;
      numCurBreadth = numNextBreadth;
      numNextBreadth = 0;
      iterations++;
   } // while nodes left to search

   return 0;
}

// Returns a 24-bit hash
int hash( char *s ) {
   int hash = 0;
   do {
      // A convenient prime slightly greater than 2^24
      hash = ( hash*257 ^ hash*3 ^ *s ) % 16777289;
   } while( *(++s) );

   hash &= 0xffffff;
   return hash;
}

// returns the node number, -1 if unfound
int hashLookup( char *name ) {
   int pos = hash( name ) % MAX_SIMS;

   while ( simNameHash[pos].name ) {
      if ( !strcmp( name, simNameHash[pos].name ) ) {
         return simNameHash[pos].index;
      }
      pos = (pos + HASH_JUMP) % MAX_SIMS;
   }
   
   return -1;
}

int main( int argc, char *argv[] ) {
   int nReturnVal = 0;
   int srcSim;
   int dstSim;
   int result;
   pathList path;

   if ( argc != 3 ) {
      fprintf( stderr, "Usage: %s [source sim] [destination sim]\n", argv[0] );
      nReturnVal = 1;
      goto cleanup;
   }

   srcSim = hashLookup( argv[1] );
   if ( srcSim < 0 ) {
      fprintf( stderr, "Unable to find sim '%s'\n", argv[1] );
      nReturnVal = 1;
      goto cleanup;
   }
   dstSim = hashLookup( argv[2] );
   if ( dstSim < 0 ) {
      fprintf( stderr, "Unable to find sim '%s'\n", argv[2] );
      nReturnVal = 1;
      goto cleanup;
   }

   printf( "Path from %s -> %s\n", argv[1], argv[2] );

   result = search( srcSim, dstSim, &path );
   if ( !result )
      printf( "Unable to find path\n" );
   else {
      for ( int i=0; i<=path.length; i++ ) {
         printf( "%s) %s\n", cardinals[path.direction], sim[path.sim].name );
      }
   }
 cleanup:
   return nReturnVal;
}

I love ROAM; I don't think I can understate the influence (it had on me personally, anyway) it had to nudge for direct teleportation--something sometimes taken for granted today.

I still wear it on my back and I don't use the "teleport" features but I use the flight accelerator and the "Super Jedi Jump".

Good times.

Massive respect to Fran and Rathe... you guys are cornerstones of Second Life creativity.

I did find Yours Torley in Friesland when I was building there (and EXAKT house what else?) and sent it back to you.. be more carefull with your things - please))))

LOL

/Tina - Still no Cofee... arghhhh...

Thanks Frans!

I never used ROAM. Out of curiosity though, why is it closing down?

- Newfie

Does there happen to be a complete open source? i like every feature of the roam! i used it for alittle bit and i loved it, sad it's gone.

I'd like one that flies at a lower altitude, low enough to be able to see the terrain better. It could go slower (not slow, just not as fast) since it would just be giving you an auto-pilot tour.