TLDR: Which option to use depends on the need. Grid-based maps use navmesh will have additional workload, but the effect is better in most cases.
Navmesh is essentially an optimization of a grid-based pathfinding scheme. Its main purpose is to reduce the number of nodes in the entire map to optimize performance. Most navmesh uses triangular meshes as basic data.
As for the relationship of them, I made a rough form:
|
cells/tiles |
triangle mesh |
| data structure |
2d-array / cross linked list |
(undirected) graph |
| shortest path search algorithm |
bfs |
graph search (floyd,dijkstra,...) |
| optimization |
A* and its variants |
A* and its variants |
| shorten the path |
Line drawing algorithm (Bresenham's line algorithm) |
funnel algorithm |
In the pathfinding algorithm, the two are basically the same thing. A 2d array can be seen as an undirected graph with a node distance of 1. When the distance between nodes in an undirected graph is 1, Dijkstra's algorithm degenerates into BFS. So tile pathfinding is a special case of graph search, some additional variants can be used, such as JPS.
A* achieves better performance by using heuristics to guide its search. It can be seen as an extension of Dijkstra's algorithm. So of course it can be used in BFS.
Now we come back to the original question.
- Create cells that covers every walkable space.
- Use A* pathfinding on the center of each rect.
From these two pieces of information, the basic solution is to divide the space into 2D regions, and then perform grid-based A* pathfinding. I don't think it's a navmesh because it doesn't optimize for the number of nodes. You can switch to a triangle-based navmesh through some schemes, or use some rectangle-based node reduction strategies. this is an example
- Use the stupid funnel algorithm to shorten the path (every vector) optimally around unwalkable objects
The funnel algorithm as far as I know is based on triangles. I don't know if there's a rectangle-based version (it's theoretically possible), but it doesn't make much sense to do so. Because grid-based paths inherently have significant precision limitations, path vector directions are always multiples of 45° or 90°. The funnel algorithm cannot eliminate this precision limitation. Maybe it can straighten your path by 10% instead of 100%.
An alternative solution is to check the visibility of the nodes between the paths (using the line drawing algorithm), and if two nodes are mutually visible, delete all nodes between them. (I will explain this algorithm in detail in the additional information.)
Questions:
- Is this a correct interpretation?
- I'm thinking of doing the cells as rects as all objects in my engine currently will be rectangular (contrary to triangles which are often recommended)?
Already answered.
- I don't know how to size my cell rects. Is it viable to do them as large as possible until they "reach" an object? Otherwise what metric should be used?
In grid-based pathfinding, it depends on how precise you want it to be, the higher the precision the lower the performance. You can get the specific parameters you want by testing. Navmesh will not have this problem, because the number of nodes has been reduced.
*Additional information: How to get a triangle based navmesh from a grid based map?
Option 1: Achieve by yourself. In general, triangles need to be generated from grid data. Generally, there will be steps such as searching for blocking polygonal edges, smoothing edges, setting boundary points, triangulation, and merging triangles. this is an example
Option 2: Add a third-party pathfinding module to your engine, such as recastnavigation. It also needs to generate the data it needs through the grid. For example, after generating triangles, convert them to .obj files, and then import them into recast to generate navmesh. The advantage of this is that there are out-of-the-box optimizations available, such as triangle merging, baking different meshes through agent radius, etc.
*Additional information2 If I adopt grid-based pathfinding, how can I reduce the path using the straight line drawing algorithm?
The basic strategy is to check if the nodes of the path obtained by pathfinding are visible between them, and if they are visible, delete all nodes between them. Two nodes are visible if the line between them does not pass through the block.
Bresenham's_line_algorithm is used to rasterize the straight line represented by the geometry into grid coordinates. In this way, we can get the coordinates that need to be detected.
If all the coordinates that need to be detected(The yellow grids in the picture above) are not blocking, then it can be seen that the two nodes are visible.
How to check the whole path? A locally optimal strategy is to start from the starting point, find the visible point farthest from the current point, and then set this point as the current point to repeat until the current point is the end point.
We represent this process in pseudocode:
path = [(1,1),(1,2),...] //original path
reducedPath = [path[0]] //path after optimization
curIndex = 0 //starting point
while(true) {
bool isOK = false
for(int i = len(path) - 1; i > curIndex; i--) {
//Traverse in reverse order to find the farthest visible point
if (isVisible(path[curIndex], path[i])) { //Visibility detection using line drawing algorithm
reducedPath.add(path[i])
curIndex = i
isOK = true
break
}
}
if !isOK {
//No optimization available, start searching from the next node
curIndex++
if (curIndex == len(path)-1) { //The last point has been reached, end the iteration
break
}
}
}
- Optional: delete all nodes with the same slope in advance, and only keep the inflection points, which can greatly reduce the number of nodes that need to be traversed. Such a strategy will not get the optimal path in some cases, but it can cover most cases.
