Jump to content
  • Advertisement
Sign in to follow this  
DanBrink

Genetic Algorithm Maze Solver

This topic is 3858 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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.x =rand() % 2 + 1;
path.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
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
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.

Share this post


Link to post
Share on other sites
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!