Skip to content

Algorithms

Choosing a Pathing Algorithm

The package includes various pathfinding algorithms that will change the shape of the path (when there is more than one optimal path available). If you're unsure of which to use, try JPS4_Horizontal first for the best performance, then AStar4 after.

There are many variants of A, it's important to note that here, tiles are unweighted to be compatible with JPS4.*

public enum EPathingAlgorithm
{
    JPS4_Horizontal,  // JPS 4-connected, horizontal-first canonical ordering
    JPS4_Vertical,    // JPS 4-connected, vertical-first canonical ordering
    AStar4,           // Traditional A* 4-connected
    AStar8            // Traditional A* 8-connected
}
Horizontal or Vertical JPS4?

These two modes specify the "canonical ordering" of the jump points used in the JPS4 Algorithm. A canonical ordering is a total ordering over paths which can eliminate many of the redundant paths. This is what drives the main performance advantage of JPS4 - it will also result in very different paths (when there is 2+ optimal paths).

Horizontal: The original implementation specified by the JPS4 paper. This will search horizontally first (w/ vertical jumps). Faster with long vertical corridors, where vertical jumping will prune more nodes.

Canonical Ordering

Vertical: An alternate version of JPS4 that will search vertically first (w/ horizontal jumps). Faster with long horizontal corridors, where horizontal jumping will prune more nodes.

Canonical Ordering

Jump Point Search optimized for 4-connected grids. This offers performance gains over A* for most grids. Horizontal-First canonical ordering will favor moving horizontally before vertically when pruning nodes, but jump points are generated vertically. So this is more performant if you have long vertical corridors.

Jump Point Search optimized for 4-connected grids. This offers performance gains over A* for most grids. Vertical-First canonical ordering will favor moving vertically before horizontally when pruning nodes, but jump points are generated horizontally. So this is more performant if you have long horizontal corridors.

Traditional A* pathfinding algorithm for 4-connected grids. This is a flexible, performant, and well-rounded approach widely used.

Traditional A* pathfinding algorithm for 8-connected grids. This is a flexible, performant, and well-rounded approach widely used.

  • Allows diagonal movement compared to JPS4
  • AllowCutCorners will determine whether the navigation agent can slip through corners where two obstacles touch.

Preprocessor Directives

To avoid expensive or redundant checks for a configuration you don't plan to use, all algorithm Job files under Scripts/PathingAlgorithms use directives that can be be commented out and/or defined in PlayerSettings.

In Project Settings > Other Settings > Script Compilation Build

#define JPS4_DEBUG
#define CHECK_DYNAMIC
#define CLOSEST_TARGET

JPS4_DEBUG

Don't ship with JPS4_DEBUG! By default DEBUG is turned off on everything because Logging in a Unity Job will disable Burst Compilation.

Editor Performance

It's important to note that Burst Jobs are much slower in the Unity Editor because of extra safety checks.

If you want to test performance or just want faster jobs in the editor, you can adjust these settings:

  • Jobs > Burst > Safety Checks = Off
  • Jobs > Burst > Native Debug Mode Compilation = Off
  • Edit > Preferences > Jobs > Leak Detection Level = Disabled
  • Edit > Preferences > Jobs > Enable Jobs Debugger = Off