IMPORTANT NOTE!

This is a fork of @dwonderley's module. I am attempting to update it for v10. Just wanted to make sure to credit the original author.

lib-find-the-path

Changelog

1.4.0

Added configuration to enable non-omniscient path planning. Added a method to determine line of sight for only vision-blocking walls (i.e. it ignores ethereal walls). Refactored configuration of path manager and utility class.

1.3.0

Refactored segments to provide better structure for eventual hex support.

1.2.0

1. Added FTPUtility class that exposes useful methods
   1. Added traverse method that moves a token along its calculated path
   2. Added moveTokenToPoint method
   1. Moves a token to the location provided by a Point object
   2. Checks line of sight and collison before movement
   3. Moved line of sight, collison detection, and isTraversable methods into utility class
2. Changed collison detection method to take in a configuration object
1. The checkCollision option can turn collision checking off
2. The token option omits a token from the collision check (prevents a token from colliding with itself)
3. In the future, this will allow the user to selectively filter what constitutes a collision
1. Can a token move through an allied space or not?
2. Can a token stop in an allied space?
3. Can a token move through enemy tokens?
3. Various bug fixes

1.1.2

Big, breaking refactor for general improvements, code cleanliness, stability, etc...

1. Path planning can now be done from macros. See the wiki page for more information.
2. Added a PoinFactory class that makes creating and using Point objects much easier.
3. Added instances of the PathManager and PathFactory classes to game.FindThePath.X.PathManager for general access, where X is the type of distance metric (Chebyshev, Euclidean, or Manhattan).

Summary

This module provides a library that performs system-agnostic path planning calculations for two-dimensional, square grids.

The library may be called "Find the Path," but the Point class is the innovation I think people will find most useful. It provides methods for handling tokens of any size, calculating the minimum distance between points, pixels, and tokens, calculating rotations, and finding neighbors. Importantly, it does these things independent of grid size, distance metrics (it supports several), game system, and the insane coordinate-system-originates-in-the-top-left industry standard. While the PathManager provides methods to find paths between tokens, points, pixels, and coordinates, it's the power of the Point class that actually makes it possible.

See the wiki page for examples of this library's use.

This module is a work in progress, but I have tested it extensively. If you find bugs or have questions, comments, or requests, please don't hesitate to leave me a comment here or on the FVTT discord (@Dave Of Wonders).

Terminology

Token is a FVTT class that contains various information about game tokens, such as their pixel coordinates, the actors they represent, or their names. Tokens exist on the Canvas. The Canvas is a grid of pixel coordinates, originating at the top-left corner, with +x going left to right and +y going top to bottom.

A pixel coordinate pair (px, py) is the offset from the Canvas origin. A Token has a pixel coordinate pair, a width, and a height. Therefore, a Token's position on the canvas is bounded by the points (px, py), (px + width, py), (px, py + height), (px + width, py + height).

However, because different maps may have different sizes or pixel counts per grid square, it is useful to abstract away the pixel part of the pixel coordinates. A grid coordinate (x, y) is the offset from the Canvas origin in terms of grid squares.

A Point is a wrapper around a pair of grid coordinates. It provides several helpful methods, starting with conversions from Tokens, pixel coordinates, and grid coordinates into a Point object, where calculations can be done more simply.

The PointFactory handles the actual creation of points. It is strongly recommended, as it is more convenient, consistent, and concise than manual construction. The PointFactory needs to be told on construction how distances should be measured between Points. It will only generate points of that type, and it will make sure the size of PointSets (and other data) is managed consistently.

A PointSet is an informal term for an Array of Points. Usually, it is used to represent a Token that has a dimension > 1. It is not a defined class, but it may become one if there is a use for it. These Arrays are provided by methods such as getPointSetFromToken and should not be manually.

A Path is a wrapper around an array of Nodes. Nodes are a private class that do not need to be accessed or constructed, but loosely speaking, they are the path planning equivalent of Points. The path between two Points can be accessed by the Path object's path () method.

The PathManager is a tool used to find and track planned paths. It provides two static methods to compute arbitrary paths, but it's standard usage is to compute paths between Tokens. Using the addToken method, a user can find the path from a Token to a new target Token. This path is stored by the PathManager and accessed by the source and destination token IDs.

Line of Sight (LoS) is the concept that a line drawn from the center of one grid coordinate to the center of another is unobstructed. Collision is the concept of two tokens occupying the same grid space. A Node is said to be traversable if it is a neighbor of the current Node, if there is line of sight between corresponding Points in the origin and destination PointSets, all Points in the destination PointSet, and if there are no collisions in the destination PointSet. This is not the best definition, but it's a WIP.

Functionality

A Point class that is agnostic to grid size. The Point class provides ways to calculate distances, rotations, and neighbors. It has constructors for the FVTT Token class, pixel coordinates, or Point coordinates. It can also return a set of contiguous Points if a token has width/height > 1.

A PathManager class that provides two ways of calculating paths. First, there are the two static methods: one that finds a path between two Points and one that finds paths from a block of configuration data. However, it also provides a way of finding paths between tokens. The addToken method finds and stores the path between two tokens, origin and target.

A Path class that uses A* to find the optimal path. Path also provides convenient methods to help make use of the data.

Line of sight and collision detection. The A* algorithm is implemented such that tokens will not move through walls or on top of other tokens.

This module supports tokens with dimension > 1.

This module can calculate a path for a token and then move that token along that path.

Future Improvements

I plan to add support for hex tiles, custom heuristics, different priority measures, settings, and better handling of collision, line of sight, attack range, and failure to find paths.