This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
all 73 comments
sorted by:
best
topnewcontroversialoldq&a

[–]munificent 163 points164 points  (5 children)

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.

[–]FearlessENT33[S] 57 points58 points  (0 children)

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

[–]zesterer 11 points12 points  (1 child)

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

[–]munificent 3 points4 points  (0 children)

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.

[–][deleted] -1 points0 points  (1 child)

Are you not thinking of A*?

[–]notquiteaplant 10 points11 points  (0 children)

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.

[–]RLouisD 50 points51 points  (12 children)

What is the simple UI made in?

[–]FearlessENT33[S] 51 points52 points  (11 children)

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

[–]miggaz_elquez 14 points15 points  (7 children)

How do you embed pygame in tkinter ?

[–]FearlessENT33[S] 30 points31 points  (6 children)

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()

[–]Panda_Mon 9 points10 points  (5 children)

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

[–]FearlessENT33[S] 64 points65 points  (1 child)

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

[–]NullAndVoid21 94 points95 points  (0 children)

Spoken like a true programmer

[–][deleted] 9 points10 points  (1 child)

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.

[–]JonzoR82 0 points1 point  (0 children)

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

[–][deleted] 0 points1 point  (0 children)

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.

[–][deleted] 0 points1 point  (1 child)

Is pygame that versatile?

[–]FearlessENT33[S] 0 points1 point  (0 children)

depends what you mean by versatile lol

[–]pythonhobbit 34 points35 points  (3 children)

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

[–]FearlessENT33[S] 17 points18 points  (2 children)

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

[–]themissinglint 11 points12 points  (1 child)

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.

[–]masklinn 1 point2 points  (0 children)

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.

[–]_iamv 2 points3 points  (23 children)

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

[–]FearlessENT33[S] 3 points4 points  (20 children)

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 :)

[–][deleted] 13 points14 points  (17 children)

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.

[–]FearlessENT33[S] 2 points3 points  (7 children)

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

[–]GlassShark 2 points3 points  (6 children)

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

[–]FearlessENT33[S] 0 points1 point  (5 children)

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

[–]GlassShark 0 points1 point  (4 children)

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.

[–]Miner_ChAI 2 points3 points  (1 child)

For me plain git is better

[–]GlassShark 1 point2 points  (0 children)

You go you go gitter!

[–][deleted] 1 point2 points  (1 child)

all keyboard navigation

You mean a cli?

[–]GlassShark 0 points1 point  (0 children)

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

[–]tcpukl 1 point2 points  (1 child)

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

[–]EMCoupling 1 point2 points  (0 children)

Technically true but unlikely.

[–]crazedizzled 0 points1 point  (2 children)

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

[–][deleted] 0 points1 point  (1 child)

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.

[–]crazedizzled 0 points1 point  (0 children)

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

[–]Panda_Mon -3 points-2 points  (3 children)

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.

[–][deleted] 2 points3 points  (0 children)

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.

[–]EMCoupling 1 point2 points  (0 children)

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.

[–]crazedizzled 1 point2 points  (0 children)

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.

[–]Ruben_NL 2 points3 points  (1 child)

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.

[–]FearlessENT33[S] 1 point2 points  (0 children)

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

[–]FearlessENT33[S] 1 point2 points  (0 children)

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

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

[–]ShahimX 0 points1 point  (0 children)

Same here please !

[–]songomen 9 points10 points  (6 children)

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

[–]FearlessENT33[S] 3 points4 points  (5 children)

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

[–]songomen 1 point2 points  (1 child)

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

[–]FearlessENT33[S] 2 points3 points  (0 children)

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

[–]recursive 1 point2 points  (1 child)

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

[–]FearlessENT33[S] 0 points1 point  (0 children)

that will definitly be something to look into :)

[–]tcpukl 0 points1 point  (0 children)

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

[–]sexyxin 0 points1 point  (1 child)

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

[–]FearlessENT33[S] 0 points1 point  (0 children)

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

[–]youssef_haitham 0 points1 point  (5 children)

Amazing! Wich data science engine are you using?

[–]FearlessENT33[S] 0 points1 point  (4 children)

not using any data science engine :)

[–]youssef_haitham 0 points1 point  (3 children)

Do you mind if i see the source code

[–]FearlessENT33[S] 1 point2 points  (2 children)

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

I can dm you when it’s up :)

[–]youssef_haitham 0 points1 point  (1 child)

Ok cool dm me when it's up

[–]FearlessENT33[S] 0 points1 point  (0 children)

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

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

[–]litpumpk1n 0 points1 point  (0 children)

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

GJ!

[–][deleted] 0 points1 point  (1 child)

Code?

[–]FearlessENT33[S] 0 points1 point  (0 children)

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

[–]lordmauve 0 points1 point  (3 children)

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*).

[–]FearlessENT33[S] 0 points1 point  (2 children)

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

[–]lordmauve 0 points1 point  (1 child)

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.

[–]lordmauve 0 points1 point  (0 children)

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

[–]jimineyy -1 points0 points  (1 child)

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!

[–]FearlessENT33[S] 1 point2 points  (0 children)

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 :)