Screeps Autobahn

A module for generating efficient road networks in Screeps

What does it do?

Autobahn will return an array of Screeps RoomPosition objects. These positions represent a road network that satisfies two conditions:

1. All destinations can be reached from the start in the minimum number of steps
2. The network uses as few roads as possible to satisfy condition 1

Thus, Autobahn can be used to generate efficient road networks for your creeps.

Setup

Manual

1. Download the Git repository
2. npm install
3. npm run bundle
4. Stick dist/autobahn.js with your Screeps code and require it

Using NPM

1. npm install screeps-autobahn
2. Require screeps-autobahn in your Screeps code

Known Issues and Limitations

• IMPORTANT: Autobahn will use between 30 and 100 CPU each time it is called. Rather than calling it repeatedly, just run it once and save the result.
• IMPORTANT: Autobahn's algorithm takes exponentially longer with more destinations. For now, you should use no more than 6 destinations at once.
• Currently, Autobahn will select a network without regard for terrain. An option to avoid swamps will be added in a future patch.
• Currently, Autobahn will use tiles adjacent to your destination. For many use cases this is undesirable, since a creep may be standing there. An option to avoid these tiles will be added in a future patch.

Example usage

// Require autobahn
const autobahn = require('./autobahn');

// Use a flag as the start point
let start = Game.flags['start'];

// Create an array of energy sources to use as the destinations
let roomName = 'W34S73';
let destinations = Game.rooms[roomName].find(FIND_SOURCES);

// Run autobahn
let network = autobahn(start, destinations);

// Build the road network
for (let i = 0; i < network.length; i++) {
	let pos = network[i];
	Game.rooms[pos.roomName].createConstructionSite(pos, STRUCTURE_ROAD);
}

Multi-room pathing

Autobahn now supports building networks that span several rooms. By default, pathfinding is limited to the room of the start point. To allow Autobahn to use additional rooms, pass in an options object containing roomFilter. The simplest roomFilter is an array of room names that are allowed, for example:

let start = new RoomPosition(28, 48, 'W34S73');
let destinations = Game.rooms['W34S75'].find(FIND_SOURCES);

// Allow autobahn to path in these three rooms
let options = {roomFilter: ['W34S73', 'W34S74', 'W34S75']};

// Run autobahn
let network = autobahn(start, destinations, options);

Alternatively, you can specify roomFilter as a function that takes in a room name string and returns a boolean:

// Allow autobahn to use any rooms starting with W34
let options = {roomFilter: (roomName) => roomName.startsWith('W34')};

Please note that Autobahn builds a breadth-first graph from the start to all destinations, so asking Autobahn to build a network over long distances with many rooms allowed could be very expensive.

Contributing

Please open an issue on GitLab to report bugs or feature requests. Feel free to open merge requests with recommended fixes as well!

Acknowledgements

Special thanks to @davaned for inspiration and feedback.