r/Python • u/anuj-99 • May 26 '20
I Made This Finding the shortest path between two points using the A Star Algorithm! I find it to be one of the best self projects to learn and get into programming. Link to the Github repository in the comments!
27
May 26 '20
In case anyone’s curious, this video provides great intuition behind the A* algorithm in 2 minutes:
17
u/erolbrown May 26 '20
Me:hmmmm ok mouse got it. Cheese, yes. Mmmm. Ok. Yes yes
Gets to maths bit
Oh fuck this.
5
u/drunkenvalley May 26 '20
The idea is fairly simple in truth. How do you find a path between two locations?
You draw a line. You try to stay close to the line. Sometimes, you'll discover you have to backtrack - where do you go? The closest intersection that allows you to progress closer while staying as close to the line as possible.
That's really about the complexity of the premise, haha.
1
u/XeA-12 May 26 '20
Does adagrad/momentum SGD work on similar principal if I am understanding it correctly ?
10
u/wongjmeng May 26 '20
Very cool! I did something just like this for a class, and the results looked suspiciously like this. I mean the pictures were nearly identical, except mine were red-green instead haha
41
u/Techie5879 May 26 '20
Fun fact, that's how lightning works! Finds path of least resistance through the atmosphere!
29
u/theChaosBeast May 26 '20
No. It's more comparable to a BFS than a*
5
u/chinpokomon May 26 '20
I'm not sure I agree. The heuristic for lightning would be the voltage potential with respect to ground and the cost is the resistance. Lightning is BFS in that it is simultaneously searching for the least resistance pathway, but it's not going to backtrack to a to a lower resistance if that also increases the voltage potential. It's not a traditional A*, but it also isn't BFS.
If it were BFS every pathway would trace an arc until it grounded. Until the strike, every potential path would have an arc and lightning would look more like a cone.
Instead you have a few paths of exploration which terminate before reaching ground and then any electrons that were following those paths reverse course and flow back through the plasma which is now very low resistance to reach ground. Because the plasma itself reduces the resistance, when ground is reached, almost instantaneously the heuristics of the entire graph are brought to 0, so it patterns A* pretty closely. It's a multithreaded A* with a constraint of the number of threads, and each fork starving the search so that a path may not actually be discovered before it exhausts it's potential, but I believe that characterizes it more like A*.
5
u/okasiyas May 26 '20
What is a BFS?
5
u/RhinoSFM May 26 '20 edited May 26 '20
It is a search algorithm, like A* shown above. It works by checking the neighbor nodes (squares in the maze in this instance) around the start point and putting them in the back of a self-made queue. Then it takes the first item in the queue and checks its neighbor nodes and puts those in the back of the queue; the cycle continues.
You can kind of think if it like searching in an increasing circle from the start point.
2
-13
7
7
u/I_Xenon_I May 26 '20
You could use this to make some sweet procedural lightning. Especially if you bake them to a few textures with different seeds, and make a gif
5
u/00mba May 26 '20
I was thinking nice river maps for a city builder.
2
u/I_Xenon_I May 26 '20
Yeah but you wouldn't get the nice windy parts in a landscape. Bit yeah in a citybuilder it would probably work
4
u/I3igB May 26 '20
I love A* applications! I implemented the algorithm during some parts of my thesis to extract water flow paths in digital elevation models. Here’s an example of it here here.
1
u/flayner5 May 26 '20
What did you use for visualization?
4
u/anuj-99 May 26 '20
Here I used plt.imshow() It's a grid form of 2d array which colors itself According to the value at that point in the array
1
May 26 '20
What heuristics did you use? Manhattan distance to the end?
1
u/anuj-99 May 26 '20
Nope, I used Euclidean distance as moving in diagonals is allowed, though if we were moving only in the 4 directions, then I would've used the Manhattan distance
1
1
u/K1ngjulien_ May 26 '20
Next step: maze generator ;)
1
u/anuj-99 May 26 '20
Actually I'm looking for an entirely different project now! It would be great if you all could help me with some suggestions! :)
3
2
u/Paradigm6790 May 26 '20
Best way to learn something is always to set a goal and build it. Very cool!
1
1
1
-2
u/gerlevodka May 26 '20 edited May 26 '20
Isn't it A* ? But it is cool no doubt!
0
May 26 '20
[deleted]
6
-5
u/emilld May 26 '20
Actually they're not quite the same. It's called A* when the heuristic is underestimating.
-2
May 26 '20
Nice.
1
u/nice-scores May 26 '20
𝓷𝓲𝓬𝓮 ☜(゚ヮ゚☜)
Nice Leaderboard
1.
u/spiro29at 9214 nices2.
u/RepliesNiceat 8209 nices3.
u/Manan175at 7096 nices...
253937.
u/steve_errkuallat 1 niceI AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS
0
u/theChaosBeast May 26 '20
Nice.
1
u/nice-scores May 26 '20
𝓷𝓲𝓬𝓮 ☜(゚ヮ゚☜)
Nice Leaderboard
1.
u/spiro29at 9243 nices2.
u/RepliesNiceat 8212 nices3.
u/Manan175at 7096 nices...
253432.
u/theChaosBeastat 1 niceI AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS
-18
u/_370HSSV_ May 26 '20
A* to GET INTO programming? What bullshit is that? Noone starts with A*
12
May 26 '20
I assume he means "get into" after they've learned the basics like what is a variable, loop, function etc. Once you're able to actually write code that runs, A* is a pretty decent step for a "first project". It's really not a very difficult algorithm to grasp.
8
6
May 26 '20
Huh? It's not that hard an algorithm, it was in my beginner Java course.
It's cool because if you are careful you can code BFS and Djikstra and A* all using the same code and just swapping out the comparator.
1
u/_370HSSV_ May 26 '20
I know it's not hard but beginners doing it will probably get frustrated and ditch programming
5
May 26 '20
I guess it depends. I wouldn't recommend it as the first programming assignment over like Hello World if someone doesn't even know what variables and loops and functions are etc.
But as a goal for a self-learner it's pretty good. Also good for interview questions.
3
u/passerbycmc May 26 '20
Why it's not a hard algorithm, but it's also a useful one that will touch on many topics if you want to make it fast.
4
u/NTaya May 26 '20
It depends on the definition of "getting into programming."
A* was one of my first "real" projects on Python, the one with a clearly defined goal; to achieve it, I had to learn and apply a lot of smaller new (for me) techniques. I had been learning coding on-and-off for a long time before approaching this task, of course—but programming A* got me into doing actual projects.
0
May 26 '20
[deleted]
14
u/scinaty2 May 26 '20
Honest question, I am new to ml. Why do you think q learning solutions are stupid?
32
u/shocsoares May 26 '20
It's more that people use them as a hammer and everything is a nail. How do I open this box, oh I know,let me smash it to pieces with q learning.
48
u/anotherplatypus May 26 '20
I have an idea to programatically figure out why people use q learning for everything, but I can already tell you're going to think my solution is stupid....
3
u/pag07 May 26 '20
If you go for q-learning you try to approximate a function. An ideal labyrinth is totally random.
Therefore there is no function to approximate.
Q Learning might be useful to beat certain labyrinth generators. But only because those generators make assumptions that reduce the randomness. And q Learning would try to learn those assumptions to get an advantage.
For example q learning could learn that a labyrinth always starts in the bottom left and the target is in the top right. So tiles moving to the top right might have a higher q value on average. However this assumption only holds true to certain generators.
1
u/scinaty2 May 27 '20
Oh, I think I get it. Let me try: If the there are 5 states known to the agent, then q-learning tries to come up with a function
action = f(s1,s2,s3,s4,s5)
and it will choose this exact action every single time of s1,...,s5 are the same. There is a total lack of context (for example, how were the states a moment before). Solving a labyrinth cannot be done with a function, but needs strategic problem solving
5
1
May 26 '20
[removed] — view removed comment
1
u/anuj-99 May 26 '20
I too don't think they're for absolute beginners, but learning interesting algorithms help get you on the right track. Also, with such appealing visualisation and connection with real world problems is motivating! :)
39
u/anuj-99 May 26 '20
Link to the Github repository - https://github.com/anuj-99/Shortest-Path-Finder
Some of the helpful resources if you want to make your own:
https://youtu.be/aKYlikFAV4k - Video by The Coding Train, though it isn't in Python
https://en.wikipedia.org/wiki/A*_search_algorithm - The pseudocode given is very helpful