Jump to content
  • Advertisement
Sign in to follow this  
Malamute

Genetic Algorithmn or Neural Networks for finding pathway in a maze?

This topic is 3942 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 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?

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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."

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

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!