Think of a graph overlayed on a game world where the edges are not uniformly weighted.

Advantages

• Goal of reducing the memory (and path search burden) of dense grid lattices
• Can be sparse or dense as appropriate for variable game world details
• Can reduce the jagged nature of paths found on grid lattice

Movement Paradigm

The graph is just a bunch of connected line segments so it does not cover every possible point on the game world. Therefore, the agent is allowed two states of movement:

Local movement

Decisions are based on entities in sight of the agent (e.g. raycast). Can be based on kinematic movement, steering behaviors, etc.

Remote movement

When the agent needs to access something out of sight, the agent queries for a path and enters this movement state.

• Can have lack of precision.
• Agent can be ON the path following from node to node and staying on or very close to the edges.
• Agent may go OFF the path due to a dynamic obstacle, opportunistic task, emergency, etc. The position upon leaving is saved (leftPos)
• Once off the path, the agent relies on local movement to get back on at leftPos.
• If not possible, new path planning can be performed.

Typical Example

• Find closest visible node to agent
  • First narrow down the nearby nodes (can perform binning, grid-lattice of neighboring region or specify a radius)
  • Then perform ray-casting to identify which closest node is visible
• Find closest visible node to goal
  • Same as above but for the goal
• Perform a search
  • Using an algorithm like A-star from the closest agent node to closest goal node.
• Agent gets to start node of path using local movement
• Agent follows the path to get to closest node to goal using remote movement
• Agent gets to the goal using local movement after it gets off the path

Issues

• Path quality can be poor since it depends on how the graph is laid out
• Problematic if no node is visible from agent position or goal position
  • Can try local movement like following along walls
  • Can subdivide edges to create more nodes until agent sees one
  • Can teleport especially if user is not looking
  • If it is leaving path for temporary opportunity, maybe the agent can keep checking to verify it can still see a node, and if not, it can drop one (like its a breadcrumb)

Building Path Network

• Manual Placement
  • Tedious but can give good results
  • Can use manual node placement, but automatic edge forming
• Automatic Placement [RESEARCH IDEA]
  • Quick, but not very efficient

Automatic Placement

Flood Fill

Points of Visibility

• Real world maps need to be simplified (possibly using colliders) as too many points to be pratical

• Inflection points must be offset by some distance to leave room for agent

  • offset along bisecting line of angle
  • Should be further than the radius of the agent to allow flexibility/buffer

• Concave angles could be used as well for better coverage of a navigable space

• Similar to previous convex angle offsetting, but you additionally need to find point on the angle bisecting line that is at least the agent's radius away from a line that coincides with one of the two line segments of convex angle

• Concave angles are not path inflection points though, so not very helpful.

• Probably better off adding extra nodes at point of interest.

Issues with PoV

• Nodes and edges can explode combinatorically
• Can end up going down a rabbit hole of adding more and more auto-placement features that never quite work
• Often requires a lot of manual tweaks, offsetting the benefits

Path Network from Candidate Nodes

• Must evaluate whether an obstacle intrudes on corridor defined by edge between node A & B
• Corridor size defined by agent radius
• This ensures that agent can traverse path AB
• Use combination of point-distance-to-line-segment test and line-seg-line-seg-intersection test
• If the corridor is clear, then add the edge to the graph

Conditions

Following conditions must be met for a node to be considered for edge pairing:

• The node falls within the game world
• The node falls outside of any obstacles
• Distance from the boundary walls to the node is bigger than agent radius
• Distance from the obstacle sides to the node is bigger than agent radius

Following conditions must be met for an edge to be valid for traversal:

• Distance from the edge to any of the obstacle corners is bigger than agent radius
• Distance from the edge to any of the boundary corners is bigger than the agent radius
• The edge does not intersect with any of the obstacle sides
• The edge does not intersect with any of the boundary walls

As you might notice, there's broadly two kinds of tests above:

• Point containment (node inside boundary but outside obstacles)
• Line to point (edge to obstacle/boundary corner; obstacle/boundary wall to node)
• Line intersects line (edge intersects obstacle/boundary wall)

Breadcrumb/Dynamic Path Network

The agent dynamically constructs the path network as it explores the environment.

• Start with a waypoint at HOME location as first node of a graph lastWayPoint
• Each Think() update, check to see if from the current position can raycast cleanly to the lastWayPoint
  • If yes, then store as lastSafePos var
  • If no, add lastSafePos to graph as a new node and connect to lastWayPoint
• Additional incremental update process to form other edges
  • Space partioning such as cell-space/bin-space to track nearby waypoints

Advantages

• Could be useful in generated worlds where it is impractical to pre-bake path planning into
• Avoids authorial burden of creating network

Disadvantages

• One issue is the path network can eventually start to loop back on itself.
  • You want to be able to connect back to previously constrcuted nodes and not keep creating nodes.
• Clean-up process can become expensive, and without it Runaway waypoint formation eats up memory.

Path Quality with Path Network

• String pulling could be utilized but would need to work against world geometry (maybe physics colliders)
• Or agent could use Greedy Path Following approach since it can be on or off path

Variable size Path Network Corridors