TLDR: Which choice to make use of is determined by the necessity. Grid-based maps use navmesh could have extra workload, however the impact is best normally.
Navmesh is actually an optimization of a grid-based pathfinding scheme. Its important objective is to cut back the variety of nodes in your entire map to optimize efficiency. Most navmesh makes use of triangular meshes as fundamental knowledge.
As for the connection of them, I made a tough kind:
| cells/tiles | triangle mesh | |
|---|---|---|
| knowledge construction | 2nd-array / cross linked checklist | (undirected) graph |
| shortest path search algorithm | bfs | graph search (floyd,dijkstra,…) |
| optimization | A* and its variants | A* and its variants |
| shorten the trail | Line drawing algorithm (Bresenham’s line algorithm) | funnel algorithm |
Within the pathfinding algorithm, the 2 are mainly the identical factor. A 2nd array will be seen as an undirected graph with a node distance of 1. When the space between nodes in an undirected graph is 1, Dijkstra’s algorithm degenerates into BFS. So tile pathfinding is a particular case of graph search, some extra variants can be utilized, reminiscent of JPS.
A* achieves higher efficiency by utilizing heuristics to information its search. It may be seen as an extension of Dijkstra’s algorithm. So after all it may be utilized in BFS.
Now we come again to the unique query.
- Create cells that covers each walkable house.
- Use A* pathfinding on the middle of every rect.
From these two items of data, the essential answer is to divide the house into 2D areas, after which carry out grid-based A* pathfinding. I do not assume it is a navmesh as a result of it does not optimize for the variety of nodes. You’ll be able to change to a triangle-based navmesh by way of some schemes, or use some rectangle-based node discount methods. that is an instance
- Use the silly funnel algorithm to shorten the trail (each vector) optimally round unwalkable objects
The funnel algorithm so far as I do know relies on triangles. I do not know if there is a rectangle-based model (it is theoretically doable), however it does not make a lot sense to take action. As a result of grid-based paths inherently have important precision limitations, path vector instructions are at all times multiples of 45° or 90°. The funnel algorithm can not remove this precision limitation. Possibly it will probably straighten your path by 10% as a substitute of 100%.
An alternate answer is to examine the visibility of the nodes between the paths (utilizing the road drawing algorithm), and if two nodes are mutually seen, delete all nodes between them.
Questions:
- Is that this an accurate interpretation?
- I am considering of doing the cells as rects as all objects in my engine at the moment will likely be rectangular (opposite to triangles which are sometimes really useful)?
Already answered.
- I do not know the way to dimension my cell rects. Is it viable to do them as giant as doable till they “attain” an object? In any other case what metric needs to be used?
In grid-based pathfinding, it is determined by how exact you need it to be, the upper the precision the decrease the efficiency. You will get the precise parameters you need by testing. Navmesh won’t have this drawback, as a result of the variety of nodes has been decreased.
*Extra info: get a triangle based mostly navmesh from a grid based mostly map?
Possibility 1: Obtain by your self. On the whole, triangles have to be generated from grid knowledge. Usually, there will likely be steps reminiscent of trying to find blocking polygonal edges, smoothing edges, setting boundary factors, triangulation, and merging triangles. that is an instance
Possibility 2: Add a third-party pathfinding module to your engine, reminiscent of recastnavigation. It additionally must generate the information it wants by way of the grid. For instance, after producing triangles, convert them to .obj recordsdata, after which import them into recast to generate navmesh. The benefit of that is that there are out-of-the-box optimizations accessible, reminiscent of triangle merging, baking completely different meshes by way of agent radius, and so on.
