A* Pathfinding to export navmesh for authoritative server

#1

Hello. Our game uses authoritative server which is written in vanilla CSharp. We export Unity navmesh triangulation to xml, then our handwritten A* implementation uses its data to do pathfinding.

We have several problems with it right now and one is performance. We use triangulation which I suppose is not raw navmesh data. It has more polygons (triangles) then original navmesh data which I think is composed of generic convex polygons.

What do you use internally in your navmesh graph implementation? Is it exportable (human-readable, parseable by computer)? How do you think, is it better to have graph composed of convex polys instead of triangles or not? Does it make any sense?
Can you estimate performance boost in completely abstract generic map case?
Can you provide any example of navmesh stored to file?

Our second problem is associating metadata with navmesh polygons. For example I have a gate which can be closed and open. In final navmesh I need system to generate additional passable polygons inside passable area for it and attach some metadata to that polygons (door id, etc). We have solution for unity navmesh, but it is very clunky. You need
to set it on another navmesh layer to force unity generate additional polygons. You need to be sure two special objects like this are on different areas or Unity will collapse them in one polygon. Then you need some way to understand which polygon is created by each object and I do something like “get center of each navmesh polygon and then in loop ask each object if it contains the polygon” and I don’t like the solution.
So can I extend your solution and attach some data to navmesh nodes in prebuild step?

#2

My package uses triangles.

Convex polygons can be more efficient in some cases, but on the other hand it requires the code to be more complex. I have found the lower complexity trade-off to be worth it.

It’s very hard to estimate the performance boost, maybe on the order of 20%, but if you have a static map there are a lot better ways to optimize it (see for example https://arongranberg.com/astar/docs/heuristicopt.html which can get you a factor of 10 performance boost in many cases).

My package can save graphs to file, see https://arongranberg.com/astar/docs/saveloadgraphs.html however it may be easier for you to just read the internal graph data and export that yourself. See https://arongranberg.com/astar/docs/accessingdata.html.

To generate additional polygons around a door, take a look at this page which may be useful: https://arongranberg.com/astar/docs/recastmeshobj.html#area. Unfortunately that data, like in Unity is not saved in the resulting navmesh, so it does not get much prettier I am afraid.