Skip to content
CrossfireCrossfire

Navigation

Navigation regions and grids, A* paths, and NavAgent nodes.

Files: navigation.odin.

File overviews

Section titled “File overviews”

From navigation.odin:

Pathfinding and navigation: NavRegion nodes say where characters can walk (a grid of cells over an area, blocked where static bodies are), and NavAgent nodes find paths through it (A*, then straightened) and steer their parent along them, keeping apart from each other.

<node kind="NavRegion" name="Floor" width="1280" height="720" cellSize="16" agentRadius="10"/>
<node kind="CharacterMover" name="Guard" x="100" y="100">
  <node kind="CollisionShape" shape="Circle" radius="10"/>
  <node kind="NavAgent" name="Nav" speed="120"/>
</node>
  • The grid (NavGrid): a NavRegion covers size from its position (its top-left corner), in cells of cellSize. A cell is blocked when a static body’s collision shape covers it, grown by agentRadius so characters that wide fit through what’s left: the walls of TileMaps and LDtk levels, StaticBody nodes. It’s built when the scene starts (NavRegion_Rebuild after walls change); NavGrid_SetBlocked blocks cells by hand (a closed door).
  • Paths (NavRegion_FindPath, NavGrid_FindPath): A* over the cells, 8 ways (diagonal; never cutting a blocked corner), then straightened where the way is clear. A target in a blocked cell goes to the nearest open one.
  • Agents (NavAgent): NavAgent_SetTarget finds a path in the region it’s in, and each update the agent works out velocity (toward the next point at speed, slowing near the end, pushed apart from other agents within avoidRadius). With autoMove it moves its parent: a CharacterMover by its velocity (CharacterMover_Move), a DynamicBody by its velocity, anything else by its position. Events: onArrived, onPathFailed.
  • Movement is in the plane (top-down games, or flying); a platformer’s walking needs jumps the grid doesn’t know about.

Types

Section titled “Types”
Section titled “NavGrid”
NavGrid :: struct {
  // The world position of cell (0, 0)'s top-left corner
  origin: [2]f32,
  // A cell's width and height
  cellSize: f32,
  // Cells across and down
  columns, rows: int,
  // Blocked cells, row by row
  blocked: []bool,
  // Paths may go diagonally (never across a blocked corner)
  diagonal: bool,
}

A grid of walkable cells (a NavRegion’s): see the file’s overview

struct. Source: navigation.odin:36

Section titled “NavSettings”
NavSettings :: struct {
  // NavRegion: a cell's size in pixels
  cellSize: f32,
  // NavRegion: how far walls are grown (half the characters' width), in pixels
  agentRadius: f32,
  // NavRegion: paths may go diagonally
  diagonal: bool,
  // NavAgent: pixels per second
  speed: f32,
  // NavAgent: how close counts as arrived, in pixels
  arriveDistance: f32,
  // NavAgent: keeps this far from other agents (0: doesn't avoid them)
  avoidRadius: f32,
  // NavAgent: moves its parent itself (else scripts read `velocity`)
  autoMove: bool,
}

A navigation area’s settings (SceneNodeData.nav): a NavRegion’s and a NavAgent’s.

struct. Source: navigation.odin:52

Section titled “NavRegion”
NavRegion :: struct {
  // The node part: transform, hierarchy, hooks
  using node: Node,
  // Its size in pixels, from its position (its top-left corner)
  size: [2]f32,
  // Its settings (cellSize, agentRadius, diagonal)
  settings: NavSettings,
  // Its grid (node arena; built when the scene starts, `NavRegion_Rebuild`)
  grid: NavGrid,
  // The grid has been built
  built: bool,
}

An area characters can walk in: see the file’s overview

struct. Source: navigation.odin:73

Section titled “NavAgent”
NavAgent :: struct {
  // The node part: transform, hierarchy, hooks
  using node: Node,
  // Its settings (speed, arriveDistance, avoidRadius, autoMove)
  settings: NavSettings,
  // The path being followed, in world positions (node arena)
  path: [dynamic][2]f32,
  // The next point of `path`
  next: int,
  // Where it's going, and whether it has somewhere to go
  target: [2]f32,
  moving: bool,
  // What it would move by this update, in pixels per second (also when not `autoMove`)
  velocity: [2]f32,
  // It reached the end of its path
  onArrived: EventSubject `event:"It reached its target"`,
  // No path leads to its target (or it's in no NavRegion)
  onPathFailed: EventSubject `event:"No path leads to its target"`,
}

A character’s path finder and steering: see the file’s overview

struct. Source: navigation.odin:87

Procedures

Section titled “Procedures”

CreateNavRegion

Section titled “CreateNavRegion”
CreateNavRegion :: proc(scene: ^Scene, size: [2]f32, settings := DEFAULT_NAV_SETTINGS) -> ^NavRegion

Creates a NavRegion and adds it to the scene (at the start of the next update). Its grid is built on its first update.

Inputs

  • scene: The scene
  • size: Its width and height in pixels, from its position (its top-left corner)
  • settings: Its cell size, agent radius, diagonal moves

Returns

  • The region

Example

floor := e.CreateNavRegion(scene, {1280, 720})
floor.settings.cellSize = 32

procedure. Source: navigation.odin:123

CreateNavAgent

Section titled “CreateNavAgent”
CreateNavAgent :: proc(scene: ^Scene, settings := DEFAULT_NAV_SETTINGS) -> ^NavAgent

Creates a NavAgent and adds it to the scene (at the start of the next update). Make it a child of the node it moves.

Inputs

  • scene: The scene
  • settings: Its speed, arrive distance, avoidance, auto move

Returns

  • The agent

Example

// Given: guard: ^e.CharacterMover
nav := e.CreateNavAgent(scene)
e.Node_AddChild(guard, nav)
e.NavAgent_SetTarget(nav, {600, 300})

procedure. Source: navigation.odin:155

Section titled “NavRegion_Rebuild”
NavRegion_Rebuild :: proc(region: ^NavRegion)

Builds a region’s grid again from the static bodies in its area (after walls were added, moved or removed). Cells blocked by hand are open again.

Inputs

  • region: The region

procedure. Source: navigation.odin:173

Section titled “NavGrid_BlockStaticBodies”
NavGrid_BlockStaticBodies :: proc(grid: ^NavGrid, scene: ^Scene, radius: f32)

Blocks the cells a scene’s static bodies’ collision shapes cover, grown by a radius.

Inputs

  • grid: The grid
  • scene: The scene
  • radius: How far shapes are grown (the characters’ half width)

procedure. Source: navigation.odin:196

Section titled “NavGrid_SetBlocked”
NavGrid_SetBlocked :: proc(grid: ^NavGrid, at: [2]f32, blocked: bool)

Blocks or opens the cell under a world point (a door closing or opening).

Inputs

  • grid: The grid (a NavRegion’s grid)
  • at: A world position
  • blocked: Blocked (true) or open

procedure. Source: navigation.odin:254

Section titled “NavGrid_CellAt”
NavGrid_CellAt :: proc(grid: ^NavGrid, at: [2]f32) -> ([2]int, bool)

The cell under a world point.

Inputs

  • grid: The grid
  • at: A world position

Returns

  • Its column and row, and false when it’s outside the grid

procedure. Source: navigation.odin:268

Section titled “NavGrid_IsBlocked”
NavGrid_IsBlocked :: proc(grid: ^NavGrid, cell: [2]int) -> bool

Whether a cell is blocked (outside the grid counts as blocked).

procedure. Source: navigation.odin:277

Section titled “NavGrid_FindPath”
NavGrid_FindPath :: proc(grid: ^NavGrid, from, to: [2]f32, allocator := context.allocator) -> ([][2]f32, bool)

Finds a path over a grid: A* over its cells, then straightened where the way is clear. A target in a blocked cell is moved to the nearest open cell.

Inputs

  • grid: The grid
  • from, to: World positions
  • allocator: For the points

Returns

  • The points from the start (excluded) to the target (included), and false when there’s no path (the start or target outside the grid, or walled off)

procedure. Source: navigation.odin:295

Section titled “NavGrid_LineClear”
NavGrid_LineClear :: proc(grid: ^NavGrid, a, b: [2]f32) -> bool

Whether a straight line between two world points crosses only open cells.

procedure. Source: navigation.odin:411

Section titled “NavRegion_FindPath”
NavRegion_FindPath :: proc(region: ^NavRegion, from, to: [2]f32, allocator := context.allocator) -> ([][2]f32, bool)

A path in a region (see NavGrid_FindPath); its grid is built first if it isn’t yet.

Inputs

  • region: The region
  • from, to: World positions
  • allocator: For the points

Returns

  • The points, and whether there’s a path

procedure. Source: navigation.odin:434

Scene_FindNavRegion

Section titled “Scene_FindNavRegion”
Scene_FindNavRegion :: proc(scene: ^Scene, at: [2]f32) -> ^NavRegion

The region a world point is in (the first that has it).

Inputs

  • scene: The scene
  • at: A world position

Returns

  • The region, or nil

procedure. Source: navigation.odin:449

Section titled “NavAgent_SetTarget”
NavAgent_SetTarget :: proc(agent: ^NavAgent, target: [2]f32) -> bool

Sends an agent somewhere: a path is found in the region it’s in, and it follows it.

Inputs

  • agent: The agent
  • target: A world position

Returns

  • false when there’s no path (onPathFailed fires too)

procedure. Source: navigation.odin:469

Section titled “NavAgent_Stop”
NavAgent_Stop :: proc(agent: ^NavAgent)

Stops an agent where it is.

procedure. Source: navigation.odin:493

Constants and variables

Section titled “Constants and variables”

DEFAULT_NAV_SETTINGS

Section titled “DEFAULT_NAV_SETTINGS”
DEFAULT_NAV_SETTINGS :: NavSettings{cellSize = 16, agentRadius = 8, diagonal = true, speed = 100, arriveDistance = 4, avoidRadius = 12, autoMove = true}

Navigation settings when the scene file sets none

constant. Source: navigation.odin:70

Crossfire is MIT licensed. Found a mistake? Report it.