Introduction

bevy_northstar is a Hierarchical Pathfinding plugin for Bevy.

The crate provides:

Pathfinding Grids: A grid represents the walkable space used for the pathfinding alogrithsm and also precalculated chunks, entrances, and internal paths used for HPA*.
Pathfinding Systems: Bevy systems to handle pathfinding and collision for you. They are not required to use HPA* or other pathfinding algorithms.
Pathfinding Algorithms: You can call the pathfinding functions easily if you desire to handle the pathfinding logic in your own systems.
Debugging Tools: Easily visualize the grid and calculated paths to troubleshoot any tilemap and pathfinding issues.

The crate is currently designed for use with 2d and 3d grid based tilemaps. It is not dependent on any specific tilemap Bevy crate, though it's been designed for ease of use with bevy_ecs_tilemap and any related crates such as bevy_ecs_tiled and bevy_ecs_ldtk.

Quick Start

Add required dependencies to your Cargo.toml file:

[dependencies]
bevy = "0.16"
bevy_northstar = "0.2"

The basic requirements to use the crate are to spawn an entity with a Grid component, adjust the points, and then call Grid::build() so the chunk entrances and internal paths can be calculated.

To use the built-in pathfinding systems for the crate, insert the NorthstarPlugin specifying the Neighborhood to use.

The built-in neighborhoods are:

CardinalNeighborhood 4 directions allowing no diagonal movement.
CardinalNeighborhood3d 6 directions, including up and down, allowing no diagonal movement.
OrdinalNeighborhood 8 directions allowing for diagonal movement.
OrdinalNeighborhood3d 26 directions which includes the base ordinal movements and their up/down directions.

use bevy::prelude::*;
use bevy_northstar::prelude::*;

fn main() {
    App::new()
        .add_plugins(DefaultPlugins)
        // Add the Northstar Plugin with a selected neighborhood to use the built in pathfinding systems
        .add_plugins(NorthstarPlugin::<CardinalNeighborhood>::default())
        .add_systems(Startup, (startup, build_grid.after(startup)))
        .run();
}

fn startup(mut commands: Commands) {
    commands.spawn(Camera2d::default());

    // Spawn the grid used for pathfinding.
    commands.spawn(Grid<CardinalNeighborhood>::new(&GridSettings {
        width: 16,
        height: 16,
        chunk_size: 4,
        ..Default::default()
    }));
}

fn build_grid(grid: Single<&mut Grid<CardinalNeighborhood>>) {
    let mut grid = grid.into_inner();

    // Let's set the position 8, 8 to a wall
    grid.set_point(UVec3::new(8, 8, 0), Point::new(u32::MAX, true));

    info!("Building the grid...");

    // The grid needs to be built after setting the points.
    // Building the grid will calculate the chunk entrances and cache internal paths.
    grid.build();

    info!("Grid built successfully!");
}

Grid Generic Neighborhood Shorthand Types

The following shorthand types are also available for constructing and referencing a Grid::<N>.

CardinalGrid
CardinalGrid3d
OrdinalGrid
OrdinalGrid3d

Rather than Grid<CardinalNeighborhood>::new you can use CardinalGrid::new. Rather than querying Single<&mut Grid<CardinalNeighborhood>> you can query Single<&mut CardinalGrid>

Grid as a Component

Currently the plugin Pathfinding and Debug systems expect there to be only a single copy of the Grid component which means you can't currently use them if you want to support multiple grids in your project.

Normally it would make sense for this to be Bevy Resource but this decision was made so the plugin can update to support multiple grids in the future without making breaking API changes. If your project needs to support multiple pathfinding grids you can avoid using the NorthstarPlugin and NorthstarDebugPlugin and call the pathfinding functions directly on the Grid components for the time being.

Pathfinding With Built-In Systems

Pathfind and GridPos Components

To use the NorthstarPlugin pathfinding systems, insert a Pathfind and GridPos component.

The GridPos you will need to maintain as the current GridPos of the entity.


#![allow(unused)]
fn main() {
commands
    .spawn((
        Name::new("Player"),
        Pathfind {
            goal: UVec3::new(12, 12, 0),
            // you can set use_astar to true to bypass HPA* and use the traditional A* pathfinding algorithm if desired.
            use_astar: false,
        },
        GridPos(UVec3::new(1, 1, 0)),
        Blocking, // Insert the Blocking component if using collision and this entity should block.
    ));
}

There are also shortened functions for creating a new component using HPA* or A*


#![allow(unused)]
fn main() {
commands
    .spawn((
        Name::new("Player"),
        // new will default to HPA*.
        Pathfind::new(UVec3::new(12, 12, 0)),
        GridPos(UVec3::new(1, 1, 0)),
        Blocking, // Insert the Blocking component if using collision and this entity should block.
    ))
    .spawn((
        Name::new("Npc"),
        // new_astar will default to using A*.
        Pathfind::new_astar(UVec3::new(14, 14, 0)),
        GridPos(UVec3::new(2, 2, 0)),
        Blocking,
    ));
}

NextPos

The pathfind system looks for any entity with a Changed Pathfind component. It then runs the pathfinding algorithm and when a valid path is found it will insert the next position in the path as a NextPos component.

Consume the NextPos component by handling the movement and then remove the NextPos component. The next_position system will insert a new NextPos component in a later frame.

If collision is enabled the next_position system will also handle local collision avoidance and adjust the entities path if there is a blocking entity in the path in the avoidance_distance look ahead set in GridSettings.

Example movement system:


#![allow(unused)]
fn main() {
fn movement(
    mut commands: Commands,
    mut query: Query<(Entity, &mut GridPos, &NextPos)>,
) {
    for (entity, mut grid_pos, next_pos) in query.iter_mut() {
        // Set the entities GridPos to the NextPos UVec3.
        grid_pos.0 = next_pos.0;

        // Update the entities translation
        let translation = Vec3::new(
            next.0.x as f32 * 32.0, // Assuming tiles are 32x32
            next.0.y as f32 * 32.0,
            0.0
        );

        commands.entity(entity)
            .insert(Transform::from_translation(translation))
            .remove::<NextPos>();
    }
}
}

Pathfinding/Collision Marker Components

PathfindingFailed will inserted into the entity if a path is not found for the desired goal. You can create your own system to handle these failures, or let the built-in system attempt another pathfind for the goal on the next frame.

AvoidanceFailed will be inserted when collision is enabled and the entity is not able to path around a local blocking entity. The reroute_path system will attempt to find a new full HPA* path in an attempt to resolve the issue. You can handle these in your own custom system if desired.

RerouteFailed is added to the component when all attempts to resolve collision pathing issues have failed and means that there's no viable path at all to the entities desired goal. At this point you will need to handle the issue in your own custom system. Whether this is looking for a new goal or waiting a set amount of time before attempting pathing is up to you. Remove the RerouteFailed component from the entity when the entity is ready to attempt pathfinding again.


#![allow(unused)]
fn main() {
fn handle_reroute_failed(
    mut commands: Commands,
    mut query: Query<(Entity, &Pathfind), With<&RerouteFailed>>,
) {
    for (entity, pathfind) {
        let some_new_goal = UVec3::new(3, 30, 0); // Just some random new goal
        commands
            .entity(entity)
            .insert(Pathfind::new(some_new_goal)
            .remove::<RerouteFailed>();
    }
}
}

Manual Pathfinding

You don't need to use the pathfinding systems in the NorthstarPlugin in order to take advantage of this crate.

You can use both, or choose to not add the NorthstarPlugin and call the pathfinding functions completely manually.

If you don't use NorthstarPlugin you'll need to maintain your own BlockingMap or HashMap<UVec3, Entity> to pass to the pathfind function to provide it a list of blocked positions.

All of the pathfinding calls can be done on the Grid component.


#![allow(unused)]
fn main() {
fn manual_pathfind(
    mut commands: Commands,
    player: Single<(Entity, &GridPos, &MoveAction), With<Player>>,
    grid: Single<&CardinalGrid>,
    // If using collision you can use the BlockingMap resource to track blockers.
    blocking: Res<BlockingMap>,
) {
    let grid = grid.into_inner();
    let (player, grid_pos, move_action) = player.into_inner();

    let path = grid.pathfind(grid_pos.0, move_action.0, blocking, true);

    // Setting use_partial to true will allow the pathfinding to return a partial path if a complete path isn't found.

    // If you're not using collision you can pass an empty hashmap for the blocking map.
    let path = grid.pathfind(grid_pos.0, move_action.0, HashMap::new(), true);
}
}

Configuration Guide

GridSettings

width: Set this to tile count width of your tilemap.

height: The tile count height of your tilemap.

depth: Set to 1 for 2d tilemaps. If using a 3d tilemap set this to the height of your tilemap.

chunk_size: How many chunks to divide the tilemap into for HPA*. You'll want to find a good middle ground for this value depending on the size of your map. Larger chunks will assist with performance but provide less optimal paths, smaller chunks will give more optimal paths while hitting performance.

chunk_ordinal: If set to true, entrances will be added to the corners of chunks. This will make Grid::build take a significantly longer for large maps. In most cases this isn't necessary, but may be considered if your map is noisy with a lot of corners and you allow diagonal movement.

For example a map where wall corners meet often with a diagonal gap.


x	o
o	x

default_cost: This sets default cost for every point of the grid. Set to 0 or 1 for cheap movement. Set to 255 if you want the cost to be the highest.

default_wall: Set to true if you want every point in the grid to a be a wall by default.

collision: Set to true to allow the plugins pathfinding systems to ensure entities aren't pathing through each other.

avoidance_distance: The plugin uses local collision avoidance mainly for performance purposes. This sets the lookahead distance in grid points to check for any possible blocking entity in it's path.

Debugging the Grid component

The NorthstarDebugPlugin adds systems that can be enabled to draw gizmos to display the following:

Chunk grid: Grid outline of where the chunks are
Entrances: Calculated entrances at the boundaries of the chunks
Cached internal paths: Cached paths inside the chunk between its own entrances.
Points: Each individual point on the grid and it's walkable status
Paths: Draws the current calculated path components

First, add the NorthstarDebugPlugin to your app.

Second, you will likely want to set the transform offset to align it with your tilemap. In this example we'll be using components from bevy_ecs_tilemap to assist with determining our offset.

Third, insert the DebugMap component to the same entity as your Grid. Currently doing this won't change anything, but in the future the Plugin will likely use that to match up DebugMap with it's Grid when multiple Grids are supported.

use bevy::prelude::*;
use bevy_ecs_tilemap::prelude::*;
use bevy_northstar::prelude::*;

fn main() {
    App::new()
        .add_plugins(DefaultPlugins)
        .add_plugins(NorthstarPlugin::<CardinalNeighborhood>::default())
        // Adding the NorthstarDebugPlugin
        // You need to specify the neighborhood here as well
        .add_plugins(NorthstarDebugPlugin::<CardinalNeighborhood>::default())
        .add_systems(Startup, startup)
        .run();
}

fn startup(mut commands: Commands, asset_server: Res<AssetServer>) {
    // Query or create your bevy_ecs_tilemap TilemapAnchor
    let anchor = TilemapAnchor::Center;

    // Query or create your bevy_ecs_tilemap TilemapSize, TilemapGridSize, and TilemapTileSize. They are required for calculating the anchor offset.
    let tilemap_size = TilemapSize { x: 128, y: 128 };
    let tilemap_gridsize = TilemapGridSize { x: 8.0, y: 8.0 };
    let tilemap_tilesize = TilemapTileSize { x: 8.0, y: 8.0 };

    // Store our offset
    let offset = anchor.as_offset(
        &tilemap_size,
        &tilemap_gridsize,
        &tilemap_tilesize,
        &TilemapType::Square,
    );

    // Let's pretend we loaded a tilemap asset and stored it in a handle and now we're spawning the entity for it.
    let mut map_entity = commands.spawn(anchor);

    // Spawn an entity with the Grid and DebugMap component as a child of the map entity.
    map_entity.with_child(
        CardinalGrid::new(&GridSettings {
            width: 128,
            height: 128,
            ..default::Default()
        }),
        DebugMap {
            tile_width: 8,
            tile_height: 8,
            map_type: DebugMapType::Square,
            draw_chunks: true,
            draw_points: false,
            draw_entrances: true,
            draw_cached_paths: false,
        },
        // Use our offset calculated from the bevy_ecs_tilemap anchor to set the transform of the DebugMap entity.
        Transform::from_translation(offset.extend(0.0))
    )
}

Debugging Paths

Debugging calculated paths for an entity requires you to add a DebugPath component to the entity or entities of your choosing. This component allows you to selectively debug specific paths.

Drawing the path gizmos also requires the NorthstarDebugPlugin to add the gizmo drawing system.


#![allow(unused)]
fn main() {
use bevy::prelude::*;
use bevy_northstar::prelude::*;

commands.spawn((
    Name::new("Player"),
    DebugPath {
        // Width of the tilemap tiles
        tile_width: 8,
        // Height of the tilemap tiles
        tile_height: 8,
        // Map Type (Square or Isometric)
        map_type: DebugMapType::Square,
        // Color of the path gizmos
        color: Color::srgb(1.0, 0.0, 0.0)
    },
))
}

Stats

Enabling the stats feature on the crate will allow the NorthstarPlugin pathfinding systems to calculate how much time is spent per frame on pathfinding and collison.

[dependencies]
bevy_northstar = { version = "0.2.0", features = ["stats"]}

You can access the statistics from the Stats Resource.


#![allow(unused)]
fn main() {
fn print_stats(stats: Res<Stats>) {
    debug!("Collision Stats: {:?}", stats.collision);
    debug!("Pathfinding Stats: {:?}", stats.pathfinding);
}
}

bevy_northstar Documentation