A* question | Official Unity Discord | Page 1

finite trout Sep 10, 2025, 12:06 AM

#

I have a graph created based on the navmesh, and I want to run A* on it, but I have a question about finding the shortest path.

As you can see in the image, the graph itself is fairly wonky in some areas due to objects cutting up the navmesh.

I am wondering if this means it is possible that A* picks the wrong path, in a potential situation where one path is shorter on the navmesh, but has more cuts causing a longer line on the graph.

Or does A* account for this somehow? Or should I find a way to optimize the graph? Or some other solution?

#

because from my understanding the funnel algorithm will have to be implemented AFTER the "shortest path" is found, yes?

#

I'm thinking I will probably have to find a way to simplify the graph, but the problem theoretically exists even if I do

hybrid sapphire Sep 10, 2025, 1:47 AM

#

Yes, it would cause issues with normal A*. Unity is accounting for this in their implementation.

finite trout Sep 10, 2025, 1:53 AM

#

do you know the method they use?

#

I'm thinking I can, at minimum, collapse groups of 2-edge nodes into "supernodes" that A* pathfinds on. it might not be theoretically perfect but I think it would help at least

#

I have noticed that unity sometimes combines two triangles on the same plane into a singular 4 sided polygon, and I would like to also reflect that in my map, but I don't know what implementation they use.

specifically, in a case of 3 touching triangles on a plane, which two are combined and which is left alone?

hybrid sapphire Sep 10, 2025, 2:57 AM

#

finite trout do you know the method they use?

No clue. This is part of the close sourced C++ side.

#

It would be simpler to just use orthodox A* implementations that don't use navmesh, but a gird of nodes instead.

#

Or maybe look up some existing navmesh like solutions.

#A* question