d(MenuKey(key)); } else { whichWindow = FrontWindow(); if (whichWindow != NULL) { myAutomaton = (tomatoPtr)GetWRefCon(whichWindow); if (myAutomaton != NULL) IterateAutomaton(myAutomaton); } } break; case activateEvt: break; case updateEvt: DrawWindow((WindowRef) event->message); break; case kHighLevelEvent: AEProcessAppleEvent( event ); break; case diskEvt: break; } //end of switch (event->what) } void DoClickInList(Point where) { bool isDoubleClick; if (PtInRect(where, &evolutionRecord.listBoundary)) { isDoubleClick = LClick(where, 0, evolutionRecord.generationList); if (isDoubleClick) OpenSelectedAutomaton(); } } void OpenSelectedAutomaton() { Point cell; cell.h=cell.v = 0; LGetSelect(true, &cell, evolutionRecord.generationList); /*If nothing is selected, do nothing... should grey out the menu option!! Use cell.v-1 as index into array, because 0 is the header row -- double-clicking that should do nothing. Also make sure this index does not go past end of array!*/ if (cell.v-1 >= 0 && cell.v-1 < kAutoPerGeneration) { /*If there's already a window open for this automaton, bring that window forward instead of making a new one.*/ if (evolutionRecord.thisGeneration[cell.v-1]->myWindow == NULL) MakeAutomatonWindow(evolutionRecord.thisGeneration[cell.v-1]); else SelectWindow(evolutionRecord.thisGeneration[cell.v-1]->myWindow); } } void DoMenuCommand(long menuResult) { short menuID; /* the resource ID of the selected menu */ short menuItem; /* the item number of the selected menu */ tomatoPtr activeAutomaton; WindowRef activeWindow; menuID = HiWord(menuResult); /* use macros to get item & menu number */ menuItem = LoWord(menuResult); activeWindow = FrontWindow(); if (activeWindow != NULL) activeAutomaton = (tomatoPtr)GetWRefCon(activeWindow); else activeAutomaton = NULL; switch (menuID) { case mApple: switch (menuItem) { case iAbout: DoAboutBox(); break; /*case iQuit: ExitToShell(); break;*/ default: break; } break; case mAuto: switch (menuItem) { case iNew: /*Create custom automata: Not associated with evolution window.*/ activeAutomaton = malloc(sizeof(struct Automaton)); activeAutomaton->partOfList = false; strcpy(activeAutomaton->name, "\pCustom Automaton"); RandomizeAutomaton(activeAutomaton); MakeAutomatonWindow(activeAutomaton); break; case iSave: if (activeAutomaton != NULL) SaveStateFile(activeAutomaton, "/Users/jono/My Code/EvolveMyAutomaton/TestSuite7"); case iReset: if (activeAutomaton != NULL) ClearAutomaton(activeAutomaton); break; case iTestCase1: case iTestCase2: case iTestCase3: case iTestCase4: case iTestCase5: case iTestCase6: case iTestCase7: case iTestCase8: if (activeAutomaton != NULL) LoadTestCase(activeAutomaton, menuItem-iTestCase1); break; } break; case mEvo: switch (menuItem) { case iTest: /*Get the selection from the generationList, and open the corresponding automaton in a new window.*/ OpenSelectedAutomaton(); break; case iFitness: RunFitnessTest(); break; case iNextGen: CreateNextGeneration(); break; } break; } HiliteMenu(0); /* unhighlight what MenuSelect (or MenuKey) hilited */ } void DrawWindow(WindowRef window) { Rect tempRect; GrafPtr curPort; tomatoPtr myAutomaton; RgnHandle visibleRgnHdl; GetPort(&curPort); SetPort(GetWindowPort(window)); BeginUpdate(window); EraseRect(GetWindowPortBounds(window, &tempRect)); DrawControls(window); DrawGrowIcon(window); myAutomaton = (tomatoPtr)GetWRefCon(window); if (myAutomaton != NULL) DrawAutomaton(myAutomaton); else { visibleRgnHdl = NewRgn(); GetPortVisibleRegion(GetWindowPort(window), visibleRgnHdl); LUpdate(visibleRgnHdl, evolutionRecord.generationList); DisposeRgn(visibleRgnHdl); } EndUpdate(window); SetPort(curPort); } void DoAboutBox(void) { (void) Alert(kAboutBox, nil); // simple alert dialog box } void NameAutomaton(const tomatoPtr theAuto, int whatGeneration, short whatLetter) { /*Make a name for this new automaton: naming convention is a number representing generation, followed by a letter representing the unique automaton in that generation. List expects to get pascal-type strings (length byte in position 0, no null termination); Carbon gives us NumToString which makes these.*/ int nameLength; NumToString(whatGeneration, theAuto->name); nameLength = theAuto->name[0]; nameLength++; theAuto->name[nameLength] = (char)(65+whatLetter); /*65 is ascii value for capital A*/ theAuto->name[0] = nameLength; } void InitAutomaton(const tomatoPtr theAuto, WindowRef drawMeHere) { int i,j; SetRect(&(theAuto->outsideEdge), 20, 20, (kAutoSize*10)+20, (kAutoSize*10)+20); for (i=0; i<kAutoSize; i++) for (j=0; j<kAutoSize; j++) theAuto->cellStates[i][j] = false; theAuto->myWindow = drawMeHere; /*This sets the window link, the drawing area, and sets all cells to 0, but does not change the truth table of the automaton.*/ } void RandomizeAutomaton(const tomatoPtr theAuto) { int i, t; /*I could completely randomize the truth table, but automatons generated that way, well, they suck. Their fitness is all so low, and so similar, that the selection pressure doesn't have much to work on, and it would take ages for a decent one to evolve that way. There are 2^2^9 possible nine-input binary automata, which is a big enough number to give Carl Sagan nightmares. To ensure that we are at least starting out in the right galactic cluster of the possibility space, I'll start with a base truth table which is not too horribly wrong, and then mutate that randomly. The base truth table is a simple one: "no change". In other words, if a cell's self-input is true, the result is true. This automaton will obviously not solve the problem, but at least it won't turn the image into complete static after ten iterations.*/ /*The Identity Automaton:*/ for (i=0; i<512; i++) theAuto->truthTable[i] = i & 1; /*the 1s column is the bit that represents self-input.*/ /*Mutate the truth table: select a number of entries equal to the kMutationRate at random, and toggle them.*/ for (t=0; t<kFirstGenVariance; t++) { i = abs(Random()) % 512; theAuto->truthTable[i] = !(theAuto->truthTable[i]); } } void DrawAutomaton(const tomatoPtr theAuto) { Rect oneCell; short i, j; if (theAuto->myWindow == NULL) return; SetPort(GetWindowPort(theAuto->myWindow)); for (i = 0; i < kAutoSize; i++) { for (j = 0; j < kAutoSize; j++) { SetRect(&oneCell, 20 + i*10, 20 + j*10, 30 + i*10, 30 + j*10); if (theAuto->cellStates[i][j]) PaintRect(&oneCell); else EraseRect(&oneCell); } } FrameRect(&(theAuto->outsideEdge)); } void HandleClickInAutomaton(Point where, const tomatoPtr theAuto) { int i, j; if (PtInRect(where, &(theAuto->outsideEdge))) { i = (where.h - theAuto->outsideEdge.left) / 10; j = (where.v - theAuto->outsideEdge.top) / 10; theAuto->cellStates[i][j] = !(theAuto->cellStates[i][j]); DrawAutomaton(theAuto); } } void ClearAutomaton(const tomatoPtr theAuto) { int i,j; for (i = 0; i < kAutoSize; i++) for (j = 0; j < kAutoSize; j++) theAuto->cellStates[i][j] = false; DrawAutomaton(theAuto); } void IterateAutomaton(const tomatoPtr theAuto) { short i, j; bool nextStates[kAutoSize][kAutoSize]; int truthIndex; //int livingNeighbors; /*Each of the 512 entries in the truth table corresponds to one of the possible combinations of the nine inputs. (Nine = the 8 surrounding cells plus this cell.) 2^9 = 512. So to use the function, we take each input, treat it as one bit, put them together to get a number, and use that number as the index into the truth table. If the output of the function is true, this cell will be alive in the next iteration. By the way, cells along the edge are missing one or more neighbor cells; consider those inputs to be false by default.*/ for (i = 0; i < kAutoSize; i++) { for (j = 0; j < kAutoSize; j++) { truthIndex = 0; if (theAuto->cellStates[i][j]) truthIndex += 1; if (i>0 && theAuto->cellStates[i-1][j]) truthIndex += 2; if (i<kAutoSize-1 && theAuto->cellStates[i+1][j]) truthIndex += 4; if (j>0 && theAuto->cellStates[i][j-1]) truthIndex += 8; if (j<kAutoSize-1 && theAuto->cellStates[i][j+1]) truthIndex += 16; if (i>0 && j>0 && theAuto->cellStates[i-1][j-1]) truthIndex += 32; if (i>0 && j<kAutoSize-1 && theAuto->cellStates[i-1][j+1]) truthIndex += 64; if (i<kAutoSize-1 && j>0 && theAuto->cellStates[i+1][j-1]) truthIndex += 128; if (i<kAutoSize-1 && j<kAutoSize-1 && theAuto->cellStates[i+1][j+1]) truthIndex += 256; nextStates[i][j] = theAuto->truthTable[truthIndex]; } } for (i = 0; i < kAutoSize; i++) for (j = 0; j < kAutoSize; j++) theAuto->cellStates[i][j] = nextStates[i][j]; DrawAutomaton(theAuto); } void LoadTestCase(const tomatoPtr theAuto, int whichTestCase) { int i, j, t; /*There are 8 test cases used to asses a certain automaton's fitness for the task of filtering noise from an image. We read those from text files in MakeEvolutionWindow. Each text file is a simple series of 1s and 0s. Any other characters in the file (i.e. whitespace) are ignored. Between them, these test cases comprise both black-on-white and white-on-black lines, horizontal, vertical, diagonal, and curved lines; and lines of varying thicknesses. Though this is far from an exhaustive test suite, it's at least enough variety to test the concept.*/ //Copy the frozen state record from the test suite into the active automaton: for (i=0; i<kAutoSize; i++) for (j=0; j<kAutoSize; j++) theAuto->cellStates[i][j] = evolutionRecord.testSuite[whichTestCase]->cellStates[i][j]; /*Now, after loading the test case, we will add some random noise to it: select n cells at random and toggle them. We want to see how well the automaton can filter out this noise and recover the original test case. The kNoisiness constant, defined in main.h, tells how many cells to toggle. It's set to 100, which out of 1032 total cells means about 10% noise.*/ for (t=0; t<kImageNoisiness; t++) { i=abs(Random())%kAutoSize; j=abs(Random())%kAutoSize; theAuto->cellStates[i][j] = !theAuto->cellStates[i][j]; } DrawAutomaton(theAuto); } int CompareAutoToTest(const tomatoPtr theAuto, const stateRecPtr theState) { /*Return number of cells which are identical between theAuto and theState. It's crucial to pick just the right test criteria to go with the test suite... for example, if the whole test suite is black-on-white, the automata may decide "Hey, the cells are mostly white, so I can get a high score by just turning all cells white!" The test suite contains both white-on-black and black-on-white patterns, so this isn't a problem when running the whole test suite. But when focus-testing on a single test case, we need to weight the score to discourage automata from settling on the "kill all cells" solution. Let's weight the score so that correctly making a live cell alive counts for more than correctly leaving a dead cell dead. This reflects what humans interpret as a good image filter -- we don't want to lose more static if it means losing parts of the picture content. Keeping what should be there is more important than getting rid of what shouldn't be there. Specifically, we will deduct one point for each wrongly dead cell. (If focus-testing on a white-on-black test pattern, these weights should be reversed.)*/ int i, j, total; total = 0; for (i=0; i<kAutoSize; i++) for (j=0; j<kAutoSize; j++) { if (theAuto->cellStates[i][j] == theState->cellStates[i][j]) total++; /*Plus one point for each correct cell...*/ #ifdef kFocusTest /*If focus testing on a black-on-white case (0 through 3), deduct one point for each wrongly dead cell*/ if (kFocusTest<4 && (theAuto->cellStates[i][j] == false) && (theState->cellStates[i][j] == true)) total --; /*If focus testing on a white-on-black case (4 through 7), deduct one point for each wrongly alive cell*/ if (kFocusTest>=4 && (theAuto->cellStates[i][j] == true) && (theState->cellStates[i][j] == false)) total--; #endif } return total; } void RunFitnessTest() { tomatoPtr thisAuto; Str255 scoreString; Point cell; int a, /*Index for automatons...*/ t, /*Index for test suite...*/ n, /*Index for repetitions on test suite...*/ i; /*Index for iterations...*/ for (a=0; a<kAutoPerGeneration; a++) { thisAuto = evolutionRecord.thisGeneration[a]; thisAuto->score = 0; #ifdef kFocusTest /*This option tells us to run the same test pattern repeatedly:*/ for (n=0; n<kTestsPerCase; n++) { LoadTestCase(thisAuto, kFocusTest); for (i=0; i<kIterationsPerTest; i++) IterateAutomaton(thisAuto); /*Rate fitness based only on the one test pattern*/ thisAuto->score += CompareAutoToTest(thisAuto, evolutionRecord.testSuite[kFocusTest]); } thisAuto->score /= kTestsPerCase; /*Divide by number of tests to find average.*/ #else /*Default behavior is to run each test pattern once (or kTestsPerCase times):*/ for (t=0; t<kNumTestSuite; t++) { for (n=0; n<kTestsPerCase; n++) { LoadTestCase(thisAuto, t); for (i=0; i<kIterationsPerTest; i++) IterateAutomaton(thisAuto); /*IterateAutomaton calls DrawAutomaton, but DrawAutomaton is safe to use even if there is no window open -- it does nothing in that case. With no window open, IterateAutomaton goes very, very fast.*/ /*Rate fitness based on each test pattern*/ thisAuto->score += CompareAutoToTest(thisAuto, evolutionRecord.testSuite[t]); } } thisAuto->score /= (kNumTestSuite * kTestsPerCase); /*Divide by number of tests to find average.*/ #endif /*What does the fitness score really mean? The score we store is the sum of the results over all test patterns, but the score we display in the window is the average over all test patterns. For the purposes of comparing who is most fit, we want to use the sum, because it's less likely to be tied. However, for display, I want to know the average, to see how close the fitness is to the target. The "perfect" score would be 1024 -- every pixel in the image correct. Since we introduce 100 incorrect pixels of "static" when starting the test, there are 924 correct pixels when the automaton starts operating. Therefore, if the average score is below 924, the automaton is actually making the image WORSE. Our goal is to find an automaton that gets between 924 and 1024, the higher the better.*/ /*Update its score in the list:*/ cell.h=1; cell.v=a+1; NumToString(thisAuto->score, scoreString); LSetCell(scoreString+1, (SInt16)scoreString[0], cell, evolutionRecord.generationList); /*Refreshing the score list periodically would show the user that something is happening and that the program has not just hung.... I'd like to do that but just calling update doesn't work, because the event loop never regains control. Hmmm.*/ } } void CreateNextGeneration() { /*Take the N most fit. (defined in the constant kNumSurvivors). Produce 1 offspring from every possible pair. Make sure to choose kNumSurvivors and kAutoPerGeneration so that kNumSurvivors*(kNumSurvivors-1) == kAutoPerGeneration. For example, 6*5 == 30.*/ int a, b, c; tomatoPtr best[kNumSurvivors]; tomatoPtr nextGeneration[kAutoPerGeneration]; Str255 newFitnessString; Point listCell; /*Even though we have the fitness of all automata, the algorithm to find the best N of an unsorted list is non-trivial. best[0] will be the best, best[1] will be the next best, etc. Let each cantidate push its way up towards number 0, bumping less fit ones out of the way.*/ best[0] = evolutionRecord.thisGeneration[0]; for (a=1; a<kNumSurvivors; a++) best[a] = NULL; for (a=1; a<kAutoPerGeneration; a++) { for (b=0; b<kNumSurvivors; b++) { if (best[b] == NULL || evolutionRecord.thisGeneration[a]->score > best[b]->score) /*Found a slot in best where thisGeneration[a] deserves to go -- the first empty slot, or the first slot with an automaton less fit than this one.*/ { if (best[b] != NULL) /*If this deserved slot is not empty, push everything else in the array to the right; the least fit one will fall off the end, and the array will still be sorted.*/ { for (c=kNumSurvivors-1; c>b; c--) best[c] = best[c-1]; } best[b] = evolutionRecord.thisGeneration[a]; break; /*out of the inner loop, and go on to next a in thisGeneration.*/ } } } /*OK, best now contains pointers to the best N automata. Now for each pair of those, we generate an offspring. We will use a temporary array to hold the next generation, then once we have them all, we will delete the old ones and copy the new ones into evolutionRecord.*/ evolutionRecord.whatGeneration ++; /*From here on, a and b are indices of parents, c is index of offspring*/ c = 0; for (a=0; a<6; a++) { for (b=0; b<6; b++) { if (a==b) continue; /*Don't mate with yourself!*/ /*make two offspring:*/ nextGeneration[c] = NewAutomatonByMating(best[a], best[b], evolutionRecord.whatGeneration); /*This will do the malloc, etc*/ NameAutomaton(nextGeneration[c], evolutionRecord.whatGeneration, c); c++; /* nextGeneration[c] = NewAutomatonByMating(best[a], best[b], evolutionRecord.whatGeneration); NameAutomaton(nextGeneration[c], evolutionRecord.whatGeneration, c); c++;*/ } } /*OK, now delete the old generation and put in the new ones:*/ newFitnessString[0]=1; newFitnessString[1]='?'; for (a=0; a<kAutoPerGeneration; a++) { free(evolutionRecord.thisGeneration[a]); evolutionRecord.thisGeneration[a] = nextGeneration[a]; /*Meanwhile, put the new names into the list.*/ listCell.h = 0; listCell.v = a+1; LSetCell(evolutionRecord.thisGeneration[a]->name +1, evolutionRecord.thisGeneration[a]->name[0], listCell, evolutionRecord.generationList); listCell.h = 1; LSetCell(newFitnessString+1, newFitnessString[0], listCell, evolutionRecord.generationList); } /*Finally, refresh the window to show changes:*/ DrawWindow(evolutionRecord.evolutionWindow); } tomatoPtr NewAutomatonByMating(const tomatoPtr mother, const tomatoPtr father, int generation) { tomatoPtr baby; int i; baby = malloc(sizeof(struct Automaton)); baby->partOfList = true; baby->myWindow = NULL; baby->score = 0; for (i=0; i<512; i++) { /*For each entry in truth table, flip a coin to see if it comes from father or mother.*/ if (abs(Random())%2 == 0) baby->truthTable[i] = father->truthTable[i]; else baby->truthTable[i] = mother->truthTable[i]; /*Now add a chance of mutation! I ran it for twenty generations without any mutations first. The fitness scores seemed to approach 924 asymptotically, but nothing got above the magic number. (924 is the magic number -- less means you are making the image worse, more means you are making it better.) I hypothesize that without muatations, there is nothing in the "gene pool" other than the (worthless) stuff that started there, so at some level no new improvements can be made. Now let's try it with mutations...*/ if (abs(Random())%1000 <= kMutationsPerThousand) baby->truthTable[i] = !(baby->truthTable[i]); } return baby; } void OpenStateFile(const stateRecPtr putStateHere, char *filename) { FILE *stateFile; char c; int i,j; /*Major flaw of this program as it currently stands is that it can't find the files if they are outside of the directory...*/ stateFile = fopen(filename, "r"); if (stateFile == NULL) return; for (i=0; i<kAutoSize; i++) for (j=0; j<kAutoSize; j++) { do { if (fscanf(stateFile, "%c", &c) == EOF) { fclose(stateFile); return; } } while (!(c=='0' || c=='1')); /*If it's any char besides 0 and 1 (like, say, newline), discard it and read another one!*/ putStateHere->cellStates[i][j] = (c=='1'); } fclose(stateFile); } void SaveStateFile(const tomatoPtr theAuto, char *filename) { FILE *stateFile; int i,j; stateFile = fopen(filename, "w"); if (stateFile == NULL) return; for (i=0; i<kAutoSize; i++) { for (j=0; j<kAutoSize; j++) { if (theAuto->cellStates[i][j]) fprintf(stateFile, "1"); else fprintf(stateFile, "0"); } fprintf(stateFile, "\n"); } fclose(stateFile); } /*void CToPascal(char *cString) { short len, i; char temp; len = strlen(cString); for (i=len; i>0; i--) cString[i] = cString[i-1]; cString[0] = len; }*/