Live Stream #72: A* Pathfinding Algorithm

Welcome to the first live episode of The Coding Train!

This unedited archive features the entire very long and messy debugging process!

Links to the edited version of this challenge:

14:00 - Intro to today's topics (A* is the only one I end up doing)
34:50 - Coding Challenge: A* Pathfinding Algorithm
2:34:15 - Recording Intros
2:53:41 - Conclusion/Q&A

Links discussed in this video:

Help us caption & translate this video!

[rashawnhoward]

HAHAH the song in the beginning I love it! dan is my teacher when I am not working on school programming projects! I learn way more on youtube than in my classes!

[MilanKarakas]

Arround 2:52:00, you said it looks almost like lightning. I can see it clearly too. Instead finding the closest and most efficient path, I think that lightning "trying" to find all ionized particles and neutralizes it in the path. Once neutralized, there are no more the same path, then lightning "clears" other remained ionized (charged) particles in the air. But, since lightning itself can produce ionizing due to ultraviolet light if some molecules are there, it splits molecules into ions, creating new ionized pairs, where new path is possible. Once it reaches ground, it discharges all at once, because at this moment, there are no sufficient charge in the main cloud.

[GuardianTam]

While I don't have the time to watch the whole video, that intro was freaking awesome!

[lupusstiger]

You're a GREAT coder, Daniel. Would you please do a artificial neural network coding tutorial for us. (!Thanks Already!)

[pelegred]

Yes ! Coding train is an awesome name!

[comarmy-eihg]

I actually used the maze generation algorithm to solve it too. It's very inefficient but it was a good way to fully understand the algorithm.

[KrausBean]

Killer job. That is some intense stuff for sure. Ignore the people mentioning the nose scratch, they are missing the point. Great work on this. Learned tons.

[june]

Ooooh, i was going to ask for A* cause you explain very well and .. here it is 😃

[Sam-byuk]

The song at the beginning is great! Wish you would bring it back.

[figfox]

OK, now you should check "Fringe Search" (it's kind of a A*)
Or if you want something more interesting "Cooperative pathfinding" (ie A* in space and time, units pathfinding can prevent each other collision)
But this last one is a little bit more difficult than basic A* ^^

[camelcase]

Pong would be cool to see. I just did one in Processing but I'd like to see your approach to making the computer paddle react like a human.

[MrCKay]

Dijkstra's algorithm actually doesn't follow every path. For a complete graph (every node has an edge to every other node, ) the number of paths can be (n-2)! where the number of nodes is n; Dijkstra however has a worst case complexity of n*log(n). The idea is that Dijkstra's algorithm will, 1. explore each path in a non-decreasing order, ie once it's explored a path, the next path it explores will always be >= the previous one. 2. It will only explore a path, if all shorter paths have been explored. And 3, it'll never explore a path that takes longer than an already know path. When the edge lengths are all the same, like in the case of this video, a run of Dijkstra's algorithm behaves exactly like a less efficient version of Breadth First Search, which we all know doesn't explore every path, but every node of a graph.

The real difference between A* and Dijkstra's algorithm is that Dijkstra's algorithm only considers the path length, while the A* algorithm also considers the heuristic. In fact, technically, if in A*'s expression f(n) = g(n) + h(h) you define h(n) = 0 (or some constant), you get Dijkstra's algorithm. The better h(n) estimates the distance between n and the end node, the faster the algorithm gets. The poorer the estimates, the closer A* behaves to Dijkstra.

The real improvements in your program come from the fact that h(n) estimates the distance to the end node very accurately. In fact if you remove the obstacles and diagonal edges, it calculates the path length exactly. With the diagonals also, there are better heuristics that you could come up with.

Of course this assumes a bounded search space. If it weren't bounded, both a* and Dijkstra's algorithm would have a worst case complexity of O(b^d) where b is the the number of neighbors each node has, and d is the depth/path length to the solution. And A* would perform better if the heuristic is better.

[Thermacon]

Is there any way you can make the live stream later in the day? I'm still in school when you make these :(

[XGJP]

Like the new name, but:

- The little bow looks more like a sweet in a wrapper!
- The tags above the two letter I's should surely be <> and </> to reflect starting and ending tags? They are both ending tags at the moment which is coding nonsense!

Keep up the great and entertaining work though :)

G

[nithinpranesh]

hey daniel, I'm working on a project using processing in netbeans and im kinda stuck right now. I'm trying to use a custom input listener class to look for mouse and keyboard events, i tried adding an instance of that class through papplet.frame.addListener(..) but i don't think it's doing anything. if this was just a small sketch i would just overwrite the papplet input methods, but in this context doing so would clutter up my main class with seemingly misplaced functionality. What is the easiest way to use my own input listener class objects with processing?

[willd]

You should do a video around the NEAT algorithm for neural networks

[rizubiswas]

How to make it run offline? (Grids do show when the intro.html is run offline but the functions like run, stop, restart are not working )

[muabyt]

Neural Networks would be nice ^^ (The Nature of Code Chapter 10)

[HejaHammerfall]

Since you haven't posted the edited A* video yet I just though you might want to a this code at the end of "addNeighbors" and mention it at the end of your video.

This code makes the shortest path more aesthetic while not using diagonals

if ((i + j) % 2 == 0)
{
// aesthetic improvement on square grids (Should work for rectangular grids as well)
this.neighbors.reverse();
}

[nagualdesign]

I have a request! :-) I'd like to realistically visualize, using real physics, the 'rubber sheet' geometry of space around a large mass like the Earth, the Sun, a neutron star or a black hole.