--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/ga_maze.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,331 @@
+/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ + Genetic Algorithm Maze Test                            +
+ + Author: Matt P.                                        +
+ + Version: 0.5                                           +
+ +                                                        +
+ + Runs a genetic algorithm test using a maze generation  +
+ + and guessing algorithm.                                +
+ +                                                        +
+ + Usage: ga_maze [options]                               +
+ + Options:                                               +
+ + -h                                                     +
+ +      Prints this information.                          +
+ + -v                                                     +
+ +      Turns on verbose output.                          +
+ + -m float                                               +
+ +      Specifies the mutation rate for each generation.  +
+ +      Default: 0.05                                     +
+ +                                                        +
+ + -d float                                               +
+ +      Specifies the survival rate for each generation.  +
+ +      Default: 0.5                                      +
+ +                                                        +
+ + -p integer                                             +
+ +      Specifies the population for each generation.     +
+ +      Default: 1000                                     +
+ +                                                        +
+ + -l integer                                             +
+ +      Specifies the maximum length of the solution code.+
+ +      Default: 20                                       +
+ +                                                        +
+ + -r integer                                             +
+ +      Specifies the number of times to repeat the test. +
+ +      Default: 20                                       +
+ +                                                        +
+ + -c char                                                +
+ +      Specifies the crossover type                      +
+ +       s / 1 - One point crossover                      +
+ +       t / 2 - Two point crossover                      +
+ +       u / 3 - Uniform crossover                        +
+ +      Default: s                                        +
+ +                                                        +
+ + -s integer integer                                     +
+ +      Specifies the size of the maze                    +
+ +      Default: 7 7                                      +
+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
+
+
+module ga_maze;
+
+import aid.ga;
+import tango.math.Random;
+import tango.math.Math;
+import tango.io.Stdout;
+//import tango.text.String;
+import Float = tango.text.convert.Float;
+import Integer = tango.text.convert.Integer;
+
+import bcd.sys.times;
+
+char[] chars = "NESW";
+
+//int numChars = 20;
+int stringLen = 28;
+
+bool[][] maze;
+int w = 7;
+int h = 7;
+
+double average(double[] array){
+	double avg = 0;
+	foreach (double v; array)
+		avg += v;
+	avg /= array.length;
+	return avg;
+}
+
+double stdDev(double[] array){
+	double avg = average(array);
+	double stddev = 0;
+	foreach (double v; array){
+		stddev += (v - avg) * (v - avg);
+	}
+	stddev = sqrt(stddev/array.length);
+	return stddev;
+}
+
+bool[][] generateMaze(uint width, uint height){
+	bool[][] maze;
+	
+	maze.length = width;
+	
+	for (auto i = 0; i < width; i++){
+		maze[i].length = height;
+	}
+	
+	bool rowStart = true;
+	bool vertical;
+	for (auto i = 1; i < width; i+=2){
+		vertical = rowStart;
+		rowStart = !rowStart;
+		
+		for (auto j = 1; j < height; j+=2){
+			maze[i][j] = true;
+			if (vertical)
+				maze[i + ((Random.shared.next(2)-1)?-1:1)][j] = true;
+			else
+				maze[i][j + ((Random.shared.next(2)-1)?-1:1)] = true;
+			vertical = !vertical;
+		}
+	}
+	
+	return maze;
+}
+
+void printMaze(bool[][] m, bool[][] trail = null,char e = '.', char f = 'X', bool outline = true){
+	if (outline){
+		Stdout("+");
+		for (auto j = 0; j < m[0].length; j++){
+			Stdout("-");
+		}
+		Stdout("+").newline;
+	}
+	
+	for (auto i = 0; i < m.length; i++){
+		if (outline) Stdout("|");
+		for (auto j = 0; j < m[i].length; j++){
+			if(m[i][j]) Stdout(""~f);
+			else if(trail && trail[i][j]) Stdout("+");
+			else Stdout(""~e);
+		}
+		if (outline) Stdout("|").newline;
+	}
+	if (outline){
+		Stdout("+");
+		for (auto j = 0; j < m[0].length; j++){
+			Stdout("-");
+		}
+		Stdout("+").newline;
+	}
+}
+
+/++++++++++++++++++++++++++ Foo ++++++++++++++++++++++++++++++/
+
+class Foo {
+	int count = 0;
+	public double calculateFitness(char[] gene){
+		
+		bool canMove(int x, int y){
+			return ((x >= 0) && (x < w) && (y >= 0) && (y < h) && (!maze[x][y]));
+		}
+		
+		double square(int v){
+			return v*v;
+		}
+		
+		/*bool[][] trail;
+		
+		trail.length = w;
+		for(uint i = 0; i < w; i++){
+			trail[i].length = h;
+		}*/
+		
+		double fitness=0;
+		int x = 0;
+		int y = 0;
+		for (uint i = 0; i < gene.length; i++){
+			//trail[x][y] = true;
+			//Stdout(""~gene[i]);
+			if(gene[i] == 'N' && canMove(x,y-1)) y--;
+			if(gene[i] == 'E' && canMove(x+1,y)) x++;
+			if(gene[i] == 'S' && canMove(x,y+1)) y++;
+			if(gene[i] == 'W' && canMove(x-1,y)) x--;
+			
+			if (x == w-1 && y == h-1){
+				return 100;
+			}
+		}
+		
+		fitness = 100 - sqrt(square(x-(w-1)) + square(y-(h-1)));
+		/*if(count < 20){
+			Stdout.format("{} {:.4}",gene,fitness).newline;
+			//printMaze(maze,trail);
+			count++;
+		}*/
+		return fitness;
+	}
+	
+	public char[] getRandomGenotype(){
+		char[] t;
+		t.length = stringLen;
+		for (int i = 0; i < stringLen; i++){
+			t[i] = chars[Random.shared.next(chars.length)];
+		}
+		return t;
+	}
+	
+	public char getRandomChar(uint index){
+		return chars[Random.shared.next(chars.length)];
+	}
+}
+
+/++++++++++++++++++++++ End Foo ++++++++++++++++++++++++++++++/
+
+void usage(){
+	auto s = 
+		"Usage: ga_maze [options]                               \n"
+		"Options:                                               \n"
+		"-h                                                     \n"
+		"     Prints this information.                          \n"
+		"-v                                                     \n"
+		"     Turns on verbose output.                          \n"
+		"-m float                                               \n"
+		"     Specifies the mutation rate for each generation.  \n"
+		"     Default: 0.05                                     \n"
+		"                                                       \n"
+		"-d float                                               \n"
+		"     Specifies the survival rate for each generation.  \n"
+		"     Default: 0.5                                      \n"
+		"                                                       \n"
+		"-p integer                                             \n"
+		"     Specifies the population for each generation.     \n"
+		"     Default: 1000                                     \n"
+		"                                                       \n"
+		"-l integer                                             \n"
+		"     Specifies the maximum length of the solution code.\n"
+		"     Default: 20                                       \n"
+		"                                                       \n"
+		"-n integer                                             \n"
+		"     Specifies how many possibilities there are for    \n"
+		"     each character of the code string.                \n"
+		"     Default: 20                                       \n"
+		"                                                       \n"
+		"-r integer                                             \n"
+		"     Specifies the number of times to repeat the test. \n"
+		"     Default: 20                                       \n"
+		"                                                       \n"
+		"-c char                                                \n"
+		"     Specifies the crossover type                      \n"
+		"      s / 1 - One point crossover                      \n"
+		"      t / 2 - Two point crossover                      \n"
+		"      u / 3 - Uniform crossover                        \n"
+		"     Default: s                                          ";
+	Stdout(s).newline;
+}
+
+void main(char[][] args){
+	Foo f = new Foo();
+	GeneticAlgorithm ga = new GeneticAlgorithm();
+	ga.calculateFitness = &f.calculateFitness;
+	ga.getRandomGenotype = &f.getRandomGenotype;
+	ga.getRandomChar = &f.getRandomChar;
+	ga.fitnessThreshold = 100;
+	int rep = 20;
+	bool dotime = true;
+	
+	
+	for (auto i = 1; i < args.length; i++){
+		char[] arg = args[i];
+		switch (arg){
+			case "-h":
+				usage();
+				return;
+			case "-m":
+				ga.mutationRate = Float.parse(args[++i]);
+				break;
+			case "-d":
+				ga.survivalRate = Float.parse(args[++i]);
+				break;
+			case "-p":
+				ga.startPopulation = Integer.parse(args[++i]);
+				break;
+			case "-l":
+				stringLen = Integer.parse(args[++i]);
+				//ga.fitnessThreshold = stringLen;
+				break;
+			case "-r":
+				rep = Integer.parse(args[++i]);
+				break;
+			case "-v":
+				ga.verbose = true;
+				break;
+			case "-s":
+				w = Integer.parse(args[++i]);
+				h = Integer.parse(args[++i]);
+				stringLen = 2*(w+h);
+				break;
+			case "-c":
+				auto t  = args[++i];
+				switch (t){
+					case "s","1":
+						ga.crossoverType = 1;
+						break;
+					case "t","2":
+						ga.crossoverType = 2;
+						break;
+					default:
+						ga.crossoverType = 3;
+				}
+				break;
+			case "-b":
+				ga.bailout = Integer.parse(args[++i]);
+				break;
+			case "-t":
+				dotime = false;
+				break;
+			default:
+				Stdout.format("Unknown parameter: {}",arg).newline;
+				usage();
+				return;
+		}
+	}
+	
+	double[] time;
+	double[] gens;
+	long start,end;
+	double generations;
+	
+	for(auto i = 0; i < rep; i++){
+		maze=generateMaze(w,h);
+		
+		if(dotime) start = iutime();
+		generations = ga.run();
+		if(dotime) end = iutime() - start;
+		
+		if(dotime) time ~= end;
+		gens ~= generations;
+	}
+	
+	if(dotime) Stdout.format("{0}, {1:.5}, {2}, {3:.5}", average(gens),stdDev(gens),average(time),stdDev(time)).newline;
+	else Stdout.format("{0}, {1:.5}", average(gens),stdDev(gens)).newline; //", {2}, {3:.5}" ,average(time),stdDev(time)
+}
\ No newline at end of file