Viveckh's Notepad

Instead of a square like in grid lattic, we could allow arbitrary shapes (polygons). But don't want too complex polygons either.

polygon-types

# Why Convex Polygons?

why-convex-polygon

navmesh-high-level

# Greedy NavMesh

# Building Algorithm

Goal: Create triangles exhaustively through scene

  • Iterate through all obstacle/boundary points selecting point a
  • Then iterate through all obstacle/boundary points selecting point b
  • Then iterate through all obstacle/boundary points selecting point c
  • This defines a candidate triangle. If the candidate triangle (normalized to CCW) meets the following conditions, add it to the valid triangle-list.
    • Has a non-zero area
    • Does not intersect with the obstacles and the current list of formed triangles
    • Is in anti-clockwise direction (not a requirement, but good for adjacency)
  • Pick another candidate triangle and continue until no more triangles can be formed.

# Performance Improvements

  • Rather than testing the entire triangle, consider each edge. * As soon as an edge fails, abandon it and try the next point
    • A candidate tri-edge that is also an obstacle edge is valid
    • A candidate tri-edge that intersects with an obstacle is not valid
    • A candidate tri-edge that has any obstacle vertices BETWEEN (collinear and intersecting) the edge endpoints, it is NOT valid. This addresses Adjancency Blocking as described below
  • The iteration process itself (nested loops 3 level deep) can be improves such that vertices are not repeated
    for (i=0; i<len-2; i++)
    for (j=i+1; j<len-1; j++)
        for (k=j+1; k<len; k++)
  • Even with optimized indexing, the edges will still repeat. The intersection tests (and other test results) for an edge can be stored in a hashtable-based data structure so if they are revisited, the cached value can be used.

My thought: Why not test make all possible global edges go through edge test in the beginning, so if they fail, they are removed from any further consideration. This will lower the global subset of edges under consideration which lowers number of candidate triangle tests that are bound to fail.

# Adjacency Blocking

Fix for this is included in Performance Improvements

adjacency-blocking

# Degenerate Triangles / FP values

degenerate-triangles

# Edge Intersection Quirk

This mostly plagues concave polygon. Fixes possible. For e.g. For concave example below, we should also verify not all other polygon points are on one side of the line in question. This helps strengthen intersection test between obstacle points to not raise false alarms for the case like shown below.

greedy-edge-obstacle-intersection

# Other Greedy Problems

  • Long skinny triangles can affect gameplay and lead to poor path quality.
    • There are algorithms like Delaunay Triangulation that can avert this. Example Implementation: Polytri
    • More advanced implementations like Recast exist
  • Run time of due to nested nature. There are alternative algorithms for navmesh building that can be as good as O(NlogN)
  • Once all navmesh polys have been created, common edges can be found among them to identify adjacency
  • Can use a hashtable of edges for quick matching
  • Note that a common edge connecting two CCW polys will be ordered opposite of its neighbor (e.g. AB and BA)
  • Hash Code can be based on Dot Product of A and B to be order invariant (commutative property)

# Triangle/Polygon Merging

  • Triangles/Polygons can be greedily merged
  • This can simplify search graph for better performance
  • Leverages efficient adjacency tracking hashtable
  • Merge two polygons into candidate polygon then test if convex
  • If so, replace the two merged triangles and update adjacency hash table
  • Repeat until no more polygons can be merged
  • Iterate through merged polygons following adjacent edges to create the nodes and edges
  • A position must be decided for the nodes (and number of nodes for polygons)
  • This is to support A* heuristic estimates (such as Euclidean distance)
  • And the actual path for agent to follow

# Placing Waypoints

Waypoints that are on the perimeter of a NavMesh polygon (corner or edge midpoint) can see every point in the connected NavMesh polygons. This can be a desirable feature since points in polygon centroid may not have a direct path.

navmesh-pathnode-at-edge

Various ways shown below. Efficiency/tradeoff is for us to choose.

# Centroid of the polygon

navmesh-pathnode-arrangement-1

The problem with picking centroid is centroids don't have clear line of sight into adjacent polygon's centroid. But this approach does ensure lower number of nodes in graph.

# Center of adjoining edges

navmesh-pathnode-arrangement-2

Increases the number of nodes significantly. Otherwise, offers safer paths than just centroids.

# Corner of each obstacle

navmesh-pathnode-arrangement-3

This can be a problem if the subject is bigger than a point. But object does turn at inflection points.

# Center of adjoining edges and corner of obstacles

navmesh-pathnode-arrangement-4

Increases the number of nodes by a huge factor.

# Expanded Geometry

expanded-geometry

expanded-geometry-corners-issue

  • Expanded Geometry is very well suited to improve navmeshes, but can also work with grids and path networks
  • Simiariies to process of generating POV path network
  • Once you have employed expanded geometry, you can consider the agent to be a single point. This greatly simplifies tests to see where an agent can go on the navmesh (or other discretized space). A raycast is sufficient.

# Quantization & Path Refinement

navmesh-path-viz

# Finding arbitary point

Can use A-star and point containment test with navmesh convex poly (but probably not best way)

  • Start at arbitrary NavMesh node
  • Use distance to candidate point p as heuristic
    • We will asssume a virtual node on the graph at p connected to node of navmesh poly it intersects with
    • Test point containment at each visited node's navmesh poly (convex)
      • Optionally store NavMesh poly bounding radius at each node for quick first pass containment filtering
  • Worse case, all nodes searched

Probably better solution: use spatial partioning such as bin queue, quadtree, octree, etc to organize navmesh polys for quick search

# Placing destinations on NavMesh

  • Best to make sure candidate destinations are on NavMesh from the start of simulation
  • Use spawn points
  • Track non-agent moving objects (such as player) relying on coherence (assumption that object moves from one adjacent navmesh poly to another)

# Simple Stupid Funnel Algorithm

simple-stupid-funnel-algo

Like climbing down with feet on two side walls. left foot on left end of the adjacent edge, and right foot on the right end of the adjacent edge. Keep going until the angle of the two foot gets so narrow that it flips. That point is the inflection point that can be used for string pulling. Continue from that point fresh end taking the inflection point as the start point.

Works great for NavMeshes with expanded geometry

# Horizon Zero Dawn Version

(of Simple Stupid Funnel)

Useful for NavMeshes without expanded geometry

# Benefits

  • Navigating when Unexpected obstacles
  • Different radiuses to account for different sized objects
  • Path planning with NavMesh can more easily consider turn angles and distances, rejecting paths that don't match performance abilities and/or targets
  • Animated Character actions, NavMesh to decide if enough room for a particular NPC actions to be executed
  • Can easily support multiple levels, can store max height in each NavMesh polygon

← Steering Behaviors →