Skip to main content
Game Development

Return to Answer

added 2719 characters in body
Source Link
Mangata
Mangata
  • 2.8k
  • 1
  • 4
  • 10

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.)

*Additional information*Additional information: How to get a triangle based navmesh from a grid based map?

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?

  1. 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. enter image description here enter image description here

  2. 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. enter image description here

  3. 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.

  4. 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. enter image description here

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
        }
    }
}
  1. 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. enter image description here

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.

*Additional information: How to get a triangle based navmesh from a grid based map?

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.

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.)

*Additional information: How to get a triangle based navmesh from a grid based map?

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?

  1. 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. enter image description here enter image description here

  2. 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. enter image description here

  3. 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.

  4. 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. enter image description here

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
        }
    }
}
  1. 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. enter image description here
Source Link
Mangata
Mangata
  • 2.8k
  • 1
  • 4
  • 10

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.

  1. Create cells that covers every walkable space.
  2. 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

  1. 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.

Questions:

  1. Is this a correct interpretation?
  2. 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.

  1. 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.