Navigating around water

General Recast graph
#1

Hey guys!
I have a dilemma here. Recently I have been researching how all the constraints work and I’ve specifically looked at using tags. Here’s my issue. Most creatures in my game cannot walk on water nor can they traverse the bottom of a lake or river. Some creatures, on the other hand, can walk on water (like water elementals). It turns out that pathfinding for things that can walk on walk is easiest. They get a -1 for their tags constraint and it works like a charm.

The recast graph scans all levels on the Y-axis so, this includes river beds, bottoms of lakes, etc. I need to make all terrain underneath my water impassable. I want to be able to switch on the water tag for monsters like water elementals and ghosts, but switch it off for a skeleton or lion. Is this even possible without me having to manually change the recast generator code?

Presently, mobs get stuck at the edge of my water because it’s trying to have it traverse the lake floor and my server does not (and cannot) allow that. If I’m standing on the other side of the lake, I want it to navigate around it.

Let me also point out that I do need to keep this multi-level scanning because I do have multi-level buildings.

Thanks in advance :smile:

EDIT: I was thinking about this and, I think it would be cool to still keep those terrain nodes beneath the water… but they need to be under a different tag. If I can do this, I could actually have bottom-crawler water creatures too! (Not to be confused with water creatures, like fish, which will not use the A* pathfinding system… they will travel in straight lines between the terrain and the water plane above). Land creatures would simply have the tags “water” and “water floor” turned off so they would be forced to navigate around a lake or across a bridge over a river. OH I NEED THIS!

1 Like
#2

Still struggling here. At the end of my ScanInternal function for my recast graph generator, I tried looping through all of my bodies of water, setting nodes below the water surface to 2 and setting all water surface nodes to 1 ( leaving the rest of the graph at 0). I wrote this data to a file and opened it with my server. My server, then, uses path.enabledTags to filter which nodes should be used.

This did not work! :frowning:

For land creatures, I passed a 1 to enabledTags, and for a water elemental, I passed a 3 to enabledTags so they can walk on water. What happens is everything tries to go in the water… water elementals walk over it but land creatures also try to. Nothing I do seems to make that region impassable to them.

I even tried using path.nnConstraint.tags as the filter just to get anything to work. That didn’t help. Plus, I know from reviewing the Seeker code that it should be enabledTags… Any ideas?

#3

Hi

Maybe because of the earlier tweak that we made

That code will make the last point in the path exactly the requested point regardless of if it could actually reach it or not.
I mentioned that you might want to snap to the closest point on the end node, and that is likely what you need to do here.

path.vectorPath[path.vectorPath.Count-1] = (path.endNode as TriangleMeshNode).ClosestPointOnNode(path.originalEndPoint);
#4

Hey there!

When you gave me that advice, I actually ended up using the StartEndModifier instead of playing around with changing the last waypoint myself. Does even the StartEndModifier potentially clip impassable areas?
Even if StartEndModifier clips unwalkable areas in order to reach the exact destination, my land creatures do not seem to be just barely clipping the edge of the water and then getting stuck. I’m seeing them slam right into a lake as though they think they can walk straight through it. I didn’t analyze the returned waypoints from the algorithm yet but I could see that it was trying to come straight to me (thru the middle of the lake), as I stood on the opposite end of the lake. It did not attempt to circumvent it at all.

Am I doing this the right way though? If I change the tiles[ii].nodes[jj].Tag for certain nodes at the end of RecastGenerator ScanInternal(), I should be able to filter on them with path.enabledTags? So, if I set a node’s tag to 1 and then calculate a path with path.enabledTags set to 1, it should not be able to walk on that node, correct? It should only be able to walk on tags marked as 0? And a tag of 31 must have the 10000000000000000000000000000000 bit set in enabledTags?

#5

Hi

Yes, that should be the correct way to do it, not sure why it is not working for you.
When you calculate the path, try logging path.path[path.path.Count-1].Tag to see which tag the last node has (also probably good to check where it is as well to check if it is actually reaching the middle of the lake.

The StartEndModifier (with the endPoint setting set to ClosestOnNode) will make sure it stays on the part of the navmesh that it can reach.

#6

I just realized there is a bigger problem. I looked closely at the lines of the graph after scanning and I realized I can’t just change certain nodes’ Tags. It’s not that simple. You know how the generator will detect fences and walls and the nodes are built all around these barriers, leaving a little cushion around it? For some stupid reason, I assumed a similar outcome around my lakes. I don’t know what I was thinking. Is this going to be prohibitively complex or is there a simple solution. The triangles around a lake should converge onto a line going around the lake. INSIDE this polygonal line, nodes should continue down along the floor of the lake whilst more nodes stretch over the water’s surface above them. Looking at the lines in my scene, this is not happening. I’ll see like one triangle that starts next to the lake and continues right over the lake and onto the water plane. It’s too big. It needs to stop at the water’s edge. It needs to subdivide nodes around the lake just like it does around impassible areas.

#7

Hi

You can use a RecastMeshObj component and set a custom area to split it up further. Note however that you will not be able to have paths that go from land to below the lake AND paths that go from land to on top of the lake since that would require that the triangles split in unnatural ways.

#8

Okay thanks! I’m not going to worry about the ground under a body of water then. But, regarding the RecastMeshObj class, I’ve been looking at the code and I haven’t been able to figure out how to use it to subdivide an area further. How exactly do I do this?

#9

I have a vague idea of a way to generate more triangles when the terrain is scanned and I can see where a mesh is created and then added to extraMeshes:

extraMeshes.Add (new ExtraMesh (terrainVertices,tris,b));

But, I want to do this cleanly and I still can’t figure out how RecastMeshObj can help me. They appear to be meshes that I’ve added to my scene. But the surrounding area around lakes and rivers is part of the terrain, not a scene mesh.

I just need it to treat the border around the lake/river as though it was a wall with many nodes surrounding it and terminating at this border, however, it will need edges that are passable onto my water plane.

Do you have a code example of how to do this?

#10

Hm… right, that’s part of the terrain…
What might work is to attach a RecastMeshObj to the water plane (and set the area to some non-zero value like e.g 3). That should split the navmesh near the edge of the water… however it will not generate a border. Unfortunately I think it might be hard to get this kind of border without manually tracing it around the edge of the water.

Also check out the documentation on RecastMeshObj, there is a video there: http://arongranberg.com/astar/docs/class_pathfinding_1_1_recast_mesh_obj.php#a5008f5aaa9ef50b1510e309dce9205d7

#11

Thank you for this information! I tried your idea and I added RecastMeshObj’s to my Water4 tiles (there were two for this lake):

lake.png1200×623 878 KB

This looks very promising. I used an area of 3 on each of the tiles. I’m not totally sure of the meaning of the different lines I see here but I see many more nodes and the basic shape of the pond is prominent.

I mentioned before that I have some post-scan code that loops through all of my bodies of water and it checks to see if any nodes fall within any of these areas, and my code will set the nodes’ tags appropriately. Is there an easier way to just tell it that certain meshes need all of their nodes to be tagged as 1, not 0?

#12

Hi

Great that it works.

There are a bunch of more lines because 1. You have several tile splits that goes through the pond and 2. Some slopes around the edge of the lake seem to have been identified as too steep, so there will be no navmesh generated there, which will split up the navmesh further.

Sorry, I have that on my todo list. Some information needs to be propagated from the voxels to the polygons that are constructed from them, but right now the relevant information is discarded at some stage in the rasterization process.

#13

Hey Aron,

Although that one lake looked okay, it actually wasn’t as neat as I thought, and the other lakes were even worse. I did try playing around with the area parameter of RecastMesjObj and had it as high as 13 but I don’t see those nice clean edges at the water’s edge. Here is what Unity generated:

UnityNavMesh.png1200×617 774 KB

I wasn’t sure if this thread was the best place to post this (cause it deals with navigating around bodies of water), or the “outside of Unity” thread. But, I wanted to go back to the idea of converting Unity’s navmesh into something usable by your system.

I did look at that Unity function you told me about that outputs all the vertices of the NavMesh. I’m wondering how easy it would be to not only get all the polygons but know which ones have their “Navigation Area” marked as water, etc, in addition to walkable or not walkable. I basically want to translate these navigation areas into A* Pathfinding Tags on nodes. I can see that the NavMeshTriangulation does have “area” indices.

One thing I noticed that seems a bit concerning is that Unity’s NavMesh seems to have all kinds of convex polygons, not just triangles. CalculateTriangulation does say it spits out triangles, which is good but I can only imagine that breaking down all these polygons further will generate a TON of triangles.

If it’s even possible, would this be a function we could maybe work on together? Does it sound like something you could include in your product for other customers? It serves two purposes:
(1) Faster bake time
(2) Unity’s NavMesh baking seems to work really well around bodies of water and other jagged obstacles.

This could be an option for any customer but nearly essential for me. Even if I didn’t care about creatures walking over water, land animals are plummeting into the water because pieces of triangles protrude into the water.

If I do this on my own, could I get a little bit of guidance?.. For example, CalculateTriangulation does not give tiles. I wouldn’t know how to generate tiles[].nodes[] for a scene from Unity’s triangle data and make it TILED… can I put it all in one tile? Also, I don’t know how to start fresh and bypass RecastGenerator. Is there anything else required for saving off a .bytes file besides the tiles[] array? I get the basic concept but there lots of gray areas surround it. Any guidance or help on the actual conversion tool would be so wonderful!

UPDATE: In an attempt to try to do this myself, I’ve become even more confused. I tried to attack this problem from a different angle by looking at what’s being serialized in the graph. The properties in a NavGraph do not seem to hold a graph. I can’t figure out how it ends up getting serialized then. I can see METHODS that can get node info, etc. I basically want to keep your code to generate settings but then replace the graph part of it with info from my NavMeshTriangulation object (which contains triangle indices, vertexes, and area “tags” per triangle [or per index triplet] ). This whole idea of tiles is confusing. It seems that they were only necessary in scanning the scene but should not be needed when serializing, deserializing, or using the graphs. I’ll wait for your response. Thanks in advance!

#14

May I ask what voxel size/cell size you are using for unity and my system respectively?

Also, the area setting on RecastMeshObj is only an ID. The navmesh will be split so that regions with different IDs are not in the same triangle. The actual number does not really matter as long as it is different from the default one (which I think is 0 or 1… I cannot remember).

#15

Ahhh, there is a difference, would this be it?

Unity voxel size: automatic but system picked 0.133333
A*Path, cell size set to 0.5

Would that be it? Even at 0.5, it takes a long time to bake. I could try closer to Unity’s setting to see how it looks. But I would still be interested in reading in NavMeshTriangulation data :smile:

#16

Yeah, voxel size makes a huge difference. See bottom of this page: http://arongranberg.com/astar/docs/getstarted2.php

#17

Okay, the scan was realllly slow at 0.2 and that was only for a 1500x1500 area. My 10000x10000 areas would probably be prohibitively slow at that voxel size. Do you have any suggestions about getting NavMeshTriangulation information into your graph object? With there being no concept of tiles anymore after CalculateTriangulation, do you know how I could handle this?

Besides the tile issue, there are other unknowns for me. If it were as simple as stuffing all of Unity’s data into tile[0] in place of doing ScanInternal(), there are data structures in tile[0].node[xx] like connections, connectionCost, and then I don’t know where to place the vertex array that node refers to. Am I getting warmer here? :smile:

#18

FYI - Here is the (uncleaned-up) code I have so far: (ScanInternal)

			tileSizeX = (int)(forcedBounds.size.x/cellSize + 0.5f);
			tileSizeZ = (int)(forcedBounds.size.z/cellSize + 0.5f);
			tileXCount = 1;
			tileZCount = 1;

			NavMeshTriangulation tri=NavMesh.CalculateTriangulation();
			tiles=new NavmeshTile[1];
			tiles[0]=new NavmeshTile();
			tiles[0].x = 0;
			tiles[0].z = 0;
			tiles[0].w = 1;
			tiles[0].d = 1;
			tiles[0].bbTree = new BBTree(tiles[0]);
			tiles[0].tris=new int[tri.indices.Length];
			for(int i=0;i<tri.indices.Length;i++) tiles[0].tris[i]=tri.indices[i]; 
			tiles[0].verts=new Int3[tri.vertices.Length];
			for(int i=0;i<tri.vertices.Length;i++) tiles[0].verts[i]=(Int3)tri.vertices[i]; 

			tiles[0].nodes=new TriangleMeshNode[tri.indices.Length/3];
			tiles[0].verts=new Int3[tri.vertices.Length];
			for(int i=0;i<tri.vertices.Length;i++) {
				tiles[0].verts[i]=(Int3)tri.vertices[i];
			}
			int ind=0;
			TriangleMeshNode.SetNavmeshHolder (1, tiles[0]);
			for(int i=0;i<tri.indices.Length;i+=3) {
				TriangleMeshNode node=new TriangleMeshNode(active);
				tiles[0].nodes[ind]=node;
				node.GraphIndex=1;
				node.v0=tri.indices[i];
				node.v1=tri.indices[i+1];
				node.v2=tri.indices[i+2];
				node.Tag=(uint)tri.areas[ind];
				node.Walkable = true;
				node.Penalty = initialPenalty;
				node.UpdatePositionFromVertices();
				tiles[0].bbTree.Insert(node);

				ind++;
			}
			CreateNodeConnections(tiles[0].nodes);
			TriangleMeshNode.SetNavmeshHolder (1, null);

I don’t know if my assumption to use one tile will even work, and plus it is crashing when I try to load and use the graph. After running this code in my scan, I DO see the node lines are all in the right place but that’s probably just because I got the node[].position’s all correct.

UPDATE on 29-Jan: I forgot to include this: (I had to increase recast’s part of the mask for the nodes because of using one tile).

#if ASTAR_RECAST_LARGER_TILES
		// Larger tiles
		public const int VertexIndexMask = 0xFFFFF;

		public const int TileIndexMask = 0x7FF;
		public const int TileIndexOffset = 20;
#else
		// Larger worlds
		public const int VertexIndexMask = 0xFFFFFF; //0xFFF;

		public const int TileIndexMask = 0x7F; //0x7FFFF;
		public const int TileIndexOffset = 24; //12;
#endif

Like I said, this does not work. It takes forever to load (even though the graph is only 3MB) and then performance is horrible and then there are multiple crashes and lots of warnings that I’m calling WaitForPath recursively, which I’m not. Obviously, the data I loaded into it (see the code section in this post) is causing chaos. I really want to fix this. The lines of the graph converted from Unity to A* look PERFECT!!

#19

I can see you’re probably very busy and I’ve asked so many questions already. I don’t want to keep burdening you. I’ve switched my focus to the RecastNavigation system that is all native C++. I’m looking into converting Unity’s navmesh to the format it can use and I’m going to see how that goes. Thanks for all of your help over the past several weeks Aron!

I’m PRAYING for dtNavMeshQuery::findPath!!! This has been the hardest part of developing an MMORPG!

Have a nice weekend

#20

Hi

Ok. Another option could be to take the mesh data from Unity and feed it directly into Recast.
E.g by exporting to a .obj file. I know I did that for testing a looong time ago (sadly I don’t think I still have the script that I used).

Also, I have made some improvements the scanning process to optimize for large worlds and a large number of tiles.

  • Scanning is now multithreaded.
  • Optimized how tiles look for objects that are inside it resulting in a large speedup for large worlds.
  • Optimized how terrains are converted to meshes. Now a terrain will be split into approximately tile sized chunks instead of being converted to a single mesh. Now each tile does not have to go through all triangles of the terrain mesh just to discover that most of them were outside the bounds anyway.

Right now I am seeing approximately a 4.2x speed improvement.
This is for a 129 tile graph, I am expecting the speed improvement to increase with larger graphs. For your 22000 tile graph it should improve things a lot.

Unfortunately you cannot just stuff everything in to the first tile. Some detection needs to be done to see what tile size Unity uses and then put the correct triangles into the correct tiles.
It’s late for me now, but if you want to try that route, I might be able to help later.