Coding Challenge 51.2: A* Pathfinding Algorithm - Part 2

Other Parts of this Challenge:

References:

Live Stream Archive:

Related Coding Challenges:

Timestamps:
0:00:00 Introduction
0:00:40 Adding Obstacles
0:03:12 Dealing With Dead Ends
0:05:48 Adding Diagonals
0:09:30 Ideas For Optimization
0:11:40 Fixing Bugs in The Code
0:15:39 Choo Choo We Did It!

Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound

#aalgorithm #pathfinding #heuristic #p5js #javascript

[noimodimi]

This guy is like the Bob Ross of coding, only more enthusiastic.

[neelparekh]

*I FREAKING DID IT! I COMBINED THIS WITH YOUR MAZE GENERATION PROJECT!*

[GogiRegion]

Thank you so much for this. Ironically enough, I figured out how to add diagonals and go past walls all by myself just using the first video and using the octagonal heuristic from a Stanford article.

I finished writing the pathfinding for the game I’m programming from the first video, and the second helped me make sure I got it right.

[TMacFuzz]

the no diagonal/no walls search looks funky because every path to the end using right and down movements has the same distance, so its going to search every spot. Every path is optimal.

[umchoyka]

Not sure, but one additional change would be to calculate the diagonal movement differently than orthogonal movement. From the beginning, your "g" cost was always to add 1, but to move diagonally the actual cost should be sqrt(2).

[JamesCoyle]

You still have a bug in there. At 15:40 you can see the path moves around a red square rather than going through it. It also appears there is a shorter path through that end part.

You could also take this further by considering that the path needs to be traveled by an entity which is not a single point. That means it can only travel diagonally directly if there is no wall adjacent otherwise it has to travel around the wall taking a path which is somewhere between sqrt(2) and 2 in length depending on the size of that entity.

Also, ideally you would want an algorithm which can find the choke points and draw the lines between those to give a smooth diagonal path rather than one that is locked to 45 degree increments. This would probably require some sort of ray-tracing algorithm looping through the path and checking to see if there are obstacles between two points

[RobinsonGames]

Explained exceptionally well, as always.

I'm looking forward to the neural network videos.

[elishmuel]

I wish I could re"like" the video everytime I learn from it

[LewisCowles]

While I don't love the code, this looks to be a better A-star than I used yesterday, and the ability to watch the iterations is quite cool too.

[Kalihomo]

I feel so great finding this hidden part 2 :D

[KDChenStudio]

Hey i followed exactly your tutorial and successfully made this algorithm on my iPhone ;)

[deltamico]

Gonna leave here the heuristic for diagonal movement:
y = vertical distance of current and goal
x = horizontal distance of currenr and goal
h = max(x, y)

[nidoking]

There's a significant optimization in calculating the heuristic only once for each Spot, rather than every time you evaluate it - the heuristic value never changes, so it's wasted effort. As for finding neighbors, my preferred method is to spend a bit more space and extend the grid by two in each dimension, filling the outermost cells with walls. Now you don't need to check for existence of neighbors in any direction - there will always be a neighbor in all directions for any non-wall Spot.

[DavidLindes]

I'm not really sure off hand what I would use it for, currently... but one thing I know that does use it is in the game Factorio. I think in several places -- for trains, probably, and certainly for "enemies", coming to attack you... they pick a target destination, and then use A* as a way to find what path to take. I believe they have a whole write-up about it...

[maximilientirard]

I think It might be more efficient to add new open paths at the beginning of the open path list. It would (I believe) safe time in cases where there are multiple paths but all of them have the same cost, like the situation in the very beginning of the video (beginning top left, end bottom right, no obstacles, diagonals not alowed). That way, it wall explore only one of all the same-costing paths.

[dheerajlxst]

You're so inspiring. Keep on these videos. Love them all.

[pianochess]

By using the taxicab-distance your heuristics will sometimes overestimate the distance (especially since you consider the diagonal steps to have length 1, but it would even if they were sqrt(2)).
Example. Consider a 3x3 box. Moving diagonally takes 2 steps, but your heuristics would estimate it as 4.

[nicolascoral]

Thank you for this video. I know it's old but it came up when searching for videos about the A* algorithm.

I do think there's another bug showing at 15'40. There's an isolated red point near the end. The path goes diagonal bottom right and top right around it. With the distance you chose, the shortest path should be straight through it. It's also showing in other examples you ran.

Anyway, thank you very much. It was really interesting and well explained. May be it got fixed later.

[nayanagarwal]

People who are trying to implement A* for finding path in a maze try to use Euclidean distance in heuristic rather than Manhattan. Manhattan distance gives you a short path as compared to Euclidean distance when you are considering the diagonals. but if we are considering top right bottom left then no doubt Euclidean distance wins.

[visintel]

The heuristic isn’t admissible even with the Euclidean distance. If we assume the goal is on the bottom right neighbor square, the current square would have a heuristic of square root of 2, which is larger than the actual distance (that is 1) since we are adding one after each step anyway