Pathfinding

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

A - - - > B

Creep.move

The most basic form of creep movement, creep.move() accepts a direction constant with TOP always being towards Y:0 in the room, RIGHT towards X:49,BOTTOM towards Y:49 and LEFT towards Y:0. A creep needs MOVE parts to be able to use this method (unless the creep is being pulled by another creep using creep.pull) and their fatigue needs to be 0. A creep executing a move into a terrain wall, structure or elsewise non-pathable object will still return OK as a code and generate an intent however in the intent stage it will fail to execute on the move, thus still costing 0.2 CPU for the call. As such, if executing pure moves, the user needs to account for if the move is possible.

TOP_LEFT:8 TOP: 1 TOP_RIGHT: 2

LEFT:7 X RIGHT:3

BOTTOM_LEFT: 6 BOTTOM:5 BOTTOM_RIGHT: 4

Fatigue

As explained in Screep's Docs fatigue is a status generated by a creep executing move commands, if a creep's fatigue is greater than zero, it can not move that tick. Every creep body part except MOVE & empty CARRY parts generate fatigue when a creep moves from one roomPosition to another, the amount is dependent on the terrain/structure they are leaving. 'Dead' parts (Parts with 0/100 hits), will still generate fatigue.

• Departing from a Road Structure regardless of terrain underneath will generate 1 point of fatigue per eligible body parts.
• Departing from a Plains terrain roomPosition will generate 2 points of fatigue per eligible body parts.
• Departing from a Swamp terrain roomPosition will generate 10 points of fatigue per eligible body parts.

For each 'alive' (1 or more hits out of 100) MOVE part a creep has in its body, the creep will lose 2 fatigue points per move part per tick, boosted MOVE parts will decrease more fatigue points proportional to its boost modifier. As such, a creep with equal parts MOVE and other parts will beable to move 1 roomPosition a tick on plains, but not on swamps, a creep with half as many MOVE parts as other parts will move 1 RoomPosition a tick on roads, but half as fast on plains and far slower still on swamps.

Boosting carry parts which increases their capacity to hold resources, will not increase the 'weight' of the singular carry part. Meaning, that a carry part that contains more resources in 1 part, will still generate fatigue at the same rate as an unboosted part.

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.

Creep.moveByPath

moveByPath is creep method that accepts either an array of RoomPositions or the output of findPath either in an array format or serialized string format.

As an Array of RoomPositions

As can be seen in the Engine Code the array of roomPositions strictly must be RoomPosition objects, not strictly {x:,y:,roomName:} due to a check & it using RoomPosition methods on the objects in the array. This is an important distinction to make, because if you to save an array of RoomPosition objects to Memory they would be considered 'generic' objects when loaded next tick, as Memory JSON.stringify() s the object at ticks end, and reconstitutes it from the string when first referenced. As such, if storing the roomPositions in memory, its required to re-make them into roomPosition objects. Another option is to store them in global as this enables storage across ticks while retaining the RoomPosition object, however when global is reset (by code push, server or server issue) it will no longer exist.

While taking more storage space then a string, roomPositions have the advantage of it being easier to get back onto 'the rail' of the path if a creep is bumped off of it, a user can find the closest roomPosition to 'snap' back onto, then moveByPath can take over as long as it is adjcent to the start, or on one of the roomPositions in the sequence. Also, simply by .reverse()ing the array, the path travel back to orgin from the target is possible.

As the output of FindPath or searlized format

moveByPath also accepts the result of a findPath & its searlized format as seen in the engine code. When stored in its string form, it can take up less memory and does not require reconstitution like roomPositions do, however as it is a 'start' position and a series of directions it can be more difficult to get on the rail as you have to trace the path until you find the 'closest' part.

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.

As of writing, all pathfinding based methods in screeps use pathFinder in some capacity (unless elsewise specified by the user to not, or the user creates their own)

PathFinder.search

The main utilization of pathFinder, the user provides it a Origin as the starting position in the form of a roomPosition, A Goal or an array of Goals which need to be roomPosition(s) as well or an object containing a pos property for the position, with a range property {pos: roomPositionObject, range: rangeIntNumber} providing a goal (or goals) in this format, will allow the pathfinder to find a position 'in range' of the roomPosition specified which can speed the process, its also required to do so for goals that are 'not walkable' by creeps as the pathFinder will not beable to pathFind to such positions. For example, a source, controller or mineral are all in 'terrain walls' which by default are considered unwalkable, so the pathFinder can never reach them without changing the costMatrix or providing a range. In the case that multiple goals are used, the cheapest path is returned and used and while the return object does not tell you which goal was selected, by looking at the last indexed roomPosition of the returned path array, you can find out. Finally, you also provide an object with opts (options) for pathFinder to use.

PathFinder.costMatrix

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.

Game.map.findRoute()

FindRoute is useful for finding the set of rooms as-it connects to another room by using the routeCallback opt, you can include or exclude rooms by traits, types or positions.

Room.findPath & RoomPosition.findPathTo

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.

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.