DEMI-PROJECT-PACKAGE
ž      {"files":[{"hash":"sha256:3065937c7cb4e2018eb4daa1569505b0ad7d2f1ec84c4c4e7a67fd7b8c3de103","path":"LICENSE","size":1492},{"hash":"sha256:8a7ec070d848238506e64ac32d4872fab2995e88c343704e004bd309a95eacd7","path":"README.md","size":3816},{"hash":"sha256:40400c33d6d75f4e00dcfba9b3fcb1d0ff54981fd5aeebfde24cc0c6cad4d9bc","path":"scripts/demi/navigation/ground.lua","size":10473},{"hash":"sha256:1f5b3166af3d35013cbdbb327765cbba3d2340c1fa0d165a99891cd463b2d0ff","path":"scripts/demi/navigation/ground_route.lua","size":3838},{"hash":"sha256:1ea51479e6c22ce5b762ba3b5852d4c67ef047b25bac9f61c9cb6b3bc60cd5b0","path":"tests/ground_test.lua","size":8231}],"format_version":1,"manifest":{"dependencies":{},"engine":"^0.1.0","exported_events":[],"files":["LICENSE","README.md","scripts/demi/navigation/ground.lua","scripts/demi/navigation/ground_route.lua","tests/ground_test.lua"],"format_version":1,"name":"demi.navigation.ground","public_modules":["demi.navigation.ground"],"version":"0.3.1"},"package_type":"DemiProjectPackage"}BSD 3-Clause License

Copyright (c) 2026, JEAPI

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its
   contributors may be used to endorse or promote products derived from
   this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
# Ground Navigation

Terrain-backed navigation and collision-aware agents for lightweight 3D games.
Each surface owns an independent native A* grid through `demi.navigation`.
Movement uses `CharacterController3D`, including its collision, slope and gravity
rules. Game scripts choose jobs and priorities.

```lua
local Ground = require("demi.navigation.ground")
local Walker = {}
function Walker:on_start()
  self.surface = Ground.create({terrain="terrain", origin={0,0}, columns=64,
    rows=64, cell_size=2, agent_radius=0.4, ignored_entity=self.entity_id})
  self.agent = self.surface:agent(self.entity_id, {speed=3})
end
function Walker:on_fixed_update(dt)
  if self.surface:update(64) and not self.requested then
    self.requested = true
    self.accepted, self.diagnostic = self.agent:move_to({30,0,40}, 3)
  end
  self.status = self.agent:update(dt)
end
function Walker:on_destroy()
  if self.agent then self.agent:stop() end
end
return Walker
```

This single-actor example owns its survey. For several actors in the same area,
share one surface and create an agent for each actor. Issue move_to when a goal
changes, not every frame. It returns success and a diagnostic; unavailable actors
and unreachable routes fail explicitly. Update returns idle, moving, arrived,
paused, surveying, unreachable or blocked. No failure teleports the actor.


The actor needs Transform3D, a supported collider and CharacterController3D.
The grid maps its axes to world X/Z; returned path points are `{x,y,z}` arrays.
One terrain surface per grid is supported; this is heightfield ground navigation,
not a multilevel navmesh, aerial navigation or crowd-avoidance system.

`surface:set_obstacles(boxes)` updates clearance around dynamic footprints;
each box contains min_x, max_x, min_z and max_z. Agents replan after revision
changes. Call `surface:invalidate()` after terrain or static collision changes;
agents stop until the incremental survey completes. `agent:stop()` cancels a route.
Disabled agents pause without advancing their path. Stalled controllers report
blocked instead of pretending to arrive. Reissue move_to to retry.

Survey defaults: max_slope=30 degrees, sample_height=500, sample_depth=1000.
Survey cells include center and four clearance samples. Bounds and sampling
heights should match your world. Physics remains authoritative between samples.

Run isolated package policy tests with `demi package test packages/sources/demi.navigation.ground`. Native A* and character collision are covered separately by engine and runtime tests.

Version 0.2 starts routes at the actorā€™s exact position, including when it is
leaving a blocked start cell. Set `face_movement=true` in agent options to turn
the actor toward its movement without tilting it; the default preserves rotation.

Version 0.3 removes unnecessary grid waypoints by taking clear straight segments
through the route. Movement can use arbitrary angles; the grid remains an
internal search and terrain-survey representation. Shortcut checks traverse every
touched survey cell (including corner neighbours) and test footprint boxes expanded
by agent radius. They use cached data and run when planning, not every frame.
Intermediate corners are reached precisely, without a frame of stale velocity.
With a zero goal radius, the endpoint is the requested world position rather than
a cell centre; blocked exact endpoints return `PATH_GOAL_BLOCKED`.

This is conservative route simplification, not a navmesh or curved steering.
Turns remain at obstacle corners, and terrain sampling resolution still matters.
The character controller remains responsible for collision between samples.

When an actor starts inside footprint clearance, simplification keeps the original
first escape edge instead of taking a long shortcut through that footprint.
local Navigation = require("demi.navigation")
local Entity = require("demi.entity")
local Physics = require("demi.physics.query3d")
local Transform = require("demi.transform3d")
local Controller = require("demi.physics.character_controller3d")
local Route = require("demi.navigation.ground_route")
local Ground = {}
local function finite(value)
  return type(value) == "number" and value == value and math.abs(value) < math.huge
end

local function positive(value, name)
  assert(finite(value) and value > 0, name .. " must be positive and finite")
  return value
end
local Surface = {}
Surface.__index = Surface
local Agent = {}
Agent.__index = Agent

---A terrain-backed X/Z grid with independent ownership. Sampling is incremental.
function Ground.create(options)
  local self = setmetatable({}, Surface)
  self.terrain = assert(options.terrain, "terrain entity required")
  self.columns, self.rows = options.columns or 64, options.rows or 64
  self.cell_size = positive(options.cell_size or 2, "cell_size")
  assert(
    finite(self.columns) and self.columns % 1 == 0 and self.columns > 0,
    "columns must be a positive integer"
  )
  assert(
    finite(self.rows) and self.rows % 1 == 0 and self.rows > 0,
    "rows must be a positive integer"
  )
  self.radius = options.agent_radius or 0.4
  assert(finite(self.radius) and self.radius >= 0, "agent_radius must be nonnegative and finite")
  local slope = options.max_slope or 30
  assert(finite(slope) and slope >= 0 and slope < 90, "max_slope must be in [0,90)")
  self.min_normal = math.cos(math.rad(slope))
  self.sample_height = options.sample_height or 500
  self.sample_depth = positive(options.sample_depth or 1000, "sample_depth")
  assert(finite(self.sample_height), "sample_height must be finite")
  self.ignore = options.ignored_entity or ""
  local origin = options.origin or { 0, 0 }
  self.grid = assert(
    Navigation.create_grid(self.columns, self.rows, self.cell_size, origin[1], origin[2]),
    "invalid ground grid"
  )
  self.next_cell, self.heights, self.obstacles, self.revision = 0, {}, {}, 0
  return self
end

function Surface:sample(x, z)
  local hit = Physics.raycast(x, self.sample_height, z, 0, -1, 0, self.sample_depth, self.ignore)
  if not hit then
    return
  end
  local id = hit.entity_id
  while id and id ~= "" and id ~= self.terrain do
    id = Entity.parent(id)
  end
  if id == self.terrain then
    return hit.point[2], hit.normal[2]
  end
end

function Surface:blocked(x, z, y)
  if not y then
    return true
  end
  for _, box in ipairs(self.obstacles) do
    if
      x >= box.min_x - self.radius
      and x <= box.max_x + self.radius
      and z >= box.min_z - self.radius
      and z <= box.max_z + self.radius
    then
      return true
    end
  end
  return false
end

function Surface:update(budget)
  budget = budget or 64
  assert(finite(budget) and budget >= 0, "survey budget must be nonnegative and finite")
  for _ = 1, math.floor(budget) do
    if self:ready() then
      return true
    end
    local index = self.next_cell
    self.next_cell = index + 1
    local cx, cz = index % self.columns, math.floor(index / self.columns)
    local x, z = self.grid:cell_to_world(cx, cz)
    local y, normal = self:sample(x, z)
    local valid = y and normal >= self.min_normal
    if valid then
      for _, offset in ipairs({
        { -self.radius, 0 },
        { self.radius, 0 },
        { 0, -self.radius },
        {
          0,
          self.radius,
        },
      }) do
        local h, n = self:sample(x + offset[1], z + offset[2])
        if not h or n < self.min_normal then
          valid = false
          break
        end
      end
    end
    if valid then
      self.heights[index] = y
    end
    self.grid:set_blocked(cx, cz, self:blocked(x, z, self.heights[index]))
  end
  return self:ready()
end

function Surface:ready()
  return self.next_cell >= self.columns * self.rows
end

function Surface:set_obstacles(boxes)
  local copy = {}
  for _, box in ipairs(boxes) do
    assert(
      finite(box.min_x)
        and finite(box.max_x)
        and finite(box.min_z)
        and finite(box.max_z)
        and box.min_x <= box.max_x
        and box.min_z <= box.max_z,
      "invalid obstacle bounds"
    )
    copy[#copy + 1] = { min_x = box.min_x, max_x = box.max_x, min_z = box.min_z, max_z = box.max_z }
  end
  self.obstacles = copy
  self.revision = self.revision + 1
  for index = 0, self.next_cell - 1 do
    local cx, cz = index % self.columns, math.floor(index / self.columns)
    local x, z = self.grid:cell_to_world(cx, cz)
    self.grid:set_blocked(cx, cz, self:blocked(x, z, self.heights[index]))
  end
end
---Resurvey after terrain/static collision changes; agents stop until ready again.
function Surface:invalidate()
  self.next_cell, self.heights = 0, {}
  self.revision = self.revision + 1
end

function Surface:path(from, goal, radius)
  if not self:ready() then
    return {}, "SURFACE_NOT_READY"
  end
  local sx, sz = self.grid:world_to_cell(from[1], from[3])
  local gx, gz = self.grid:world_to_cell(goal[1], goal[3])
  if not sx or not gx then
    return {}, "PATH_OUT_OF_BOUNDS"
  end
  local candidates = {}
  local cells = math.ceil((radius or 0) / self.cell_size)
  for z = gz - cells, gz + cells do
    for x = gx - cells, gx + cells do
      local wx, wz = self.grid:cell_to_world(x, z)
      if wx and not self.grid:blocked(x, z) then
        local distance = (wx - goal[1]) ^ 2 + (wz - goal[3]) ^ 2
        if cells == 0 or distance <= (radius or 0) ^ 2 then
          candidates[#candidates + 1] = { x = x, z = z, d = distance }
        end
      end
    end
  end
  table.sort(candidates, function(a, b)
    if a.d == b.d then
      return a.z == b.z and a.x < b.x or a.z < b.z
    end
    return a.d < b.d
  end)
  for _, target in ipairs(candidates) do
    local path, diagnostic = self.grid:path(sx, sz, target.x, target.z, false)
    if #path > 0 then
      -- Start at the actual actor, not a possibly blocked cell centre. A route
      -- may leave a blocked start cell, but must never ask the actor to enter it.
      local points = { { from[1], from[2], from[3] } }
      for i = 2, #path do
        local cell = path[i]
        points[#points + 1] =
          { cell.world_x, self.heights[cell[2] * self.columns + cell[1]], cell.world_y }
      end
      if #path == 1 then
        local cell = path[1]
        points[#points + 1] =
          { cell.world_x, self.heights[cell[2] * self.columns + cell[1]], cell.world_y }
      end
      if (radius or 0) == 0 then
        local y, normal = self:sample(goal[1], goal[3])
        local exact = { goal[1], y or 0, goal[3] }
        if not y or normal < self.min_normal or not Route.clear(self, points[#points], exact) then
          return {}, "PATH_GOAL_BLOCKED"
        end
        points[#points + 1] = exact
      end
      return Route.simplify(self, points), diagnostic
    end
  end
  return {}, "PATH_UNREACHABLE"
end

function Surface:agent(entity, options)
  options = options or {}
  return setmetatable({
    surface = self,
    id = entity,
    speed = positive(options.speed or 3, "speed"),
    arrival = positive(options.arrival_distance or 0.15, "arrival_distance"),
    face_movement = options.face_movement == true,
    stuck_timeout = positive(options.stuck_timeout or 3, "stuck_timeout"),
    state = "idle",
    elapsed = 0,
  }, Agent)
end

function Agent:stop()
  Controller.set_velocity(self.id, 0, 0, 0)
  self.goal, self.path, self.state = nil, nil, "idle"
end

function Agent:move_to(goal, radius)
  assert(
    type(goal) == "table" and finite(goal[1]) and finite(goal[2]) and finite(goal[3]),
    "goal must be a finite Vec3"
  )
  radius = radius or 0
  assert(finite(radius) and radius >= 0, "goal radius must be nonnegative and finite")
  self.goal, self.radius = { goal[1], goal[2], goal[3] }, radius
  local position = Entity.world_position(self.id)
  if not position then
    self.state, self.diagnostic = "unreachable", "AGENT_UNAVAILABLE"
    return false, self.diagnostic
  end
  self.path, self.diagnostic = self.surface:path(position, self.goal, self.radius)
  self.index, self.revision, self.elapsed = 1, self.surface.revision, 0
  self.last_position = Entity.world_position(self.id)
  self.state = #self.path > 0 and "moving" or "unreachable"
  if self.state == "unreachable" then
    Controller.set_velocity(self.id, 0, 0, 0)
  end
  return self.state == "moving", self.diagnostic
end

function Agent:update(dt)
  assert(finite(dt) and dt >= 0, "dt must be nonnegative and finite")
  if not Entity.exists(self.id) or not Entity.is_enabled(self.id) then
    Controller.set_velocity(self.id, 0, 0, 0)
    return "paused"
  end
  if not self.goal then
    return self.state
  end
  if not self.surface:ready() then
    Controller.set_velocity(self.id, 0, 0, 0)
    return "surveying"
  end
  if self.revision ~= self.surface.revision then
    self:move_to(self.goal, self.radius)
  end
  if self.state ~= "moving" then
    return self.state
  end
  local position = Entity.world_position(self.id)
  local target, dx, dz, distance
  while true do
    target = self.path[self.index]
    dx, dz = target[1] - position[1], target[3] - position[3]
    distance = math.sqrt(dx * dx + dz * dz)
    -- Keep a millimetre of solver tolerance at intermediate corners. Requiring
    -- exact equality can strand a controller on its resting contact offset.
    -- Consume reached points immediately instead of retaining the old velocity.
    local tolerance = self.index == #self.path and self.arrival or 0.001
    if distance > tolerance then
      break
    end
    self.index = self.index + 1
    if self.index > #self.path then
      self.state = "arrived"
      Controller.set_velocity(self.id, 0, 0, 0)
      return self.state
    end
  end
  local speed = math.min(self.speed, distance / math.max(dt, 0.001))
  if self.face_movement then
    Transform.look_at(self.id, position[1] + dx, position[2], position[3] + dz)
  end
  Controller.set_velocity(self.id, dx / distance * speed, 0, dz / distance * speed)
  self.elapsed = self.elapsed + dt
  if self.elapsed >= self.stuck_timeout then
    local old = self.last_position
    if (position[1] - old[1]) ^ 2 + (position[3] - old[3]) ^ 2 < 0.04 then
      self.state, self.diagnostic = "blocked", "AGENT_BLOCKED"
      Controller.set_velocity(self.id, 0, 0, 0)
    end
    self.last_position, self.elapsed = position, 0
  end
  return self.state
end

return Ground
-- Route geometry stays independent of physics sampling and agent movement.
local Route = {}

local function intersects(ax, az, bx, bz, min_x, max_x, min_z, max_z)
  local first, last = 0, 1
  for _, axis in ipairs({ { ax, bx - ax, min_x, max_x }, { az, bz - az, min_z, max_z } }) do
    local origin, delta, low, high = table.unpack(axis)
    if math.abs(delta) < 1e-12 then
      if origin < low or origin > high then
        return false
      end
    else
      local enter, leave = (low - origin) / delta, (high - origin) / delta
      if enter > leave then
        enter, leave = leave, enter
      end
      first, last = math.max(first, enter), math.min(last, leave)
      if first > last then
        return false
      end
    end
  end
  return true
end

function Route.clear(surface, from, target)
  local ax, az, bx, bz = from[1], from[3], target[1], target[3]
  local grid, size = surface.grid, surface.cell_size
  local sx, sz = grid:world_to_cell(ax, az)
  local gx, gz = grid:world_to_cell(bx, bz)
  if not sx or not gx then
    return false
  end
  for _, box in ipairs(surface.obstacles) do
    local r = surface.radius
    local min_x, max_x = box.min_x - r, box.max_x + r
    local min_z, max_z = box.min_z - r, box.max_z + r
    -- If the actor starts inside clearance, keep the original first edge.
    -- A long shortcut must not use that exception to cross the whole building.
    if intersects(ax, az, bx, bz, min_x, max_x, min_z, max_z) then
      return false
    end
  end

  -- Traverse every touched cell, including both neighbours at grid corners.
  -- This uses cached survey data; shortcut checks do not cast physics rays.
  local cx, cz = sx, sz
  local dx, dz = bx - ax, bz - az
  local step_x, step_z = dx >= 0 and 1 or -1, dz >= 0 and 1 or -1
  local wx, wz = grid:cell_to_world(cx, cz)
  local next_x = dx == 0 and math.huge or (wx + step_x * size / 2 - ax) / dx
  local next_z = dz == 0 and math.huge or (wz + step_z * size / 2 - az) / dz
  local delta_x = dx == 0 and math.huge or size / math.abs(dx)
  local delta_z = dz == 0 and math.huge or size / math.abs(dz)
  local function blocked(x, z)
    return not (x == sx and z == sz) and grid:blocked(x, z)
  end
  local along_x_edge = dx == 0 and math.abs(ax - (wx - size / 2)) < 1e-9
  local along_z_edge = dz == 0 and math.abs(az - (wz - size / 2)) < 1e-9
  while true do
    if
      blocked(cx, cz)
      or (along_x_edge and blocked(cx - 1, cz))
      or (along_z_edge and blocked(cx, cz - 1))
    then
      return false
    end
    if cx == gx and cz == gz then
      return true
    end
    if math.min(next_x, next_z) >= 1 - 1e-12 then
      local cross_x, cross_z = next_x <= 1 + 1e-12, next_z <= 1 + 1e-12
      if cross_x and blocked(cx + step_x, cz) then
        return false
      end
      if cross_z and blocked(cx, cz + step_z) then
        return false
      end
      if cross_x and cross_z and blocked(cx + step_x, cz + step_z) then
        return false
      end
      return not blocked(gx, gz)
    end
    if math.abs(next_x - next_z) < 1e-9 then
      if blocked(cx + step_x, cz) or blocked(cx, cz + step_z) then
        return false
      end
      cx, cz = cx + step_x, cz + step_z
      next_x, next_z = next_x + delta_x, next_z + delta_z
    elseif next_x < next_z then
      cx, next_x = cx + step_x, next_x + delta_x
    else
      cz, next_z = cz + step_z, next_z + delta_z
    end
  end
end

function Route.simplify(surface, points)
  local result, index = { points[1] }, 1
  while index < #points do
    local next_index = index + 1
    for candidate = #points, index + 2, -1 do
      if Route.clear(surface, points[index], points[candidate]) then
        next_index = candidate
        break
      end
    end
    result[#result + 1], index = points[next_index], next_index
  end
  return result
end

return Route
local Test = require("demi.test")
local facing
package.preload["demi.transform3d"] = function()
  return {
    look_at = function(_, x, y, z)
      facing = { x, y, z }
      return true
    end,
  }
end
local samples, position, enabled, velocity, path_calls = 0, { 0.5, 1, 0.5 }, true, nil, 0
package.preload["demi.entity"] = function()
  return {
    exists = function()
      return position ~= nil
    end,
    is_enabled = function()
      return enabled
    end,
    world_position = function()
      return position
    end,
    parent = function()
      return "terrain"
    end,
  }
end
package.preload["demi.physics.query3d"] = function()
  return {
    raycast = function(x, _, z)
      samples = samples + 1
      return { entity_id = "surface", point = { x, 0, z }, normal = { 0, 1, 0 } }
    end,
  }
end
package.preload["demi.physics.character_controller3d"] = function()
  return {
    set_velocity = function(_, x, y, z)
      velocity = { x, y, z }
      return true
    end,
  }
end
package.preload["demi.navigation"] = function()
  return {
    create_grid = function(w, h, size)
      local grid = { flags = {} }
      function grid:set_blocked(x, z, blocked)
        self.flags[z * w + x] = blocked
      end
      function grid:blocked(x, z)
        return x < 0 or z < 0 or x >= w or z >= h or self.flags[z * w + x]
      end
      function grid:cell_to_world(x, z)
        if x >= 0 and z >= 0 and x < w and z < h then
          return (x + 0.5) * size, (z + 0.5) * size
        end
      end
      function grid:world_to_cell(x, z)
        return math.floor(x / size), math.floor(z / size)
      end
      function grid:path(sx, sz, gx, gz)
        path_calls = path_calls + 1
        if self:blocked(gx, gz) then
          return {}, "PATH_GOAL_BLOCKED"
        end
        return {
          { sx, sz, world_x = (sx + 0.5) * size, world_y = (sz + 0.5) * size },
          { gx, gz, world_x = (gx + 0.5) * size, world_y = (gz + 0.5) * size },
        },
          "OK"
      end
      return grid
    end,
  }
end
local Ground = require("demi.navigation.ground")
local function surface()
  return Ground.create({ terrain = "terrain", columns = 4, rows = 4, cell_size = 1 })
end
Test.case("survey work is bounded and obstacle inputs are copied", function()
  samples = 0
  local nav = surface()
  local path, reason = nav:path({ 0.5, 0, 0.5 }, { 3.5, 0, 0.5 })
  Test.equal(#path, 0)
  Test.equal(reason, "SURFACE_NOT_READY")
  Test.equal(nav:update(2), false)
  Test.equal(samples, 10)
  Test.truthy(nav:update(14))
  local boxes = { { min_x = 1, max_x = 2, min_z = 1, max_z = 2 } }
  nav:set_obstacles(boxes)
  boxes[1].min_x = 99
  Test.equal(nav.obstacles[1].min_x, 1)
  Test.truthy(nav.grid:blocked(1, 1))
  nav:set_obstacles({})
  Test.equal(nav.grid:blocked(1, 1), false)
end)
Test.case("stalled actors report blocked rather than arriving", function()
  position, enabled = { 0.5, 1, 0.5 }, true
  local nav = surface()
  nav:update(16)
  local agent = nav:agent("worker", { stuck_timeout = 1 })
  Test.truthy(agent:move_to({ 3.5, 0, 0.5 }))
  for _ = 1, 20 do
    agent:update(0.1)
  end
  Test.equal(agent.state, "blocked")
  Test.equal(velocity[1], 0)
end)
Test.case("pause and resurvey halt motion; obstacle changes replan", function()
  local nav = surface()
  nav:update(16)
  local agent = nav:agent("worker")
  Test.truthy(agent:move_to({ 3.5, 0, 0.5 }))
  agent:update(0.1)
  enabled = false
  Test.equal(agent:update(0.1), "paused")
  Test.equal(velocity[1], 0)
  enabled = true
  local before = path_calls
  nav:set_obstacles({})
  agent:update(0.1)
  Test.truthy(path_calls > before)
  nav:invalidate()
  Test.equal(agent:update(0.1), "surveying")
  Test.equal(velocity[1], 0)
  agent:stop()
  Test.equal(agent.state, "idle")
end)
Test.case("invalid settings and missing actors have explicit failures", function()
  Test.equal(
    pcall(function()
      Ground.create({ terrain = "terrain", agent_radius = -1 })
    end),
    false
  )
  local nav = surface()
  nav:update(16)
  local agent = nav:agent("missing")
  position = nil
  local ok, reason = agent:move_to({ 1, 0, 1 })
  Test.equal(ok, false)
  Test.equal(reason, "AGENT_UNAVAILABLE")
  position = { 0.5, 1, 0.5 }
end)

Test.case("routes start at the actor and facing is opt in", function()
  local nav = surface()
  nav:update(16)
  position, enabled = { 0.8, 1, 0.8 }, true
  nav.heights[0] = nil
  nav.grid:set_blocked(0, 0, true)
  local points = nav:path(position, { 3.5, 0, 0.5 })
  Test.equal(points[1][1], 0.8)
  Test.equal(points[1][2], 1)
  Test.equal(points[1][3], 0.8)
  local agent = nav:agent("worker", { face_movement = true })
  Test.truthy(agent:move_to({ 3.5, 0, 0.5 }))
  agent:update(0.1)
  agent:update(0.1)
  Test.truthy(facing)
  Test.equal(facing[2], position[2])
end)

local Route = require("demi.navigation.ground_route")
Test.case("open ground routes are direct and preserve off-grid goals", function()
  local nav = surface()
  nav:update(16)
  local route = Route.simplify(
    nav,
    { { 0.5, 0, 0.5 }, { 1.5, 0, 0.5 }, { 2.5, 0, 0.5 }, { 2.5, 0, 1.5 }, { 2.5, 0, 2.5 } }
  )
  Test.equal(#route, 2)
  local points = nav:path({ 0.7, 0, 0.8 }, { 2.8, 0, 2.2 })
  Test.equal(#points, 2)
  Test.equal(points[2][1], 2.8)
  Test.equal(points[2][3], 2.2)
end)
Test.case("shortcuts retain detours and cannot cross blocked corners", function()
  local nav = surface()
  nav:update(16)
  nav.grid:set_blocked(1, 1, true)
  Test.equal(Route.clear(nav, { 0.5, 0, 0.5 }, { 2.5, 0, 2.5 }), false)
  Test.equal(Route.clear(nav, { 0.5, 0, 1.5 }, { 1.5, 0, 2.5 }), false)
  local route = Route.simplify(
    nav,
    { { 0.5, 0, 1.5 }, { 0.5, 0, 2.5 }, { 1.5, 0, 2.5 }, { 2.5, 0, 2.5 }, { 2.5, 0, 1.5 } }
  )
  Test.truthy(#route > 2)
  for i = 2, #route do
    Test.truthy(Route.clear(nav, route[i - 1], route[i]))
  end
  Test.equal(Route.clear(nav, { 1, 0, 0.5 }, { 1, 0, 2.5 }), false)
end)
Test.case("footprint clearance catches obstacles between survey centres", function()
  local nav = surface()
  nav:update(16)
  nav.radius = 0.1
  nav:set_obstacles({ { min_x = 1.9, max_x = 2.1, min_z = 0.9, max_z = 1.1 } })
  Test.equal(nav.grid:blocked(1, 0), false)
  Test.equal(Route.clear(nav, { 0.5, 0, 0.85 }, { 3.5, 0, 0.85 }), false)
  Test.truthy(Route.clear(nav, { 0.5, 0, 0.5 }, { 3.5, 0, 0.5 }))
end)
Test.case("agents move at arbitrary angles without a frame of stale velocity", function()
  position, enabled = { 0.7, 1, 0.8 }, true
  local nav = surface()
  nav:update(16)
  local agent = nav:agent("worker")
  Test.truthy(agent:move_to({ 2.8, 0, 2.2 }))
  agent:update(0.1)
  Test.truthy(velocity[1] > 0 and velocity[3] > 0)
  Test.truthy(math.abs(velocity[1] / velocity[3] - 1.5) < 0.0001)
  position = { 2.8, 1, 2.2 }
  Test.equal(agent:update(0.1), "arrived")
  Test.equal(velocity[1], 0)
end)

Test.case("segments ending on grid boundaries work in both directions", function()
  local nav = surface()
  nav:update(16)
  for _, pair in ipairs({
    { { 0.5, 0, 2.5 }, { 2, 0, 1 } },
    { { 2.5, 0, 0.5 }, { 1, 0, 2 } },
    { { 0.5, 0, 0.5 }, { 2, 0, 2 } },
    { { 2.5, 0, 2.5 }, { 1, 0, 1 } },
  }) do
    Test.truthy(Route.clear(nav, pair[1], pair[2]))
    Test.truthy(Route.clear(nav, pair[2], pair[1]))
  end
end)

Test.case("controller contact noise does not strand intermediate waypoints", function()
  local nav = surface()
  nav:update(16)
  position, enabled = { 0.5, 1, 0.5 }, true
  local agent = nav:agent("worker")
  Test.truthy(agent:move_to({ 3.5, 0, 2.5 }))
  agent.path = { { 0.5, 0, 0.5 }, { 1.5, 0, 0.5 }, { 3.5, 0, 2.5 } }
  agent.index = 2
  position = { 1.4996, 1, 0.5002 }
  agent:update(0.1)
  Test.equal(agent.index, 3)
  Test.truthy(velocity[1] > 0 and velocity[3] > 0)
end)

Test.case("escaping a blocked start cannot shortcut through a footprint", function()
  local nav = surface()
  nav:update(16)
  nav:set_obstacles({ { min_x = 1, max_x = 2, min_z = 1, max_z = 2 } })
  Test.equal(Route.clear(nav, { 0.8, 0, 1.5 }, { 3.5, 0, 1.5 }), false)
  local points =
    { { 0.8, 0, 1.5 }, { 0.5, 0, 1.5 }, { 0.5, 0, 2.5 }, { 2.5, 0, 2.5 }, { 3.5, 0, 1.5 } }
  local route = Route.simplify(nav, points)
  Test.equal(route[2][1], 0.5)
  Test.equal(route[2][3], 1.5)
end)