Assets Custom Pathfinding For Advanced Ai And Spherical Worlds

Hello, folks! I've been working on a custom pathfinding solution for a little while now and figured I'd start documenting my progress. My original goal was gaining access to navmesh data so low-level that I could manipulate the weights of individual nodes, facilitating advanced AI. I'll be exploring this for most of the series, but eventually I'll focus on navigation around tiny planets like in Super Mario Galaxy.

>> Intro Link <<

I expect everything else I post to be pure tutorial, but I took the opportunity here to muse about the state of Unity and its systems over the years...something I'm sure we've all been frustrated with at one point or another. This post doesn't contain a line of code, but it does illustrate why such a project is worthwhile and just how much more can be achieved in the realm of pathfinding.

I have a decent backlog of topics to cover, although I need to flesh out various features along the way. Provided I can keep up with that, my goal is to publish once every couple of weeks. To make up for the lack of coding in my intro, here's a preview of the next post - a neat visualization of an A* path as it's being built. The maze-like bit near the goal drags out the calculation, but optimization is among the many topics on the horizon.

Thanks for reading and watching!

 

I'm thouroughly interested on planet pathfinding that can flank the player ...

 

I actually have a working test of A* on a sphere. One of the quirks I discovered is how funky the great-circle path looks using haversine distance, when you're expecting a path that starts and ends on the same latitude to travel that latitude the entire way. It really is shorter to increase and decrease latitude, though, like with commercial flights. I'm going to try Mercator projection and other tricks to give preference to consistent latitudes.

My plan is to stick with grid-based A* for a while, then graduate to navmeshes and finally sphere navigation. I'd like the option of skipping ahead to sphere navigation if that's where most of the interest is, but navmeshes will be needed there. The good thing about that is, advanced behaviors like flanking should apply just fine on a sphere.

 

I never implemented it, but I thought of just using a dot product of normal, scaled by the radius as the distance heuristic, but I'm now interested in researching " great-circle path looks using haversine distance" Thanks for that, I knew nothing about it

 

Sure thing! If you're looking for more intuitive paths - longer but straighter - I recommend projecting to a Mercator map. I haven't tried it yet, but it should discourage paths from curving toward the poles. You'll just have to allow wrapping at the edges of the Mercator projection, like wrapping around the screen edges in Asteroids. Cheers!

 

My next post is live! It was delayed due to an unrelated post taking longer than expected. This tutorial is an in-depth look at A*, to catch up those who are new to pathfinding. It contains a detailed breakdown of the key concepts, a step-by-step example, and code translated into C#. At the end I also included a WebGL build with a link to the full demo project.