Sign in to follow this  
  • entries
    73
  • comments
    131
  • views
    54684

It breathes!

Sign in to follow this  

83 views

I don't know what to call it.. be a snake or just a person trying to find the exit. Whatever it is, it's a genetic algorithm!

Here's that pathfinding program I promised. It's really easy to play around with as everything can be dynamically changed. I hope it doesn't have any problems running on different computers... though I'm pretty confident about its stability (I'm usually scared to release my programs!) [grin]

Don't forget to read the readme! Straight from the readme:
GA Notes:
- This algorithm tries to find a path between 2 points. Once a solution is found, the path turns red and it pauses for 2 seconds, then forces a re-population. If a solution is not found within 15 seconds, it forces a re-population.
- It uses Roulette Wheel Selection, random per-gene mutation, and single point crossover
- Fitness scores are based on the distance from the end point, 1/(distX*distX + distY*distY + 1), as well as the number of moves made
- I made it so that it could NOT backtrack, ie it cannot visit cells more than once. It's kind of cheap, but it works much faster!
- Meh, it works well on some map configurations, and horribly on others :)"


Its basic but so cool to me because I made it!

Download (459kb)


Sorry about the size of it, it runs on a framework that I'm currently working on which is starting to get large. I need to find a way to compile in only parts of the framework...
Sign in to follow this  


2 Comments


Recommended Comments

Very Nice!! One thing I noticed is that it sometimes takes unnecessary steps to arrive at the goal position. Perhaps you could add a post processing step to optimize the path generated by the GA.

Share this comment


Link to comment
Thanks! You're right, I noticed that too. [grin] It's simply the result of the genetic algorithm. It tries random paths and picks the best ones, but since the fitness function is based on the distance from the end, the path can be non-optimal. I tried to help this by factoring in the number of moves in the fitness function, but it's bound to go out of its way, and I'm not too worried about it :)

Well, I could make it a little better.. I'd rather optimize the GA than do a post-processing step. That would require me having to figure out a way to evaluate the path, and thus code some kind of pathfinding algorithm myself, but I just want the GA to do it!

I could probably tweak the fitness function and also give it more time once it's reached the end to optimize the way to it. Hm.. thanks for the idea!

Share this comment


Link to comment

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