#navigation #system #pathfinding #avoidance

landmass

A navigation system for video game characters to walk around levels

8 unstable releases (3 breaking)

0.4.0 Feb 18, 2024
0.3.3 Jan 13, 2024
0.2.1 Jan 7, 2024
0.2.0 Nov 15, 2023
0.1.1 Jun 22, 2023

#164 in Game dev

Download history 8/week @ 2023-11-05 74/week @ 2023-11-12 13/week @ 2023-11-19 19/week @ 2023-11-26 14/week @ 2023-12-03 44/week @ 2023-12-10 12/week @ 2023-12-17 15/week @ 2023-12-24 4/week @ 2023-12-31 156/week @ 2024-01-07 48/week @ 2024-01-14 3/week @ 2024-01-21 24/week @ 2024-01-28 4/week @ 2024-02-04 40/week @ 2024-02-11 407/week @ 2024-02-18

475 downloads per month
Used in bevy_landmass

MIT/Apache

175KB
5K SLoC

landmass

A Rust crate to provide a navigation system for video game characters to walk around levels.

What is a navigation system?

A navigation system is essentially the collection of tools needed for robust agent movement in video games. This generally involves 4 things:

  • Path finding (e.g. A-star)
  • Path simplification (e.g. SSFA)
  • Steering (e.g. boids)
  • Local collision avoidance

In addition, managing agents and the navigation meshes they walk on can be cumbersome, so a navigation system ideally will handle that for you.

Generally it is difficult to find a full, free system to handle all of these for you, and the goal is for landmass to work relatively easily with other languages so it can be used anywhere.

Overview

landmass has three major components: Archipelagos, Islands and Agents. An Archipelago is composed of several Islands, as well as the Agents that travel across those Islands. Each Island holds a single navigation mesh. Each game character (controlled by AI) should correspond to one Agent. To start using landmass:

  1. Create an Archipelago.
  2. Create an Island.
  3. Assign a ValidNavigationMesh to the Island.
  4. Add Agents to the Archipelago.

Each frame of the game:

  1. Set the position and velocity of each game character to its corresponding Agent.
  2. Call update on the Archipelago.
  3. Use the desired move from each Agent to inform the corresponding game character where it should move.

Note: landmass intentionally does not update the Agents position itself. Generally, characters are moved using some other method (like a physics simulation) rather than just moving the character, so moving the Agent would be confusing.

Example

use glam::Vec3;
use landmass::*;
use std::sync::Arc;

let mut archipelago = Archipelago::new();

let nav_mesh = NavigationMesh {
  mesh_bounds: None,
  vertices: vec![
    Vec3::new(0.0, 0.0, 0.0),
    Vec3::new(15.0, 0.0, 0.0),
    Vec3::new(15.0, 0.0, 15.0),
    Vec3::new(0.0, 0.0, 15.0),
  ],
  polygons: vec![vec![0, 1, 2, 3]],
};

let valid_nav_mesh = Arc::new(
  nav_mesh.validate().expect("Validation succeeds")
);

let island_id = archipelago.add_island();
archipelago
  .get_island_mut(island_id)
  .set_nav_mesh(
    Transform { translation: Vec3::ZERO, rotation: 0.0 },
    valid_nav_mesh,
  );

let agent_1 = archipelago.add_agent({
  let mut agent = Agent::create(
    /* position= */ Vec3::new(1.0, 0.0, 1.0),
    /* velocity= */ Vec3::ZERO,
    /* radius= */ 1.0,
    /* max_velocity= */ 1.0,
  );
  agent.current_target = Some(Vec3::new(11.0, 0.0, 1.1));
  agent.target_reached_condition = TargetReachedCondition::Distance(0.01);
  agent
});
let agent_2 = archipelago.add_agent({
  let mut agent = Agent::create(
    /* position= */ Vec3::new(11.0, 0.0, 1.1),
    /* velocity= */ Vec3::ZERO,
    /* radius= */ 1.0,
    /* max_velocity= */ 1.0,
  );
  agent.current_target = Some(Vec3::new(1.0, 0.0, 1.0));
  agent.target_reached_condition = TargetReachedCondition::Distance(0.01);
  agent
});

for i in 0..200 {
  let delta_time = 1.0 / 10.0;
  archipelago.update(delta_time);

  for agent_id in archipelago.get_agent_ids().collect::<Vec<_>>() {
    let agent = archipelago.get_agent_mut(agent_id);
    agent.velocity = agent.get_desired_velocity();
    agent.position += agent.velocity * delta_time;
  }
}

assert!(archipelago
  .get_agent(agent_1)
  .position
  .abs_diff_eq(Vec3::new(11.0, 0.0, 1.1), 0.1));
assert!(archipelago
  .get_agent(agent_2)
  .position
  .abs_diff_eq(Vec3::new(1.0, 0.0, 1.0), 0.1));

License

License under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~4MB
~112K SLoC