Difference between revisions of "Maturity Matrix"

From Screeps Wiki
Jump to navigation Jump to search
Line 73: Line 73:
   
 
== Creep Movement (Pathfinding) ==
 
== Creep Movement (Pathfinding) ==
  +
  +
=== moveTo ===
  +
moveTo is the main pre-packaged solution when it comes to pathfinding, a user mainly only has to set a target desired to 'move to' and the function takes care of the pathing, caching and executing of the movement all in one. This is a powerful function that will carry a user far, however possibly by design it is not 'perfect' allowing the user to get familiar with the movement system and evolve past it in the future.
  +
  +
=== adding Options to moveTo ===
  +
moveTo allows for various opts or 'options' to be passed as an argument in the form of an object along with the target you are looking to move to. These options can have a huge impact on the way moveTo itself acts and behaves allowing for more complex/efficient movement.
  +
  +
==== reusePath ====
  +
by default, moveTo will cache and use the results of 'new' moveTo request for 5 ticks, or when it crosses a exit tile (as paths are only cached an encoded string 'in room'). This behavior can be modified by passing an object with the property <code>reusePath</code> along with a numerical value of the amount of game ticks the user wishes the function to reuse the cached path. Depending on how far away the target is, or the complexity of the room(s) considered, repathing every 5 ticks can become costly when many creeps are considered. Increasing this, means that you have creeps that will reuse the path for longer but will react slower to pathing obstructions. This is up to the user to resolve normally in the form of collision management.
  +
  +
==== ignoreCreeps & Collision management ====
  +
by default, moveTo will consider creep objects found when pathingfinding as 'impassable'. This means that it will attempt to pathfind around the creep found in the path, which can result in higher costs, even though the creep in the path is moveable, or may have moved by the time the creep arrives at that step in the path. The <code>ignoreCreeps</code> option allows for a user to as the name suggests, tell moveTo to ignore creeps when considering blockages/obstacles in the path. This generally allows for faster/shorter routes to be found as in a crowded base or a long busy areas of road creeps can often be found.
  +
  +
However, if the creep in question blocking the path remains, that is where collision management comes in. moveTo will continue to attempt to execute the next step in the path, even though the path is obstructed meaning the creep does not move. Implementing a system that detects when a path obstruction/blockage/collision has occurred, and then resolving it helps fix this issue as insures that the creeps are taking the 'shortest route'
  +
  +
==== range ====
  +
by default, the moveTo will attempt to path 'onto or near' the object it is targeting. However, there are times when moving between rooms or to certain areas that the user's creeps do not need to necessarily worry about being so precise. For example, a creep traveling to a distant room to scout without vision does not need to path to any particular tile to do so, just enter the room. This is where the <code>range</code> option comes in handy, the pathfinding of moveTo will attempt to find a pathable location 'in range' of the target provided meaning many operations of pathfinding can be saved thus saving CPU.
  +
  +
==== maxRooms and maxOps ====
  +
While not necessary in most use-cases, these two operations are important in several specific functions. For example with maxRooms, you can tell the moveTo function to only consider X number of rooms when pathfinding. If you have a creep, for example, that you want to only ever stay within its home room for whatever reason, then you can pass a maxRooms opt of 1 and it will not attempt to path outside of the room to get to any given target (even if it is a shorter path). As well, maxOps allows the user to set the maximum number of operations while pathfinding, when going a far distance or a complex path, increasing the number of maxOps opt will allow it to run for longer hopefully finding a path. This does, however, use more CPU.
  +
  +
==== costCallback and PathFinder.CostMatrix ====
  +
by default, the moveTo system will use the built in PathFinder in screeps to create and cache (when necessary) CostMatricies for a user's creeps to use when using moveTo. With the costCallback option however, a user can provide a customized cost matrix to be used instead of the default one that is generated/cached. This is probably the more complex of the options and likely the last step before moving on beyond the confines of moveTo. The user must make a costMatrix for a room considering (or not considering) all impathable objects, this can include custom values for whatever locations the user desires either to fully obstruct or allow passage though. An example, say the user has dedicated static mining creeps that should not move, or be moved. As such, even though the container they stand on is passable, or the creep passable if ignoreCreeps is on, the user can modify the costmatrix for the room to make this location impassable so the creeps do not consider it when trying to move, allowing the miner to continue without being obstructed, moved ect.
  +
  +
=== PathFinder.search ===
  +
This is the base function that as-of-writing all other pathfinding functions in Screeps uses. It is by far the most powerful solution to pathfinding given by the API. It requires the user to be far more specific when passing options but allows for a wide flexibility of path generation options.
  +
  +
=== Path Caching & moveByPath ===
  +
Generally once a user has become familiar with the pathfinder system, they can begin storing paths to be reused along common routes. An example would be a miner is always assigned to X source, and spawns from a spawn. The route is always the same, or becomes the same once they reach a certain point along the path. This path can be found, cached, and then reused by moveByPath or a user's custom implementation to execute move commands so that instead of pathfinding every time, the user only has to pathfind the once, or once in a while (incase new structures or obstructions have been added) dramatically reducing CPU costs.
  +
  +
=== Node Networks & cached path assignment ===
  +
Once paths have been cached, a user can then evolve into caching common routes or destinations to areas that can be reused by various creeps dynamically instead of by specific need. Mainly, a user needs to create this pathing network with a 'start' node and 'end' node or any other amount of 'nodes' they desire. A creep (or its management system) can then consider its position as well as the position of its assigned task (goal position, lets say) when looking for a path. If the goal position is within X distance of a pathing end, start, or other node and the creep is within Y of the 'other end' of the cached path / node pair then the creep can be assigned the cached path to use for traversing to nearby its target. This may require a short moveTo/pathing operation to snap to / affix to the path, but once on the path movebypath or a user's system of executing moves by the stored path can be used. The creep thereby didn't need to do the complex pathing operations to its target, only short jumps, saving CPU.
  +
  +
An Example:
  +
  +
A hauler creep is assigned a container in a remote harvesting room 2 rooms away, it is currently idling by the storage from a previous drop off. The hauler creep first looks at node(s) in the same room as its target, searching for the closest one to its assigned container, the creep then looks for the node(s) that pair with the desired node(s) for ones it is standing on or near to. Once found, it then moves to the 'start' node and once there, proceeds along the path till it is nearby its target (or closer enough to leave the 'rail' path).
   
 
== Creep Action Management ==
 
== Creep Action Management ==

Revision as of 15:07, 10 January 2022

While developing your bot, there many, many different implementations different systems can use. Some are more efficient than others, comparing your progress to other such implementations can be useful to gauge where you are and how far you have to go. It is important to remember, that Screeps is a sandbox however, if something works for you and your happy with it, use it. However, if you are looking to improve a system, or just wondering how your implementation can compare then you may find this useful.

Structure

This article will be broken up into various game 'systems' that a bot normally has. Each system will then list different implementations generally from 'least efficient' or 'easiest to code' to 'most efficient' or 'hardest to code'. This will vary by user, of course, some things may be on-par or similar to other implementations efficiency wise, or be a small part to add on not necessarily a full rework.

Spawning Creeps

Hard-Coded & Console Generated

The first stage for spawning creeps introduced in Screep's tutorial. Creeps can be generated by a user typing the information out into the console, and subsequently spawning the creep, or hard-coding it into the main or other modules. This is very easy, as it is mostly user controlled but not very robust. If data changes in-game (say, a spawn in destroyed) the hard-coded item will cease to function, and a user can only spend so much time without having to fulfil other requirements than spawning creeps, like eating, or sleeping.

If & Else-If Chain & Filter Head-count

Introduced in Screep's Tutorial, this implementation centers around getting a head-count for currently living creeps then going though either a set of IF statements or a chain of IF ELSE IF statements looking for a (normally) hardcoded value. When a discrepancy is found, a spawning call is put out and a creep is spawned. This system can be further improved by optimizing how and when the headcount is done, vs how long / how many statements are checked. This implementation does tend to run into challenges when the number of roles/type of creeps a user is spawning gets past a certain point.

Library Object & Looping

A further evolution of the spawning system, by keeping an 'object' of paired role/type names along with quantities or other data a user can thereby implement a looping architecture to iterate though the object, using the contained data to fetch counts, and compare needs. This can then be further evolved by a management system adjusting counts as needed by pressures of the environment on the colony so that a balance of creeps of many times is maintained when they are needed, or counts reduced when they are not.

Queue System

Instead of looking down a list of 'highest priority' strictly on an object, a management system can go though its own processes to determine what 'needs to be' spawned next, then simply push it to a queue that the 'spawning system' can execute on when it can, or adjust as needed.

Dynamic Energy Considerations

Another part though not normally a major overhaul, depending on colony/room need some times it is imperative that certain creeps are replenished but not necessarily always at the maximum size. Having a user's spawn system know this, and take into account when it needs to 'make do' with what energy is at hand is useful to maintain a constant operation.

Examples Include:

  • Catch-up - If a user's spawn/extension filler(s) have perished and no creep is going to take over, a creep needs to be spawned to do so, even if the 'normal size' is not available due to energy.
  • Cold boot / Recovery - If something catastrophic has happened, and a user is not getting any more energy, the spawn system can take this into account (either by measuring income or by measuring reserves) and spawn with what it has to recover accordingly.

Dynamic Part Generation

Normally implemented along-side systems that keep track of things such as Hauling Logistics, Defense/Combat creeps, or other such systems. Dynamic Part Generation takes into account not only that a creep needs to be spawned, but what size and composition it needs to be. Examples include:

  • Hauling Logistics - How many 'total carry parts' required to haul energy for a room (or chain of rooms), by how many creeps required/exist (as dependent on RCL creeps can only be so large due to energy requirements) and what energy is available now.
  • Combat Logistics - How many 'total combat parts' are required to defeat the enemy defenses / enemy creeps? What configuration/order? Spread out over how many creeps?

Harvesting Energy

Harvesters

Harvesters and 'on demand' source mining roles as shown in Screep's tutorial are the first most common implementation of creeps acquiring energy. When a creep needs energy, it seeks out a source acquires the energy needed then moves on. While easy to implement, this often leave sources with energy left-over in them when their regeneration timer goes off, meaning that it is 'wasted' (not used).

Drop-Mining & Static Harvesting

Static harvesters are a big step when it comes to maximizing energy for a room, with a creep or creeps dedicated to harvesting a source, a user can normally drain it long before the regeneration timer lapses meaning the maximum amount of energy is pulled from the source to be used. The first step is normally drop mining where the energy is dropped to the floor, some energy may be lost in this implementation as energy evaporates/sublimates (decays) and is lost forever. However, creeps when needing energy can instead move to these piles to collect energy without having to mine it.

Container Mining & Hauler Logistics

Container mining is a big step in insuring that the decay of the drop mining/static harvesting method is lessened though some investment must be made into the container as its hits will decay and require repair at a rate dependent on the state of the room (Owned/Unowned). To drop mine into the container, a creep also has to specifically select a location to stand, and always stand on to insure the energy is property dropped into the container.

Remote Mining

Once a room's energy has been harnessed, energy from other rooms can be as well. This becomes more complex due to having to assign miners to multiple rooms, getting them to the rooms (pathing), building and maintaining containers, reserving the room to increase the energy, and various other tasks.

Source Keeper Mining

Currently the hardest challenge when it comes to gathering energy. While source keeper's (SK's) rooms are very energy rich, and even include a mineral with a public extractor to mine resources from they are always guarded by SKs generated from SK lairs paired with each source. As well invasions in these rooms still occur and with stronger invaders as well as Invader Strongholds which have a chance to spawn.

To mine a SK room you generally need:

  • A way to kill the keepers consistently
  • Miners that know to avoid danger
  • Haulers that know to avoid danger
  • A way to deal with, or avoid invasions
  • A plan for how to deal with or avoid Strongholds

Hauling Logistics

Opportunity Gathering

Generally when first starting on hauling energy around to either store or use, the first implementation tends to be having creeps seek out sources (such as piles of energy, containers with energy or storages) and then transporting to some centeralized location dependent on the creep's function (container/drop -> storage or storage -> controller to use for upgrading, ect). without consideration of other creep(s) actions.

Mining / Hauler Pairs

Another implementation is to have every container/drop miner have its own 'twin' hauler, this way there is not a conflict in different haulers going for similar tasks, but depending on how they are managed does mean the creep may have downtime or be waiting for a miner to spawn, or other situations in where it could do something else while 'waiting'

Task execution

When using a Top-Down or Management based approach haulers generally execute on tasks that they are assigned by their manager. The manager takes care to not have conflicts and assign tasks as-needed.

Creep Combat

Lab Logistics

Creep Movement (Pathfinding)

moveTo

moveTo is the main pre-packaged solution when it comes to pathfinding, a user mainly only has to set a target desired to 'move to' and the function takes care of the pathing, caching and executing of the movement all in one. This is a powerful function that will carry a user far, however possibly by design it is not 'perfect' allowing the user to get familiar with the movement system and evolve past it in the future.

adding Options to moveTo

moveTo allows for various opts or 'options' to be passed as an argument in the form of an object along with the target you are looking to move to. These options can have a huge impact on the way moveTo itself acts and behaves allowing for more complex/efficient movement.

reusePath

by default, moveTo will cache and use the results of 'new' moveTo request for 5 ticks, or when it crosses a exit tile (as paths are only cached an encoded string 'in room'). This behavior can be modified by passing an object with the property reusePath along with a numerical value of the amount of game ticks the user wishes the function to reuse the cached path. Depending on how far away the target is, or the complexity of the room(s) considered, repathing every 5 ticks can become costly when many creeps are considered. Increasing this, means that you have creeps that will reuse the path for longer but will react slower to pathing obstructions. This is up to the user to resolve normally in the form of collision management.

ignoreCreeps & Collision management

by default, moveTo will consider creep objects found when pathingfinding as 'impassable'. This means that it will attempt to pathfind around the creep found in the path, which can result in higher costs, even though the creep in the path is moveable, or may have moved by the time the creep arrives at that step in the path. The ignoreCreeps option allows for a user to as the name suggests, tell moveTo to ignore creeps when considering blockages/obstacles in the path. This generally allows for faster/shorter routes to be found as in a crowded base or a long busy areas of road creeps can often be found.

However, if the creep in question blocking the path remains, that is where collision management comes in. moveTo will continue to attempt to execute the next step in the path, even though the path is obstructed meaning the creep does not move. Implementing a system that detects when a path obstruction/blockage/collision has occurred, and then resolving it helps fix this issue as insures that the creeps are taking the 'shortest route'

range

by default, the moveTo will attempt to path 'onto or near' the object it is targeting. However, there are times when moving between rooms or to certain areas that the user's creeps do not need to necessarily worry about being so precise. For example, a creep traveling to a distant room to scout without vision does not need to path to any particular tile to do so, just enter the room. This is where the range option comes in handy, the pathfinding of moveTo will attempt to find a pathable location 'in range' of the target provided meaning many operations of pathfinding can be saved thus saving CPU.

maxRooms and maxOps

While not necessary in most use-cases, these two operations are important in several specific functions. For example with maxRooms, you can tell the moveTo function to only consider X number of rooms when pathfinding. If you have a creep, for example, that you want to only ever stay within its home room for whatever reason, then you can pass a maxRooms opt of 1 and it will not attempt to path outside of the room to get to any given target (even if it is a shorter path). As well, maxOps allows the user to set the maximum number of operations while pathfinding, when going a far distance or a complex path, increasing the number of maxOps opt will allow it to run for longer hopefully finding a path. This does, however, use more CPU.

costCallback and PathFinder.CostMatrix

by default, the moveTo system will use the built in PathFinder in screeps to create and cache (when necessary) CostMatricies for a user's creeps to use when using moveTo. With the costCallback option however, a user can provide a customized cost matrix to be used instead of the default one that is generated/cached. This is probably the more complex of the options and likely the last step before moving on beyond the confines of moveTo. The user must make a costMatrix for a room considering (or not considering) all impathable objects, this can include custom values for whatever locations the user desires either to fully obstruct or allow passage though. An example, say the user has dedicated static mining creeps that should not move, or be moved. As such, even though the container they stand on is passable, or the creep passable if ignoreCreeps is on, the user can modify the costmatrix for the room to make this location impassable so the creeps do not consider it when trying to move, allowing the miner to continue without being obstructed, moved ect.

PathFinder.search

This is the base function that as-of-writing all other pathfinding functions in Screeps uses. It is by far the most powerful solution to pathfinding given by the API. It requires the user to be far more specific when passing options but allows for a wide flexibility of path generation options.

Path Caching & moveByPath

Generally once a user has become familiar with the pathfinder system, they can begin storing paths to be reused along common routes. An example would be a miner is always assigned to X source, and spawns from a spawn. The route is always the same, or becomes the same once they reach a certain point along the path. This path can be found, cached, and then reused by moveByPath or a user's custom implementation to execute move commands so that instead of pathfinding every time, the user only has to pathfind the once, or once in a while (incase new structures or obstructions have been added) dramatically reducing CPU costs.

Node Networks & cached path assignment

Once paths have been cached, a user can then evolve into caching common routes or destinations to areas that can be reused by various creeps dynamically instead of by specific need. Mainly, a user needs to create this pathing network with a 'start' node and 'end' node or any other amount of 'nodes' they desire. A creep (or its management system) can then consider its position as well as the position of its assigned task (goal position, lets say) when looking for a path. If the goal position is within X distance of a pathing end, start, or other node and the creep is within Y of the 'other end' of the cached path / node pair then the creep can be assigned the cached path to use for traversing to nearby its target. This may require a short moveTo/pathing operation to snap to / affix to the path, but once on the path movebypath or a user's system of executing moves by the stored path can be used. The creep thereby didn't need to do the complex pathing operations to its target, only short jumps, saving CPU.

An Example:

A hauler creep is assigned a container in a remote harvesting room 2 rooms away, it is currently idling by the storage from a previous drop off. The hauler creep first looks at node(s) in the same room as its target, searching for the closest one to its assigned container, the creep then looks for the node(s) that pair with the desired node(s) for ones it is standing on or near to. Once found, it then moves to the 'start' node and once there, proceeds along the path till it is nearby its target (or closer enough to leave the 'rail' path).

Creep Action Management

Role Modules & Agent Based Approach

An agent based approach known as 'roles' is what is presented in Screep's Tutorial. Primarily, each creep is assigned a role via memory (normally as a string) which is used to then determine what module (normally of the 'same' or similar name) to have the creep execute. The creep then works though the module's logic to determine what to do and how to act. This works well in keeping creeps consistent and focused with their logic, however it does mean that unless otherwise programmed to do so, they only consider their own situation and also normally run checks multiple times instead of just once.

Top Down / Management based Approach

A Top-Down or Management based approach primarily means that instead of each creep being responsible for finding its own goals, targets, information and the like, it is instead assigned these things by a manager considering the entire picture. This enables the system to fetch data as-needed, pass it / use it over the span of multiple creeps instead of multiple times over creeps and even change creeps as needed.

An example:

A management system for assigning tasks for haulers beings its tick. It looks first for available haulers that do not have a task assigned to them, if found, it then proceeds to look at all available containers assigned to its room, filtering out any containers that are already assigned to other creeps already or that energy will be not enough for the task to be worth assigning. If containers were found, it then progresses though the available creeps, assigning them to containers as they are available. The creeps (or their own different management systems) then only act on their assigned task.