Nonetheless, I got the basic principle of it, and with some effort was able to make it work. I was tipped off to it by Ben Bartlett’s article on Screeps logistics, which goes into realms of mathematical wizardry that frighten even me. But that means B is stuck with Minion 2, which is far more expensive! We need a better way to balance these requests.įortunately, the Gale-Shapley stable marriage algorithm exists to meet this need. TransferAction A will pick minion 1, because that’s its best option. TransferAction A - Minion 1 : 20 ticks TransferAction A - Minion 2 : 25 ticks TransferAction B - Minion 1 : 10 ticks TransferAction B - Minion 2 : 35 ticksĪs things stand now, we’ll loop through our list of requests. We have two idle minions, and the best paths have been calculated for both: Let’s say we have two TransferAction requests from containers A and B. This makes picking the best TaskPath for the minion easy. While we’re at it, we can also get the SpeculativeMinion’s predicted output: a hauler with 100 capacity will be able to transfer twice as much as one with 50 capacity. Whew! We now have a TaskPath and we know long it will take the minion to perform it. Then the cost function can calculate accurately based on the minion’s predicted state.
#Screeps creep update
Each Task will update the SpeculativeMinion with its predicted outcome: a HarvestAction will increase the SpeculativeMinion’s capacityUsed, while a MoveAction will change the SpeculativeMinion’s position. That’s okay we’ll create a SpeculativeMinion that predicts the minion’s state along the task path and use that to calculate the cost. So the cost for the minion to move to the Build Site right now will be different from its cost to move to the Build Site after it collects energy from a container. But while we’re calculating, the minion isn’t moving. We’re calculating the cost based on the minion doing the action. So, now that we have a path, we just have to call the cost for each Action in the path and add them up to find the total. We can tune this cost later: it should also factor in the creep’s effective move speed, for example. In this case, we’re approximating with range, because doing the actual pathfinding gets expensive fast. The cost method lets us predict approximately how much the action will cost (in ticks). So let’s start breaking this up conceptually:Ĭlass MinionCanWork () Well, okay, one optimization: can a minion fulfill a request? A hauler minion, for example, can’t fulfill a Build request because it doesn’t have any WORK parts! On the other hand, an empty hauler can’t currently fulfill a Transfer request, but it might if it stopped to fill up on energy first. We’ll worry about optimization later for now, let’s consider each possible path, and figure out the best way for a given minion to fulfill a given request. You could send a minion to a Source, have it harvest the energy, then send it to the Spawn to transfer it or, you could send a minion to a Container, have it withdraw the energy, and then send it to the Spawn to transfer it. This gets difficult when you consider that there could be more than one way to fulfill a request. Buckle up this is going to be a long post! Predicting Task Fulfillment Now we need to figure out which minion is best suited to fulfill which request.
![screeps creep screeps creep](https://www.jonwinsley.com/assets/screeps-report.png)
![screeps creep screeps creep](https://docs.screeps.com/api/img/bodyparts.png)
Since the Task Supervisor handles all work being done, we’ll just look for all of our minions and cross off any that are currently busy with something else. Then we need to collect the minions that are idle. The Task Supervisor will collect these as they come in. How do you make sure your minions are doing the work that most needs done?įirst we need to track the work that needs done.
![screeps creep screeps creep](https://s3.amazonaws.com/forum-static.screeps.com/c90b7e94-3d80-498b-9b7c-2bd71e1fedd7.png)
Here’s the GitHub repo if you’d like to follow along. The article below describes the AI in its current state: I’m still expanding and refining my codebase.