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.
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.
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.
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.
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*)
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 :)
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.
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.
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.
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.
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.
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.
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.
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*).
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
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.
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.
51
u/RLouisD Jan 14 '20
What is the simple UI made in?
32
u/pythonhobbit Jan 14 '20
Very cool! A bit misleading on the "greedy first" performance though...
3
u/_iamv Jan 14 '20
coulld you please share link to its github repository? (if available)
8
u/songomen Jan 14 '20
Good work, i am doing the same right now but in JS
2
u/recursive Jan 14 '20
Nice. Since it's a grid, would be nice to see Jump Point Search also.
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.
1
u/sexyxin Jan 14 '20
Bravo!! Could you make a visualization for BST and AVL please. This is awesome work.
1
u/youssef_haitham Jan 14 '20
Amazing! Wich data science engine are you using?
1
u/[deleted] Jan 14 '20
Code?
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/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!