The Most Basic Pathfinding Algorithm, Explained

- Support Me -

- Other Stuff -

[Miziziziz]

Had an idea for a series where I cover different game algorithms. What are your thoughts and suggestions on this?

[lanorothwolf]

The missile knows where it is by subtracting where it was to where it will be

[fabiboiii]

To everyone struggling with this:
It's crazy hard the first time
But the moment it clicks after getting it right, you will never ever forget how to do it

[AniMesuro]

Dude this is perfect. Was trying to learn A* pathfinding a few weeks ago but couldn't do it because the tutorials seemed too advanced.

[shadowpenguin]

3:45 the time needed is quadratic (O n^2) to the distance, not exponential

[unfa]

I'm so glad you're demonstrating this using the Godot engine - it's becoming real open-source competition to Unity and Unreal engines.

[Phoenix]

you can also add an optimization, by using the player direction using a Pythagorean to the goal, then set a bias to that angle, but if something blocks the tree, eg it ran out of options in that angle, then it will still continue but just using a different biased angle to the end goal. this will save you on using a tree that goes into the wrong direction if it does not need to.

[shabaq]

I absolutely love this! I have never made a pathfinding algorithm before, but this was very concise and easy to understand.

[brownspottedcat]

Wish I had this kind of explanation when I was making the AI for an SRPG prototype back in 2016. Delving through unreliable forum posts for that project wasn't too fun :D

[AnoNymous-iewc]

Thanks for this tutorial. Was very helpful to get into pathfinding 👍😃.
I had to modify it a little bit so the path will prefer straight movement over changing direction. I'll refine it later to get it into a single loop

var delta_vector = Vector2(pos_last.x, pos_last.y) - Vector2(pos.x, pos.y)
if delta_vector == Vector2(1, 0):
queue.push_back({"pos" : {"x" : pos.x + 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x - 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y + 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y - 1}, "last_pos" : pos})

elif delta_vector == Vector2(-1, 0):
queue.push_back({"pos" : {"x" : pos.x - 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x + 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y + 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y - 1}, "last_pos" : pos})

elif delta_vector == Vector2(0, 1):
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y + 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y - 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x - 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x + 1, "y" : pos.y}, "last_pos" : pos})

elif delta_vector == Vector2(0, -1):
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y - 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x, "y" : pos.y + 1}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x + 1, "y" : pos.y}, "last_pos" : pos})
queue.push_back({"pos" : {"x" : pos.x - 1, "y" : pos.y}, "last_pos" : pos})

[mikaxms]

I made something similar for a 2D flooding algorithm. I got the adjacent tiles of each point in the database, checked those for obstacles and added the clear ones to the database. Only issue was that it was very expensive. Couple projects later, I realised I should have used the adjacent tiles of the previous tiles that were added to the database. So, it doesn't check the entire 'surface' just the 'edge' of the map in the database (if that makes sense).

[noelreed]

> A* algorithm
> Look inside
> Breadth first search

[FreddyNewton]

such a great video! I like really the jump point search

[lamihh]

There should be more of this on the internet

[skaruts]

I think this algorithm is a good candidate to be included in Godot's native toolset, much like Simplex Noise is. Currently Godot has A* (classes Astar and Astar2D), but as far as I know it's missing all the variants of search algorithms, like this one (dijkstra?). Godot could have a class for this kind of stuff, perhaps all in one. And tbh I think even bresenham lines and circles are good candidates to be in such a class, as they can also be useful for tiled games.

[KoltPenny]

Finally found a good use for GDNative. Thanks, bro.

[jassingh]

Really like this video, would love to see more

[Juke]

You could also optimize that pathfinding by only trying first to get to closer points first and branch out from there if it can't go straight to the target. Like calculating the distance from the point to the target is smaller and so on…


Did you know Godot already has a pathfinding API called AStar and AStar2D? It's actually pretty good. You can also add weights to the points to imitate how slow movable surfaces work, like water. So the AI tries to avoid those if it's not necessary to pass over to the target and try to optimize fastest path to the target.


Interesting topic though, I would love to see more of these.

[Warjun]

Nice, will try to implement that with c++

[kiyasuihito]

Very nice. I tried doing this in Gdscript and was frustrated with the inefficiency using an array as a queue (having to shift everything forward whenever popping from the front). I really want to make a C module for these pathfinding algorithms and a min heap at some point soon. That's the great thing about Godot!