Sign in to follow this  
DanBrink

Genetic Algorithm Maze Solver

Recommended Posts

DanBrink    122
I'm trying to write a program that utilizes a genetic algorithm to solve a small maze. This is for a project in school where I'm studying the effectiveness (or ineffectiveness from what I hear...) at using genetic algorithm to solve a maze. My teacher wants me to do it in C++, even though I'm pretty poor in it. I've got the gist of what I want to do, I just find myself looking up little nitpick things about C++ (like setting up a multidimensional array). Here's basically what I have planned for the program: Have the maze as a constant 2D array of 0s and 1s (0=walkable 1=not) Then generate a starting population which would just be a series of random directions. Sort them based on how close they get to the target. Crossover and Mutate. I hope for the maze to be a 3x5 array, something like: const int maze[3][5] = [[0,0,1,1,1],[1,0,0,0,0],[1,0,0,0,2]]; //Maze, 2=goal I'm confused on how to do the genes, I want to have a coordinate structure and then have an array of it. Something like coords path[15] = [[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0],[1,0]] where its the [change in x, change in y] [1,0] would be moving one to the right. I THINK I have the concept down, I just need help generating the C++ code. I come from a Pascal / Flash (Actionscript) background.

Share this post


Link to post
Share on other sites
assaf    260
Hey there Dan!

Your general ideas seem fine. I'm not 100% what you mean by "coordinate structure", but the idea to use 2 bits to represent a step is correct. Is there anything in particular that confuses you?

You could also allow for variable length for your genetic code vector, although at first I recommend you stick with a constant length vector, having 2*n bits (where n is the maximal number of steps - 15 in your example).

Regarding the c++ part, I'm not the best person around to help you out, I hope someone with better skills than myself comes along :). But it seems to me that you'd like to have some class "GeneticCode" with methods Mutate, (static?) CrossOver and so forth.

Share this post


Link to post
Share on other sites
DanBrink    122
Transitioning to C++ is by far the hardest part, I'm getting tons of errors and I know its all just little things. Now that I think about it, this probably would've done better posted in a C++ category rather then a AI one (Now that I know I'm doing it correctly anyhow).

If someone could debug my very poorly written code, I would VERY much appreciate it. A friend of mine mentioned classes over structs, I'm all for that I just saw a struct used a GA library so I started using them (Although, not very effectively.)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include<conio.h>

struct gene
{
int path[14];
float fitness;
};

struct coords
{
int x;
int y;
};

const int maze[3][5] = [[0,0,1,1,1],[1,0,0,0,0],[1,0,0,0,2]]; //Maze
const coords goal;
coords goal.x = 3; //Coords of Goal
coords goal.y = 5;
/*
Maze Layout:
00111
10000
10002
*/


/*
float evalFitness(gene g) //takes the path and evaluates its fitness
{

return fit;
}

int[] evalEnd(int[][] path) //Evaluates the final point of a path
{

}

void generateGene() //Generate a gene and create a random path for it.
{
coords path[14];
for(int i = 0;i<=14;i++)
{
path[i].x =rand() % 2 + 1;
path[i].y =rand() % 2 + 1;
}
return path;
}
*/
int main(void)
{
srand ( time(NULL) );
getch(); //Wait for a key before closing the program.
return 0;
}


I'm trying to have path be a array of the differences in X and Y, consult my original post for more information on that.

Lastly, thanks for the reply! I'm glad someone looked at and took the time to reply in such a timely manner.

P.S. By coordinate structure I meant the struct coords, so I could use X and Y of something. I probably did it all wrong though...

Share this post


Link to post
Share on other sites
Steadtler    220
A little reflexion here:

Think about what you are doing. Why would crossing over two paths (as described) in the action space wield you a good path? The resulting path could lead you ANYWHERE, and most likely will be an invalid path (bumping into walls).

As people told you before, using GA to solve a maze is pretty dumb. But the way you describe your solution, its not even a gradient descent search (as usual with GA), but its a completely random search, and not a very good one.

The only way I see to solve this problem with GA would be to label each intersection in the maze, and use have each "gene" to describe the direction the agent will take at each particular crossing (N,E,S,W). Then your "cross over and mutate" will at least have some sense, and the algorithm will *maybe* converge (but is unlikely too given large complex mazes).

Share this post


Link to post
Share on other sites
Steadtler    220
Quote:
Original post by DanBrink
Thanks for the insight, I had originally planned something like that.

I still need help with fixing that C++ syntax if anyone cares to help me with it.


Well, lets see. First, your code aint C++, its all C.

These headers:

Quote:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include<conio.h>


are all depreciated in C++, you are using multi-dimensional C-style arrays, you are using structs without any constructor or operators... its all C. I suggest grabbing a C++ book and doing some exercices, peaking in other people's source code won't teach you object-oriented programming (not correctly anyway). As for the syntax, the compiler should tell you, is there a particular error that you can't understand?

Share this post


Link to post
Share on other sites
DanBrink    122
Could you define the constant multidimensional array for me? I've been getting TONS of errors from it.

Also (If you could possibly spare more time for me) a brief overview of what classes you think I should create (I'm decently familiar with classes from C# games I made)

Share this post


Link to post
Share on other sites
Steadtler    220
Quote:
Original post by DanBrink
Could you define the constant multidimensional array for me? I've been getting TONS of errors from it.

Also (If you could possibly spare more time for me) a brief overview of what classes you think I should create (I'm decently familiar with classes from C# games I made)


1- Just dont use multidimensional c-style arrays. Its a thing of the past. Either use an STL container (std::map for example), or create your own "map" class that wrap around an 1D buffer. And load the maze from file, you can't possible "study the effectiveness" of anything with just one hardcoded sample.

2-No, that would be too close to doing your homework, plus I dont do GAs.

Pardon my bluntness, but you seem way over your head. You dont seem to have either the AI nor the coding background to be doing that kind of stuff right now. Did you choose this project or is this an assignement?

Share this post


Link to post
Share on other sites
DanBrink    122
This was an assignment not taken by choice,I'd like to think I could complete this despite my horrible C++ skills, you're not out of line to think this may be a bit over my head, but I'm trying to make it work not make it work nicely, effectively, or any of that jazz. I'm just trying to get it done.

I'd much rather use an array because I'm familiar with it but if I were to use the map container would it go something like this?

Would I do something along the lines of this to define it:
std::map <int, int[]> map;
map[1] = [0,0,1,1,1];
map[2] = [1,0,0,0,0];
map[3] = [1,0,0,0,2];

Then to call a particular value could I...

map[1][0] = 0;

As for classes, I was thinking one for the gene (get fitness, hold path, find end point) and one for the population (breed, mutate, elitism). I've failed horrible at OOP every time I tried, so I'm trying to keep this simple.

Thanks for your help so far Steadtler, if you ever need help with web programming maybe I could return the favor (Although, I find it a lot easier then this stuff and I'm sure you do/would too)

Share this post


Link to post
Share on other sites
Steadtler    220
Im not impressed by your teacher for giving out an assignement to students who dont have the proper background to understand it. You need some basis in AI to understand just what GA are really doing, and to get just how dumb and hopeless trying to solve a maze with a GA is.

Anyway, forget std::map for now, seems a bit too much. Just study how classes works in C++ and make a class like this:


const int maxsize = 100; //max 10x10 maze;

class mazemap
{
public:
mazemap(int sizex, int sizey); //constructor
void Build(); //fill your buffer in this operator
bool CanPass(int x, int y); //returns the value of the buffer at this point
private:

void SetPass(int x, int y, bool value); //set a value in the buffer
bool _map[maxsize]; //buffer containing the wall/passage value
int _sizex;
int _sizey; //sizex*sizey need to be smaller than maxsize

};


I tried to keep it the simplest possible. The _map buffer is an 1D array, which is easier to manage. To access any "2D" point in the buffer, simply do the maths: (x,y) = y*_sizex + x;

Begin by building this class, what you'll learn should make the rest easier. Then you can manipulate this class instead of manipulating a 2D c-style array, which gets confusing really fast and is prone to errors and typos.

Share this post


Link to post
Share on other sites
DanBrink    122
Thank you for going into such detail Steadtler, I never would've thought of doing the maze that way. I think I have the class set up decently, I'm having trouble with CanPass function. I'm getting numbers like 61, 189, whereas I should be getting true/false. If I do CanPass with a 0 for X it always gives me a 0, anything higher results in some seemingly random integer.
Quote:

const int maxsize = 15; //max 10x10 maze;

class mazemap
{
public:
mazemap(int sizex, int sizey)//constructor
{
_sizex = sizex;
_sizey = sizey;
}
void Build(){//fill your buffer in this operator
for(int i = 0; i<=_sizey; i++)
{
for(int j = 0; j<=_sizex; j++)
{
SetPass(i,j,false);
}
}
}
bool CanPass(int x, int y)//returns the value of the buffer at this point
{
return _map[y * _sizex + x];
}
private:

void SetPass(int x, int y, bool value) //set a value in the buffer
{
_map[y * _sizex + x] = value;
}
bool _map[maxsize]; //buffer containing the wall/passage value
int _sizex;
int _sizey; //sizex*sizey need to be smaller than maxsize

};

int main(void)
{
mazemap map(5,3);
map.Build();
cout << "(1,1)=" << map.CanPass(1,1);
srand ( time(NULL) ); //prepare
getch(); //Wait for a key before closing the program.
return 0;
}


Thanks in advance to anyone who takes the time to read this.

Share this post


Link to post
Share on other sites
Steadtler    220

Lets see...

First, you ought to put your definitions in a .cpp file, and your declarations in a .h file, just for clarity.

Then in your "build" operator, you have a buffer overflow.


for(int i = 0; i<=_sizey; i++)
for(int j = 0; j<=_sizex; j++)


should be


for(int i = 0; i<_sizey; i++)
for(int j = 0; j<_sizex; j++)


this means that your operators _sizex and _sizey and probably other stuff were overwritten with zeros. Its a good idea to use asserts in operators like setpass and canpass to verify the validity of the inputs...

Also, remember that "false" is defined as zero while "true" is ANYTING but the zero-value.

Bufferoverflows like that are why you want to learn to use STL in due time :)

Maybe you ought to move this to the begginer's forum; its not exactly an AI discussion anymore.

Share this post


Link to post
Share on other sites
DanBrink    122
The only thing I'm confused by at the moment is if I set all the maze values to false (Through the two for loops) Why am I still getting non-zero values when I do a check pass?

Also, Crivens, my teacher was all excited about getting me to use C++. I didn't have much choice in the matter. I think I'll be able to complete this, I've still got a little less then a week and I'm just looking for a very rough, working draft of the program (Although, I'm taking this long just to setup the maze which I thought I'd have done on the first day).

Thanks for all the help guys, if any moderator would like to move this to Beginner's forum feel free too.

Share this post


Link to post
Share on other sites
Deadpenguin    176
** Ignore this post, read my post a few posts down from this one **

First thing you need to get rid of those implicit type cast dependencies.

Have the return logic for your canPass function be based on conditional logic. I.e.:
if(_map[y * _sizex + x]==0||_map[y * _sizex + x]==2) return true;
else return false;

Have your setPass function take an int instead of a boolean (this will also allow you to use this same function to set the exit tile).

Your reliance on the compiler to appropriately cast from boolean to int and back may very well be the cause of your current problems.

Basically never do this:
someInteger = someBoolean;

An explicit way would be:
someInteger = someBoolean?1:0;
someBoolean = someInteger==0?false:true;
but don't use these in your project either.

[Edited by - Deadpenguin on November 29, 2007 2:31:50 AM]

Share this post


Link to post
Share on other sites
Steadtler    220
Quote:
Original post by Deadpenguin
First thing you need to get rid of those implicit type cast dependencies.

Have the return logic for your canPass function be based on conditional logic. I.e.:
if(_map[y * _sizex + x]==0||_map[y * _sizex + x]==2) return true;
else return false;

Have your setPass function take an int instead of a boolean (this will also allow you to use this same function to set the exit tile).

Your reliance on the compiler to appropriately cast from boolean to int and back may very well be the cause of your current problems.

Basically never do this:
someInteger = someBoolean;

An explicit way would be:
someInteger = someBoolean?1:0;
someBoolean = someInteger==0?false:true;
but don't use these in your project either.


I agree on principle, but I fail to see which line(s) in the code provided perform an implicit cast. Must be the lemonade getting to my head.

However, replacing all bool's with int's would allow you to reuse this class as your "gene" class.

Share this post


Link to post
Share on other sites
Deadpenguin    176
Whoops, looks like I switched to the decaf tea too soon. =)

Somehow my brain melded the two code postings by DanBrink and I completely missed that he had redefined his map as a set of boolean values. Doh! (In his original code posting it was a set of integers and his map consisted of values 0-2). My assumption was that 2 was meant to be an exit tile/node.

Also I did not go into depth about implicit type conversions, which the OP may not be familiar with, so an explanation for completeness:

An implicit type conversion is when you assign a value of one type to a variable of another type. (Example: someDouble = someInt) The compiler has to decide how to handle this or throw a type error. In most cases the compiler will attempt to convert your right hand value to the type of the left hand variable. So when you type (someBool = someInt) the compiler will attempt to convert that integer value to a boolean value. This can have unexpected results if you are inexperienced with how the compiler will convert that value.

Had you still been using an array of integers that might have been the problem... =)

Anyways, to the problem at hand. I ran your code and took a good look at it (no dyslexia this time!) and I did see one mistake:

for(int i = 0; i<=_sizey; i++)
{
for(int j = 0; j<=_sizex; j++)
{
SetPass(i,j,false);

Your setPass function takes (x,y,bool) but you're giving it (y,x,bool) since i=y and j=x. That will cause some parts of the array to not be filled as well as over flow. Specifically that will fill index[0,1,2,5,6,7,10,11,12,15,16,17,20,21,22] with zeros.

Switching those lines to:
for(int i = 0; i<=_sizex; i++)
{
for(int j = 0; j<=_sizey; j++)
{
SetPass(i,j,false);

resolved the issue you were having in my compiled version.

I'm just happy I redeemed myself and thank you to Steadtler for not rubbing my nose in my sleepy mistake. =)

Share this post


Link to post
Share on other sites
coderx75    435
Genetic algorithms aren't very good for maze problems. My human brain uses sentient intelligence (version 3.21 beta IIRC) and I know that my highest rate of success would be to simply turn left at every possible opportunity. In a maze purely made of up of unknown decisions (turn left or right or just go straight), there's no wrong or right answer. Genetic algorithms are good for coming to a definable conclusion not random decisions. Unless the algorithm can evolve to eliminate areas, I don't see this working out very well for you (then again, that may be your answer).

You could just present the code for the algorithm and write a paper on why genetic algorithms don't work for mazes, using your experience on the subject.

Share this post


Link to post
Share on other sites
DanBrink    122
Alright guys, I've coded a bit further and I'm now at the crossover stage of my program. Only problem is, I'm getting stuck at one fitness. I output the best fitness after every crossover and it gets stuck on its first fitness, 9.

This is probably the last step in my project as I won't be adding in mutation (probably anyway)
Quote:

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>

const int maxsize = 15; //max 10x10 maze;
const int maxx = 5;
const int maxy = 3;
const int looplimit = 10; //number of times the program loops through process
const int genesize = 19;
const int popsize = 50;

//MAZE CLASS
class mazemap
{
public:
mazemap(int sizex, int sizey)//constructor
{
_sizex = sizex;
_sizey = sizey;
}
mazemap()
{

}
void Build(){//fill your buffer in this operator
for(int i = 0; i<_sizey; i++)
{
for(int j = 0; j<_sizex; j++)
{
SetPass(j,i,0);
}
}
SetPass(3,0,1); //some walls
SetPass(1,1,1);
}
int CanPass(int x, int y)//returns the value of the buffer at this point
{
if(_map[y * _sizex + x]==0||_map[y * _sizex + x]==2) return 0;
else return 1;
}
private:

void SetPass(int x, int y, int value) //set a value in the buffer
{
_map[y * _sizex + x] = value;
}
int _map[maxsize]; //buffer containing the wall/passage value
int _sizex;
int _sizey; //sizex*sizey need to be smaller than maxsize

};

//GENE CLASS
class gene
{
public:
gene() //Constructor
{
_x = 0;
_y = 0;
randomizePath();

}

char getDirection(int index)
{
if(index <= genesize)
{
return(_path[index]);
}
else
{
return 'T'; //getting a T will mean an error
}
}

void SetPath(int index, char dir)
{
_path[index] = dir;
}
void outputCoords()
{
cout << "X: " << _x << " Y: " << _y;
}
double getFitness()
{
return _fitness;
}
void fitness(mazemap maze)
{
for(int n = 0; n <= genesize; n++)
{
switch(_path[n])
{
case 'N': if( maze.CanPass(_x,_y-1)==0 && _y-1 >= 0)
{
_y--;
}
break;

case 'S': if( maze.CanPass(_x,_y+1)== 0 && _y+1 <= maxy)
{
_y++;
}
break;
case 'W': if( maze.CanPass(_x-1,_y) == 0 && _x-1 >= 0)
{
_x--;
}
break;
case 'E': if( maze.CanPass(_x+1,_y) == 0 && _x+1 <= maxx)
{
_x++;
}
break;
}
_fitness = round(sqrt( ((5-_x)*(5-_x)) + ((3*-_y)*(3*-_y))));
}

}

private:


char _path[genesize]; //path of gene
double _fitness;
int _x, _y;
void randomizePath()
{
for(int in = 0; in <= genesize; in++)
{
int n = rand() % 4 + 1;
//cout << n;
switch(n)
{
case 1: SetPath(in,'N'); break;
case 2: SetPath(in,'W'); break;
case 3: SetPath(in,'S'); break;
case 4: SetPath(in,'E'); break;
default: SetPath(in,'N');
} //end switch
} //end for loop
}//end function
};



int main(void)
{
srand ( time(NULL) ); //prepare
mazemap map(maxx,maxy);
map.Build();
gene pop[popsize], oldpop[popsize];

/* for(int i = 0; i<3; i++) //show the map
{
for(int j = 0; j<5; j++)
{
cout << map.CanPass(j,i);
}
cout << "\n";
}
*/


while(pop[0].getFitness()!= 0) // while maze isn't completed
{

for(int n = 0; n <= popsize; n++) //Compute fitness of population
{
pop[n].fitness(map);
}
//SORTING POPULATION BY FITNESS
int i, j, flag = 1; // set flag to 1 to begin initial pass
gene temp; // holding variable
int arrayLength = popsize + 1;
for(i = 1; (i <= arrayLength) && flag; i++)
{
flag = 0;
for (j=0; j < (arrayLength -1); j++)
{
if (pop[j+1].getFitness() > pop[j].getFitness()) // ascending order simply changes to <
{
temp = pop[j]; // swap elements
pop[j] = pop[j+1];
pop[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}

//END SORTING

for(int i = popsize; i >= 0; i--) // Breeding
{
int parenta = rand() % 10 + 1;
int parentb = rand() % 10 + 1;
int crossover = rand() % genesize-1 + 1;//point where parenta and parentb's genes cross
for(int j = 0; j <= genesize; j++)
{
if(j <= crossover)
{
pop[i].SetPath(j, pop[parenta].getDirection(j));
}
else
{
pop[i].SetPath(j, pop[parentb].getDirection(j));
}
}
pop[j].fitness(map); // record the fitness of the newly created gene
}

cout << pop[0].getFitness() << "\n";
}
for(int n = 0; n <= popsize; n++) //show genes' fitness
{
cout << n << ":" << pop[n].getFitness() << " ";
pop[n].outputCoords();
cout << " \n" ;
}
getch(); //Wait for a key before closing the program.
return 0;
}



I pretty much made some messy work-arounds and I wouldn't mind finishing with one. I don't care if its pretty, I just want it to work for the most part.

Thanks for reading and thanks to all of those who've helped me on this program before.

EDIT: After running some tests, it messes up in the cross over part. No idea how though.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this