A* Algorithm with Python-Pygame

[Beriaal]

Very impressive

[CorneliusPappenheime]

Better than minecraft pathfinding

[stonetwig]

Nice done :)

[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

[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

[HierisBestand]

epic :D

[kenorb2]

you have broken links in that page

[SOPM2007]

Very interesting! Recently I was thinking about to learn Python - the programming with the snake ;-))

[pVVENx]

Oops, I meant the maze in the middle of the video, around 0:40

[pVVENx]

When you draw that maze at the end, why does it continue pathfinding going left from the first big wall? Shouldn't it only expand out when it finds an obstacle, and not if its found a suitable path to follow?

Or is it that I just have the benefit of seeing the maze's layout, and it's checking other possibilities when hitting a dead end?

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

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



[Stauricus]

freakin cool :D

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

[timonix2]

@Keebus87 i guessed, it just seemed so slow and I just chose to blame it on the gui as it has a tendency to be inefficient.

[a00021]

Hey Keebus, is there any chance you can re-upload the source somewhere? I'm really interested in taking a peek, since I have no idea how A* (and pygame, for that matter) works - I'm wondering if I can spot the similarities to dijkstra =]

Cheers,

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

[WhiteDragon103]

you should deprioritize seaches that stray away from the target point. 0:51 A more efficient algorithm would not fill the entire left side of the screen.

[micfoley8]

is it a DFS algorothm?

[etskh]

@micfoley8 A* is an elaborated Dikjstra's Algorithm which is an elaborated BFS algorithm. So, no it isn't.

[dragonmekill]

says the code is broken bro...

[Buttons840]

Your source code is no longer available from the pygame website. Also, the heuristics to guess which would be the next best node to search could use some work. In the second example it's searching open nodes (green ones) which are far away instead of those which are close to the goal. You seem to sort the open nodes (green squares) based on their distance from the beginning rather than their distance from the ending goal?

Great video, 5 star. I want the source code, so please fix the link.

[SpecklePattern]

Not really optimized on the simple problems but the maze was nice :)

[Neomex000]

it works so slow, or you just make it for show?

[thrasas]

i think pygame makes it slow

[zamliman]

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

[QuaziGNRLNose]

not really advanced, just a bitch to program

[spiricn]

@QuaziGNRLNose it's not really a bitch to program either if you know what you're doing ..

[bedmanz]

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

[AlbertoEAF]

Downloaded the source but only see the panels and the background is completely black!?!? Everything is installed correctly because other python games that require pygame work perfectly

[superscatboy]

Nice work on the GUI!

I realise that A* itself is very easy to implement (and nice and quick to run if you don't animate the process), but I'm most impressed by the GUI elements. What library did you use for that part?

[AlbertoEAF]

AWESOME!!

Can you reupload the source-code somewhere else or send it in a message to my youtube's account?

The site is down! :(

[RussianDesert]

Very Very nice keep on work!

[rainydays925]

nice job. ive been trying to get A* working in a game im writing in Obj-C. nice video.

[Keebus87]

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

[blytqb]

please give some infos.. great job!

[faraday428]

very great, first time to see such great GUI a* algorithm.

[jamboylew]

i dont get it...

[fyamnky]

holy shit. how long did it take you to code this? and more importantly is the source online somehwere?

[McBainMwa]

Very nice!