// anttest5.c // S-bot test with chain forming arising from mechanism that makes ant in // chain resist changes in its genes" stronger than an ant that's not // part of a chain. // MR Jun 2001 #include #include #include #include #include #include "bool.h" #include "byte.h" #include "int2char.h" #include "rand.h" #include "phmap1.h" //---------------------------------------------------------------------------- // Data structures for administration of s-bot states and positions //---------------------------------------------------------------------------- typedef struct { // Programming in brain of s-bot (table of "prio" values): // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ double l; // Other state variables of s-bot: // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int x, y; //position on chessboard int dirn; //direction, in [0,3) int isb_clamp; //ix of s-bot that is clamping to me (-1 if none) int isb_target; //ix of s-bot I'm clamping to (-1 if none) int isb_chain; //ix of s-bot at base of chain (ix of myself if // I'm the only one in the chain) } 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', '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; } #if 0 void w_chainbots( w_t * pw, int isb_base, int iChainVal ) // Set the fields 'isb_chain' of all s-bots in the chain // based at s-bot 'isb_base' to value 'iChainVal'. { int ii; int irep = 0; for ( ii = isb_base; ii != -1; ii = pw->asb[ii].isb_target ) { if ( irep > 0 && ii == isb_base ) { return; } //Circular chain ! pw->asb[ii].isb_chain = iChainVal; irep++; //if ( ++irep > 100 ) { fatal( "irep>100" ); } } } #endif void w_unclampbot( w_t * pw, int isb_actor, int isb_oldtarget ) { pw->asb[isb_actor].isb_target = -1; pw->asb[isb_oldtarget].isb_clamp = -1; { int isb = isb_oldtarget; while ( isb != -1 && pw->asb[isb].isb_chain == isb_actor ) { pw->asb[isb].isb_chain == isb_oldtarget; isb = pw->asb[isb].isb_target; } } //w_chainbots( pw, isb_oldtarget, isb_oldtarget ); } void w_clampbot( w_t * pw, int isb_actor, int isb_newtarget ) { pw->asb[isb_actor].isb_target = isb_newtarget; pw->asb[isb_newtarget].isb_clamp = isb_actor; //w_chainbots( pw, isb_actor, pw->asb[isb_actor].isb_chain ); } int w_chainlen( w_t * pw, int isb_base ) // Return # of s-bots in front of s-bot 'isb-base' // in same chain. (Return 0 if none.) { int irep = 0; int isb = isb_base; for(;;) { int isb_next = pw->asb[isb].isb_target; // End of chain if ( isb_next == -1 ) { return irep; } // Circular chain bites tail ! if ( isb_next == isb_base ) { return irep; } //Next s-bot in chain isb = isb_next; irep++; //if ( ++irep > 100 ) { fatal( "irep>100" ); } } } //---------------------------------------------------------------------------- // (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 s-bot contents/values pw->asb[isb].dirn = n_rand( 4 ); pw->asb[isb].isb_clamp = -1; pw->asb[isb].isb_target = -1; pw->asb[isb].isb_chain = isb; pw->asb[isb].l = f_rand( 1.0 ); //put s-bot in empty square w_putinsbot( pw, isb, ix, iy ); } pw->nsb = nsb; return NULL; //success } //---------------------------------------------------------------------------- // 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, char mode, _bool highlight ) { const sb_t * psb = &( pw->asb[isb] ); aas[2][1] = int2char( isb ); 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 ( mode == 'c' || mode == '*' ) { aas[3][2] = int2char( psb->isb_clamp ); } if ( mode == 'C' || mode == '*' ) { aas[1][0] = int2char( psb->isb_chain ); } //if ( psb->siP == 1 ) { aas[3][0] = '\''; } if ( highlight ) { aas[0][0] = aas[4][0] = aas[4][2] = aas[0][2] = '*'; } } static char GLOB_fdrawbigmode = 'C'; 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_fdrawbigmode == 'p' || GLOB_fdrawbigmode == '*' ) { 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_fdrawbigmode, ( isb == isb_hi ) ); } for ( icol = 0; icol = 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; } // // 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 nsb ); psb = pw->asb + isb; // // If I'm not clamped by anyone, then // reset my isb_chain to my own isb. // if ( psb->isb_clamp == -1 ) { psb->isb_chain = isb; } // // If I'm clamping someone, and if the cmd is 'f','q', or 'Q', // then swap my "program" into him. // cisb = psb->isb_target; if ( ( cisb != -1 ) //I'm clamping someone && ( action == 'f' || action == 'q' || action == 'Q' ) ) { // if ( action == 'f' || action == 'Q' ) { //Overwrite target s-bot's isb_chain and "l" // with my own. pw->asb[cisb].isb_chain = pw->asb[isb].isb_chain; pw->asb[cisb].l = pw->asb[isb].l; } return; } // // Otherwise : // // (1) Un-clamp the s-bot I'm clamping at this moment cisb = psb->isb_target; if ( cisb != -1 ) { w_unclampbot( pw, isb, cisb ); //This resets his 'isb_chain' //pw->asb[cisb].isb_chain = cisb; } // (2) Examine what's in front of me. fInBoard = w_botlookfwd( pw, isb, &fx, &fy, &fisb ); // (3) Translate action 'q'/'Q' to n/f/L/R if ( action == 'q' || action == 'Q' ) { action = w_botMaxPhAction( pw, isb ); //printf( "q/Q --> %c\n", action ); } // (4) Execute movement n/f/L/R switch ( action ) { case 'L': //Turn left psb->dirn = ( psb->dirn + 3 ) % 4; break; case 'R': //Turn right psb->dirn = ( psb->dirn + 1 ) % 4; 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 //if someone is clamping me, then my movement // un-clamps him from me if ( psb->isb_clamp != -1 ) { w_unclampbot( pw, psb->isb_clamp, isb ); // This also makes my 'isb_chain' // revert to my own 'isb'. //psb->isb_chain = isb; } //move s-bot w_pickupsbot( pw, isb ); w_putinsbot( pw, isb, fx, fy ); break; }//switch // (5) Again examine what's in front of me (my movement may have // changed this) fInBoard = w_botlookfwd( pw, isb, &fx, &fy, &fisb ); // (6) Automatically (re-)clamp the s-bot in front of me, if // it's not already clamped by someone else. #if 0 if ( fisb != -1 && //s-bot in front of me pw->asb[fisb].isb_clamp == -1 ) //he's not clamped // and if he is not already clamping me, // and if he's not in the same chain as me. pw->asb[isb].isb_clamp != fisb && //I'm not clamped by him pw->asb[isb].isb_chain != pw->asb[fisb].isb_chain ) //Not same chain #endif if ( fisb != -1 && //s-bot in front of me pw->asb[fisb].isb_clamp == -1 && //he's not clamped pw->asb[isb].isb_clamp != fisb && //I'm not clamped by him pw->asb[isb].isb_chain != pw->asb[fisb].isb_chain ) //Not same chain // pw->asb[fisb].isb_chain == psb->isb_chain ) { w_clampbot( pw, isb, fisb ); } } //---------------------------------------------------------------------------- // High-level s-bot funcs //---------------------------------------------------------------------------- // 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; double hjhja; for ( isb = 1; isb nsb; isb++ ) { } return 1; } 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 ); } } void w_randReinitAllBots( w_t * pw ) { int isb; for ( isb = 0; isb nsb; isb++ ) { pw->asb[isb].l = f_rand( 1.0 ); } } _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 ); isb_chainbase = pw->asb[isb_center].isb_chain; // Myself I don't emit smell if ( isb == isb_center ) { return 0; } // Others in same chain don't emit smell if ( pw->asb[isb].isb_chain == isb_chainbase ) { return 0; } // S-bots that are being clamped don't emit smell if ( pw->asb[isb].isb_clamp != -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 ); if ( cmotor == 'A' ) { // Choose motor action according to value of "l" cmotor = 'q'; if ( f_rand( 1.0 ) asb[isb].l ) { cmotor = 'Q'; } } // Move the bot w_movebot( pw, isb, cmotor ); } void w_execrandombot( w_t * pw, char cmotor, _bool bmut ) //Choose a random s-bot, and execute it. //if bmut == 1, then mutate the selected bot after the move. { int isb; assert( pw->nsb != 0 ); isb = n_rand( pw->nsb ); w_execbot( pw, isb, cmotor ); if ( bmut ) { w_mutatebot( pw, isb ); } } //---------------------------------------------------------------------------- // Stdio output //---------------------------------------------------------------------------- void w_fprintsbot( FILE * fp, const w_t * pw, int isb ) { const sb_t * psb = &( pw->asb[isb] ); fprintf( fp, "%02d: x=%02d y=%02d dirn='%c' " "l=%4.2f " "TS=%c " "cl=%02d ta=%02d Ch=%02d\n", isb, psb->x, psb->y, getDirnChar( psb->dirn ), psb->l, w_botTrackSmell( pw, isb ), psb->isb_clamp, psb->isb_target, psb->isb_chain ); } 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 ); } } //---------------------------------------------------------------------------- // 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