bevyflowfieldtiles_plugin

Inspired by the work of Elijah Emerson and with inspiration from leifnode and jdxdev this is an attempt to implement the data structures and logic required to generate a Flowfield representation of a world which can be used to pathfind movable actors.

| bevy | bevyflowfieldtiles_plugin | |------|-----------------------------| | commit | main | | 0.11 | 0.2 | | 0.11 | 0.1 |

Table of Contents

1. Intro
2. Useful Definitions
3. Design/Process
4. Usage
5. Features
6. Performance
7. License

Intro

Pathfinding in games can take different forms and those forms have certain benefits aligned with the type of game they are being applied to. Generally people run across:

• Way-point Graph - points in space linked together, very strict structure, an actor will move from one way-point to another. Great for games played on a small grid where movement needs to be restricted to precise lines, will be cumbersome when multiple actors are sharing a path - particularly when actors have some kind of collision system in place
• NavMesh - a walkable surface generated from the topology of meshes in a game world defining a valid area of movement. It allows for a range of dynamic movement within the confines of the mesh and is a natural evolution of the Way-point Graph
• FlowField Tiles - a means of handling crowd and flocking behaviour by generating a flow field (vector field) describing how an actor flows across a world. A large number of actors can flow in unison to an endpoint while sharing the same pathing data structure - saving compute resources and time

For larger and larger environemnts with an increasing number of pathing actors it may be beneficial to adopt a FlowField based approach due to the data sharing and formation/group like movement it promotes. FlowField Tiles are complex, it's effectively akin to fluid mechanics, so this is an attempt to bring an agnostic implementation to the Bevy game engine. My motivation for this is that I recently implemented a Way-point Graph for a prototype. In order to provide 'ok' actor movement it had to be made from 16 million data points. To prevent an actor from occasionally zig-zagging across the game world the granularity had to be boosted to 80 million data points to create a 'lifelike' impression of movement. That was just silly so I began looking into the history of pathfinding whereupon I stumbled across FlowField Tiles and decided to try and implement it with my favourite langauge and engine.

Useful Definitions

• Sector - a slice of a game world composed of three 2D arrays called fields (CostField, IntegrationField and FlowField). A game world is effectively represented by a number of Sectors
• CostField - a 2D array describing how difficult it is to path through each cell of the array. It is always present in system memory
• Cost - how difficult/expensive it is to path somewhere, you could also call it weight, each cell of CostField has one of these
• Portal - a navigatable point which links one Sector to another to enable movement from one side of the world to another
• IntegrationField - a 2D array which uses the CostField to determine a cumulative cost of reaching the goal/endpoint (where you want to path to). This is an ephemeral field - it exists when required to calculate a FlowField
• FlowField - a 2D array built from the IntegrationField which decribes how an actor should move (flow) across the world
• FlowField Cache - a means of storing FlowFields allowing multiple actors to use and reuse them
• Ordinal - a direction based on traditional compass ordinals: N, NE, E, SE, S, SW, W, NW. Used for discovery of Sectors/field cells at various points within the algorithm
• Field cell - an element of a 2D array
• Goal - the target field cell an actor needs to path to
• Portal goal - a target point within a sector that allows an actor to transition to another sector, thus bringing it closer towards/to the goal

Design/Process

Usage

Update your Cargo.toml and add any features you require, to actually interface with calculated fields you should enable either 2d or 3d depending on the coordinate system of your world:

toml [dependencies] bevy_flowfield_tiles_plugin = { version = "2", features = ["3d"] }

Default

Add the plugin to your app:

```rust use bevyflowfieldtiles_plugin::prelude::*;

fn main() { App::new() // ... snip .add_plugins(FlowFieldTilesPlugin) // ... snip } ```

Custom System Setup and Constraints

In your own simulation you may well be using custom schedules or stages to control logic execution, the plugin as is sets all the logic to run as part of the Update phase of the main Bevy schedule. To implement the logic into your own scheduling disect the contents of plugin/mod.rs - note that certain systems have been chained together and they must remain chained for accurate paths to be computed.

Initialising Data

Next it' time to spawn the bundle entity configured to your world size (looking through the examples will give some pointers on this too).

The size and resolution of the world need to be known at initialisation and three values are required:

• map_length - in 2d this refers to the pixel x size of the world. In 3d this is simply the x size
• map_depth - in 2d this refers to the pixel y size of the world. In 3d this is the z size
• sector_resolution - determines the numder of sectors by taking each size and dividing them by this value. In 2d this is basically the pixel length of each sector side and likewise for 3d it's the length of each sector side using whatever unit of measurement you've defined (for ease of use I go with a unit of x is 1 meter and a unit of z is one meter)
  • 2d: a world of pixel size (1920, 1080) with a resolution of 40 will produce 48x27 sectors. Another way of looking at this could be based on the idea of having a world made of sprites where each sprite corresponds to where a FieldCell would be. If these regular sized sprites have a pixel length and height of 64 and your world is made from a 20x20 grid of these sprites then you can calcualte what the size is. map_length would be your sprite length multiplied by the number sprites along the x axis of the world, i.e 64 * 20 = 1280. map_depth follows a likewise calculation 64 * 20 = 1280. As for resolution it will depend on how granular you want, in this example case a 10x10 CostField is supposed to overlay an exact number of sprites so we use the sprite size to find the resolution 64 * 10 = 640.
  • 3d: a world of size (780x440) with resolution 10 produces 78x44 sectors. Given that fields are 10x10 arrays this translates to a single FieldCell representing a 1x1 unit area

Within a system somewhere you can spawn the Bundle:

rust fn my_system(mut cmds: Commands) { let map_length = 1920; let map_depth = 1920; let sector_resolution = 640; cmds.spawn(FlowfieldTilesBundle::new(map_length, map_depth, sector_resolution)); }

Note that this will initialise all the CostFields representing the world with cell values of 1. Meaning everywhere is pathable, in all likihood you'll then need to seed the fields with true values.

In 3d you could consider making a raycast to the centre of where each FieldCell would be and use something like the y position of the ray hit to determine if something is passable or not and then flip the value of that particular FieldCell (EventUpdateCostfieldsCell can be used to queue a cost change).

Most likely for 2d or more complex 3d scenarios you'll probably want to enable either the ron or csv feature which allows for creating a FlowfieldTilesBundle with inital CostFields from a .ron file or a collection of .csv, the examples showcase this in more detail.

Path Request

When it comes to interacting with the algorithm this is based on an event to be emitted when a movable actor needs a path:

rust struct EventPathRequest { /// The starting sector of the request source_sector: SectorID, /// The starting field cell of the starting sector source_field_cell: FieldCell, /// The sector to try and find a path to target_sector: SectorID, /// The field cell in the target sector to find a path to target_goal: FieldCell, }

Each parameter can be determined by querying the MapDimension component of the Bundle with the starting and end Transform::translation of actor position and target position.

Using some example components to track and label an Actor:

```rust /// Enables easy querying of Actor entities

[derive(Component)]

struct Actor; /// Consumed by an Actor steering pipeline to produce movement

[derive(Default, Component)]

struct Pathing { sourcesector: Option, sourcefieldcell: Option, targetsector: Option, targetgoal: Option, portalroute: Option

We can then do something like process mouse clicks to fire off PathRequest events (in 3d use the methods ending in xyz instead):

rust fn user_input( mouse_button_input: Res<Input<MouseButton>>, windows: Query<&Window, With<PrimaryWindow>>, camera_q: Query<(&Camera, &GlobalTransform)>, dimensions_q: Query<&MapDimensions>, mut actor_q: Query<(&Transform, &mut Pathing), With<Actor>>, mut event: EventWriter<EventPathRequest>, ) { if mouse_button_input.just_released(MouseButton::Right) { // get 2d world positionn of cursor let (camera, camera_transform) = camera_q.single(); let window = windows.single(); if let Some(world_position) = window .cursor_position() .and_then(|cursor| camera.viewport_to_world(camera_transform, cursor)) .map(|ray| ray.origin.truncate()) { // from 2d mouse position get the sector and field cell it is in // (if not outside the world) let map_dimensions = dimensions_q.get_single().unwrap(); if let Some((target_sector_id, goal_id)) = map_dimensions.get_sector_and_field_id_from_xy(world_position) { // from actor translation find what sector and cell it is in let (tform, mut pathing) = actor_q.get_single_mut().unwrap(); let (source_sector_id, source_field_cell) = map_dimensions .get_sector_and_field_id_from_xy(tform.translation.truncate()) .unwrap(); // send an event asking for a path to be generated event.send(EventPathRequest::new( source_sector_id, source_field_cell, target_sector_id, goal_id, )); // update the actor pathing (we get the route later once it is built) pathing.source_sector = Some(source_sector_id); pathing.source_field_cell = Some(source_field_cell); pathing.target_sector = Some(target_sector_id); pathing.target_goal = Some(goal_id); pathing.portal_route = None; } else { warn!("Cursor out of bounds"); } } } }

The actor can then query the RouteCache to begin following a high-level portal-to-portal route.

Note this example is very basic as it only handles a single actor, in an application you'd devise your own handling system:

rust fn actor_update_route(mut actor_q: Query<&mut Pathing, With<Actor>>, route_q: Query<&RouteCache>) { let mut pathing = actor_q.get_single_mut().unwrap(); // indicates whether the Actor has requested a route and doesn't have one assigned if pathing.target_goal.is_some() && pathing.portal_route.is_none() { // check the cache to see if the route has been built yet // routes are ID'ed by the starting and end sectors and the target field cell at the end let route_cache = route_q.get_single().unwrap(); if let Some(route) = route_cache.get_route( pathing.source_sector.unwrap(), pathing.target_sector.unwrap(), pathing.target_goal.unwrap(), ) { // it has! So set the Actors (high level) pathing route and you // can optionally implement a pre-cursor steering pipeline to walk // the route until the FlowFields are built too pathing.portal_route = Some(route.clone()); } } }

And once the FlowFields have been built they can query the FlowFieldCache instead and apply/queue up some kind of movement.

Note this example is very basic as it only handles a single actor, in an application you'd devise your own handling system:

```rust const ACTORSPEED: f32 = 64.0; fn actorsteering( mut actorq: Query<(&mut Transform, &mut Pathing), With>, flowcacheq: Query<(&FlowFieldCache, &MapDimensions)>, ) { let (mut tform, mut pathing) = actorq.getsinglemut().unwrap(); let (flowcache, mapdimensions) = flowcacheq.get_single().unwrap();

if pathing.target_goal.is_some() {
    // lookup the overarching route
    if let Some(route) = pathing.portal_route.as_mut() {
        // find the current actors postion in grid space
        let (curr_actor_sector, curr_actor_field_cell) = map_dimensions
            .get_sector_and_field_id_from_xy(tform.translation.truncate())
            .unwrap();
        // tirm the actor stored route as it makes progress
        // this ensures it doesn't use a previous goal from
        // a sector it has already been through when it needs
        // to pass through it again as part of a different
        // segment of the route
        if curr_actor_sector != route.first().unwrap().0 {
            route.remove(0);
        }
        // lookup the relevant sector-goal of this sector
        'routes: for (sector, goal) in route.iter() {
            if *sector == curr_actor_sector {
                // get the flow field
                if let Some(field) = flow_cache.get_field(*sector, *goal) {
                    // based on actor field cell find the directional vector it should move in
                    let cell_value = field.get_field_cell_value(curr_actor_field_cell);
                    let dir = get_2d_direction_unit_vector_from_bits(cell_value);
                    let velocity = dir * ACTOR_SPEED;
                    // move the actor based on the velocity
                    tform.translation += velocity.extend(0.0);
                }
                break 'routes;
            }
        }
    }
}

} ```

NB: generated FlowFields and Routes expire from their caches after 15 minutes, your steering pipeline may need to send a new EventPathRequest if one gets expired that an actor was relying on.

NB: when a CostField is modified Portals and the PortalGraph are updated and any Routes or FlowFields involving the modified Sector CostField are removed. This means an actor would need a way of knowing (implicitly or explicitly) that it needs to have a new Route made via an EventPathRequest. Hopefully auto regeneration of these routes can be solved to take the burden away from the actors, see issue.

Features

• serde - enables serlialisation on some data types
• ron - enables reading CostField from files. NB: fixed-size arrays in .ron are written as tuples
• csv - enables creating all of the CostFields by reading from a directory of csv files. Note that csv filenames need to follow the sector ID convention of column_row.csv, the underscore is important, and the path of the directory should be fully qualified and the files themselves should not contain any headers
• 2d - enables interface methods when working with Flowfields in a 2d world
• 3d - enables interface methods when working with FlowFields in a 3d world

Performance

Benchmarks are split into two categories:

• Data initialisation
  • initcostfields - measures the time it takes to initalise 100x100 sector CostFields
  • initportals - measures the time it takes to build Portals across 100x100 sectors
  • initportalgraph - measure the time it takes to build the PortalGraph for 100x100 sectors
  • initbundle - measure the total time it takes to have the FlowFieldTilesBundle ready
• Algorithm use - measures generating a set of FlowFields
  • calc_route - measures how long it takes to generate a route from one corner of a 100x100 sector layout to the opposite corner
  • calcflowopen - measure how long it takes to create a full set of FlowFields describing movement across uniform CostFields (cost = 1) from one corner to another
  • calcflowmaze - measures how long it takes to create a full set of FlowFields describing movement from one corner to another in a 100x100 sector world. The world is composed of vertical corridors meaning that the actor has to path up and down to eventually snake it's way to the goal

Currently the slowest area is generating the PortalGraph (7s on my machine) so this should be some initialisation that happens behind the scenes (like a loading screen or some such).

Depending on pathing complexity I've seen FlowField generation range from 5-90ms.

LICENSE

Dual license of MIT and Apache.