Difference between revisions of "Pathfinding"

From Screeps Wiki
Jump to navigation Jump to search
(categorized)
(Progress on re-writin')
Line 1: Line 1:
 
Pathfinding refers to the process of getting from Position A to Position B.  
 
Pathfinding refers to the process of getting from Position A to Position B.  
  
 +
[ - A to B Graphic - ]
 +
 +
== Creep.move ==
 +
The most basic form of creep movement, <code>creep.move()</code> accepts a direction constant with <code>TOP</code> always being towards Y:0 in the room, <code>RIGHT</code> towards X:49,<code>BOTTOM</code>  towards Y:49 and <code>LEFT</code> towards Y:0.  A creep needs <code>MOVE</code> 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 <code>OK</code> 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 TO BOTTOM graphic - ]
 +
 +
<code>TOP_LEFT      TOP        TOP_RIGHT</code>
 +
 +
<code>LEFT                          RIGHT</code>
 +
 +
<code>BOTTOM_LEFT  BOTTOM    BOTTOM_RIGHT</code>
 +
 +
== Fatigue ==
 +
As explained in [https://docs.screeps.com/creeps.html#Movement Screep's Docs] fatigue is a status generated by a creep executing move commands, if a creep's fatigue is greater than 0, it can not move.  Every creep body part except <code>MOVE</code> & empty <code>CARRY</code> 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, will still generate fatiuge.
 +
 +
* 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
 +
 +
== 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.
  
 
== Pathfinder ==
 
== Pathfinder ==
Line 6: Line 36:
 
Created by [https://screeps.com/a/#!/profile/The_General The General], the PathFinder module provides a specialized version of the [https://en.wikipedia.org/wiki/Jump_point_search Jump point search] algorithm. It provides a multiroom pathfinder that performs extremely well.
 
Created by [https://screeps.com/a/#!/profile/The_General The General], the PathFinder module provides a specialized version of the [https://en.wikipedia.org/wiki/Jump_point_search 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.
+
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 <code>Origin</code> as the starting position in the form of a [[roomPosition]], A <code>Goal</code> or an array of <code>Goals</code> which need to be roomPosition(s) as well or an object containing a <code>pos</code> property for the position, with a <code>range</code> property <code>{pos: roomPositionObject, range: rangeIntNumber}</code> 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 <code>opts</code> (options) for pathFinder to use.
  
== Costmatrixes ==
+
=== Opts (options) ===
  
 +
=== 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.
 
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.
  
Line 16: Line 49:
  
 
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 [http://pieroxy.net/blog/pages/lz-string/index.html| lzstring] potentially useful.
 
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 [http://pieroxy.net/blog/pages/lz-string/index.html| lzstring] potentially useful.
 +
 +
== Game.map.findRoute() ==
  
  
== Room.findPath ==
+
== 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.  
 
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.  
Line 25: Line 60:
  
 
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.
 
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 ==
 
== External Tools ==
 
 
* [https://gist.github.com/bonzaiferroni/bbbbf8a681f071dc13759da8a1be316e Traveler.js] - a full replacement for moveTo with additional features and an improved cache.
 
* [https://gist.github.com/bonzaiferroni/bbbbf8a681f071dc13759da8a1be316e Traveler.js] - a full replacement for moveTo with additional features and an improved cache.
 
* [https://gist.github.com/tedivm/80be3d82976b8ab5f857 Screeps Astar] - a custom astar implimentation specifically for Screeps with many additional features that make it useful for wall planning.
 
* [https://gist.github.com/tedivm/80be3d82976b8ab5f857 Screeps Astar] - a custom astar implimentation specifically for Screeps with many additional features that make it useful for wall planning.
 
[[Category:Development]]
 
[[Category:Development]]
 
[[Category:Game Knowledge]]
 
[[Category:Game Knowledge]]

Revision as of 16:58, 15 March 2021

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

[ - A to B Graphic - ]

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 TO BOTTOM graphic - ]

TOP_LEFT TOP TOP_RIGHT

LEFT RIGHT

BOTTOM_LEFT BOTTOM BOTTOM_RIGHT

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 0, it can not move. 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, will still generate fatiuge.

  • 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

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.

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.

Opts (options)

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()

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.