I want to have an algorithm that computes a path through a 2d maze like this: I was thinking of having a NN where each node is a tile on the maze the input is a 1 or 0 that corresponds to filled or not and it outputs a path through the maze in the same format, where 1 indicates a tile on the solution path and 0 indicates a tile not on the solution path. You could also do a GA where the solutions are 2d tilemaps where all the tiles that belong to the solution are filled in. This would keep the solutions DNA at a constant length. So will this work?

I don't think either neural nets or a GAs are good tools for maze pathfinding. If you want to pathfind, use some implementation of A*.

http://www.policyalmanac.org/games/aStarTutorial.htm

-me

Why would you complicate a trivial problem?

I know about a star but I want to do something different!

Quote: Original post by Malamute
I know about a star but I want to do something different!

That's fine as long as you're just doing it to play around with different AI algorithms. Otherwise, both those approaches are just plain bad choices for pathfinding. Pathfinding through a maze is pretty close to a "solved" problem.

If you really just want to play around with those algorithms it might be a lot more useful if you pick some problems that they're actually good at solving. (google can fill you in on those)

-me

GAs and NNs are not appropriate tools for this. It's like asking "How do I drive a nail into a piece of wood with a duck or echidna? I know about hammers, but I want to do something different."

ok well would it work at all if I attempted this?

I suppose it might. It certainly wouldn't work well. It would most likely be a disappointment. But you could probably make it work some of the time on especially simple mazes (like, 4x4 or something).

Out of those two options I think a GA is a better option than an NN, but as mentioned previously neither are overly suitable options for the task. As a side note I dont think DNA is common terminology for GAs, 'Genomes' are and 'Chromosomes' maybe, but DNA stands for Deoxyribonucleic acid which a GA doesnt encounter - I think its just too 'low level'?

I used to design/program for micromouse robots and we used to use a weighted flood-fill algorithm, give it a look.

If the entrance and the exit to the maze are both on the 'outside', then place one hand on a wall and just start walking. You will eventually find the exit. This does not work if the exit or entrance is on an island in the middle though.

--
This hammer is good enough to drive a railroad spike! Now where's that roofing nail?