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.

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]]; //Mazeconst coords goal;coords goal.x = 3; //Coords of Goalcoords goal.y = 5;/*Maze Layout:001111000010002*//*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...

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).

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.

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?

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)

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?

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)

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 pointprivate:   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.