Navmesh on a spherical planet

@Christougher i am not able to find the files you shared. :frowning:

They contain pro only code so you’ll have to have them forwarded to you by Aron

Hi everyone

So since there seems to be quite a lot of interest in this, I have spend the last few days working on an official implementation of this. Instead of the multiple quadtrees as implemented by @Raphael_Ninpo I extended the quadtree to an octree which scales better (well, technically I haven’t profiled this yet, but it seems 1 octree ought to be faster than 6 separate quadtrees) and it also allows local avoidance to function on more complex surfaces (not necessarily spherical). I also improved the AI script a bit to also do surface normal interpolation (otherwise it would change direction very suddenly when moving from one triangle to the next).


2 Likes

That looks amazing! I’m so eager to try it! :smiley:
I’m glad you picked up on this because I definitely wouldn’t have done a better job than you, and it’s great to see that other people did need this for their project.
The more we are interested in this, the better it will get!
Please tell us when it’s available to use.
Thank you Aron, you rock! :+1:

1 Like

What he said! x2 :smiley: oh my gosh I’m more excited for this than nested prefabs

2 Likes

Hey

I just uploaded a beta here: https://www.arongranberg.com/astar/download (click on ‘show older versions’ and download the spherical beta).
I also wrote a small (work in progress) tutorial page for it. Take a look at this page: https://www.arongranberg.com/astar/documentation/spherical_4_1_20_17f940b2/spherical.html)

2 Likes

I guess the next obvious question is once this is implemented and we have it on a navmesh, how are we going to cut out water areas? For me, its one giant sphere within my terrain sphere. Is this a good approach or am I going to have to procedurally cut my water zones?

Hi

Spherical graphs do not support any kind of navmesh cutting, so this will have to be done inside your 3D modelling application. With most of them it should be fairly easy to remove all the geometry overlapping in the water.

What about the navmesh modifier volume that you’ve been working on? Would that work to set tags/ penalties? Also I was thinking as my lil project has a similar planet/ ocean setup could one simply do a distance check with the center of the planet with each node to add penalties or tags? That seems doable without hacking up one’s mesh…

Also, finally had a chance to play with this and compare to the prior arbitrary surface stuff! First off the octree approach seems to be blazingly fast, thanks again for picking this feature up. Also the movement now seems to expect the agent to have gravity to keep it pulled down into place whereas the prior iteration didn’t. Is the gravity necessary? Will play with it more later when I can.

Problem for me is that my planets are all procedurally generated, not statically modeled. :frowning:
Still, I know my high, mid, and low vertices so maybe I could use that as a basis for cutting water zones.

I think the previous implementation used a raycast and then just moved the agent directly to the surface. So it was roughly equivalent to an infinite gravity.

You can change the parameters of the existing nodes in the navmesh. That will work just fine, you just cannot use e.g navmesh cutting to cut the navmesh.

Hi everyone,

@aron_granberg Thanks so much for adding the spherical example on the latest beta! It works great.
I’ve been trying to implement a way to avoid obstacles in real time but I can’t find an efficient way to do it.
Navmesh Cut and Tag Manipulation doesn’t work on this new type of navmeshes.

Does anyone have a method to avoid real time obstacles on spherical navmesh? Thanks.

Hi

Tag manipulation should work as mentioned in my previous post. Isn’t it working for you?

Thanks Aron for your continuous support. Tag manipulation didn’t work for me but I might be doing something wrong. I’ll give it another try. Thanks.

Here is an example of tag manipulation that took me a bit to figure out. This should work for the planet/ocean dilemma @phil.atha mentioned by simply measuring the distance of each node from the planetCenter and setting it to my ocean tag (1) if it’s shorter then the landRadius…
@chocominyo perhaps a similar approach could help you having an obstacle check if nodes are within an obstacle’s bounds?

    public NavMeshGraph NMG;
    public GameObject Planet;
    public Vector3 planetCenter;
    public int LandRadius;
    
    public void SetNodes()
    {
        NMG = AstarPath.active.data.navmesh;
        planetCenter = Planet.transform.position;
        Vector3 tileV3;

        for (int z = 0; z < NMG.tileZCount; z++)
            {
                for (int x = 0; x < NMG.tileXCount; x++)
                {
                NavmeshTile tile = NMG.GetTile(x, z);
                for (int i = 0; i < tile.nodes.Length; i++)
                    {
                    GraphNode node = tile.nodes[i];
                        tileV3 = (Vector3)node.position;
                    float dist = Vector3.Distance(planetCenter, tileV3);
                    if (dist <=LandRadius)
                    {
                       // tile.nodes[i].Walkable = false;
                        tile.nodes[i].Tag = 1;
                    }
                    else
                    {
                        //tile.nodes[i].Walkable = true;
                        tile.nodes[i].Tag = 0;
                    }
                    }

                }

            }
        
    }

first if there are any glaring problems with this forgive me. I’m not a great coder AT ALL lol. This took me an embarrassing long time to figure out. I suppose if its for sure a navmesh type then the first two for loops could be done away with and use the line:

NavmeshTile tile = NMG.GetTile(0, 0);
as NavmeshGraphs only have one tile, right?

This above approach left me with some questions however… the line " NMG = AstarPath.active.data.navmesh;" gets the first navmesh type graph on the main A* component. What is an easy way to get a specific navmeshgraph from say 5 different navmesh graphs in one scene?

Also for say an “obstacle” that can set tags within it’s bounds how can one keep a list of nodes affected by it to later reset them once it is moved? Hmmm, maybe just have each obstacle use a list of bools that correspond to each node and cycle through em?

Any recommendations as far as optimally getting nodes within a volume? Thx

1 Like

@Christougher

So you’re method doesn’t work for my scenario but you got me on the right path. In my case, my planets have mountains, ocean floors, and then clamped areas in the middle. The clamped areas are the ‘safe zones’ where the pathfinding/player can move. Since I happen to know these vertices and my navmesh is 1:1 with the model anyway I can simply iterate through these and then set the matching node position to Walkable since I can be sure the Vector3s are exactly the same. So far this appears to mostly work. Comparing against the distance of the ocean inwards to the center will only work for areas under the seabed.

            for (int i = 0; i < verts.Count; i++)
            {
                NNInfoInternal nnii = graph.GetNearest(verts[i]);
                if ((Vector3)nnii.node.position != verts[i])
                    nnii.node.Walkable = false;
            }

1 Like

@Christougher
Nice! Great example.
There are a few ways to simplify it a bit though.
Here is some updated code

public NavMeshGraph graph;
public GameObject Planet;
public Vector3 planetCenter;
public int LandRadius;

public void SetNodes() {
	graph = AstarPath.active.data.navmesh;
	planetCenter = Planet.transform.position;
	Vector3 tileV3;

	graph.GetNodes(node => {
		var nodePosition = (Vector3)node.position;
		float dist = Vector3.Distance(planetCenter, nodePosition);
		if (dist <= LandRadius) {
			// node.Walkable = false;
			node.Tag = 1;
		} else {
			//node.Walkable = true;
			node.Tag = 0;
		}
	});
}

Thx for the reply! I had wondered how GetNodes worked! :slight_smile: I had to clean up the code a little bit more such as changing tileV3 to nodePosition in the dist calc and changing the tile.nodes[].Tag=1 lines to
node.Tag = 1;

1 Like

Hi, after about a year now since the spherical pathfinding beta came out i was just wondering if there might be plans to work it permanently into A*PP? Especially as you are now in ernest delving into jobifying… (droooool…) :grinning:

1 Like