Delaunay + Exterior Corner Waypoints

from Red Blob Games

{ start by showing grid pathfinding, then path smoothing. observe that path smoothing always picks certain intermediary points. if we can preprocess, we only have to run path finding on those points. }

If we start with a grid map, we don’t have to do pathfinding on the grid directly. Instead, we can identify the key decision points (waypoints) and do pathfinding on them only. This speeds things up!

Button: use all grid points vs use only exterior corners

Building edges

Diagrams and implementations of each of these?
  1. Brute force O(N^2)
  2. Delaunay graph O(N log N)
  3. Distance limited

Pruning edges

No diagram, just explanation
  1. Line of sight
  2. Line of sight on grid - we can index the edges, or use line drawing, or FOV from roguelike


Diagram showing why string pulling neededmovement can still be on grid even if waypoints diagram doesn't show it

Email me , or tweet @redblobgames, or comment: