A* Algorithm with Python-Pygame

My second video about the A* algorithm. I used python to code this little application combined with pygame.

All critics and suggestions are welcome.

Edit: Source code can be found here
http://www.pygame.org/project/767/

Category:

Science & Technology

Tags:

• astar
• pygame
• python
• pathfinding
• artificial
• intelligence
• ai

[timonix2]

i think the gui slows it down too much. make a much simpler one and you might gain a lot in speed

[Keebus87]

@timonix2 speed is intended to be this slow for algorithm showing purposes.

[parthakakoti]

nice man !!!! will you please tell me wat kind of software is this ? you have develoed it or what ? coding much be a hillarios one !

[Keebus87]

@parthakakoti Yes I developed it some time ago using Python/Pygame and my own library for GUI.

[Keebus87]

Read video infos to know where to find the source code.

[zamliman]

wow this is epic, i can't imagine how advanced this is o.o

[Psmc40]

the two press dislike actually dont know makeing a game is difficult -.-

[CorneliusPappenheime]

Better than minecraft pathfinding

[stonetwig]

Nice done :)

[bedmanz]

@zamliman special for you : become lvl 80 is much harder.

[Lytyr]

This is very interesting - I'm going to poke around the code and see what I can learn.

[ZyphyrOfTheWinds]

The download link is broken on pygame.org.  Could you please repost an updated link? I'm planning to use A* for my senior project :D

[wickeand000]

VV more specifically A* calculates the distance a square is from the start vs how far away it is from the finish. so as it searches toward the finish square, the squares to the left of the start also get searched because although they are farther away from the finish, they are also closer to the start. This ensures that the solution it finds is the shortest possible.

[wickeand000]

@pVVENx the way A* pathfinding works is that it keeps spreading from the start point in all possible directions. The black line is just showing the route it thinks is the "best" at that moment in time (notice how in the large maze it can't seem to make up its mind). A* works so well for mazes because a maze provides "pipes" for the algorithm to work through, as opposed to an open map, in which case it acts more like spilling water on the floor.

[HierisBestand]

wouldn't for the maze case it even go faster if you'd do a reverse search too? from the red dot to the green, and then make the 2 endings (current paths) find each other, should be another 40 % off :) in effort