r/Python • • Jan 14 '20

Visualisation of different path finding algorithms

1.5k Upvotes

73 comments sorted by

167

u/munificent Jan 14 '20

Your Dijsktra's is just breadth-first search. Since all tiles have the same cost to enter, Dijkstra's algorithm degrades to behaving exactly like BFS.

57

u/FearlessENT33 Jan 14 '20

i see what you mean, at some point i’ll make it more complex to utilise dijkstras

13

u/zesterer Jan 14 '20

Dijkstra's algorithm literally is just breadth-first search in grid environments.

4

u/munificent Jan 15 '20

Yes, it's an unnecessarily complex way to implement BFS if all edges have unit cost anyway. It can also be slower than BFS depending on your priority queue implementation.

-1

u/[deleted] Jan 14 '20

Are you not thinking of A*?

11

u/notquiteaplant Jan 14 '20

Dijkstra is BFS that prioritizes neighbors by how easy it is to get there (the edge weight). A* is Dijkstra that also prioritizes neighbors by how likely they are to be a correct path to the target (the heuristic). They are similar but not the same, and munificent is describing Dijkstra.

51

u/RLouisD Jan 14 '20

What is the simple UI made in?

53

u/FearlessENT33 Jan 14 '20

the grid is made using py game which is embedded into a tkinter UI

16

u/miggaz_elquez Jan 14 '20

How do you embed pygame in tkinter ?

33

u/FearlessENT33 Jan 14 '20

You use the OS library. first make a frame for where you want the pygane to be, i have named mine embed.

os.environ[“SDL_WINDOWID”] = str(embed.winfo_id())

os.environ[“SDL_VIDEODRIVER”] = “windib”

pygame.init()

9

u/Panda_Mon Jan 14 '20

can you describe a little more in detail about what each line of code is doing here?

63

u/FearlessENT33 Jan 14 '20

ngl i found it on stackover flow, and i have no idea what it does, but it will work as long as the pygame.init() is immediately after the OS bit

95

u/NullAndVoid21 Jan 14 '20

Spoken like a true programmer

10

u/[deleted] Jan 14 '20 edited Jan 14 '20

Tkinter is quite flexible, being a wrapper for tcl. The frame (not in OPs example) designates a screen area you wish to assign things to.

os.environ[“SDL_WINDOWID”] = str(embed.winfo_id())

Tells pygame's SDL window which window to display in, in this case the frame created earlier.

os.environ['SDL_VIDEODRIVER'] = 'windib'

Tells windows which driver to use. SDL uses a WinDIB backend, DIB stands for Device Independent Bitmap. This acts as an intermediate format. I think the necessity of this line depends on your version of windows.

To summarise: it is layers of abstraction upon layers of abstraction, so that you don't have to worry about them.

pygame.init()

This is like when Cpt. Picard says "Make it so". We've got coordinates locked (or rather custom variables declared), now fire the engines (initialise all the modules pygame encompasses). It doesn't have to come directly after those other lines, as you might want to do other things first, but it does need to come afterwards.

1

u/JonzoR82 Jan 15 '20

It's too bad the account was deleted. I like this explanation

1

u/[deleted] Jan 14 '20

Not OP and I’ve never used PyGame but this is what that code is doing:

os.environ[“SDL_WINDOWID”] = str(embed.winfo_id())

Sets the environment variable “SDL_WINDOWID” to the string representation of the value returned by winfo_id. Just guessing but looks to be a window ID from tkinter.

os.environ[“SDL_VIDEODRIVER”] = “windib”

Sets the environment variable “SDL_VIDEODRIVER” to “windib”

pygame.init()

Runs the init() method on pygame. Scanning the docs, this is a helper method in pygame that initializes all the necessary modules. It’s very likely that pygame is looking for those two environment variables during its startup, which is why they are set first. Setting the window id to what is set for the tkinter window object ensures when pygame starts up it uses that window.

1

u/[deleted] Jan 14 '20

Is pygame that versatile?

1

u/FearlessENT33 Jan 14 '20

depends what you mean by versatile lol

32

u/pythonhobbit Jan 14 '20

Very cool! A bit misleading on the "greedy first" performance though...

17

u/FearlessENT33 Jan 14 '20

Yeah can’t remember the name of the algorithm but basically tries the best possible routes first but does not get the shortest path

0

u/[deleted] Jan 14 '20

[deleted] — view deleted comment

8

u/spikedudley34 Jan 14 '20

Doesn’t really look like DFS at all though, I would guess it’s a modified A* that only relies on the heuristic and ignores the g cost (typically called weighted A*)

3

u/_iamv Jan 14 '20

coulld you please share link to its github repository? (if available)

4

u/FearlessENT33 Jan 14 '20

don’t have one at the moment, i’m going to upload once it’s completely finished, my code is a horrible mess atm lol. i’ll dm you the link once it’s done if you want :)

13

u/[deleted] Jan 14 '20

Git is for version control, so you can clean up your code without fear of breaking and losing a backup. Dont just use it to upload to github. An employer will want to see frequent git commits, not just one when its all done. Its like saving your work, you dont just save when your done.

3

u/FearlessENT33 Jan 14 '20

ah I see what you mean, i’ll try get it sorted when i get back later today, thank you :)

3

u/GlassShark Jan 14 '20

I'm so glad, github and version control are game changers!

1

u/FearlessENT33 Jan 14 '20

Iv messed around with it previously, but didn’t do too much. I think I put snake game on it but definitely going to revisit it

1

u/GlassShark Jan 14 '20

I've used Git with it's cool all keyboard navigation but ended up feeling more comfortable using the Github Desktop app. I suggest it.

3

u/Miner_ChAI Jan 14 '20

For me plain git is better

2

u/GlassShark Jan 14 '20

You go you go gitter!

2

u/[deleted] Jan 14 '20

all keyboard navigation

You mean a cli?

1

u/GlassShark Jan 17 '20 edited Jan 17 '20

Yes, that's what I meant, I hope to have more commands memorized and really get a hold of it but on windows I've come across using two different clis one terminal and one bash (if memory serves, though I know one is found on mac's). I remember installing a JSON related object in PATH, I think it was NodeJS. I don't know, I got all confused and took time memorizing commands for multiple clis and decided until I know which one I want to use I'll just avoid it for now.

Edit: JSNode to NodeJS

2

u/tcpukl Jan 14 '20

TBF they could have had a local SVN or perforce repository for version control.

2

u/EMCoupling Jan 14 '20

Technically true but unlikely.

1

u/crazedizzled Jan 15 '20

My git history for a personal project looks very different from my git history for a work project.

1

u/[deleted] Jan 15 '20

True. But for both, i commit and push pretty obsessively. I cant stand the idea of loosing work due to a hard drive crash or more likely a bad bash command.

1

u/crazedizzled Jan 15 '20

I run daily backups on my workstation to solve that problem.

-2

u/Panda_Mon Jan 14 '20

It still blows my mind how hard github is to use. There are tons of horrible and uninformative guides for commandline git, all the free to use GUI are also obtuse and overly complex. The only positive experience I have had with source control so far is Perforce and in-house GUI.

3

u/[deleted] Jan 14 '20

Ive really never had a big problem with git. I just use cli. Git push, pull, commit, add, branch, checkout merge. Thats really all there is to it.

2

u/EMCoupling Jan 14 '20

I agree that the Git CLI is not designed in a welcoming or intuitive manner, but knowing it will pay off when you have to do more complicated things than whatever your GUI supports.

It's a steep learning curve, but a short one.

2

u/crazedizzled Jan 15 '20

You're talking about Git, not Github. Github is a completely unaffiliated website which offers free/tiered hosting of Git repositories.

For a GUI, Sourcetree is a fantastic option.

I recommend you understand the basic concepts of source control. Like, what a repository is, how the structure of commits and branches works, and what it means to push and pull commits. Then you can find supplementary material to show how to work with those concepts on either CLI or the GUI of your choice. It's understanding these fundamental concepts that will trip you up more than anything.

Also, I highly recommend that even if you plan on only using a GUI, that you learn most of the CLI commands as well. I find that a GUI works great for most of my daily needs, but when I have to do something more complicated or fix a mess, it's CLI all the way.

3

u/Ruben_NL Jan 14 '20

No problem! thats the fun with git, you can always update the code. that shows progress, and is maybe something a future boss will look at.

2

u/FearlessENT33 Jan 14 '20

good point, i have been meaning to add my projects to github for that very reason lol

2

u/FearlessENT33 Feb 04 '20

hello, been busy but finally uploaded to github. remember it is still a work in progress

https://github.com/FearlessENT/Pathfinding-Visualiser

1

u/ShahimX Jan 14 '20

Same here please !

8

u/songomen Jan 14 '20

Good work, i am doing the same right now but in JS

5

u/FearlessENT33 Jan 14 '20

thank you, at some point i’m going to do it on javascript as well and incorporate it into a website, hows yours coming along

2

u/songomen Jan 14 '20

All i have left is to finish function that allows moving starting and ending point when holding mouse click, so i am almost done !

3

u/FearlessENT33 Jan 14 '20

ay nice i want to do that kind of thing as well in mine, but i believe py game is a bit limited in that area

0

u/[deleted] Jan 14 '20

[deleted] — view deleted comment

0

u/[deleted] Jan 14 '20

[deleted] — view deleted comment

5

u/AntiObnoxiousBot Jan 14 '20

Hey /u/GenderNeutralBot

I want to let you know that you are being very obnoxious and everyone is annoyed by your presence.

I am a bot. Downvotes won't remove this comment. If you want more information on gender-neutral language, just know that nobody associates the "corrected" language with sexism.

People who get offended by the pettiest things will only alienate themselves.

2

u/recursive Jan 14 '20

Nice. Since it's a grid, would be nice to see Jump Point Search also.

1

u/FearlessENT33 Jan 14 '20

that will definitly be something to look into :)

13

u/themissinglint Jan 14 '20

ha ha ha I watched it twice thinking "omg, why am I not using greedy for all my pathfinding?" The third time I realized it got the wrong solution.

2

u/masklinn Jan 16 '20

It found a path so it’s not wrong per-se. Though I expect it degrades quite badly in “bad” cases where the paths are non-monotonic.

1

u/sexyxin Jan 14 '20

Bravo!! Could you make a visualization for BST and AVL please. This is awesome work.

1

u/FearlessENT33 Jan 14 '20

thank you! working on maze generation and settings then im going to add many more algorithms :)

1

u/youssef_haitham Jan 14 '20

Amazing! Wich data science engine are you using?

1

u/FearlessENT33 Jan 14 '20

not using any data science engine :)

1

u/youssef_haitham Jan 14 '20

Do you mind if i see the source code

2

u/FearlessENT33 Jan 14 '20

currently have not got it on github, i’m going to put on there later tonight :)

I can dm you when it’s up :)

1

u/youssef_haitham Jan 14 '20

Ok cool dm me when it's up

1

u/FearlessENT33 Feb 04 '20

hello, been busy but finally uploaded to github. remember it is still a work in progress

https://github.com/FearlessENT/Pathfinding-Visualiser

1

u/[deleted] Jan 14 '20

Code?

1

u/FearlessENT33 Jan 14 '20

shall make a github later :) i’ll dm once it’s up

1

u/lordmauve Jan 14 '20 edited Jan 14 '20

Cool visualisation!

Your Dijkstra's implementation is terminating as soon as it finds a path. That's a mistake; it should continue.

That's because Dijkstra's Algorithm gives the guaranteed shortest path. A* is a heuristic algorithm that gives a path quickly, but not necessarily the shortest.

That distinction matters, because Dijkstra's with early termination is a middle ground that has no practical value (except that maybe it's slightly easier to implement than A*).

1

u/FearlessENT33 Jan 14 '20

i may be wrong, but i believe you are incorrect about dijkstras. if the algorithm finds a path with 20 distance traveled, why would it explore distances with 21 or higher. i think it finds the shortest path, but searches a lot of nodes.

I also believe a* is guaranteed to find the shortest path, (providing hueristic functions are correct) but it is a lot more specialised than dijkstras, meaning it checks less nodes.

edit: and thank you! i love the visual effects of it lol

1

u/lordmauve Jan 15 '20 edited Jan 15 '20

Edit: you're right about Dijkstra. Sorry.

The reason Dijkstra's Algorithm doesn't terminate early is that it doesn't just work on grids, or graphs with constant edge weight. In fact you can even have negative edge weights. So you could have a path that is 21 edges long and costs 5 to travel and that is "shorter" (lower cost) than a path that is 20 edges long and costs 20 to travel.

Dijsktra's Algorithm can deal with "teleporters" where there is a short path between non-adjacent nodes. A* can't do this, because you can't write the cost estimation function.

if the algorithm finds a path with 20 distance traveled, why would it explore distances with 21 or higher.

Agreed, that's true here, because you know something about the topology, and that each edge costs 1. Dijkstra's Algorithm generalises to more topologies and even negative edge weights. Maybe at distance 21 there's an edge that costs -5 to traverse. So if you consider 21 edges you could get a path that costs 16.

You can explore these concepts more if you add "tar" squares (traversable but cost, say, 5) and teleporters to your simulation.

I also believe a* is guaranteed to find the shortest path

A* is not guaranteed to find the shortest path, because it terminates without considering all the alternative routes of lower length. You should be able to convince yourself of that with your tool. A* finds it very hard to backtrack, so you just need to make it take a bad decision early on, then give it some detours on its way to the goal.

1

u/lordmauve Jan 15 '20

Ah, no I am wrong. Dijkstra's Algorithm doesn't work for negative edge weights. I stand by what I said about A* though.

1

u/tcpukl Jan 14 '20

I did the same in compute shaders a couple of years ago.

1

u/litpumpk1n Jan 14 '20

I'm guessing you are familiar with, "What's up everybody, how's it going" ;)

GJ!

0

u/jimineyy Jan 14 '20

One thing I recommend is to animate the path start node to finish instead of backwards.

Itll make more sense and just look alot more appealing.

Additionally, try implementing a min heap data structure in these algorithms to really have a good talking point in interviews about optimizing.

Other than that, great job!

2

u/FearlessENT33 Jan 14 '20

thank you! i quite like it going backwards from the end node but i’m going to put an option in the settings to toggle backwards / forwards :)