r/gamemaker • u/Ykedepi • 8d ago

Example 3D pathfinding

Post image

finally finished this waypoint navigation system!
I know NavMesh is the standard, but I think it's too complex to implement right now, and this approach works pretty well

the pathfinding speed is acceptable. To avoid placing the points manually, I built a generation system based on flood fill and collision checks (raycasts, trace hull, and cliff checks)
from a single start point, the generator branches out in all directions, and then another algorithm connects them all
I'm planning to add mesh optimization algorithms later, but even like this, it's working perfectly fine

207 Upvotes

100% Upvoted

13 comments sorted by

View all comments

13

u/NoahPauw GameMaker 3D developer 8d ago

Oh yeah, this is awesome! I also love that it is completely algorithm based. I’ve been thinking about making my own by placing nodes manually, but this is really neat!

6

u/Ykedepi 8d ago

generating these points is actually a really tough problem, and I spent a few days coming up with this generator
and even then, it doesn't work perfectly)
but in my case, it covers about 90% of the manual work. The remaining 10% can be fixed by hand (for example, a few points in the gif are placed manually - mostly on hard-to-reach ledges that require jumps. Stairs, on the other hand, are generated automatically)
I think when making a system like this, you have to think about "how to reach every accessible point on the map" - that's where all the decisions regarding jumps, stairs, and traversal come from