Intro
In Path Planning, path networks are another way to discretize a game world space
Alternative to grid lattice and other structures
- The path network is an alternative to Grid Lattice and other structures like Quad Trees
Path Network
Why path networks?
- Grid lattice not very space-efficient
New agent movement paridigm
Path network movement
Remote movement
Design implication
Path network example
How to build a path network?
Automatic placement- flood fill
Points of visibility
- Features of the world create natural inflection points
- Make path network nodes at the inflection points
Points of visibility process
Automate path network- POV graph
Points of visibility bloat
Points of visibility
Building a path network from candidate nodes
Quake Reaper bot
- Steven Polge used handmade path networks for movements
Breadcrumbs/Dynamic path network
- The agent drops waypoints at important locations, creating a complete path network in doing so.
- Whenever the agent can’t see where the last waypoint is, store the last waypoint as a node, and continue on the new path
- Eventually, you run into scenario of looping back
- Disadvantages
Addressing path quality with path network
- String pulling
- Greedy path following- spread the processing out over multiple frames
Greedy steering
- Agent looks ahead to furthest node it can see
Problems
- Raycasting will miss some things and can also get expensive
Path network pros
Cons
- Might not see a node in the network