// botconnect1.c MR Jun 2001 // #include #include #include #include #include #include "bool.h" #include "byte.h" #include "int2char.h" #include "rand.h" #include "phmap1.h" //---------------------------------------------------------------------------- // General-purpose funcs //---------------------------------------------------------------------------- void fatal( const char * pmsg ) { fprintf( stderr, "botconnect1 fatal: %s\n", pmsg ); exit( -1 ); } //---------------------------------------------------------------------------- // Data structures for administration of s-bot states and positions //---------------------------------------------------------------------------- #define N_BV 16 // bv1 is in [ 0, N_BV ). typedef struct { // Position & direction: // ~~~~~~~~~~~~~~~~~~~~~ int x, y; //position on chessboard int dirn; //direction, in [0,3) // Programming in brain of s-bot (table of "prio" values): // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int bv1; // Other state variables of s-bot: // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int ic; int iclamp; //ix of s-bot that clamps me (-1 if none). } sb_t; //S-bot typedef struct { int isb; //Index of s-bot in Gasb[] array, or -1 if empty. } sq_t; //Chessboard square typedef struct { //S-bot collection: #define SBMAX 64 sb_t asb[SBMAX]; int nsb; //Chessboard: #define CBXMAX 30 #define CBYMAX 20 sq_t aasq[CBXMAX][CBYMAX]; int nsqx; int nsqy; //Pheromone map (used for internal calculations) int phmap[ CBXMAX * CBYMAX ]; } w_t; //World //---------------------------------------------------------------------------- // Direction data structures/funcs // Chessboard position/bounds checking funcs //---------------------------------------------------------------------------- const char DIRN_CHAR[4] = { '>', 'V', 'nsb ) ) { return NULL; } return pw->asb + isb; } _bool w_sqisempty( const w_t * pw, int ix, int iy ) { assert( inboard( ix, iy, pw->nsqx, pw->nsqy ) ); return ( pw->aasq[ix][iy].isb == -1 ); } _bool w_botlookfwd( const w_t * pw, int isb, int * pfx, int * pfy, int * pfisb ) // Examine the square in front of s-bot 'isb'. // If that square is inside the chessboard, then return 1, // if not, then return 0. // Set (*pfx,*pfy) to the coords of the square in front // of s-bot 'isb' (which may be outside the chessboard). // If the square is inside the chessboard and occupied by // another s-bot, then set *pfsib to ix of that s-bot; set // it to -1 otherwise. { const sb_t * psb; assert( 0 nsb ); psb = pw->asb + isb; oneforward( pfx, pfy, psb->x, psb->y, psb->dirn ); if ( ! inboard( *pfx, *pfy, pw->nsqx, pw->nsqy ) ) { *pfisb = -1; return 0; } *pfisb = pw->aasq[*pfx][*pfy].isb; // -1 if square is empty. return 1; } void w_pickupsbot( w_t * pw, int isb ) // Remove s-bot 'isb' from the chessboard // (but keep it in the asb[] array). { int ix = pw->asb[isb].x; int iy = pw->asb[isb].y; pw->aasq[ix][iy].isb = -1; } void w_putinsbot( w_t * pw, int isb, int ix, int iy ) // Put s-bot 'isb' on empty square (ix,iy). { assert ( w_sqisempty( pw, ix, iy ) ); pw->aasq[ix][iy].isb = isb; pw->asb[isb].x = ix; pw->asb[isb].y = iy; } //---------------------------------------------------------------------------- // (De-)Initialization of w_t data structure //---------------------------------------------------------------------------- const char * w_init( w_t * pw, int wx, int wy, //chessboard size int nsb ) //# of s-bots // Return err.msg. on failure, NULL if OK. { int isb; int ix, iy; assert ( wx > 0 && wy > 0 && nsb > 0 ); if ( wx > CBXMAX ) { return "wx > CBXMAX"; } if ( wy > CBYMAX ) { return "wy > CBYMAX"; } if ( nsb > SBMAX ) { return "nsb > SBMAX"; } // Clear chessboard for ( ix = 0; ix aasq[ix][iy].isb = -1; } } pw->nsqx = wx; pw->nsqy = wy; // Put in randomly initialized s-bots in random positions for ( isb = 0; isb 1000 ) { return "init trouble: too may s-bots on too " "small chessboard"; } //init direction pw->asb[isb].dirn = n_rand( 4 ); //init s-bot contents/values pw->asb[isb].bv1 = n_rand( N_BV ); pw->asb[isb].ic = isb; pw->asb[isb].iclamp = -1; //put s-bot in empty square w_putinsbot( pw, isb, ix, iy ); } pw->nsb = nsb; return NULL; //success } //---------------------------------------------------------------------------- // Aux funcs to interpret input smell to s-bot //---------------------------------------------------------------------------- // // w_neighborGetSmell(): // // Look at the neighbour square of square of s-bot 'isb' in the direction // 'dirnRel' *RELATIVE* to where the s-bot is oriented: // dirnRel = 0 means forward, // dirnRel = 1 means right // dirnRel = 2 means backward // dirnRel = 3 means left. // // The neighbour square is first examined as to whether it's a "valid" // square; return 1 if it's valid, 0 if not. The square is not valid if // it's outside the chessboard. The square is not valid is it's occupied // by a non-smell-emitting s-bot. The square is valid if it's empty or // if it's occupied by a smell-emitting s-bot. Squares containing a // smell-emitting s-bot are recognized from their having the value iPh = // 0 in the pheromone map. // This definition of a "valid square" makes that s-bots that base their // action upon this function walk towards smell-emitting s-bots and avoid // squares containing non-smell-emitting s-bots. // // If the square is "valid", then set *piPh to the pheromone level in // that square (and to INT_MAX if there's no pherom.emitter on the // chessboard) and return 1. // If the square is not "valid", then set *piPh to INT_MAX and // return 0. // The value written to *piPh is always >= 0. // _bool w_neighborGetSmell( const w_t * pw, int isb, int dirnRel, int * piPh ) { const sb_t * psb; int ix, iy; int iPh; assert( 0 nsb ); // Determine coords (ix,iy) of the square to examine psb = pw->asb + isb; oneforward( &ix, &iy, psb->x, psb->y, ( psb->dirn + dirnRel ) % 4 ); // Check whether square is in board if ( ! inboard( ix, iy, pw->nsqx, pw->nsqy ) ) { *piPh = INT_MAX; return 0; } // Get pheromone level iPh = phmap_getdist( pw->phmap, pw->nsqx, pw->nsqy, ix, iy ); if ( iPh == -1 ) { iPh = INT_MAX; } assert( iPh >= 0 ); // Exclude square occupied by non-pheromone emitting s-bot if ( pw->aasq[ix][iy].isb != -1 && //occupied by s-bot iPh != 0 ) //not a pheromone source { *piPh = INT_MAX; return 0; } *piPh = iPh; return 1; } _bool GLOB_n_when_no_pherom = 1; // No move ('n') when bot senses no // pheromone emitter. // // w_botTrackSmell(): // // Look at the neighbour squares of s-bot 'isb' that are "valid", with // "valid" in the sense/definition of the function 'w_neighborGetSmell()'. // Return 'f' if the square forward is valid and if its pherom.concentr. // value is the highest of all the valid neighb. squares. I.e. fwd and // left valid and equal max. ph.conc. in both returns 'f'. // ( Note: "highest ph.conc." means that the distance to nearest // ph-emitter is smallest. ) // Return 'L' or 'R' when the neighbour square to the left or right, // respectively, of the s-bot is valid and contains the max. pherom.conc. // value of all the valid neighbour squares. I.e. return 'R' if only // right and back are valid and both have equal ph.conc. // Return '?' if both the left and right square are valid and have the // max. and equal ph.conc. // Return 'b' if the square behind is valid and has a ph.conc. greater // than any other valid neighbour square. // Return 'n' if there's no valid neighbour square. // char w_botTrackSmell( const w_t * pw, int isb ) { #define FWD 0 #define RIGHT 1 #define BACK 2 #define LEFT 3 _bool ok[4]; int iph[4]; int i; _bool oneOK = 0; int iph_best = INT_MAX; // Get input smell values for ( i = 0; i asb[isb] ); fprintf( fp, "%02d: x=%02d y=%02d dirn='%c' c=%02d " "TS=%c " "bv=%c ic=%02d\n", isb, psb->x, psb->y, getDirnChar( psb->dirn ), psb->iclamp, w_botTrackSmell( pw, isb ), int2char( psb->bv1 ), psb->ic ); } void w_fprint( FILE * fp, const w_t * pw ) { int isb; fprintf( fp, "nsb = %d\n", pw->nsb ); for ( isb = 0; isb nsb; isb++ ) { w_fprintsbot( fp, pw, isb ); } } //---------------------------------------------------------------------------- // Stdio drawing funcs //---------------------------------------------------------------------------- void w_fdraw( FILE * fp, const w_t * pw, int isb_hi ) // S-bot to highlight; -1 for none. { int ix, iy; char nextBr = 0; for ( iy = 0; iy nsqy; iy++ ) { for ( ix = 0; ix nsqx; ix++ ) { char c; _bool hi = 0; if ( w_sqisempty( pw, ix, iy ) ) { c = '.'; } else { int isb = pw->aasq[ix][iy].isb; int dirn = pw->asb[isb].dirn; c = getDirnChar( dirn ); if ( isb == isb_hi ) { hi = 1; } } if ( hi ) { fprintf( fp, "[%c", c ); nextBr = 1; } else if ( nextBr ) { fprintf( fp, "]%c", c ); nextBr = 0; } else { fprintf( fp, " %c", c ); } } if ( nextBr ) { fprintf( fp, "]" ); nextBr = 0; } fprintf( fp, "\n" ); } } //---------------- void stamp_clear( char aas[5][3] ) { int i, j; for ( i = 0; i phmap, pw->nsqx, pw->nsqy, ix, iy ) ); } void stamp_addbot( char aas[5][3], const w_t * pw, int isb, _bool show_isb, _bool show_ic, _bool show_bv1, _bool highlight ) { const sb_t * psb = &( pw->asb[isb] ); aas[2][1] = ( show_isb ? int2char( isb ) : 'O' ); switch ( psb->dirn ) { case 0: aas[4][1] = aas[3][1] = '-'; break; case 1: aas[2][2] = '|'; break; case 2: aas[0][1] = aas[1][1] = '-'; break; case 3: aas[2][0] = '|'; break; } if ( psb->iclamp != -1 ) { aas[1][0] = '`'; } if ( show_ic ) { aas[3][0] = int2char( psb->ic ); } if ( show_bv1 ) { aas[3][2] = int2char( psb->bv1 ); } if ( highlight ) { aas[0][0] = aas[4][0] = aas[4][2] = aas[0][2] = '*'; } } static _bool GLOB_fdrawbig_showpherom = 0; static _bool GLOB_fdrawbig_showisb = 1; static _bool GLOB_fdrawbig_showic = 1; static _bool GLOB_fdrawbig_showbv1 = 0; void w_fdrawBig( FILE * fp, const w_t * pw, int isb_hi ) // S-bot to highlight; -1 for none. { int ix, iy; int line; for ( ix = 0; ix nsqx; ix++ ) { fprintf( fp, "._____" ); } fprintf( fp, ".\n" ); for ( iy = 0; iy nsqy; iy++ ) { for ( line = 0; line nsqx; ix++ ) { char aas[5][3]; int icol; stamp_clear( aas ); if ( GLOB_fdrawbig_showpherom ) { stamp_addpheromone( aas, pw, ix, iy ); } if ( ! w_sqisempty( pw, ix, iy ) ) { int isb = pw->aasq[ix][iy].isb; stamp_addbot( aas, pw, isb, GLOB_fdrawbig_showisb, GLOB_fdrawbig_showic, GLOB_fdrawbig_showbv1, ( isb == isb_hi ) ); } for ( icol = 0; icol ic == fisb ) { pfsb->iclamp = -1; pfsb->ic = fisb; //reset } // Execute movement n/f/L/R/s switch ( action ) { case 'l': //Turn left case 'L': case 'r': //Turn right case 'R': //my turn un-clamps the bot I'm clamping if ( pfsb != NULL && pfsb->iclamp == isb ) { pfsb->iclamp = -1; pfsb->ic = fisb; //reset } //do the turn switch ( action ) { case 'l': //Turn left case 'L': psb->dirn = ( psb->dirn + 3 ) % 4; break; case 'r': //Turn right case 'R': psb->dirn = ( psb->dirn + 1 ) % 4; break; } break; case 'f': //Go one step forward if possible if ( ! fInBoard ) { break; } //dest. square not in board if ( fisb != -1 ) { break; } //dest. square not empty //move s-bot w_pickupsbot( pw, isb ); w_putinsbot( pw, isb, fx, fy ); //the move un-clamps me psb->iclamp = -1; psb->ic = isb; //reset break; case 's': //Swap stuff into bot in front of me if ( ! fInBoard ) { break; } //dest. square not in board if ( fisb == -1 ) { break; } //dest. square empty if ( pfsb->iclamp != isb ) { break; } //I'm not clamping him (he's prolly // clamped by someone else) pw->asb[fisb].ic = pw->asb[isb].ic; pw->asb[fisb].bv1 = pw->asb[isb].bv1; break; }//switch // Examine what's in front of me. fInBoard = w_botlookfwd( pw, isb, &fx, &fy, &fisb ); pfsb = getpsb( pw, fisb ); if ( pfsb != NULL && pfsb->iclamp == -1 ) //someone in front // of me who's not yet clamped { //don't clamp someone with same ic if ( pfsb->ic == psb->ic ) { return; } #if 0 //don't clamp someone who's clamping me if ( psb->iclamp == fisb ) { return; } #endif pfsb->iclamp = isb; } } void w_movebot( w_t * pw, int isb, char action ) { sb_t * psb; int fx, fy; // Coords of square in front of me. int fInBoard; // 1 if square in front of me is inside chessboard. int fisb; // Ix of s-bot in front of me, -1 if none. sb_t * pfsb; char orAction; // ( Terminology note: "Me" = s-bot 'isb'. ) assert( 0 nsb ); psb = pw->asb + isb; // Examine what's in front of me. fInBoard = w_botlookfwd( pw, isb, &fx, &fy, &fisb ); pfsb = getpsb( pw, fisb ); if ( action == 'A' || action == 'a' ) { // Choose motor action 'q' or 'Q' according to value // of "bv1". // bv1 in [ 0, N_BV ). // // bv1 == 0: always choose 'q'. // bv1 == maximum (= N_BV - 1): always choose 'Q'. action = 'q'; if ( n_rand( N_BV - 1 ) asb[isb].bv1 ) { action = 'Q'; } } if ( action == 'q' ) { //action = ( ( fisb != -1 ) ? 'n' : 'p' ); action = 'p'; if ( pfsb != NULL && pfsb->iclamp == isb ) { action = 'n'; } } if ( action == 'Q' ) { //action = ( ( fisb != -1 ) ? 's' : 'P' ); action = 'P'; if ( pfsb != NULL && pfsb->iclamp == isb ) { action = 's'; } } // Translate action 'p' (= seek pheromone) to n/f/l/r orAction = action; if ( action == 'p' || action == 'P' ) { action = w_botMaxPhAction( pw, isb ); //printf( "p --> %c\n", action ); if ( orAction == 'P' && action == 'f' && ( fisb != -1 ) ) //bot in front of me { action = 's'; } } // Execute the elementary command w_elementarymovebot( pw, isb, action ); } _bool w_botEmitsSmell( const w_t * pw, int isb, int isb_center ) // Return 1 if s-bot 'isb' emits pheromone that is // observable by s-bot 'isb_center'. { int isb_chainbase; assert( isb_center != -1 ); // Myself I don't emit smell if ( isb == isb_center ) { return 0; } // Others with same 'ic' don't emit smell if ( pw->asb[isb].ic == pw->asb[isb_center].ic ) { return 0; } // I don't emit smell if I'm clamped if ( pw->asb[isb].iclamp != -1 ) { return 0; } return 1; } void w_updatephmap( w_t * pw, int isb_center ) // Update pheromone map, exclude s-bot 'isb_center' from it. // (I.e. calculate ph.map as seen from s-bot 'isb_center'. { int isb; // Init phmap_init( pw->phmap, pw->nsqx, pw->nsqy ); // Enter pheromone-emitting entities for ( isb = 0; isb nsb; isb++ ) { if ( ! w_botEmitsSmell( pw, isb, isb_center ) ) { continue; } phmap_enteremitter( pw->phmap, pw->nsqx, pw->nsqy, pw->asb[isb].x, pw->asb[isb].y ); } // Calculate pheromone distribution map phmap_calc( pw->phmap, pw->nsqx, pw->nsqy ); } void w_execbot( w_t * pw, int isb, char cmotor ) // Execute movement action of s-bot 'isb'. // If cmotor == 'A', then // let s-bot 'isb' determine its own action; otherwise // let it execute action "cmotor". // Don't do mutation. { // Get pheromone map as seen by me w_updatephmap( pw, isb ); // Move the bot w_movebot( pw, isb, cmotor ); } //---------------------------------------------------------------------------- // High-level funcs for looping over all s-bots //---------------------------------------------------------------------------- // Functions iterating over all s-bot ``brains'' (= l-values) _bool w_allBrainsSame( const w_t * pw ) // ---> delta( l-values ) smaller than given arg "d" { int isb; int bv1_0 = pw->asb[0].bv1; for ( isb = 1; isb nsb; isb++ ) { if ( pw->asb[isb].bv1 != bv1_0 ) { return 0; } } return 1; } #if 0 void w_mutatebot( w_t * pw, int isb ) // Mutate the s-bot's ``brain(s)'' { // l +- f_rand( f_mutrate ); } void w_mutateallbots( w_t * pw ) { int isb; for ( isb = 0; isb nsb; isb++ ) { w_mutatebot( pw, isb ); } } #endif void w_randReinitAllBots( w_t * pw ) { int isb; for ( isb = 0; isb nsb; isb++ ) { pw->asb[isb].bv1 = n_rand( N_BV ); pw->asb[isb].ic = isb; } } void w_setAllBrains( w_t * pw, int bv1 ) { int isb; for ( isb = 0; isb nsb; isb++ ) { pw->asb[isb].bv1 = bv1; } } //---------------------------------------------------------------------------- // Main //---------------------------------------------------------------------------- _bool options( int argc, char ** argv, int * pwx, int * pwy, int * pnsb, unsigned int * pseed, _bool * pbatchmode ) { int i; for ( i = 1; i ': isb_hi = ( isb_hi + 1 ) % w.nsb; break; case '= 1 ) ) { printf( "%c?\n", cmd[0] ); break; } for ( i = 0; i