|
|
DLA.cpp - diffusion limited aggregation
This program was derived from
adapt.cpp, but has a completely
different purpose. It creates multiple agents (cells) that wander
around randomly on the screen. When they collide, they stick together
into a blob. The blobs also wander the screen colliding
and sticking.
Like
traject.cpp, this was easily derived
from adapt.cpp by ripping out most of the code and giving the
agents different behavior.
Borland C++ 4.0 for MSDOS. BGI graphics.
Previous versions:
-
DLA3.BAS (GWBASIC / BASICA)
-
DLA.C (DeSmet C for the Heathkit H-100 computer)
Screenshot:
Earlier version of DLA.CPP after a long run. The newer version shows a red dot at the
center of mass of each blob.
|
DLA.cpp
/* DLA.cpp 6-26-97
Copyright (C)1990-97 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 3 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.
SIMULATES DIFFUSION LIMITED AGGREGATION
A completely new version of DLA that incorporates the "blobs" idea
(conglomerated points also move around the screen), using the routines
from adapt.cpp, and demonstrating what may be the versatility
of those routines in modeling various things.
Only a small portion of the adapt.cpp routines are used for DLA, but any features
that could conceivably ever be useful (plus some others) have been left in.
------
TO DO:
It probably doesn't make any sense to L(oad) a file at start, since the file
contents can't be turned into active blobs. (or it may: is motion blocked
even if no cell owns the blocking point? If so, could use to load a specific environment,
as in robot.)
Add routines for rotating the blob around its center of mass.
and for translating by a specified amount (currently only moves in multiples of
sine,cosine of heading).
add a set of "rotate by x degrees" instructions to the cell instruction set.
does the bc4 complex class have any usefulness for vector math?
look at atan2(): it may make unnecessary the 2nd test to determine if to left
or right of y axis. Probably will work, but remember that y-axis is upside down;
probably not important for distance calc., but it will make the angle wrong.
If it works, make same change in adapt.cpp.
Consider converting to Windows: screen can be made rightside up, and video is faster.
add the possibility of reflection. Also, once the center of mass of each blob
is calculated, allow rotation around that center. It should also be possible,
though complicated, to allow blobs that bounce off each other to 1) bounce at
an angle appropriate to the relationship of the contact point to their centers
of mass, (exit trajectories from the collision are always either inline or at right angles?)
2) transfer momentum (speed) proportional to their masses, 3) transfer
or induce angular momentum (spin) from off-center blows.
version like accumulation in stove flue: dust particles start on
one side of screen, motion vectors are biased towards moving across screen,
with additional random motion. (easy: just add the sequence (heading = 0)(move)
to the programs)
"gravity" version: points generally move towards center of mass. This would be particularly
interesting if heading and energy were changed by collisions.
nuclear fission version where some collisions cause blobs to shatter & all bounce away
Add angular momentum variable.
Also for constructing a blob from an area of the screen: to allow drawing the
blob with something like editpic, then marking the area, and constructing the
blob from the coordinates of all the points in the marked area that aren't black.
Modify viewcell() so that user can edit the parameters of the selected blob,
such as adding thrust, etc. Remove the display of anything that was adapt-specific
and not useful here. Add display of new variables.
In general, make the blobs into as versatile "physical" objects as possible.
-----------------------
NOTES:
--The red dot among the white is the blob's center of mass.
--An interesting addition is that before testing whether any point in the blob
is going to hit another blob when it moves, the entire first blob is erased
from screen: this allows testing only for whether there's a point at the
new location; no danger of misidentifying itself as blocking the way,
because it's invisible at that moment.
Misc. elements taken from DLA before its deletion, as reminders that the options existed:
enum { reflect, stick } hitmode; // what happens when the point hits something
*/
#include <math.h>
#include <graphics.h>
#include <classlib\arrays.h>
#pragma hdrstop
#include "c:\bcs\my.h"
#include "c:\bcs\mylib.cpp"
/////////////////////////////////////////////////////////////////////////
// global variables
//----------------------------------------------------------------------------
enum { DEAD, BORN, EATEN }; // states for sound effects
const int CENTERCOLOR = LIGHTRED; // color for a blob's center of mass point
const int BLOBCOLOR = WHITE; // color for all the rest of the blob's points
// These consts were previously #defines.
const int AGSIZE = 1000; // the total SIZE of the ag[] container. large, but
// not expandable should prevent program crashes
// due to xalloc: allow only # we know can be created.
const int AGSTART = 50; // STARTING number of agents (can be < AGLIMIT)
const int AGLIMIT = 500; // the maximum number of agents ALLOWED (maintenance level)
const int ICOUNT = 100; // number of basic instructions in cell instruction set
const int STEPMAX = 200; // maximum instructions executed in 1 run() call
const int PGMLENGTH = 2; // maximum STARTING length of an agent's internal program
const int MAXPGMLENGTH = 1000; // pgm[] cannot extend beyond this length
const int MUTATIONRATE = 10; // 1 cell in this many has a mutation
const double STARTENERGY = 1e6; // amount of energy a cell is born/initialized with
// Enforce array size relationships:
#if((AGLIMIT >= AGSIZE) || (AGSTART >= AGSIZE) || (AGSTART > AGLIMIT))
#error AG relationships must be: AGSTART <= AGLIMIT < AGSIZE
#endif
Trigtable t; // so they only have to be calculated once
long childcount; // total number of offspring produced
long runloops = 0L; // number of entries to the for loop that calls agent::run()
unsigned lowpop = 0; // lowest ag[] population ever reached
unsigned highpop = 0; // highest ag[] population ever reached
BOOL beepon = FALSE; // whether to use sound effects, test is in play()
BOOL delayon = FALSE; // whether to impose delay for better viewing
BOOL trailon = FALSE; // whether to show trail as a point moves
BOOL lookon = FALSE; // whether to show direction of sight
BOOL autoclear = FALSE; // whether to auto-clear screen every ## loops
char *opcodes[ICOUNT+1] = // English translations of numeric opcodes
{ // have not been checked for accuracy against switch cases
"Move()", // 0
"LABEL / NOP", // 1
"jumpforward()", // 2
"if(ax < 0.) jumpforward()", // 3
"if(ax > 0.) jumpforward()", // 4
"if(ax == 0.) jumpforward()", // 5
"if(ax != 0.) jumpforward()", // 6
"jumpbackward()", // 7
"if(ax < 0.) jumpbackward()", // 8
"if(ax > 0.) jumpbackward()", // 9
"if(ax == 0.) jumpbackward()", // 10
"if(ax != 0.) jumpbackward()", // 11
"skip next step", // 12
"if(ax < 0.) skip next step", // 13
"if(ax > 0.) skip next step", // 14
"if(ax == 0.) skip next step", // 15
"if(ax != 0.) skip next step", // 16
"restart program", // 17
"if(ax < 0.) restart program", // 18
"if(ax > 0.) restart program", // 19
"if(ax == 0.) restart program", // 20
"if(ax != 0.) restart program", // 21
"heading = 0.", // 22
"heading += 1.", // 23
"heading += 90", // 24
"heading += 180", // 25
"heading -= 90", // 26
"heading -= 1.", // 27
"heading += random(360)", // 28
"turn toward center of mass", // 29
"turn away from center of mass", // 29
"turn toward nearest neighbor", // 30
"turn away from nearest neighbor", // 30
"match heading to nearest neighbor",
"ax = 0.", // 31
"ax = fabs(ax)", //32
"ax = -ax", //33
"ax += 1.", //34
"ax -= 1.", //35
"ax += this->x", //36
"ax -= this->x", //37
"ax = this->x", //38
"ax += this->y", //39
"ax -= this->y", //40
"ax = this->y", //41
"ax += this->heading", //42
"ax -= this->heading", //43
"ax = this->heading", //44
"ax += this->energy", //45
"ax -= this->energy", //46
"ax = this->energy", //47
"ax += this->color", //48
"ax -= this->color", //49
"ax = this->color", //50
"ax += this->pgm.length()", //51
"ax -= this->pgm.length()", //52
"ax = this->pgm.length()", //53
"ax += opcode of next program step", //54
"ax -= opcode of next program step", //55
"ax = opcode of next program step", //56
"ax += pointer to agent being sighted", //57
"ax -= pointer to agent being sighted", //58
"ax = pointer to agent being sighted", //59
"ax += pointer to itself", //60
"ax -= pointer to itself", //61
"ax = pointer to itself", //62
"if(inview) ax += inview->x", //63
"if(inview) ax -= inview->x", //64
"if(inview) ax = inview->x", //65
"if(inview) ax += inview->y", //66
"if(inview) ax -= inview->y", //67
"if(inview) ax = inview->y", //68
"if(inview) ax += inview->heading", //69
"if(inview) ax -= inview->heading", //70
"if(inview) ax = inview->heading", //71
"if(inview) ax += inview->energy", //72
"if(inview) ax -= inview->energy", //73
"if(inview) ax = inview->energy", //74
"if(inview) ax += inview->color", //75
"if(inview) ax -= inview->color", //76
"if(inview) ax = inview->color", //77
"if(inview) ax += inview->pgm.length()", //78
"if(inview) ax -= inview->pgm.length()", //79
"if(inview) ax = inview->pgm.length()", //80
"if(inview) ax += what the object in view HAS in view", // 81
"if(inview) ax -= what the object in view HAS in view", //82
"if(inview) ax = what the object in view HAS in view", //83
"if(inview) ax += distance to object in sight", //84
"if(inview) ax -= distance to object in sight", //85
"if(inview) ax = distance to object in sight", //86
"ax += total current population", //87
"ax -= total current population", //88
"ax = total current population", //89
"ax += centerofmass->x", //90
"ax -= centerofmass->x", //91
"ax = centerofmass->x", //92
"ax += centerofmass->y", //93
"ax -= centerofmass->y", //94
"ax = centerofmass->y", //95
"divide", // 99
"" // easier if they all have commas except this last one
// ALWAYS MAKE SURE ALL OPCODES APPEAR HERE!!!
};
/////////////////////////////////////////////////////////////////////////
struct POINT
{
POINT() { x = y = 0.; }
POINT(double i, double j) { x = i; y = j; }
POINT(int i, int j) { x = (double)i; y = (double)j; }
BOOL operator == (const POINT& other) const // equal if they would occupy same pixel
{ return(((int)x == (int)(other.x)) && ((int)y == (int)(other.y))); }
double x;
double y;
};
/////////////////////////////////////////////////////////////////////////
// entity, shown as a screen dot, that can move around, interact with others, etc.
class agent
{
public:
agent(); // constructor
~agent(); // destructor
BOOL operator == (const agent& other) const;
BOOL operator < (const agent& other) const;
friend ostream& operator << (ostream& os, agent* a); // put-to operator
friend istream& operator >> (istream& is, agent* a); // get-from operator
void reinit(); // reborn at a new location
void absorb(agent* other); // absorb all of another agent's points
BOOL contains(const POINT& p); // whether point belongs to this blob
BOOL incrementip(BOOL);
BOOL decrementip();
void play(int state); // plays a sound
double calcdistance(class agent* other); // distance from this to another agent
class agent* identifynearestneighbor();
class agent* move();
int run();
BOOL sense(); // update all sensors with current surroundings
BOOL samespecies(class agent* other); // test whether other is same species
void jumpforward();
void jumpbackward();
void turntoward(double x,double y);
int mapneighbors(int* map);
void calccentofmass(); // calculate the center of mass into (x,y)
void hidepoints(); // remove all the blob's points from screen display
void showpoints(); // display all the blob's points on screen
void adjustforscreenwrap();
void add(POINT*); // add a point to the array & recalc mass center
TIArrayAsVector<POINT> par; // list of this blob's points
double x; // center of mass
double y;
double heading; // direction of motion (and sight): 0=East, 90=North
double ax; // math & test register (accumulator)
double energy; // dies when 0
int color; // dot leaves a TRAIL in this color (the dot itself is always white)
long birthorder; // i.e. this cell is the Nth cell born
unsigned children; // number of offspring this cell has produced
unsigned ate; // number of cells this one has eaten
string pgm; // holds the agent's program. NEVER use pgm.c_str() (contains NULLS)
int ip; // instruction pointer: next instruction to execute
BOOL reachedend; // whether agent ever reached end of its pgm (not used)
BOOL ran; // whether agent has run its pgm
class agent* inview;// pointer to the agent object currently in line of sight
// its relevant data elements are directly accessible to this agent
};
/////////////////////////////////////////////////////////////////////////
// global array of agents. Must define here because some agent:: functions use it.
// large model can handle at least 1000, but it's way too many.
// Array always AGSIZE, but AGSTART still sets the starting count.
TIArrayAsVector<agent> ag(AGSIZE,0,0);
//-----------------------------------------------------------------------
// constructor
agent::agent() : par(1,0,10)
{
int i = 0;
do // disallow born on top of another cell
{
if(++i > 20000) // prevent endless loop if screen fills up
graborts("Screen filled up.");
x = (double)random(640);
y = (double)random(480);
}
while(getpixel((int)x,(int)y)); // test for already occupied
add(new POINT(x,y)); // put 1st point into points array
heading = (double)(random(360));
ax = 0.;
// if energies all start the same, then without interactions, they'll all move together.
// That is, a pgm step subtracts the same amount from each.
energy = STARTENERGY; // all equal starting energy
// energy = (double)(lrandom(1000000L)); // random starting energy
// int pgmlength = random(PGMLENGTH)+1; // randomly assign SPECIES (length 1 to PGMLENGTH)
int pgmlength = PGMLENGTH; // all same species (same length pgm)
// pgm = turn by a random amount, then move. Changing the assigned program
// may be able to produce different simulations, such as a flow across screen, etc.
pgm = (char)28; // heading = random(360)
// pgm = (char)23; // heading += 1
pgm += (char)(random(1)); // THIS works, but (char)0 doesn't!
ip = 0;
reachedend = ran = FALSE;
color = random(13)+2; // random color, except black, blue, or white (reserved)
birthorder = childcount++;
children = ate = 0;
putpixel((int)x,(int)y,CENTERCOLOR); // display on screen
inview = 0; // nothing in sight
}
//-----------------------------------------------------------------------
// allows an absorbed point to be reborn as a new point,
// an alternative to destroying it and creating another.
void agent::reinit()
{
par.Flush(TShouldDelete::Delete);
int i = 0;
do // disallow born on top of another cell
{
if(++i > 20000) // prevent endless loop if screen fills up
graborts("Screen filled up.");
x = (double)random(640);
y = (double)random(480);
}
while(getpixel((int)x,(int)y)); // test for already occupied
add(new POINT(x,y)); // put 1st point into points array
heading = (double)(random(360));
energy = STARTENERGY; // all equal starting energy
int pgmlength = PGMLENGTH; // all same species (same length pgm)
// pgm = turn by a random amount, then move. Changing the assigned program
// may be able to produce different simulations, such as a flow across screen, etc.
pgm = (char)28; // heading = random(360)
// pgm = (char)23; // heading += 1
pgm += (char)(random(1)); // THIS works, but (char)0 doesn't!
ip = 0;
reachedend = ran = FALSE;
color = random(13)+2; // random color, except black, blue, or white (reserved)
children = ate = 0;
putpixel((int)x,(int)y,CENTERCOLOR); // display on screen
inview = 0; // nothing in sight
}
//-----------------------------------------------------------------------
// destructor, removes from screen. OK if a dead cell's energy is zero,
// but if residual energy is ever allowed, it might be better to leave lying
// around for another cell to eat (scavenger).
agent::~agent()
{
par.Flush(TShouldDelete::Delete);
// putpixel((int)x,(int)y,BLACK);
}
//-----------------------------------------------------------------------
// == currently isn't used for anything, but there should be a way to make it useful.
BOOL agent::operator == (const agent& other) const
{
if((x == other.x) && (y == other.y))
return(TRUE);
return(FALSE);
}
//-----------------------------------------------------------------------
// < Sorts blobs by the number of points they contain.
BOOL agent::operator < (const agent& other) const
{
return(par.GetItemsInContainer() < other.par.GetItemsInContainer());
}
//----------------------------------------------------------------------------
// determine if the given point is in this blob's points list
BOOL agent::contains(const POINT& p)
{
int count = par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
if(*par[i] == p)
return(TRUE);
return(FALSE);
}
//----------------------------------------------------------------------------
// output an agent's pgm[] to any ostream.
ostream& operator << (ostream& os, agent* a)
{
if(a)
{
int count = a->pgm.length();
for(int i = 0 ; i < count ; i++)
{
os.width(4);
os << (int)(a->pgm[i]);
}
os << endl;
}
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 to the file.
istream& operator >> (istream& is, agent* a)
{
if(a && is) // testing "is" is intended to prevent reading from a failed or null stream
{ // doesn't seem to hurt, but haven't seen it done anywhere else.
// 4 spaces for each pgm step, plus some extra
char* buf = new char[4 * MAXPGMLENGTH + 100]; // lines can be very long
// the getline() block below will produce a cell for every line in the file,
// even if the line is blank. This block will eat up any imbedded or trailing
// blank lines. (An unreadable line will still produce an extra cell.)
while(is.good()) // quit on eof (and then getline() will fail, too)
{
if(isspace(is.peek())) // if the next char is whitespace,
is.get(); // extract it,
else // otherwise break to get the next line (if any)
break;
}
if(is.getline(buf,4 * MAXPGMLENGTH + 100)) // read LINE into buffer
{
string oldpgm(a->pgm); // save old pgm in case nothing is read.
BOOL gotone = FALSE; // TRUE if at least one pgm step was read and added
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, (this works)
{ // but it succeeds if ANYTHING can be extracted,
gotone = TRUE; // so keep the gotone test, in case of file garbage.
a->pgm += (char)pgmstep; // add corresponding chars to pgm[] array.
}
if(!gotone) // not even one char read,
a->pgm = oldpgm; // so restore a->pgm to previous value
}
delete[] buf;
}
return(is);
}
//-----------------------------------------------------------------------
// calculate the center of mass into (x,y)
// The center of mass often will not coincide with any point in the blob,
// especially if the blob spans a screen edge or has a jagged shape with a blank interior.
// There may be more efficient ways to calculate this.
void agent::calccentofmass()
{
x = y = 0.; // use for tallying
int count = par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
{
x += par[i]->x;
y += par[i]->y;
}
x /= (double)count;
y /= (double)count;
}
//-----------------------------------------------------------------------
// add a point to the array and recalculate the center of mass
void agent::add(POINT* p)
{
par.Add(p);
// calccentofmass();
}
//-----------------------------------------------------------------------
// remove all the blob's points from screen display
void agent::hidepoints()
{
int count = par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
putpixel((int)(par[i]->x), (int)(par[i]->y), BLACK);
}
//-----------------------------------------------------------------------
// adjust all the blob's point coordinates for screen wrap
void agent::adjustforscreenwrap()
{
int count = par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
{
if((int)(par[i]->x) >= 640) par[i]->x -= 640.;
if((int)(par[i]->x) <= -1) par[i]->x += 640.;
if((int)(par[i]->y) >= 480) par[i]->y -= 480.;
if((int)(par[i]->y) <= -1) par[i]->y += 480.;
}
}
//-----------------------------------------------------------------------
// display all the blob's points on screen
// you can only display the center of mass if it happens to coincide with one of the points.
void agent::showpoints()
{
calccentofmass();
int count = par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
{
POINT p(par[i]->x,par[i]->y);
POINT center(x,y);
int color = ((p == center) ? CENTERCOLOR : BLOBCOLOR);
putpixel((int)(p.x),(int)(p.y),color); // show new position
}
}
//-----------------------------------------------------------------------
// play a sound
void agent::play(int state)
{
if(!beepon) // not using sound at all
return;
int frequency;
switch(state)
{
case DEAD: frequency = 220; break;
case BORN: frequency = 1000; break;
case EATEN: frequency = 440; break;
}
sound(frequency);
delay(50);
nosound();
}
//-----------------------------------------------------------------------
// incrementip() increment instruction pointer by one. When at end of pgm,
// it wraps around to beginning. Tests whether last instruction has been executed.
// NO test when it's called merely to jump or locate a program label.
// TESTS when it's called to get the next executable instruction.
// returns TRUE
BOOL agent::incrementip(BOOL testforend) // whether to test for reaching pgm end
{
if(++ip >= pgm.length()) // if at program end (the > test just prevents disaster)
{
ip = 0; // wrap to pgm beginning
if(testforend)
reachedend = TRUE;
}
return(TRUE);
}
//-----------------------------------------------------------------------
// decrementip() decrement ip by one
// returns TRUE
BOOL agent::decrementip()
{
if(--ip < 0) // if below 0,
ip = pgm.length()-1; // wrap back to last pgm step
return(TRUE);
}
//-----------------------------------------------------------------------
// calcdistance() computes the distance between the centers of mass of two cells
double agent::calcdistance(class agent* other)
{
return(hypot(x - other->x, y - other->y));
}
//-----------------------------------------------------------------------
// test whether other is same species. TRUE if their pgms are the same length.
BOOL agent::samespecies(class 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);
}
//-----------------------------------------------------------------------
// locates the weakest cell in ag[]
// in case of a tie, it chooses the first (oldest) with that energy.
// returns pointer to the weakest cell, or 0 if none (empty)
class agent* findweakest()
{
double lowest = 1e300;
class agent* weakest = 0;
int count = ag.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
if(ag[i]->energy < lowest)
{
lowest = ag[i]->energy;
weakest = ag[i];
}
return(weakest);
}
//-----------------------------------------------------------------------
// kills (Destroys) the weakest cell in ag[]
// use caution calling from within loops: when a cell is destroyed, ag[] 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 killweakest()
{
class agent* weakest = findweakest();
if(weakest)
{
weakest->play(DEAD);
ag.Destroy(weakest);
return(TRUE);
}
return(FALSE);
}
//-----------------------------------------------------------------------
// identify which agent is occupying a pixel & return pointer
// returns pointer, or ZERO if match not found.
// generally, you should know that the pixel IS occupied before calling, because this is slow.
class agent* identify(int findx, int findy)
{
POINT p(findx,findy);
int count = ag.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
if(ag[i]->contains(p))
return(ag[i]);
return(0);
}
//-----------------------------------------------------------------------
// 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.
class agent* agent::move()
{
if(energy <= 0.) // it has no energy to make any moves
return(0);
int i;
int count = par.GetItemsInContainer();
class agent* other = 0; // nonzero if any cell blocked path
// Minor flaw: with 1 "step" defined by the trig functions, the magnitude of
// a move depends on the heading: you get a little farther at the 45 degree angles.
double xdif = t.cosines[(int)heading]; // amount of the proposed move
double ydif = t.sines[(int)heading]; // screen's y axis is upside down
// Each point in the points array will be moving: so you must make sure the
// expected new location of each point is not already occupied by another blob.
// Since the locations are doubles and screen locations are only ints,
// each move causes a slightly different rounding, so blobs may change shape
// somewhat as they move around.
// take blob off the screen while testing surrounding points, so it can ignore itself
hidepoints();
// if a proposed new location is occupied, get pointer to agent blocking the way, if any
for(i = 0 ; i < count ; i++)
{
double newx = par[i]->x + xdif;
double newy = par[i]->y + ydif;
if((int)newx >= 640) newx -= 640.; // adjust for screen wrap
if((int)newx <= -1) newx += 640.;
if((int)newy >= 480) newy -= 480.;
if((int)newy <= -1) newy += 480.;
if(getpixel((int)newx,(int)newy))
{
other = identify((int)newx,(int)newy); // save the blocking cell
xdif = ydif = 0.; // set "move" amount to zero,
break; // and quit trying to move.
}
}
if(xdif || ydif) // if we're moving,
{
for(i = 0 ; i < count ; i++)
{
par[i]->x += xdif; // recalculate all the point coordinates,
par[i]->y += ydif;
}
adjustforscreenwrap(); // adjust them for screen wrap,
}
showpoints(); // and make visible again.
return(other);
} // end move()
//-----------------------------------------------------------------------
// 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.
int agent::mapneighbors(int* map)
{
int xi = (int)x;
int yi = (int)y;
int count = 0; // counts neighbors
*map = 0; // clear the map to start
// getpixel(offscreen) returns 0
if(getpixel(xi-1,yi-1)) { *map |= 128; count++; } // above left
if(getpixel(xi ,yi-1)) { *map |= 64; count++; } // above
if(getpixel(xi+1,yi-1)) { *map |= 32; count++; } // above right
if(getpixel(xi-1,yi )) { *map |= 16; count++; } // to left
if(getpixel(xi+1,yi )) { *map |= 8; count++; } // to right
if(getpixel(xi-1,yi+1)) { *map |= 4; count++; } // below left
if(getpixel(xi ,yi+1)) { *map |= 2; count++; } // below
if(getpixel(xi+1,yi+1)) { *map |= 1; count++; } // below right
return(count);
}
//-----------------------------------------------------------------------
// 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.
// returns TRUE if another cell is in view, FALSE if not.
BOOL agent::sense()
{
if(energy <= 0.)
return(FALSE);
inview = 0; // start with nothing in sight
// mapneighbors(); // construct a map of the neighborhood
double targetx = x;
double targety = y;
while(1) // exits loop if an object sighted or vision ran off screen
{ // because it returns, this loop must be last thing sense() does.
double oldx = targetx;
double oldy = targety;
// must get away from current pixel, or it'll be shown as "occupied" (by itself!)
while(((int)targetx == (int)oldx) && ((int)targety == (int)oldy))
{
targetx += t.cosines[(int)heading];
targety -= t.sines[(int)heading]; // screen's y axis is upside down
}
// our "vision" ran off screen, so we're through looking.
if(((int)targetx >= 640) || ((int)targetx <= -1) ||
((int)targety >= 480) || ((int)targety <= -1))
return(FALSE);
// if new location is occupied, it is the object we're looking at.
if(getpixel((int)targetx,(int)targety))
{
inview = identify((int)targetx,(int)targety);
if(inview)
return(TRUE);
cout << "Warning: Object was sighted that isn't in array.\n";
return(FALSE);
}
if(lookon) // didn't sight anything or run off screen: show where we're looking
putpixel((int)targetx,(int)targety,BLUE);
} // end while(1)
} // end sense()
//-----------------------------------------------------------------------
// 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()
{
while((ip != pgm.length()-1) && (pgm[ip] != 1)) // stop when it hits a 1 or program end
incrementip(FALSE); // (so pgm[0] is next one executed)
}
//-----------------------------------------------------------------------
// 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)
}
//-----------------------------------------------------------------------
// absorb all of another blob's points
void agent::absorb(agent* other)
{
int count = other->par.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
add(other->par[i]); // add point to ours,
other->par.Flush(TShouldDelete::NoDelete); // remove all from theirs
// calccentofmass(); // new points changed the center of mass
}
//-----------------------------------------------------------------------
// find mass center of all points on screen
// uses average, could use least squares
// it averages the already-calculated centers of masses of all the blobs
void screencenterofmass(double* x, double* y) // variables to fill
{
double sumx, sumy;
sumx = sumy = 0.;
int count = ag.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
{
sumx += ag[i]->x; // (x,y) is the center of mass of this blob
sumy += ag[i]->y;
}
*x = sumx / (double)count;
*y = sumy / (double)count;
} // end screencenterofmass()
//-----------------------------------------------------------------------
// returns pointer to nearest cell neighbor, or 0 if none
class agent* agent::identifynearestneighbor()
{
double distance;
double mindistance = 1e6;
int nearest = -1;
int count = ag.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
if(ag[i] != this) // don't find itself
{
distance = calcdistance(ag[i]);
if(distance < mindistance)
{
mindistance = distance;
nearest = i;
}
}
return((nearest == -1) ? 0 : ag[nearest]);
}
//-----------------------------------------------------------------------
// change heading to point at a given point
// Should only be called from run(), because heading isn't adjusted to 0-359.
// complementary turnawayfrom() is easy: just call this, then add 180 degrees.
void agent::turntoward(double towardx, double towardy)
{
if(x == towardx) // target is straight up or down
{
if(towardy < y) // target is directly above
heading = 90.;
else
if(towardy > y) // target is directly below
heading = 270.;
return; // no change if it's sitting on target point
}
if(towardy == y) // straight left or right
{
if(towardx < x) // target is directy left
heading = 180.;
else
heading = 0.; // target is directy right
return;
}
// y axis is inverted.
heading = atan((y - towardy) / (towardx - x)); // returns radians
heading *= 57.29577951; // convert to degrees
// determine if it should actually be to LEFT of y-axis:
if(x > towardx)
heading += 180.;
}
//-----------------------------------------------------------------------
// run() execute next program block of an agent's program
// returns TRUE if cell survived, FALSE if not.
int agent::run()
{
if(energy <= 0.) // dead cell (probably eaten by another, but not yet Destroyed)
return(FALSE);
int neighbormap = 0;
int mated = 0;
int stepmax;
BOOL turned;
double tempx, tempy;
double oldheading; // used to determine how many degrees cell turned
long templong;
class agent* other = 0;
// sense(); // update all sensors for current surroundings/conditions
// ax = 0.; // seems like cheating to reset ax,ip, but cell is "unconscious" while
ip = 0; // the other cells are moving, so you have to.
// limit the # of steps executed to prevent endless loops
// stepmax = STEPMAX; // for same limit for all
stepmax = pgm.length(); // each cell can run its entire pgm once, maximum
for(int stepcount = 0 ; stepcount < stepmax ; stepcount++)
{ // could impose a TIME limit instead.
turned = FALSE;
oldheading = heading;
switch((int)(pgm[ip])) // each case is a basic cell instruction
{
case 0: // move along heading
other = move();
if(other) // If its way was blocked, the two blobs merge.
{
absorb(other);
other->energy = 0;
}
break;
// program control:
case 1: break; // mark as label but do nothing (so it also serves as a NOP)
case 2: jumpforward(); break; // go to next label FORWARD or program start
case 3: if(ax < 0.) jumpforward(); break;
case 4: if(ax > 0.) jumpforward(); break;
case 5: if(ax == 0.) jumpforward(); break;
case 6: if(ax != 0.) jumpforward(); break;
case 7: jumpbackward(); break; // go to PREVIOUS label or program start
case 8: if(ax < 0.) jumpbackward(); break;
case 9: if(ax > 0.) jumpbackward(); break;
case 10: if(ax == 0.) jumpbackward(); break;
case 11: if(ax != 0.) jumpbackward(); break;
case 12: incrementip(FALSE); break; // skip over the next step
case 13: if(ax < 0.) incrementip(FALSE); break;
case 14: if(ax > 0.) incrementip(FALSE); break;
case 15: if(ax == 0.) incrementip(FALSE); break;
case 16: if(ax != 0.) incrementip(FALSE); break;
case 17: ip = 0; break; // Restart Program
case 18: if(ax < 0.) ip = 0; break;
case 19: if(ax > 0.) ip = 0; break;
case 20: if(ax == 0.) ip = 0; break;
case 21: if(ax != 0.) ip = 0; break;
// change heading
case 22: heading = 0.; turned = TRUE; break; // a reference position
case 23: heading += 1.; turned = TRUE; break; // turn 1 degree clockwise
case 24: heading += 90.; turned = TRUE; break; // turn 90 degrees
case 25: heading += 180.; turned = TRUE; break; // turn 180 degrees
case 26: heading -= 90.; turned = TRUE; break; // turn 270 degrees
case 27: heading -= 1.; turned = TRUE; break; // turn 1 degree counterclockwise
// case 28: heading += (double)(random(360)); turned = TRUE; break;// by a random amount
case 28: heading = (double)(random(360)); turned = TRUE; break; // same effect & simpler
case 29: // turn TOWARD center of mass
screencenterofmass(&tempx,&tempy); // (probably useless, but maybe fun to watch)
turntoward(tempx,tempy);
turned = TRUE;
break;
case 30: // turn AWAY FROM center of mass
screencenterofmass(&tempx,&tempy);
turntoward(tempx,tempy);
heading += 180.;
turned = TRUE;
break;
case 31: // turn TOWARD nearest neighbor
other = identifynearestneighbor();
if(other)
{
turntoward(other->x,other->y);
turned = TRUE;
}
break;
case 32: // turn AWAY FROM nearest neighbor
other = identifynearestneighbor();
if(other)
{
turntoward(other->x,other->y);
heading += 180.;
turned = TRUE;
}
break;
case 33: // match heading to nearest neighbor
other = identifynearestneighbor();
if(other)
{
heading = other->heading;
turned = TRUE;
}
break;
// arithmetic
case 34: ax = 0.; break; // zero ax (reset)
case 35: ax = fabs(ax); break; // absolute value of (ax)
case 36: ax = -ax; break; // negative of (ax)
case 37: ax += 1.; break; // increment ax
case 38: ax -= 1.; break; // decrement ax
// variables about itself:
case 39: ax += x; break; // screen location x
case 40: ax -= x; break; // screen location x
case 41: ax = x; break;
case 42: ax += y; break; // screen location y
case 43: ax -= y; break; // screen location y
case 44: ax = y; break;
case 45: ax += heading; break; // heading
case 46: ax -= heading; break; // heading
case 47: ax = heading; break;
case 48: ax += energy; break; // energy
case 49: ax -= energy; break; // energy
case 50: ax = energy; break;
case 51: ax += (double)color; break; // color
case 52: ax -= (double)color; break; // color
case 53: ax = (double)color; break;
// pgm.length()
case 54: ax += pgm.length(); break;
case 55: ax -= pgm.length(); break;
case 56: ax = pgm.length(); break;
// opcode of next program step
case 57: ax += (double)(pgm[ip < (pgm.length()-1) ? (ip+1) : 0]); break;
case 58: ax -= (double)(pgm[ip < (pgm.length()-1) ? (ip+1) : 0]); break;
case 59: ax = (double)(pgm[ip < (pgm.length()-1) ? (ip+1) : 0]); break;
// pointer to agent being sighted
case 60: templong = (long)inview; ax += (double)templong; break;
case 61: templong = (long)inview; ax -= (double)templong; break;
case 62: templong = (long)inview; ax = (double)templong; break;
case 63: templong = (long)this; ax += (double)templong; break; // pointer to itself
case 64: templong = (long)this; ax -= (double)templong; break; // pointer to itself
case 65: templong = (long)this; ax = (double)templong; break; // pointer to itself
// variables about the object in sight (must prohibit if no object):
case 66: if(inview) ax += inview->x; break; // screen location x
case 67: if(inview) ax -= inview->x; break; // screen location x
case 68: if(inview) ax = inview->x; break; // screen location x
case 69: if(inview) ax += inview->y; break; // screen location y
case 70: if(inview) ax -= inview->y; break; // screen location y
case 71: if(inview) ax = inview->y; break; // screen location y
case 72: if(inview) ax += inview->heading; break; // heading
case 73: if(inview) ax -= inview->heading; break; // heading
case 74: if(inview) ax = inview->heading; break; // heading
case 75: if(inview) ax += inview->energy; break; // energy
case 76: if(inview) ax -= inview->energy; break; // energy
case 77: if(inview) ax = inview->energy; break; // energy
case 78: if(inview) ax += (double)(inview->color); break; // color
case 79: if(inview) ax -= (double)(inview->color); break; // color
case 80: if(inview) ax = (double)(inview->color); break; // color
// length of other's pgm
case 81: if(inview) ax += (double)(inview->pgm.length()); break;
case 82: if(inview) ax -= (double)(inview->pgm.length()); break;
case 83: if(inview) ax = (double)(inview->pgm.length()); break;
// what the object in view HAS in view (me?)
case 84: if(inview) {templong = (long)(inview->inview); ax += (double)templong;} break;
case 85: if(inview) {templong = (long)(inview->inview); ax -= (double)templong;} break;
case 86: if(inview) {templong = (long)(inview->inview); ax = (double)templong;} break;
case 87: if(inview) ax += calcdistance(inview); break; // distance to object in sight
case 88: if(inview) ax -= calcdistance(inview); break; // distance to object in sight
case 89: if(inview) ax = calcdistance(inview); break; // distance to object in sight
// variables about the overall environment
case 90: ax += ag.GetItemsInContainer(); break; // total current population
case 91: ax -= ag.GetItemsInContainer(); break; // total current population
case 92: ax = ag.GetItemsInContainer(); break; // total current population
case 93: screencenterofmass(&tempx,&tempy); ax += tempx; break; // center of mass x
case 94: screencenterofmass(&tempx,&tempy); ax -= tempx; break; // center of mass x
case 95: screencenterofmass(&tempx,&tempy); ax = tempx; break; // center of mass x
case 96: screencenterofmass(&tempx,&tempy); ax += tempy; break; // center of mass y
case 97: screencenterofmass(&tempx,&tempy); ax -= tempy; break; // center of mass y
case 98: screencenterofmass(&tempx,&tempy); ax = tempy; break; // center of mass y
// REMEMBER TO ADD ALL NEW CASES TO OPCODES[]!!!!
} // end switch
// the following steps are all performed after each opcode is executed
if(turned)
{
// 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;
if(heading >= 360.) heading -= 360.;
if(heading < 0.) heading += 360.;
// sense();
}
incrementip(TRUE); // increment instruction pointer
}
return(TRUE); // survived alive
} // end run()
// end agent member functions
/////////////////////////////////////////////////////////////////////////
// global functions
//-----------------------------------------------------------------------
// display a short program description
void intro()
{
}
//-----------------------------------------------------------------------
// show the help screen
void drawhelp()
{
cout << "\nCall program with: DLA option\n";
cout << "Options:\n\n";
cout << "H Just show this help screen and exit\n";
cout << "Lfname Load .PIC file before starting\n";
cout << "#### Plot this many points (default = " << AGSTART << ")\n";
cout << "\nThese commands are available while program is running:\n\n";
cout << "B BEEP (sound effects) (toggle)\n";
cout << "E Save picture and Exit\n";
cout << "H HELP (show this screen)\n";
cout << "M MASS - Show center of mass once\n";
cout << "P PAUSE (any key to resume)\n";
cout << "R RESTART new game\n";
cout << "T TRAIL display (toggle)\n";
cout << "<ESC> Quit without saving\n\n";
presskey();
}
//-----------------------------------------------------------------------
// redraw all the agents on the screen
void drawagents()
{
clearviewport();
int count = ag.GetItemsInContainer();
for(int i = 0 ; i < count ; i++)
ag[i]->showpoints();
}
//-----------------------------------------------------------------------
// 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.
class agent* selectcell()
{
int ch; // USER INPUT
int oldcolor;
class 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(),WHITE); // start with cursor on
cout << "\a"; // audible tone: now in View mode.
while(1)
{
ch = ci(); // wait for user input
putpixel(getx(),gety(),oldcolor); // before moving, restore cell
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()))
selection = identify(getx(),gety());
return(selection);
} // END SWITCH
oldcolor = getpixel(getx(),gety()); // save original color of new location
if(oldcolor != BLACK) // audible signal that we hit a cell
cout << "\a";
putpixel(getx(),gety(),WHITE); // cursor on while idle
} // END WHILE(1)
} // end selectcell
//-----------------------------------------------------------------------
// view data about a cell, including its program
void viewcell()
{
class agent* a = selectcell();
if(!a)
return;
int opcode;
while(1)
{
clearviewport();
cout << "\n#" << a->birthorder << " at (" << ((int)(a->x)) << "," << ((int)(a->y)) << ")";
cout << " Heading: " << ((int)(a->heading)) << " Color: " << 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 << " Cellcount: " << a->par.GetItemsInContainer();
cout << endl << endl;
int count = a->pgm.length();
for(int i = 0 ; i < count ; i++)
{
opcode = (int)(a->pgm[i]);
cout << (i+1) << "." << '\t'; // give the pgm steps line numbers
cout << opcode;
if(a->ip == i) // star shows current ip location
cout << "*";
cout << '\t';
if(opcode < ICOUNT) // prevent trying to print opcode text that is
cout << 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();
}
if(!yesno("Done. Show list again"))
break;
}
}
//-----------------------------------------------------------------------
// main()
int main(int argc,char** argv)
{
int i, grmode;
int ch; // USER INPUT
int loadfile = FALSE; // whether to start by loading a file
int pointcount = AGSTART; // number of points to start with
double tx, ty; // used for center of mass calculation
randomize();
intro();
drawhelp();
if(argc > 1)
{
if(tolower(argv[1][0]) == 'h') // HELP ONLY
return(0);
i = atoi(argv[1]);
if(i > 0)
pointcount = i;
if(tolower(argv[1][0]) == 'l') // LOAD FILE BEFORE START
loadfile = TRUE;
}
grmode = initgraf();
if(loadfile)
if(picload(&(argv[1][1])) == EOF)
aborts("Input file not found or corrupt.");
while(1)
{
childcount = 0L;
clearviewport();
ag.Flush(TShouldDelete::Delete); // empty array
for(i = 0 ; i < pointcount ; i++) // fill it back up
ag.Add(new agent);
while(1)
{
if(kbhit())
{
ch = tolower(getch());
if(ch == 'r') // restart
break;
switch(ch)
{
case 'e':
picsave("SCREEN.PIC"); // save-exit
case 27: // user quit
nosound(); // just in case
closegraph();
return(0);
case 'b': beepon = !beepon; break; // toggle sound effects
case 'd': delayon = !delayon; break; // toggle delay
case 'h': // help
restorecrtmode();
drawhelp();
setgraphmode(grmode);
drawagents();
break;
case 'l': lookon = !lookon; break; // toggle showing where cell is looking
case 'm': // show center of mass
screencenterofmass(&tx,&ty); // show where center of mass is
setcolor(GREEN);
circle(tx,ty,2);
setcolor(RED);
circle(tx,ty,1);
break;
case 'p': getch(); break; // user pause
case 't': trailon = !trailon; break; // toggle trail display
case 'v': viewcell(); drawagents(); break; // view cell's program
}
} // end if(kbhit())
// Destroy() can't be done in run() or any member function because it would be
// Destroy(this), which seems disastrous.
for(i = 0 ; i < ag.GetItemsInContainer() ; i++) // run each cell's program
{
if(ag[i]->energy <= 0.) // cell was absorbed into another,
ag[i]->reinit(); // so just re-init it at a new location
ag[i]->run();
}
} // end inner while(1)
} // end outer while(1)
} // end main()
Copyright ©2008
Steven Whitney. Last modified
07/06/2008.
