Module pathfinding

bracket-pathfinding (in conjunction with bracket-algorithm-traits) provides pathfinding functionality. A-Star (A*) and Dijkstra are supported. It also

Macros

smallvec

Creates a SmallVec containing the arguments.

Structs

Bresenham

Line-drawing iterator

BresenhamCircle

An implementation of [Bresenham’s circle algorithm]. [Bresenham’s circle algorithm]: http://members.chello.at/~easyfilter/bresenham.html Derived from the line_drawing crate, but specialized to use BTerm’s types.

BresenhamCircleNoDiag

A version of the Bresenham circle that does not make diagonal jumps

BresenhamInclusive

New type over Bresenham which include the end points when iterated over.

Degrees

Convenience type: you can define an angle in Degrees and it is convertible to Radians (and vice versa)

DijkstraMap

Representation of a Dijkstra flow map. map is a vector of floats, having a size equal to size_x * size_y (one per tile). size_x and size_y are stored for overflow avoidance. max_depth is the maximum number of iterations this search shall support.

NavigationPath

Holds the result of an A-Star navigation query. destination is the index of the target tile. success is true if it reached the target, false otherwise. steps is a vector of each step towards the target, including the starting position.

Point

Helper struct defining a 2D point in space.

Point3

Helper struct defining a 2D point in space.

Radians

Convenience type: you can define an angle in Radians and it is convertible to Degrees (and vice versa)

Rect

Defines a two-dimensional rectangle.

RectF

Defines a rectangle with floating-point coordinates.

SmallVec

A Vec-like container that can store a small number of elements inline.

VectorLine

Define a line using a fast 2D vector. It may not be as pixel-perfect as Bresenham, but with vectorization it is sometimes faster for a quick line solution.

Enums

DistanceAlg

Enumeration of available 2D Distance algorithms

FieldOfViewAlg

Enumeration of available FOV algorithms

LineAlg

Enumeration of available 2D Distance algorithms

Traits

Algorithm2D

Implement these for handling conversion to/from 2D coordinates (they are separate, because you might want Dwarf Fortress style 3D!)

Algorithm3D

Implement these for handling conversion to/from 2D coordinates (they are separate, because you might want Dwarf Fortress style 3D!)

BaseMap

Implement this trait to support path-finding functions.

Functions

a_star_search

Request an A-Star search. The start and end are specified as index numbers (compatible with your BaseMap implementation), and it requires access to your map so as to call distance and exit determinations.

field_of_view

Calculates field-of-view for a map that supports Algorithm2D.

field_of_view_set

Calculates field-of-view for a map that supports Algorithm2D, returning a HashSet. This is a bit faster than coercing the results into a vector, since internally it uses the set for de-duplication.

line2d

Plots a line between two 2D points and returns a vector of points along the line.

line2d_bresenham

Uses a Bresenham’s algorithm to plot a line between two points. On some CPUs, this is faster than Bresenham.

line2d_vector

Uses a 2D vector algorithm to plot a line between two points. On some CPUs, this is faster than Bresenham.

project_angle

From a given start point, project forward radius units at an angle of angle_radians degrees. 0 Degrees is north (negative Y), 90 degrees is east (positive X)

Type Aliases

PointF

A 2D floating-point position.