Generic error understanding and rounding errors/generation reasoning

Ok, i will be blunt about this. I am having a few issues with my recast graphs.
First of all, some settings will cause the entire regraph file to mess up with rounding errors somehow. I had an example up on the vanilla forum which got taken down or something.

For now i have the following issue, i have no clue how to properly set some of the values in the recast graph to get what i want.

I am using the following settings for my level which is a 1unit = 1 meter scale of an office:

  1. My level is just 3 meters tall (no actual 2nd level for now, so the size is just 1.5) yet it generates paths up to 9 meters high for no reasons whatsoever.
  2. Some settings cause my path to be generated half a meter above the ground instead of ON the ground, which i do not get at all. There is no indication as to why this happens. The size/center is alligned with the ground exactly. Moving this just a bit and recaclulating changes the outcome so drastically that i can not make up why or when the navmesh starts floating in air (and ignoring some of my smaller obstacles).
  3. Edge error doesn’t make a lot of sense in general, i do not see what it does.
  4. I keep getting the error: Degenerate triangles might have been generated.
    Usually this is not a problem, but if you have a static level, try to modify the graph settings slightly to avoid this edge case.
    However, it doesn’t tell me what parameters to fiddle with, and i can’t get it to stop doing that.
  5. In the map on the left, left of the bright cyan outlined door, there is a part of the ground that is not mapped, it used to map it, but now it refuses outright. Only doors have been added to meshnavIgnore layers, the rest should just be fine to path over.
  6. Small pathways of 1 by X meters are generally weird. The generator seesm to preffer to map the middle and the +X side of the path, but not the -X side of the same path. (it gets closer to one wall, then it does to the other wall) Why does this happen and how do i fix it? (see the little pillars in the left bottom corner, it shows the same thing in ISOMETRIC top view)
  7. i had to set my character radius a lot smaller just to compensate for point 6. I feel like this is wrong as well.
  8. Is it just me, or can i NOT rotate the navmeshcut over the X or Z axis? It seems to just squash and dissapear instead of rotating (Use Rotation is on)

Any insight on the previous points would be very helpfull. In general i just have no idea how the graph generates or why it does some of it’s quirks. A better understanding of the mechanics might clear everything up, but i feel like i am missing a lot of information even when using the examples.

Sincerely,
Vince

Hi

Background: The recast graph is generated by voxelizing the whole world. Think of it as converting it to a minecraft-like world built out of blocks. Then it processes that world and generates a navmesh.

  1. I am not totally sure what you mean by “generates paths up to 9 meters tall” since paths have no such thing as “height”. Do you think you could elaborate a bit?

  2. Your cell height is set to 0.9. The cell height is basically the resolution of the graph on the Y axis. Think of it as minecraft, the cell height would be the height of each block. I would suggest that you lower that value to maybe 0.01.
    This might very well have affected a lot of the other points.

  3. The edge error field will simplify some contours of the navmesh to contain fewer vertices if the maximum distance from the simplified contour to a vertex that was removed is less than the specified value. Basically, higher value -> less accurate contour.

  4. Oh, you actually get that error. That is pretty rare. Yeah it is best to try to fiddle around a bit with the settings, though usually it shouldn’t cause any problems.

  5. Can’t say what this is caused by unfortunately. You could try to expand the bounds of your graph since right now the size along the Y axis is only 1.5 and you say your level is 3 meters high, so it might miss some colliders.

  6. As with (2), the resolution of the graph depends on the cell size. If you think of it as minecraft, this is the width of the blocks that the whole world is rasterized to. Since your cell size is 0.2, it might have an error up to 0.2 meters on both sides (well, you also have “max edge error” set to 0.5 so the error might be a bit higher).

  7. Usually some margin is required to make it work since the graph generation only has a finite resolution.

  8. No, you cannot. The navmesh cut is a 2D shape projected from a top view.

Best regards,
Aron

I migrated to this forum software a few days ago, but all posts should have been transfered to this forum.
However you might have had bad luck and posted after I exported the database but before the redirect went through.

  1. My graph height is 1.5 units. Somehow it generates paths 7ish units ABOVE the white square that marks the location in which it will calculate paths. (see the image, that object it generates path on top of, that is like 4 meters above the floor, way outside the white wireframe rectangle)

  2. That does make sense, my logic was that since i have only 1 height (the ground, nothing else, no elevation) i could make it a high value so it wouldn’t generate as much voxels in the Y (so it had less calculations to do). I will attempt a lower value.

  3. Guessing the error value is in units, i would want it in the range of 0.2? (20cm in my world, so the character won’t scrape against objects at any point) Would that be correct?

  4. I actually have no clue which settings apply to this error, and looking at the code, i couldn’t make much sense of why it happens. What does the error actually mean? (This error dissapeared when i fixed the missing tiles on point 5 by editing cell size to 0.1, but made generation MUCH slower)

  5. Again, i made the area this small due to my recuirement of fast graph generation at the start of my level (it has to run on mobile, and i want to keep the generation after the map is generated under 5 seconds~) Does height influence the math a whole lot if the area is just empty space?

  6. Ok, ill fiddle with those 2 values.

  7. how finite is this resolution? it might be important to understand how much of a margin might be needed compared to your level size etc. I have a level of 100x100 units, which i want almost 0.1 units of precision in. I know that might be pushing the limit.

  8. Can we get around this somehow? I have characters that tend to change rotation/position due to animations. Laying it on it’s back makes the whole thing dissapear. I might just create a script to edit the 2D shape based on the characters current bounding box of the renderer. Ill post if i have real issues with this.

As for the missing post, i suppose it might be lost then, or my bookmark magically failed to update to the correct new post, and was on a different account. The problem was changing cell size to 0.15 and then adding obstacles made the tile dissappear from the graph. I can’t seem to replicate it now though.

I’ll try and fix my problems with this information, the minecraft example makes a load of sense so far.

  1. Well, the bounding box is more to tell it from which location in the world to get colliders/meshes. The actual generated navmesh might go outside that box.

  2. In the future I am planning to remove that field altogether. The reason is that, contrary to intuition, it is not more expensive to use a low value, it just gives you more precision. However a too low value might mean that you run out of numbers if your level is very high. But I plan to automatically calculate this value to something reasonable.

  3. Yes it is in world units.

  4. It is caused by mostly by floating point errors if I remember correctly. So there are not really any direct connection to any of the settings. However changing the cell size is usually the best since that causes large changes in the navmesh even with very small changes (e.g change 0.2 to 0.201).

  5. No, only the actual colliders that it find in that bounding box will influence the calculation time.

  6. The resolution is the cell size basically. With the minecraft analogy again, that’s the size of the blocks. So smaller blocks means a higher quality. For 0.1 units of precision, that would mean that you need a cell size of maybe 0.05, which will take some time to generate.

  7. Not really, doing more general 3D computational geometry would be several magnitudes harder and slower. So the best option is just to use a script which rotates it correctly.

I couldn’t get links to posts to update correctly. But you could try searching for it.

  1. Good to know.

  2. Might make sense, if it doesn’t cost a lot more, you might just want to give the user a “scale” dropdown. so he can pick 1 unity = 1 meter in my game, and that orders the scale on the Y around without to much of a hassle.

  3. And i suppose using a Double will cause the whole thing to be that much slower? (you might want to add that info to the error in future releases so people know what causes it and that cell size might just fix it)

  4. That means my precision is down the drain for this reason. But i think i found something reasonable. Most levels can use a saved/loaded graph anyway, which is nice.

Extra:
Is it normal for navMeshCut to ignore the character radius? I can make the cut bigger but in some cases it will make my character try and move somewhere, where the walkway just got a bit to narrow due to an open door.

  1. Using double likely be slower and more importantly, would increase the memory usage a lot.

Yes, the navmesh cut ignores character radius completely. That is one of the things that make it a lot faster than regular graph updates.