|
|
Adapt.cpp: artificial life evolution
This "simple" artificial life program creates imaginary animals (as
dots) that move around on the screen according to a self-contained
program, eating each other or producing offspring using a genetic algorithm,
such that the programs evolve by natural selection, survival determined
by which
ones are most effective at obtaining food or producing offspring.
It was originally inspired by sections of the book Complexity, by M.
Mitchell Waldrop, and the concept of this type of evolutionary program is also
mentioned in other books, including Chaos Under Control, by Peak
and Frame.
The program was developed with Borland C++ 4.0 for MSDOS,
and uses Borland BGI graphics. This program listing is included in the
download file for the Windows version,
WAdapt.cpp, which also has some additional data and other related
files.
Although the program is simple in what it is supposed to do, the
program itself is unfortunately not simple at all. A large amount of
overhead code implements the "virtual machine" that defines,
manages, and runs the cell programs, which use an opcode-based
programming language that, of course, first had to be invented. One of the main
frustrations was having to spend so much time on this part of the
program. I suspect (and hope) that there now exist
programming frameworks that handle much of this overhead for you and
allow you to focus on the behaviors of the objects and on creating more
interesting environmental rules and conditions.
[In a sense, this program did serve as such a framework for two
completely unrelated programs: in
traject.cpp, one cell is shot from
the side of the screen and follows a parabolic
path up and then down to the screen bottom, its
vertical speed changing realistically, simulating the effect of
gravity.
DLA.cpp simulates diffusion limited aggregation, in which
randomly wandering particles stick together when they collide.]
Adapt.cpp uses some sound effects through the PC speaker. When a
cell is born or dies, the speaker beeps. When there is a
mass extinction (culling), the continuous beeping can last for a minute
or so. It's normal, not something wrong with the program.
This is a screenshot of the DOS version, showing the cell trails as they
move. This is a starting population. The cells have short programs. Many
are non-movers. Those that do move do so in a straight line along their
original heading because their short programs lack any instructions for
turning or seeking others. As longer cell programs evolve, the cell paths become
jagged and purposeful. A cell will, for example, seek out a weaker
neighbor, move to it, eat it, then find another neighbor and move
toward it, maybe consuming several neighbors in one turn.
|
|
Adapt.cpp
/* adapt.cpp 7-1-00
Copyright (C)1995-2000 Steven Whitney.
Initially published by http://25yearsofprogramming.com.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License (GPL)
Version 2 as published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Built with Borland C++ 4.0 for MSDOS target. Borland BGI graphics.
Inspired by sections of the book Complexity, by M. Mitchell Waldrop, this program
creates imaginary animals (as dots) that move around on the screen according to
a self-contained program, eating each other and creating offspring using a genetic algorithm,
such that the programs evolve by a genetic method, according to which are most
effective at either obtaining food or producing offspring.
It's hoped that methods used here for implementing a "virtual machine"
with its own programming language (the agent's program within this program)
will be useful in determining how to "evolve" more complicated systems.
------
to do:
------
Notes:
--Windows and DOS Version file formats are now incompatible with each other.
--FILES:
ADAPT.PGM : starting, interim, and ending cell data: #, energy, pgm
ADAPTPGM.0... : hourly extracts from long runs, for saving, copied from adapt.pgm
STRONGST.PGM : pgm for all the ending cells with energy != initialenergy
it is overwritten when program exits, and read from at start of program
(if you want a clean run from scratch, you must manually empty it)
STRONGST.BAK has the previous starting array, so to do a rerun,
copy it to STRONGST.PGM.
STRONGST.SAV : to manually archive strongst.pgm sections into, or to copy it from
MYBEST.PGM : text file describing my attempt at best possible pgm,
supposed to take over if added to a set.
##.PIC : hourly-saved screen displays
--To more easily compare pgms, copy ending cell data to temp file, and sort on column 25.
--All other notes are in COMPLEX.DOC.
*/
// You MUST comment these out for any final version, since you don't want
// debug output generated if not running under debugger.
// #define __DEBUG 2
// #define __TRACE
// #define __WARN
#include <alloc.h>
#include <complex.h>
#include <graphics.h>
#include <classlib\time.h>
#include <classlib\arrays.h>
#pragma hdrstop
#include "c:\bcs\my.h"
#include "c:\bcs\mylib.cpp"
extern unsigned _stklen = 20000U;
/////////////////////////////////////////////////////////////////////////
// global variables
//----------------------------------------------------------------------------
BOOL beepon = FALSE; // whether to use sound effects, test is in play()
/////////////////////////////////////////////////////////////////////////
// entity, shown as a screen dot, that can move around, interact with others, etc.
class Colony; // forward ref
class agent
{
public:
agent(Colony&); // MUST be a colony member
~agent(); // destructor
BOOL operator == (const agent& other) const;
friend ostream& operator << (ostream& os, const agent& a); // write
friend istream& operator >> (istream& is, agent& a); // read
// functions
int run();
void play(int state); // plays a sound
BOOL divide(BOOL); // cell division (identical copy)
double calcdistance(agent* other); // distance from this to another agent
void RestoreStartEnergy(); // top up to start, if necessary
// variables
static int ICOUNT; // NUMBER of instructions in cell instruction set
static int MAXPGMLENGTH; // 1000 agents * 200 = 200k for pgms.
static double STARTENERGY; // amount of energy a cell is born/initialized with
static const char* opcodes[];
static Trigtable t; // so they only have to be calculated once
Colony* Col; // the Colony (group) this agent belongs to
enum { DEAD, BORN, EATEN }; // states for sound effects
// must use doubles for true loc, or agent could only move in multiples of 45 degrees
complex Loc; // this cell's space location
int xi, yi; // screen location, used often
int color; // dot leaves a TRAIL in this color (the dot itself is always white)
double energy; // dies when 0
unsigned children; // number of offspring this cell has produced
unsigned ate; // number of cells this one has eaten
BOOL ran; // whether agent has run its pgm yet this pass
long id; // i.e. this cell is the Nth cell born
string pgm; // holds the agent's program. NEVER use pgm.c_str() (it contains NULLS)
double heading; // direction of motion (and sight): 0=East, 90=North
double ax; // math & test register (accumulator)
agent* inview; // pointer to the agent object currently in line of sight
int ip; // instruction pointer: next instruction to execute
int maxip; // highest pgm loc it has ever executed
protected:
void incrementip(BOOL);
void decrementip();
void jumpforward();
void jumpbackward();
BOOL samespecies(agent* other); // test whether other is same species
BOOL mate(agent* other); // mate, shuffling all genes (my version)
BOOL crossover(agent* other); // mate using crossover from book
void mutate(); // mutates pgm
void turntoward(complex loc);
void turnawayfrom(complex loc);
agent* move();
agent* sense(); // update all sensors with current surroundings
void eat(agent* other);
};
//----------------------------------------------------------------------------
// end agent
//////////////////////////////////////////////////////////////////////////////
class Colony : public TIArrayAsVector<agent>
{
public:
Colony(int maxsize = 1000, int startsize = 900, int optimumsize = 200);
~Colony(); // destructor
friend ostream& operator << (ostream& os, const Colony& s); // write
friend istream& operator >> (istream& is, Colony& s); // read
// functions
agent* AddAgent(); // tries to add a generic agent, returns ptr to it, or 0
int Destroy(agent*); // override base member
BOOL IsOccupied(int x, int y); // whether there is an agent at that loc
agent* Occupant(int x, int y); // ptr to agent at that loc, or 0
agent* nearestneighbor(agent*);
int mapneighbors(agent*, int& map);
agent* pickadjacent(agent*); // randomly choose an adjacent cell (if any)
void Reset(string filename = "");
complex centerofmass();
BOOL screenwrap(complex& point);
void ShowAgent(agent* a);
void HideAgent(agent* a);
void MoveAgent(agent* a, int x, int y, BOOL erase = TRUE);
void ShowLookPoint(int x, int y);
void drawhelp();
void drawagents();
agent* selectcell();
void viewcell();
void PlaceAgent(agent*); // assign screen location
void PlaceAllAgents(); // assign screen locations
string buildrep();
agent* findstrongest();
void pgmstodisk(const char *title, unsigned maxcount = MAXINT);
void savestrongesttodisk(string filename);
void getstrongestfromdisk(string filename);
void setPGMLENGTH();
void RunEach();
void CullOrTopUp();
// variables
long childcount; // total number of offspring produced
long runloops; // number of entries to the for loop that calls agent::run()
unsigned lowpop; // lowest population ever reached
unsigned highpop; // highest population ever reached
BOOL trailon; // whether to show trail as a point moves
BOOL lookon; // whether to show direction of sight
int passlimit; // if nonzero, autoclear every N passes (here for drawhelp)
int PGMLENGTH; // length of an agent's internal program
int MUTATIONRATE; // 1 PGM STEP in this many has a mutation
// in colony so effects of different rates can be compared
// reserved colors, ints for DOS, TColors for Win
int BKCOLOR;
int AGCOLOR;
int LOOKCOLOR;
int AGSIZE; // maximum size of colony
int AGSTART; // STARTING number of agents
int OPTIMUM; // optimum level.
protected:
// functions
BOOL killweakest();
};
//----------------------------------------------------------------------------
// end Colony
//////////////////////////////////////////////////////////////////////////////
// agent members
//----------------------------------------------------------------------------
// initialize static members
Trigtable agent::t;
int agent::MAXPGMLENGTH = 200; // pgm normally cannot grow beyond this length
double agent::STARTENERGY = 1e6; // amount of energy a cell is born/initialized with
const char* agent::opcodes[] = // English translations of numeric opcodes
{
"Label/NOP", // 0
"Restart Program", // 1
"jumpforward", // 2
"jumpbackward", // 3
"skip next step", // 4
"if(ax < 0.) skip next step", // 5
"if(ax > 0.) skip next step", // 6
"if(ax == 0.) skip next step", // 7
"if(ax != 0.) skip next step", // 8
"heading = 0.", // 9
"heading += 1.", // 10
"heading += 90.", // 11
"heading += 180.", // 12
"heading -= 90.", // 13
"heading -= 1.", // 14
"heading += random amount", // 15
"turn TOWARD center of mass", // 16
"turn AWAY FROM center of mass", // 17
"turn TOWARD nearest neighbor (chase)", // 18
"turn AWAY FROM nearest neighbor (flee)", // 19
"match heading to nearest neighbor (flock)", // 20 but neighbor will probably turn
"ax = 0.", // 21
"ax = fabs(ax)", // 22
"ax = -ax", // 23
"ax += 1.", // 24
"ax -= 1.", // 25
"ax += this->energy", // 26
"ax -= this->energy", // 27
"if(inview) ax += inview->energy", // 28
"if(inview) ax -= inview->energy", // 29
"just move", // 30
"move to eat", // 31
"move to mate", // 32
"mate with adjacent, if any", // 33
"eat adjacent, if any", // 34
"" // easier if they all have commas except this placeholder
// MAKE SURE ALL OPCODES APPEAR HERE!!!
// IF YOU ADD OPCODES, UPDATE ICOUNT (below)
};
int agent::ICOUNT = 35; // NUMBER of basic instructions in cell instruction set
//-----------------------------------------------------------------------
// constructor
agent::agent(Colony& c) // reference so it can't be 0
{
Col = &c;
heading = random(360);
ax = 0.;
energy = STARTENERGY; // all equal starting energy
for(int i = 0 ; i < Col->PGMLENGTH ; i++) // randomly assign (all same length)
pgm += (uchar)random(ICOUNT);
ip = 0;
maxip = 0;
ran = FALSE;
children = 0;
ate = 0;
inview = 0; // nothing in sight
Loc = complex(0,0);
xi = yi = 0;
}
//-----------------------------------------------------------------------
// destructor
agent::~agent()
{
}
//-----------------------------------------------------------------------
// must use &other, to uniquely distinguish between agents.
BOOL agent::operator == (const agent& other) const
{
return(this == &other);
}
//----------------------------------------------------------------------------
// output an agent's pgm to any ostream.
ostream& operator << (ostream& os, const agent& a)
{
int count = a.pgm.length();
for(int i = 0 ; i < count ; i++)
os << setw(4) << (uint)(a.pgm[i]);
return(os);
}
//-----------------------------------------------------------------------
// load an agent's program (ONLY) from an istream.
// The cell's other data members will be unchanged from
// the values the constructor gave them, meaning they will be different from
// the values the original cell had when its data was written.
// #error check whether unread/unchanged t members need default values set, for multiple reads
istream& operator >> (istream& is, agent& a)
{
// allow 4 spaces for each pgm step, plus some extra
// remember lines from old file might exceed current MAXPGMLENGTH
// 4100 will accomodate pgm lengths of 1000, highest I've ever used.
int bufsize = max(4 * agent::MAXPGMLENGTH + 100, 4100); // lines can be very long
char* buf = new char[bufsize];
// the getline() block below will produce a cell for every line read,
// even if the line is blank. is >> ws eats up any imbedded or trailing
// blank lines to prevent this. (An unreadable line will still produce an extra cell.)
is >> ws;
if(is.getline(buf,bufsize)) // read LINE into buffer
{
string oldpgm = a.pgm; // save old pgm in case nothing is read.
istrstream instr(buf); // make an input string we can read data from
a.pgm.remove(0); // empty the existing string
int pgmstep;
while(instr >> pgmstep) // while we can read data,
a.pgm += (uchar)pgmstep; // add corresponding chars to pgm
if(a.pgm.length() == 0) // not even one char read,
a.pgm = oldpgm; // so restore a.pgm to previous value
}
delete[] buf;
return(is);
}
//-----------------------------------------------------------------------
// test whether other is same species. TRUE if their pgms are the same length.
BOOL agent::samespecies(agent* other)
{
if(pgm.length() != other->pgm.length()) // pgms must be the same length
return(FALSE);
return(TRUE); // for option below, remove this line
// This never-used version determines how many of the two cells's pgm[] locations are the same.
// Returns TRUE if 90% or more of the pgm[] chars match.
// int samecount = 0;
// int count = pgm.length();
// for(int i = 0 ; i < count ; i++)
// if(pgm[i] == other->pgm[i])
// samecount++;
// long percent = 100L * (long)samecount / (long)count;
// return(percent >= 90L ? TRUE : FALSE);
} //samespecies
//-----------------------------------------------------------------------
// mutate the agent's pgm, used by all the mate() functions.
void agent::mutate()
{
// old method was to CALL mutate() for only 1 in MUTATIONRATE cells.
// now the call is unconditional, but enabling this would restore the same effect.
// falls through for only 1 in MUTATIONRATE cells.
// if(random(Col->MUTATIONRATE) != 0)
// return;
// new method: "cosmic ray hits or misses DNA": falls outside pgm.
// if it hits and falls through, don't use this loc as the location for mutation;
// legal location depends on mutation type below, so you must recalculate one there.
// if pgm length ever routinely exceeds MUTATIONRATE, should modify this so
// there are multiple cosmic ray hits.
if(random(Col->MUTATIONRATE) > pgm.length())
return;
switch(random(3)) // keep section even if not used, for reference how to do these.
{
// step removal, internal or can be first or last char in string
case 0:
if(pgm.length() > 1)
pgm.remove(random(pgm.length()),1);
break;
// step insertion, internal or can be at first or last pos in string
case 1:
pgm.insert(random(pgm.length()+1),string((char)random(ICOUNT)));
break;
// internal mutation w/no length change
case 2:
pgm[random(pgm.length())] = (char)random(ICOUNT);
break;
// truncate string at a random location, but leave at least 1 char
// this causes devastating reductions in pgm length. Such short pgms
// have too low a probability of containing at least 1 move or mate opcode.
// with this possibility removed, 1-step insertion and removal offset each other,
// meaning that if pgm lengths tend to grow, it means the new longer pgms
// have some kind of selective advantage.
// case 3:
// if(pgm.length() > 1) // can't truncate if only 1 char
// {
// int i;
// do // endless loop if length is 1
// {
// i = random(pgm.length());
// }
// while(i == 0);
// pgm.remove(i);
// }
// break;
}
// keep below max in case written to file and read back in
if(pgm.length() > MAXPGMLENGTH)
pgm.remove(MAXPGMLENGTH);
} //mutate
//-----------------------------------------------------------------------
// create 2 children using "crossover" from book.
// Tends to copy longer identical pgm sequences from the parents.
// This may be the better way to produce offspring when the sequences are
// interpreted sequentially as a program.
// This version allows agents with different length pgms to mate.
BOOL agent::crossover(agent* other)
{
BOOL succeeded = FALSE; // true if at least 1 child produced
// 2 passes = 2 children
for(int j = 0 ; j < 2 ; j++, succeeded = TRUE, children++, other->children++)
{
agent* a = Col->AddAgent(); // create a new cell
if(!a)
break;
// 1st pass: this genes first, 2nd pass: other's genes first
agent *first, *second;
if(j == 0) { first = this; second = other; }
else { first = other; second = this; }
// determine crossover point, can be from 1 to length(), inclusive
int cutpoint = random(first->pgm.length()) + 1;
// copy first->pgm from beginning to pos(cutpoint-1)
// minimum 1 char, can result in entire string being copied.
a->pgm = first->pgm; // first copy the whole string
if(cutpoint < a->pgm.length())
a->pgm.remove(cutpoint); // then cut off the end
// if second->pgm has a char at pos(cutpoint), append from there to end,
// else append nothing. second parent has its chance next (or previous) pass.
// a->pgm may be very long, but gets truncated later.
// min start point = pos(1) (2nd char). if first and second were same length,
// and entire first was copied, nothing gets copied from second.
// With this method, pgm steps generally retain their absolute positions,
// except for migrations 1 position at a time due to mutate() insertions.
// They don't migrate wildly as they did before.
if(cutpoint < second->pgm.length())
a->pgm += second->pgm.substr(cutpoint);
// if both parents reached the end of their pgms, the new cell's pgm can
// exceed the maximum, otherwise it's truncated.
if(a->pgm.length() > MAXPGMLENGTH)
// if((maxip < (pgm.length()-1)) || (other->maxip < (other->pgm.length()-1)))
a->pgm.remove(MAXPGMLENGTH);
a->mutate(); // create random mutation(s)
if(a->pgm.length() == 0) // remove when sure it never happens
logerror("pgm length is zero");
} //for(2 children)
// if parents aren't weakened, runaway population results.
// this version, if a parent hasn't eaten, the mating probably kills it soon,
// otherwise, its energy is cut in half.
// only this parent is penalized.
if(succeeded)
{
play(BORN); // at least one successfully added
if(energy > STARTENERGY)
energy /= 2.;
else
energy /= 1000.;
}
return(succeeded);
} //crossover
//-----------------------------------------------------------------------
// create 1 child, each pgm step randomly selected from 1 parent or the other.
// see complex.doc for discussion.
// returns TRUE if successful, FALSE if not
BOOL agent::mate(agent* other)
{
agent* a = Col->AddAgent(); // create a new cell
if(!a)
return(FALSE);
play(BORN); // successfully created, so
children++; // increment child tally
other->children++;
a->pgm.remove(0); // empty the constructor-assigned pgm string
// when using max:
// if parent has data at the location, append it to child, else append nothing.
// thus, the longer parent's trailing data is appended, but with holes where
// the other parent was chosen, but it had no data to append.
// could change so longer parent's data is appended in its entirety, as a "tail"
// when using min:
// copying stops when length of shortest parent is reached.
agent* parent; // for choosing one parent or the other
int count = max(pgm.length(),other->pgm.length());
for(int i = 0 ; i < count ; i++) // give it pgm steps from parents.
{
parent = random(2) ? this : other; // choose one of the parents
if(i < parent->pgm.length()) // if it has data at this loc,
a->pgm += parent->pgm[i]; // append it to child.
}
a->mutate(); // mutate
// if parents aren't weakened, runaway population results.
// only this parent is penalized.
// if(energy > STARTENERGY)
// energy /= 2.;
// else
// energy /= 1000.;
return(TRUE);
} //mate
//-----------------------------------------------------------------------
// mate: cell division. Offspring is an identical copy, with possible mutation.
// the parent cell's energy can be cut in half by the process.
// (Option of No energy loss was for topping up array from main() using cloning).
BOOL agent::divide(BOOL halfenergy = TRUE)
{
agent* a = Col->AddAgent(); // create a new cell
if(!a)
return(FALSE);
// play(BORN); // enable only if divide is an opcode
children++; // increment child tally
a->pgm = pgm; // give child the same pgm string
a->mutate(); // mutate
if(halfenergy)
energy /= 2.; // only parent has 1/2 original energy
return(TRUE);
} //divide
//-----------------------------------------------------------------------
// play a sound
void agent::play(int state)
{
if(!beepon) // not using sound at all
return;
int frequency = 440; // a default val
switch(state)
{
case DEAD: frequency = 440; break;
case BORN: frequency = 1000; break;
case EATEN: frequency = 660; break;
}
sound(frequency);
delay(30); // 50 worked well
nosound();
} //play
//-----------------------------------------------------------------------
void agent::RestoreStartEnergy()
{
energy = max(energy,STARTENERGY);
}
//-----------------------------------------------------------------------
// increment instruction pointer by one. When at end of pgm,
// it wraps around to beginning. Can update maxip (highest pgm step executed).
// NO update when it's called merely to jump or locate a program label.
// updates when it's called to get the next executable instruction.
void agent::incrementip(BOOL updatemax)
{
if(++ip >= pgm.length()) // if at program end (the > test just prevents disaster)
ip = 0; // wrap to pgm beginning
if(updatemax)
maxip = max(maxip,ip); // update highest-step-reached counter
} //incrementip
//-----------------------------------------------------------------------
// decrement ip by one
void agent::decrementip()
{
if(--ip < 0) // if below 0,
ip = pgm.length() - 1; // wrap back to last pgm step
} //decrementip
//-----------------------------------------------------------------------
// FORWARD jump to next program label (or program start)
// Remember that incrementip() is called AGAIN at end of switch in run().
// This function should leave ip at the step BEFORE the next step to be executed.
// But it's ok to leave it ON a label, since that's a NOP anyway.
// It's NOT ok to leave it on pgm[0], because then pgm[0] will get skipped.
// Pgm start must be a stopping point, to prevent endless looping if pgm contains no labels.
void agent::jumpforward()
{
// stop when it hits a 1 or program end (so pgm[0] is next one executed)
while((ip != pgm.length()-1) && (pgm[ip] != 1))
incrementip(FALSE);
} //jumpforward
//-----------------------------------------------------------------------
// BACKWARDS jump to previous program label (or program start)
// Same notes from jumpforward() apply here.
void agent::jumpbackward()
{
while((ip != pgm.length()-1) && (pgm[ip] != 1)) // stop when it hits a 1 or program end
decrementip(); // (so pgm[0] is next one executed)
} //jumpbackward
//-----------------------------------------------------------------------
// computes geometric distance between two cells
// #error still doesn't account for screen wrap
double agent::calcdistance(agent* other)
{
return abs(Loc - other->Loc);
// this fn is used often: Manhattan would be much faster, though maybe not always correct
// return fabs( real(Loc) + imag(Loc) - real(other->Loc) - imag(other->Loc) );
} //calcdistance
//-----------------------------------------------------------------------
// move a cell 1 unit along its heading.
// Can only move 1 pixel at a time so it knows whether next step will hit something.
// returns pointer to the cell that blocked this one's path, if any,
// or ZERO if path was clear.
agent* agent::move()
{
// most moves succeed, so it's more efficient to make it first, and undo if necessary
complex oldloc = Loc;
// must get away from current PIXEL, or it'll be shown as "occupied" (by itself),
while( ((int)real(Loc) == xi) && ((int)imag(Loc) == yi) )
Loc += complex( t.cosines[(int)heading], -(t.sines[(int)heading]) ); // y upside down
Col->screenwrap(Loc); // wrap the raw values
// truncate to the actual screen values (tentative only). you can't set xi, yi
// yet, because if the new loc IS occupied by another agent, the search below
// might erroneously find THIS agent on the loc instead of the other one.
int tx = real(Loc), ty = imag(Loc);
if((tx >= 640) || (tx < 0) || (ty >= 480) || (ty < 0))
logerror("tx or ty still out of range in move()");
// if new location is occupied, can't move there
if( (inview = Col->Occupant(tx, ty)) != 0)
{
Loc = oldloc; // restore old loc (xi, yi didn't change)
return(inview);
}
Col->MoveAgent(this,tx,ty,TRUE); // xi, yi will be updated to the new pos
return(0); // no cell blocked movement
} //move
//-----------------------------------------------------------------------
// update all sensors with current surroundings
// determine if there is another cell in the current line of sight along our heading
// similar to move() except it just looks, doesn't go anywhere, and vision doesn't wrap
// beyond edge of screen.
// This fn is slow, and mainly just sets inview. If inview turns out not very
// useful, this may not be, either.
// returns pointer to agent in line of sight, or 0 if none.
agent* agent::sense()
{
inview = 0; // start with nothing in sight
// I think I commented this out because doing it every call was slow.
// int map; // to build the neighborhood map in
// Col->mapneighbors(this,map); // construct a map of the neighborhood
complex oldloc = Loc; // use Loc for the imaginary moves, and undo when done.
int tx = xi, ty = yi; // must use temporaries; can't use xi, yi
// because it returns, this loop must be last thing sense() does.
while(1) // returns if an object sighted or vision ran off screen
{
// must get away from current PIXEL, or it'll be shown as "occupied" (by itself),
while( ((int)real(Loc) == tx) && ((int)imag(Loc) == ty) )
Loc += complex( t.cosines[(int)heading], -(t.sines[(int)heading]) ); // y upside down
// if our "vision" ran off screen, we're through looking.
if(Col->screenwrap(Loc))
{
Loc = oldloc; // (xi, yi didn't change)
return 0;
}
tx = real(Loc), ty = imag(Loc); // translate to screen point
// if new location is occupied, it is the object we're looking at.
if((inview = Col->Occupant(tx,ty)) != 0)
{
Loc = oldloc;
return inview;
}
// didn't sight anything or run off screen: (maybe) show where we're looking
Col->ShowLookPoint(tx,ty);
} // end while(1)
} //sense
//-----------------------------------------------------------------------
// eat neighbor, or TRY to!. Could fail and get eaten instead.
// If eat() never fails, (if someone always gets eaten)
// then you need to produce > 1 child in mate(), or population can't increase.
void agent::eat(agent* other)
{
if(other == this) // disaster prevention
return;
play(EATEN); // one or the other will get eaten
if(energy >= other->energy) // we're stronger, and get a meal
{ // (a tie goes to this, the attacker)
energy += other->energy; // add what was eaten
// I know I studied it and decided it was ok to destroy other here, but it seems risky
Col->Destroy(other); // ok to Destroy other
ate++; // tally
}
else // attack failed,
{
other->energy += energy; // this gets eaten.
other->ate++; // tally
energy = 0.; // to be Destroyed immediately upon return
}
} //eat
//-----------------------------------------------------------------------
// change heading to point at a given point
// the calculation seems to be wrong (still?)
// atan only returns +90 to -90 degrees, and screen y is upside-down, besides.
// Should only be called from run(), because heading isn't adjusted to 0-359.
void agent::turntoward(complex p)
{
// #error is there a complex fn that can do this?
double tx = real(p), ty = imag(p);
double x = real(Loc), y = imag(Loc);
if(x == tx) // target is straight up or down
{
if(ty < y) // target is directly above
heading = 90.;
else
if(ty > y) // target is directly below
heading = 270.;
return; // no change if it's sitting on target point
}
if(y == ty) // straight left or right
{
if(tx < x) // target is directy left
heading = 180.;
else
heading = 0.; // target is directy right
return;
}
// y axis is inverted.
heading = atan((y - ty) / (tx - x)); // returns radians
heading *= 57.29577951; // convert to degrees
// determine if it should actually be to LEFT of y-axis:
if(x > tx)
heading += 180.;
} //turntoward
//-----------------------------------------------------------------------
void agent::turnawayfrom(complex point)
{
turntoward(point);
heading += 180.;
} //turnawayfrom
//-----------------------------------------------------------------------
// execute next program block of an agent's program. each step costs some energy.
// returns TRUE if cell survived, FALSE if not.
// "if(test) repeat previous step" is not used because there's no way to change the
// data being tested, and an unconditional "repeat" is just an endless loop.
// Remember to add sense() at end of any case that might have caused changes
// to the environment that are detectable by sense().
// contains both "elemental" opcodes, and "macro" opcodes that could be defined
// in terms of the elemental ones. (Cells behave more interestingly when the macro opcodes
// are available.)
int agent::run()
{
if(energy <= 1.) // dead cell (probably eaten by another, but not yet Destroyed)
return(FALSE);
int mated = 0; // number of children produced during this run() call
int matelimit = 1; // max number of children allowed in 1 run call
// use 1 for crossover (which produces 2 children),
// 2 for mate (which produces only 1),
// or only 1 if mate() doesn't reduce energy
double oldheading; // used to determine how many degrees (if any) cell turned
agent* other = 0; // temporaries that can't be declared within a switch{}
sense(); // update all sensors for current surroundings/conditions
ax = 0.; // cell is "unconscious" while the other cells are moving
ip = 0; // so you have to start fresh
// limit the # of steps executed to prevent endless loops
// int stepmax = 200; // same limit for all: max instructions executed per call
// int stepmax = pgm.length(); // or each cell can run its entire pgm once, maximum
// for(int stepcount = 0 ; stepcount < stepmax ; stepcount++)
clock_t start = clock(); // elapsed time for imposing a TIME limit
while((clock() - start) < 1) // limit is in 1/1000 sec. but DOS only times to 1/20th
{ // that is, clock() jumps by 50ms each 1/20th.
oldheading = heading;
switch((uint)(pgm[ip])) // each case is a basic cell instruction
{
// program control:
case 0: break; // program label, does nothing (label/NOP)
// case 1: ip = 0; break; // Restart Program (old version: wrong(?)
case 1: ip = pgm.length() - 1; // last step: 1st step w/b next executed!
case 2: jumpforward(); break; // go to next label FORWARD or program start
case 3: jumpbackward(); break; // go to PREVIOUS label or program start
// these conditional skips, combined with subsequent jumps
// can code conditional jumps
case 4: incrementip(FALSE); break; // skip over the next step
case 5: if(ax < 0.) incrementip(FALSE); break;
case 6: if(ax > 0.) incrementip(FALSE); break;
case 7: if(ax == 0.) incrementip(FALSE); break;
case 8: if(ax != 0.) incrementip(FALSE); break;
// change heading
case 9: heading = 0.; break; // a reference position
case 10: heading += 1.; break; // turn 1 degree clockwise
case 11: heading += 90.; break; // turn 90 degrees
case 12: heading += 180.; break; // turn 180 degrees
case 13: heading -= 90.; break; // turn 270 degrees
case 14: heading -= 1.; break; // turn 1 degree counterclockwise
case 15: heading += random(360); break; // by a random amount
case 16: // turn TOWARD center of mass
turntoward(Col->centerofmass());
break;
case 17: // turn AWAY FROM center of mass
turnawayfrom(Col->centerofmass());
break;
case 18: // turn TOWARD nearest neighbor (chase)
if((other = Col->nearestneighbor(this)) != 0)
turntoward(other->Loc);
break;
case 19: // turn AWAY FROM nearest neighbor (flee)
if((other = Col->nearestneighbor(this)) != 0)
turnawayfrom(other->Loc);
break;
case 20: // match heading to nearest neighbor (flock)
if((other = Col->nearestneighbor(this)) != 0)
heading = other->heading;
break;
// could add match heading to (inview)->heading
// arithmetic
case 21: ax = 0.; break; // zero ax (reset)
case 22: ax = fabs(ax); break; // absolute value of (ax)
case 23: ax = -ax; break; // negative of (ax)
case 24: ax += 1.; break; // increment ax
case 25: ax -= 1.; break; // decrement ax
// variables about itself:
// keep energy for comparing its own energy to others
case 26: ax += energy; break; // energy
case 27: ax -= energy; break; // energy
// variables about the object in sight (must prohibit if no object):
// keep energy for comparing with its own
case 28: if(inview) ax += inview->energy; break; // energy
case 29: if(inview) ax -= inview->energy; break; // energy
case 30: move(); break; // just move
case 31: // move along heading and eat neighbor
other = move();
if(other) // if it hit another cell,
{
eat(other); // eat or get eaten
sense(); // other may be gone now
}
break;
case 32: // move along heading and mate with neighbor
// other will still be there (blocking) after mating
other = move();
if(other) // if it hit another cell,
{
while(++mated <= matelimit)
mate(other);
}
break;
case 33: // mate with adjacent cell, if any
if((other = Col->pickadjacent(this)) != 0)
while(++mated <= matelimit)
mate(other);
break;
case 34: // eat adjacent cell, if any
if((other = Col->pickadjacent(this)) != 0)
{
eat(other); // eat or get eaten
sense(); // other may be gone now
}
break;
// REMEMBER TO ADD ALL NEW CASES TO OPCODES[]!!!!
} //switch
//-----------------------------------------------------------------------
// the following steps are all performed after each opcode is executed
if(heading != oldheading)
{
// heading is always USED as (int)heading, (for trig table lookup),
// so this will cause rounding to NEAREST int, when truncated.
if(heading > 0.) heading += .5;
if(heading < 0.) heading -= .5;
while(heading >= 360.) heading -= 360.;
while(heading < 0.) heading += 360.;
if(((int)heading < 0) || ((int)heading > 359))
logerror("Heading out of bounds in run()");
sense();
}
if(energy <= 1.) // got eaten or is very weak
break;
incrementip(TRUE); // increment instruction pointer
}
// deduct "aging" (per call) cost: .933 will deplete 1e6 to 1 in 200 calls
energy *= .933;
return(energy > 1.); // TRUE if it survived alive
} //run
//-----------------------------------------------------------------------
// end agent members
/////////////////////////////////////////////////////////////////////////
// Colony members
//----------------------------------------------------------------------------
// constructor
//
// AGSTART still sets the actual starting count.
Colony::Colony(int maxsize, int startsize, int optimumsize):
TIArrayAsVector<agent>(maxsize,0,0) // it's nonexpandable
{
childcount = 0L;
runloops = 0L; // number of entries to the for loop that calls agent::run()
lowpop = 0; // lowest population ever reached
highpop = 0; // highest population ever reached
trailon = TRUE; // whether to show trail as a point moves
lookon = FALSE; // whether to show direction of sight
passlimit = 2; // autoclear every N passes (here for drawhelp)
PGMLENGTH = 1; // avg pgm length of agents in this colony
// 1 at start works fine. There is pressure to lengthen.
// it is modified in setPGMLENGTH().
MUTATIONRATE = 99; // 1 PGM STEP in this many has a mutation
BKCOLOR = BLACK; // reserved colors, ints for DOS, TColors for Win
AGCOLOR = WHITE;
LOOKCOLOR = BLUE;
AGSIZE = maxsize; // maximum size of colony
AGSTART = startsize; // STARTING number of agents
OPTIMUM = optimumsize; // optimum level.
} // constructor
//----------------------------------------------------------------------------
// destructor
Colony::~Colony()
{
Flush(TShouldDelete::Delete);
} // destructor
//----------------------------------------------------------------------------
// output to a stream
ostream& operator << (ostream& os, Colony& )
{
os << "" << endl;
return(os);
}
//----------------------------------------------------------------------------
// read from a stream
// be sure to set ALL members, even those not read from the stream
// this example is complicated, for reference, but uses >> ws unusually, particularly:
// do not use a final >> ws after you have all the input you need for the object,
// because if you got what you needed, it shouldn't return as failed until the *next* call.
istream& operator >> (istream& is, Colony& )
{
#if 0
char buf[80];
is >> ws; // ensure first getline has something to read
while(is.getline(buf,sizeof(buf)))
{
istrstream str(buf);
str >> x >> ws; // do force a failure if there's nothing left on the line
if(str) // if there is anything left, it is Y
{
str >> y;
s.Add(x,y);
}
else
s.Add(x); // this x is really the y variable
is >> ws; // skip blank lines before the next getline()
}
#endif
return(is);
} // operator >>
//----------------------------------------------------------------------------
// reset/reinitialize to starting values. pulled out of main().
void Colony::Reset(string infilename)
{
childcount = 0L;
Flush(TShouldDelete::Delete); // empty array
if(infilename.length())
getstrongestfromdisk(infilename); // load starting cell programs
setPGMLENGTH(); // set length for new randoms
while(GetItemsInContainer() < AGSTART) // fill up to starting level with randoms
AddAgent();
lowpop = highpop = GetItemsInContainer(); // population counters
// #error multiple Colonies can't share this file
unlink("adapt.pgm"); // get rid of pre-existing file
pgmstodisk("Starting",OPTIMUM); // save initial programs to adapt.pgm
} //Reset
//----------------------------------------------------------------------------
// kills (Destroys) the weakest cell in array
// in case of a tie, it chooses the first (oldest) with that energy.
// use caution calling from within loops: when a cell is destroyed, array contracts.
// This MUST NOT be called FROM any agent member function, because it could Destroy(this).
// returns TRUE if one was killed, FALSE if not.
BOOL Colony::killweakest()
{
int count = GetItemsInContainer();
if(!count)
return(FALSE);
agent* weakest = (*this)[0]; // start with first as the weakest
for(int i = 0 ; i < count ; i++)
if((*this)[i]->energy < weakest->energy)
weakest = (*this)[i];
weakest->play(agent::DEAD);
Destroy(weakest);
return(TRUE);
} //killweakest
//-----------------------------------------------------------------------
// returns TRUE if given point is occupied, FALSE if not.
// can experiment with methods, and change easily for platforms.
// this version tests the screen dot, which is only set if the agent is "really" there:
// if you change it to search the array,
// it could cause problems; an agent can be temporarily invisible on screen,
// but with temporarily invalid xi,yi that would match in the search. (see sense())
BOOL Colony::IsOccupied(int x, int y)
{
// sgetpixel returns 0 if offscreen
return(sgetpixel(x,y) == AGCOLOR);
} //IsOccupied
//-----------------------------------------------------------------------
// identify which agent is occupying a pixel & return pointer
// returns pointer, or ZERO if match not found.
agent* Colony::Occupant(int x, int y)
{
if(!IsOccupied(x,y)) // quick test, quick return (must be VISIBLE to be an occupant)
return 0;
int count = GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
if( ((*this)[i]->xi == x) && ((*this)[i]->yi == y) )
return((*this)[i]);
logerror("White dot not found by Occupant()");
return(0);
} //Occupant
//-----------------------------------------------------------------------
// returns pointer to nearest cell neighbor, or 0 if none
agent* Colony::nearestneighbor(agent* a)
{
int count = GetItemsInContainer();
if(count < 2) // min=2: a and a neighbor
return(0);
agent* nearest = ((a != (*this)[0]) ? (*this)[0] : (*this)[1]);
double distance;
double mindistance = MAXDOUBLE;
for(int i = 0 ; i < count ; i++)
if((*this)[i] != a) // don't find itself
{
distance = a->calcdistance((*this)[i]);
if(distance < mindistance)
{
mindistance = distance;
nearest = (*this)[i];
}
}
return(nearest);
} //nearestneighbor
//-----------------------------------------------------------------------
// create a bitmapped map of neighboring pixels.
// each pixel encoded in 1 bit (excluding pixel occupied by itself).
// use if(mapneighbors()) to determine if *any* neighboring pixel is occupied.
// use & (bitwise and) operator on map to determine if a specific pixel is occupied.
// For use in DLA and in 2nd version of Life.
// returns the NUMBER of neighbors, and creates the map in the given int parameter.
// could be changed to return a pointer to one of the neighbors, chosen randomly,
// or to return 1-9 (not 5, itself), the loc of a neighbor, chosen randomly.
int Colony::mapneighbors(agent* a, int& map)
{
int count = 0; // counts neighbors
map = 0; // clear the map to start
int left = wrap(a->xi - 1,0,getmaxx()); // standard template wrap() from my.h
int right = wrap(a->xi + 1,0,getmaxx());
int above = wrap(a->yi - 1,0,getmaxy());
int below = wrap(a->yi + 1,0,getmaxy());
if(IsOccupied(left, above)) { map |= 128; count++; } // above left
if(IsOccupied(a->xi,above)) { map |= 64; count++; } // above
if(IsOccupied(right,above)) { map |= 32; count++; } // above right
if(IsOccupied(left ,a->yi)) { map |= 16; count++; } // to left
if(IsOccupied(right,a->yi)) { map |= 8; count++; } // to right
if(IsOccupied(left ,below)) { map |= 4; count++; } // below left
if(IsOccupied(a->xi,below)) { map |= 2; count++; } // below
if(IsOccupied(right,below)) { map |= 1; count++; } // below right
return(count);
} //mapneighbors
//-----------------------------------------------------------------------
// choose an adjacent cell (if there is one or more), modified from mapneighbors()
// allows choosing from multiple neighbors
// returns pointer to the chosen cell, or 0 if none
agent* Colony::pickadjacent(agent* ag)
{
int count = 0; // counts neighbors
int map = 0; // clear the map to start
agent* a = 0;
int left = wrap(ag->xi - 1,0,getmaxx()); // standard template wrap() from my.h
int right = wrap(ag->xi + 1,0,getmaxx());
int above = wrap(ag->yi - 1,0,getmaxy());
int below = wrap(ag->yi + 1,0,getmaxy());
// multiple neighbors is unlikely, so if count is 0, any hit is likely the only neighbor.
// In case it is, save the pointer so you can return it immediately.
// Once you know there are multiple neighbors, don't bother; you'll have to choose.
if(IsOccupied(left ,above)) {map |= 128; if(!count) a=Occupant(left,above); count++; }
if(IsOccupied(ag->xi,above)) {map |= 64; if(!count) a=Occupant(ag->xi,above); count++; }
if(IsOccupied(right ,above)) {map |= 32; if(!count) a=Occupant(right,above); count++; }
if(IsOccupied(left ,ag->yi)){map |= 16; if(!count) a=Occupant(left,ag->yi); count++; }
if(IsOccupied(right ,ag->yi)){map |= 8; if(!count) a=Occupant(right,ag->yi); count++; }
if(IsOccupied(left ,below)) {map |= 4; if(!count) a=Occupant(left,below); count++; }
if(IsOccupied(ag->xi,below)) {map |= 2; if(!count) a=Occupant(ag->xi,below); count++; }
if(IsOccupied(right ,below)) {map |= 1; if(!count) a=Occupant(right,below); count++; }
if(!map) // no neighbors (most common)
return(0);
if(count == 1) // 1 neighbor, and you already know who it is (also common)
return a;
while(1) // multiple neighbors; you have to choose
{
// generate random positions within map until the bit-shifted 1
// lands on a spot mapped in map as occupied
count = random(8);
if(map & (1 << count))
switch(count)
{
case 7: return(Occupant(left, above));
case 6: return(Occupant(ag->xi, above));
case 5: return(Occupant(right, above));
case 4: return(Occupant(left, ag->yi));
case 3: return(Occupant(right, ag->yi));
case 2: return(Occupant(left, below));
case 1: return(Occupant(ag->xi, below));
case 0: return(Occupant(right,below));
}
}
} //pickadjacent
//-----------------------------------------------------------------------
// assign screen location
void Colony::PlaceAgent(agent* a)
{
do // use the ints to find a slot
{
a->xi = random(getmaxx() + 1);
a->yi = random(getmaxy() + 1);
}
while(IsOccupied(a->xi, a->yi)); // test for already occupied
a->Loc = complex(a->xi, a->yi); // set the actual loc
ShowAgent(a);
} //PlaceAgent
//-----------------------------------------------------------------------
// reassign screen locations to all
// needed when window size changed (but probably don't call from EvSize())
void Colony::PlaceAllAgents()
{
int count = GetItemsInContainer();
// first, remove all from screen so they don't block placements
// you must clear the entire screen: various xi, yi may now be offscreen.
clearviewport();
for(int i = 0 ; i < count ; i++)
PlaceAgent((*this)[i]);
} //PlaceAllAgents
//-----------------------------------------------------------------------
// tries to add a generic agent,
// returns ptr to it, or 0 if it fails (array full)
// you can alter the added agent after adding it (reassign pgm, etc.)
agent* Colony::AddAgent()
{
if(GetItemsInContainer() >= AGSIZE)
return 0;
agent* a = new agent(*this);
if(!Add(a)) // but it should always succeed
{
delete a;
return 0;
}
a->color = random(13)+2; // random color, except black, blue, or white (reserved)
a->id = ++childcount;
PlaceAgent(a); // assign screen loc
return a;
} //AddAgent
//-----------------------------------------------------------------------
int Colony::Destroy(agent* a)
{
putpixel(a->xi, a->yi, BKCOLOR); // remove from screen
return TIArrayAsVector<agent>::Destroy(a);
} //Destroy
//-----------------------------------------------------------------------
// find mass center of all points on screen = (average(x),average(y))
complex Colony::centerofmass()
{
int count = GetItemsInContainer();
if(!count)
return complex(getmaxx() / 2, getmaxy() / 2);
complex sum = complex(0,0);
for(int i = 0 ; i < count ; i++)
sum += (*this)[i]->Loc;
return(sum / count);
} //centerofmass
//-----------------------------------------------------------------------
// construct a pgm representative of the set, containing at each location
// the opcode most common at that location. Tested, agrees with .xls version.
// returns the composite representative pgm
string Colony::buildrep()
{
int* t = new int[agent::ICOUNT]; // tallies opcode incidences
int i, j; // counters
// #error find LONGEST pgm, eliminate use of MAXPGMLENGTH: see drawhelp() and below
string composite;
int count = GetItemsInContainer();
for(i = 0 ; i < agent::MAXPGMLENGTH ; i++) // for each possible column in the pgms,
{
for(j = 0 ; j < agent::ICOUNT ; j++) // zero out array (i.e. count of all opcodes
t[j] = 0; // at this location is zero)
// count each opcode's incidence at this location
for(j = 0 ; j < count ; j++) // for all cell pgms,
if(i < (*this)[j]->pgm.length()) // if i is a valid index in this pgm
t[(int)((*this)[j]->pgm[i])]++; // increment counter for this opcode
// find the most common opcode at this loc.
// A tie goes to the lowest numbered, for no particular reason.
int opcode = 0; // corresponding index (encodes opcode)
for(j = 0 ; j < agent::ICOUNT ; j++) // for each opcode tally slot,
if(t[j] > t[opcode]) // if this one's tally is the highest,
opcode = j; // it is the highest-frequency opcode
// give this most common opcode (or zero) its position in composite
composite += (uchar)opcode;
}
delete[] t;
// determine length of the longest pgm
unsigned longest = 0;
for(j = 0 ; j < count ; j++)
longest = max((*this)[j]->pgm.length(),longest);
// composite has MAXPGMLENGTH chars in it, padded at end with opcode 0
// cut off anything beyond length of longest pgm.
composite.remove(longest);
return composite;
} //buildrep
//-----------------------------------------------------------------------
// write cell data to adapt.pgm. adapt.pgm can become extremely large.
// only saving the top STRONGEST would be nice, but difficult because you
// can't delete them as you go, as savestrongesttodisk() does. However,
// maxcount allows writing only the first N. The first are the oldest and
// usually, though not always, the strongest (i.e. those that eat).
// Sometimes the most numerous pgms are weak but produce lots of children,
// so a composite pgm is also created to represent them.
void Colony::pgmstodisk(const char *title, unsigned maxcount)
{
int count = min(maxcount,GetItemsInContainer());
ofstream outfile("adapt.pgm",ios::app); // append to file
outfile << title << ", Population = " << GetItemsInContainer();
outfile << ", Childcount = " << childcount << ", " << TTime() << endl;
for(int i = 0 ; i < count ; i++)
{
// write data not written by <<
outfile << "#" << setw(7) << (*this)[i]->id;
outfile << ", E=" << setw(11) << (*this)[i]->energy << ":";
outfile << *((*this)[i]) << endl; // use << to write out the pgm
}
// write out a hypothetical pgm representative of the whole set
agent a(*this); // it will temporarily be on the screen
a.pgm = buildrep();
outfile << "Representative Program :" << a << endl;
} //pgmstodisk
//-----------------------------------------------------------------------
// returns pointer to strongest agent in array, or 0 if array empty
// In case of a tie, it chooses the first (oldest) cell with that energy.
agent* Colony::findstrongest()
{
int count = GetItemsInContainer();
if(!count)
return 0;
agent* strongest = (*this)[0]; // start with first as strongest
for(int j = 0 ; j < count ; j++)
if((*this)[j]->energy > strongest->energy) // find highest, if any
strongest = (*this)[j];
return strongest;
} //findstrongest
//-----------------------------------------------------------------------
// show the help screen
void Colony::drawhelp()
{
// tabulate stats on pgm lengths
unsigned shortest = agent::MAXPGMLENGTH;
unsigned longest = 0;
long sum = 0;
int count = GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
{
shortest = min(shortest,(*this)[i]->pgm.length());
longest = max(longest,(*this)[i]->pgm.length());
sum += (*this)[i]->pgm.length();
}
long average = (count ? (sum / (long)count) : (shortest + longest) / 2);
cout << endl;
cout << "These commands are available while program is running:" << endl << endl;
cout << "0 DON'T clear screen automatically" << endl;
cout << "1-9 Clear screen every N loops" << endl;
cout << "B BEEP (sound effects) (toggle, now " << (beepon ? "ON" : "OFF") << ")" << endl;
cout << "C CLEAR screen once" << endl;
cout << "H HELP (show this screen)" << endl;
cout << "L LINE-of-sight display (toggle, now " << (lookon ? "ON" : "OFF") << ")" << endl;
cout << "P PAUSE (any key to resume)" << endl;
cout << "R RESTART new game (all new programs)" << endl;
cout << "S SAVE current program set to file ADAPT.PGM, and continue with same set" << endl;
cout << "T TRAIL display (toggle, now " << (trailon ? "ON" : "OFF") << ")" << endl;
cout << "V VIEW text listing of cell data" << endl;
cout << "<ESC> Quit" << endl;
cout << endl;
cout << "Current population = " << GetItemsInContainer()
<< ". Lowest was " << lowpop << ". Highest was " << highpop << "." << endl;
cout << "There have been " << childcount << " cells, "
<< runloops << " passes through cells array." << endl;
cout << "Cell pgms: Shortest = " << shortest << " Longest = " << longest
<< " Average = " << average << endl;
cout << "Available memory = " << farcoreleft() << endl;
cout << endl;
presskey(); // 1 screenful to here
// show selected data about strongest agent; some data is only available during pgm run
agent* a = findstrongest();
if(a)
{
cout << "Strongest:" << endl;
cout << "#" << a->id << " at (" << a->xi << "," << a->yi << ")";
cout << " Color:" << DOSCOLORS[a->color];
cout << " Children:" << a->children << " Ate:" << a->ate;
cout << " Energy:" << a->energy << endl;
cout << *a << endl;
// give it, and show, a hypothetical pgm representative of the whole set
a->pgm = buildrep();
cout << "Representative Program :" << endl;
cout << *a << endl;
cout << endl;
presskey();
}
} //drawhelp
//-----------------------------------------------------------------------
// wraps a point back into range usable for the display screen.
// it assumes that the double values used for x, y will be TRUNCATED when used,
// so any point from 0 to < 1 will become 0 (NOT rounded up), 1-2 is 2, 639-640 is 639, etc.
// thus, the raw values might remain slightly outside the display area, and
// the display is offset leftward by .5 compared to the actual points in space,
// but it eliminates serious complications that rounding would necessitate.
// width and height are the highest bounding values, NONinclusive, such as
// are provided by SDib.Width(), TRect.Height(), etc. Minimum is assumed always 0.
// places the wrapped value in point, returns TRUE if wrapping was required, FALSE if not.
BOOL Colony::screenwrap(complex& point)
{
int width = getmaxx() + 1, height = getmaxy() + 1;
double x = real(point);
double y = imag(point);
BOOL wrapped = FALSE;
while(x < 0) { x += width; wrapped = TRUE; }
while(x >= width) { x -= width; wrapped = TRUE; }
while(y < 0) { y += height; wrapped = TRUE; }
while(y >= height) { y -= height; wrapped = TRUE; }
point = complex(x,y);
return wrapped;
} //screenwrap
//-----------------------------------------------------------------------
void Colony::ShowLookPoint(int x, int y)
{
if(lookon)
putpixel(x,y,LOOKCOLOR);
}
//-----------------------------------------------------------------------
// make an agent invisible at its current display screen location,
// replacing its pixel with the background color or its trail.
// these fns may get more complicated if agents become TWindows.
void Colony::HideAgent(agent* a)
{
putpixel(a->xi, a->yi, trailon ? a->color : BKCOLOR);
}
//-----------------------------------------------------------------------
// display an agent onscreen
void Colony::ShowAgent(agent* a)
{
putpixel(a->xi, a->yi, AGCOLOR);
}
//-----------------------------------------------------------------------
// move an agent to a new location.
// erase must be false when first creating the agent, since its xi, yi loc is invalid.
void Colony::MoveAgent(agent* a, int newx, int newy, BOOL erase)
{
if(erase) // uses its current xi, yi
HideAgent(a);
a->xi = newx; // NOW set new position
a->yi = newy;
ShowAgent(a); // and show it there
}
//-----------------------------------------------------------------------
// redraw all the agents on the screen
void Colony::drawagents()
{
clearviewport();
int count = GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
ShowAgent((*this)[i]);
} //drawagents
//-----------------------------------------------------------------------
// select a cell to view by moving cursor around screen. The cursor is white, to show up.
// You only tell it from the cells by its movement.
agent* Colony::selectcell()
{
int ch; // USER INPUT
int oldcolor;
agent* selection = 0; // pointer to cell at cursor location, or 0 if none
moveto(320,240); // set BGI (x,y) to start position
oldcolor = getpixel(getx(),gety());
putpixel(getx(),gety(),AGCOLOR); // start with cursor on
putchar(7); // audible tone: now in View mode.
while(1)
{
ch = ci(); // wait for user input
// before moving, restore cell, or leave black trail
putpixel(getx(),gety(),oldcolor == AGCOLOR ? AGCOLOR : BKCOLOR);
switch(ch) // arrows = 1 pixel. numlock or shifted = 10 pixels.
{
case 18: // ^R
case('8'): // 8 = up 10 pixels
moverel(0,-9);
case UP: // up arrow = up 1 pixel
case 5: // ^E
moverel(0,-1);
break;
case 3: // ^C
case('2'): // 2 down
moverel(0,9);
case DOWN:
case 24: // ^X
moverel(0,1);
break;
case 6: // ^F
case('6'): // 6 right
moverel(9,0);
case RIGHT:
case 4: // ^D
moverel(1,0);
break;
case 1: // ^A
case('4'): // 4 left
moverel(-9,0);
case LEFT:
case 19: // ^S
moverel(-1,0);
break;
//---
case('5'):
case FIVE: // GO TO CENTER OF SCREEN
moveto(320,240);
break;
//---
case('3'):
case PGDN: // middle of lower right quadrant
moveto(480,360);
break;
case('7'):
case HOME: // middle of upper left quadrant
moveto(160,120);
break;
case('9'):
case PGUP: // middle of upper right quadrant
moveto(480,120);
break;
case('1'):
case END: // middle of lower left quadrant
moveto(160,360);
break;
//---
case 13: // c/r = select this cell (or quit if not on a cell)
selection = 0;
if(getpixel(getx(),gety()) == AGCOLOR)
selection = Occupant(getx(),gety());
return(selection);
} // END SWITCH
oldcolor = getpixel(getx(),gety()); // save original color of new location
if(oldcolor == AGCOLOR) // audible signal that we hit a cell
putchar(7);
putpixel(getx(),gety(),AGCOLOR); // cursor on while idle
} // end while(1)
} //selectcell
//-----------------------------------------------------------------------
// view data about a cell, including its program
void Colony::viewcell()
{
agent* a = selectcell();
if(!a)
return;
int opcode;
while(1)
{
clearviewport();
cout << endl;
cout << "#" << a->id << " of " << childcount;
cout << " at (" << a->xi << "," << a->yi << ")";
cout << " Heading:" << ((int)(a->heading)) << " Color:" << DOSCOLORS[a->color];
cout << " Children:" << a->children << " Ate:" << a->ate << endl;
cout << "Energy:" << a->energy;
cout << " AX:" << a->ax << " Inview:" << (a->inview ? "YES" : "NO");
cout << " PgmLength:" << a->pgm.length();
cout << " Maxip:" << (a->maxip + 1) << endl << endl;
int count = a->pgm.length();
for(int i = 0 ; i < count ; i++)
{
opcode = (uint)(a->pgm[i]);
cout << (i+1) << "." << '\t'; // give the pgm steps line numbers
cout << setw(2) << opcode;
if(a->ip == i) // star shows current ip location
cout << "*";
if(a->maxip == i) // + shows highest step ever reached
cout << "+";
cout << '\t';
if(opcode < agent::ICOUNT) // prevent trying to print opcode text that is
cout << agent::opcodes[opcode]; // beyond end of opcodes[] array.
else // (old files may contain obsolete opcodes)
cout << "NOP: obsolete opcode";
cout << endl;
if(i && !(i % 20))
{
presskey();
// cout << endl;
}
}
if(!yesno("Done. Show list again"))
break;
}
} //viewcell
//-----------------------------------------------------------------------
// save cell pgms to strongst.pgm in order of decreasing energy.
// Use only at END of run, because it Destroys() the cells as it writes them out.
// It writes out ALL cells that aren't newborns.
// (Thus, to reduce the number, you can cut lines off the end of the file.)
void Colony::savestrongesttodisk(string filename)
{
ofstream outfile(backupfile(filename).c_str());
agent* strongest;
while((strongest = findstrongest()) != 0) // until container is emptied
{
if(strongest->energy != agent::STARTENERGY) // if it's not a newborn,
outfile << *strongest << endl; // write out its data (pgm),
Destroy(strongest); // Destroy it so next pass won't find it again
}
} //savestrongesttodisk
//-----------------------------------------------------------------------
// load starting cell programs, usually from strongst.pgm
void Colony::getstrongestfromdisk(string infilename)
{
ifstream infile(infilename.c_str());
for(int i = 0 ; infile ; i++)
{
agent* a = AddAgent(); // create a new cell
if(!a)
{
cout << to_upper(infilename) << " has too many cell programs to load them all." << endl;
cout << "Will proceed with only the " << i << " that were read." << endl;
presskey();
break;
}
infile >> *a; // get its program from disk
if(!infile) // Additional check ensures the read succeeded.
{
logerror("read failure in getstrongestfromdisk");
Destroy(a);
break;
}
infile >> ws; // force failure if only blanks left
}
TRACE("Read " << i << " pgms from " << infilename);
} //getstrongestfromdisk
//----------------------------------------------------------------------------
void Colony::RunEach()
{
// Cells born during this pass ARE run() within this pass,
// so all newborns get at least one chance to save themselves.
// But it means they could mate and ADD yet more cells, which could also mate, etc. etc.
// So all mate() functions must now test for array full, and fail if it is.
// Destroy() can't be done in any member function because it would be Destroy(this)
int count = GetItemsInContainer(); // reset each cell's "ran" flag
for(int i = 0 ; i < count ; i++)
(*this)[i]->ran = FALSE;
for(i = 0 ; i < GetItemsInContainer() ; i++) // run each cell's program
{
if((*this)[i]->ran) // already got run() during this loop pass
continue;
agent* thisone = (*this)[i];
if(thisone->run()) // survived
thisone->ran = TRUE;
else // didn't survive
{
if(thisone->energy > 0) // if eaten, EATEN was already played;
thisone->play(agent::DEAD); // DEAD means it ran out of energy
Destroy(thisone);
i--; // reuse i next pass, because it's a different cell now
}
}
runloops++; // how many times preceding for() loop has been called
CullOrTopUp();
} // RunEach
//----------------------------------------------------------------------------
void Colony::CullOrTopUp()
{
highpop = max(highpop,GetItemsInContainer()); // test when at its peak
// if there are more agents than allowed in the array, delete the weakest.
if(GetItemsInContainer() >= AGSIZE)
while(GetItemsInContainer() > OPTIMUM)
killweakest();
lowpop = min(lowpop,GetItemsInContainer()); // test when at its probable lowest
if(GetItemsInContainer() <= (OPTIMUM / 2)) // array nearly empty (too many dead)
{
if(beepon) // sound warning
{
sound(2000);
sleep(5);
nosound();
}
// keep survivors competitive. If array is depleted this badly,
// even the strongest survivors may be weaker than the new cells.
// restore them to STARTENERGY if necessary.
int count = GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
(*this)[i]->RestoreStartEnergy();
// Now top up the array with random cells. They may not
// be very fit, but they can serve as food and a more varied
// gene pool for the remaining ones.
setPGMLENGTH(); // set length for random cells
while(GetItemsInContainer() < AGSTART) // fill up the array
AddAgent();
}
} // CullOrTopUp
//-----------------------------------------------------------------------
// new cell pgms are PGMLENGTH chars long. At the start of a completely new
// run, this is 1, but when continuing a previous run or topping up a depleted
// array, you want new cell pgms to be about the same length as the existing
// ones. If not (if PGMLENGTH remains unmodified), then when old cells mate
// with new ones, the child pgms are greatly mangled (collapsed) mutations of
// the existing ones. If you adjust PGMLENGTH, as here, it is like a sudden
// influx of a new population at a similar stage of development, but with much
// wider (random) genetic variation, which is what you need for a population
// that hasn't been able to sustain itself.
// Sets PGMLENGTH to the average length of existing cells.
void Colony::setPGMLENGTH()
{
PGMLENGTH = 1; // default for new run or when array is empty
int count = GetItemsInContainer();
if(!count)
return;
long sum = 0;
for(int i = 0 ; i < count ; i++)
sum += (long)((*this)[i]->pgm.length());
PGMLENGTH = max((int)(sum / (long)count),1); // min = 1
string::initial_capacity(max(PGMLENGTH,30)); // size strings to match
} //setPGMLENGTH
//----------------------------------------------------------------------------
// end class Colony
/////////////////////////////////////////////////////////////////////////
// main()
int main()
{
randomize();
TTime::PrintDate(TRUE);
TDate::SetPrintOption(TDate::Numbers);
string::set_paranoid_check(TRUE);
string::set_case_sensitive(FALSE);
int ch, passcount;
TTime referencetime; // for timing 1-hour intervals for file saves
int piccount = 0; // for building .pic file names
if(yesno("See program description"))
system("type adapt.txt | more");
cout << "\nRemember to disable Windows 3.1 Schedule+ calendar before long unattended runs." << endl;
if(!yesno("Start program"))
return(0);
BOOL fromdisk = yesno("Load starting cells from file STRONGST.PGM");
cout << endl;
cout << "Each hour, the program will save cell data and screen display to disk." << endl;
cout << "These .PIC files from previous runs are currently on your disk:" << endl;
system("dir *.pic");
cout << endl;
if(yesno("Delete all .PIC files before starting"))
system("del *.pic");
Colony ag;
ag.drawhelp();
unlink("adapt.err"); // new error log each run
initgraf();
while(1)
{
clearviewport();
ag.Reset(fromdisk ? "strongst.pgm" : ""); // needs graphics mode: puts dots on screen
passcount = 0;
while(1)
{
//-----------------------------------------------------------------------
// user input and utility section, unrelated to program operation
if(kbhit())
{
ch = tolower(getch());
if(ch == 'r') // restart (no write to disk, nor save strongest)
{
restorecrtmode();
if(yesno("Restart the program as though the current run never occurred"))
{
setgraphmode(getgraphmode());
break; // exit to outermost while()
}
else
{
setgraphmode(getgraphmode());
ag.drawagents(); // clear and restore screen
}
}
switch(ch)
{
case 27: // user quit
// restorecrtmode(); // technically correct, but ok without it
if(!yesno("Exit program")) // calls cout while in graphics mode
{
setgraphmode(getgraphmode());
ag.drawagents();
break;
}
ag.pgmstodisk("Ending");
// setgraphmode(getgraphmode()); // destructor requires graphics mode
ag.savestrongesttodisk("strongst.pgm");
nosound(); // just in case
closegraph();
cout << "There were " << logerror() << " errors. See ERROR.LOG." << endl;
cout << endl;
cout << "ADAPT.PGM contains all the ending cell programs." << endl;
cout << "STRONGST.PGM contains the strongest of them, ";
cout << "to reload at start of next run." << endl << endl;
presskey();
return(0);
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
ag.passlimit = ch - '0';
break;
case 'b': beepon = !beepon; break; // toggle sound effects
case 'c': ag.drawagents(); break; // clear screen this pass
case 'h': // help
restorecrtmode();
ag.drawhelp();
setgraphmode(getgraphmode());
ag.drawagents();
break;
case 'l': ag.lookon = !ag.lookon; break; // show where cell is looking
case 'p': getch(); break; // user pause
case 's': ag.pgmstodisk("Interim"); break; // write interim programs to disk
case 't': ag.trailon = !ag.trailon; break; // trail display
case 'v': ag.viewcell(); ag.drawagents(); break; // show agent data
}
} // end if(kbhit())
//-----------------------------------------------------------------------
// save cell pgms to disk each hour, useful backup in case of crash
if(TTime().Hour() != referencetime.Hour())
{
ag.pgmstodisk("Interim",10); // write first 10 cell pgms to disk
referencetime = TTime(); // current time becomes the new reference
// write a numbered .pic file. you can later look at hourly progress
// later, SDib can write itself, but this isn't very useful, anyway.
char buf[20];
ostrstream(buf,sizeof(buf)) << piccount++ << ends;
picsave((string(buf) + ".pic").c_str());
}
//-----------------------------------------------------------------------
ag.RunEach();
if(ag.passlimit)
if(++passcount >= ag.passlimit)
{
ag.drawagents();
passcount = 0;
}
} // end inner while(1)
} // end outer while(1)
} //main
Copyright ©2007
Steven Whitney. Last modified
09/25/2007.
