Pathfinding

Pathfinding refers to the process of getting from Position A to Position B.

Pathfinder

Created by The General, the PathFinder module provides a specialized version of the Jump point search algorithm. It provides a multiroom pathfinder that performs extremely well.

This can be utilized using either the Pathfinder.search function or Room.findPath.

Costmatrixes

Each element in the world can be given a weight that affects how the Pathfinder generates it's results. Terrain based weights can be added using options, but custom weights need to be added using costmatrixes. These are classes formed off of the Pathfinder module that allow elements to be specified individually. A weight of one makes an element the most prefered, while a weight of 255 means the element is completely blocked.

Costmatrixes are not generated directly and given to the Pathfinder. Instead a callback function that takes a room name can be sent as an option, and it should return either a costmatrix or false if the room should be off limits. Depending on the needs of the program this function could add creeps, structures, and roads with different weights. It can even be used to have creeps avoid source keepers or hostiles.

To avoid the potentially expensive task of generating the costmatrix each tick the costmatrix class comes with serialize and deserialize functions. These can be large with a lot of redundant data, making options like lzstring potentially useful.

Room.findPath

The findPath function is the first and easiest way to access paths. Internally it uses the Pathfinder module, and it has with a number of options to create the appropriate costmatrixes to provide to Pathfinder.

Prior to the introduction of the Pathfinder module this function was the only built in way to get paths. It depended on the astar algorithm to generate the path. This old behavior can be reenabled by running `Pathfinder.use(false)`, although there are no real benefits to doing so.

The Room.findPath function is used by all other functions in the game which require pathfinding (ie, RoomPosition.findClosestByPath, Creep.moveTo). Since these functions also pass all of their options into the Room.findPath function, overloading this function with new features will also add those features to all of these dependent functions.

Creep.moveTo

Creep.moveTo is a built in function that wraps around Pathfinder.search and Creep.moveByPath.

Any options passed to Creep.moveTo also get passed to the Room.findPath call it does.

It has a per-creep cache to prevent the path from being regenerated each tick. It does not reuse paths among creeps or cache costmatrixes, making it an ideal function to focus on by players looking to optimize their code and regain some cpu.

External Tools

• Traveler.js - a full replacement for moveTo with additional features and an improved cache.
• Screeps Astar - a custom astar implimentation specifically for Screeps with many additional features that make it useful for wall planning.