Skip to content

Instantly share code, notes, and snippets.

@derofim

derofim/path_cache.js

Created March 20, 2016 15:54
Show Gist options
  • Save derofim/72b7a5e1a57b77877892 to your computer and use it in GitHub Desktop.
Save derofim/72b7a5e1a57b77877892 to your computer and use it in GitHub Desktop.
Download ZIP
Path cache for screeps
Raw
path_cache.js
module.exports = (function () { // store and reuse often used paths
function addPath(from, to, path) {
var key = getPathKey(from, to);
var cache = Memory.pathCache || {};
var cachedPath = {
path: path,
uses: 1
}
cache[key] = cachedPath;
Memory.pathCache = cache;
}
function getPath(from, to) {
var cache = Memory.pathCache;
if(cache) {
var cachedPath = cache[getPathKey(from, to)];
if(cachedPath) {
cachedPath.uses += 1;
Memory.pathCache = cache;
return cachedPath;
}
}
}
function cleanCache() {
//cleanCacheByUsage(1);
}
function cleanCacheByUsage(usage) {
if(Memory.pathCache && _.size(Memory.pathCache) > 1500) { //1500 entries ~= 100kB
console.log('Cleaning path cache (usage == '+usage+')...');
var counter = 0;
for (var key in Memory.pathCache) {
var cached = Memory.pathCache[key];
if(cached.uses === usage) {
Memory.pathCache[key] = undefined;
counter += 1;
}
}
Game.notify('Path cache of usage '+usage+' cleaned! '+counter+' paths removed', 6 * 60);
cleanCacheByUsage(usage + 1);
}
}
// require('pathCache').showCacheUsage();
function showCacheUsage() {
var usageCountCounter = {};
var howManyTimesCacheUsed = 0;
for (var key in Memory.pathCache) {
var cached = Memory.pathCache[key];
usageCountCounter['used'+cached.uses] = usageCountCounter['used'+cached.uses] + 1 || 1;
howManyTimesCacheUsed += cached.uses;
}
console.log(JSON.stringify(usageCountCounter));
console.log('howManyTimesCacheUsed: ' + howManyTimesCacheUsed);
console.log('cache size: ' + _.size(Memory.pathCache));
}
function getPathKey(from, to) {
//console.log("getPathKey= "+getPosKey(from) + '$' + getPosKey(to));
return getPosKey(from) + '$' + getPosKey(to);
}
function getPosKey(pos) {
return pos.x + 'x' + pos.y + pos.roomName;
}
return {
add: addPath,
get: getPath,
clean: cleanCache,
showCacheUsage: showCacheUsage
}
}());
Raw
role_harvester.js
var pathCache = require('path_cache');
var MINE_FLAG = 1, MINE_FIND =2;
module.exports = {
PATH_FAIL : -1,
PATH_FOUND : 1,
PATH_CHANGED : 2,
PATH_WALKING : 3,
PATH_END : 4,
PATH_ERROR : 5,
onSpawn: function(creep) {
this.creep = creep;
creep.memory.onSpawned = true;
creep.memory.last_path_broken_wait = 0;
creep.memory.broken_attemts = 0;
creep.memory.curTask = MINE_FIND;
},
run : function (creep) {
if (creep.memory.onSpawned === undefined) this.onSpawn(creep);
if(creep.memory.curTask==MINE_FLAG) {
this.goFlag(creep, FIND_FLAGS, COLOR_GREEN);
} else if(creep.carry.energy < creep.carryCapacity) {
this.collectEnergy(creep, FIND_SOURCES_ACTIVE);
}
else {
this.storeEnergy(creep, FIND_MY_SPAWNS);
}
},
collectEnergy: function ( creep, target ) // example target: FIND_SOURCES_ACTIVE
{
var aim = creep.pos.findClosestByPath(target);
if(aim){
var path_result = this.moveByMemoryPathTo(creep, aim, 1); //console.log("path result: "+ result);
if(path_result == this.PATH_END && creep.harvest(aim) == ERR_NOT_IN_RANGE) console.log("bug_path");
}
},
goFlag: function ( creep, target, color ) // example {target: FIND_FLAGS, color:COLOR_GREEN}
{
var aim = creep.pos.findClosestByRange(target, {
filter: function(x) {
if(x.color == color) return true;
return null;
}
});
if(aim){
creep.memory.curTask=MINE_FLAG;
var path_result = this.moveByMemoryPathTo(creep, aim, 1); //console.log("path result: "+ result);
if(path_result == this.PATH_END) creep.memory.curTask=MINE_FIND;
}
},
storeEnergy: function ( creep, target ) // example target: FIND_MY_SPAWNS
{
//console.log(1);
var aim = creep.pos.findClosestByRange(target, {
filter: function(x) {
if(x.energy < x.energyCapacity) return true;
return null;
}
});
if(aim){
//console.log(2);
//
//
//
//
//
var path_result = this.moveByMemoryPathTo(creep, aim, 1); //console.log("path result: "+ result);
if(path_result == this.PATH_END && creep.transfer(aim, RESOURCE_ENERGY) == ERR_NOT_IN_RANGE) console.log("bug_path");
} else this.goFlag(creep, FIND_FLAGS, COLOR_GREEN);
},
/**
/* Use for moving to almost static target (flag, source, e.t.c.)
/* distance: min allowed final distance between creep and target (for example, 1 if target is source)
/* Note: Stuck ticks: if creep is moving by target path and dont move N ticks, than path refreshes.
/* Note: If distance not correct, than creep may stay harvesting/building/e.t.c and stuck ticks will increase!
/* findPathTo: If the target is in another room, then the corresponding exit will be used as a target => recreate path!
**/
moveByMemoryPathTo : function ( creep, target, distance )
{
if( !creep || creep.spawning || creep.fatigue>0 ) return this.PATH_FAIL;
if ( creep.pos.getRangeTo(target)<=distance) return this.PATH_END; // if at position
if( !creep.memory.path || !creep.memory.path[creep.memory.path.length-1] || creep.memory.ticks_stuck && creep.memory.ticks_stuck > creep.memory.path.length) // if no path or stuck for N ticks
{
creep.memory.path = this.setPathTo(creep, target, distance);
if(creep.memory.path) return this.PATH_FOUND; // if new path created
else return this.PATH_FAIL; // if cant find path
} else if ( !target.pos.isEqualTo( creep.memory.path[creep.memory.path.length-1].x, creep.memory.path[creep.memory.path.length-1].y ) ) { // path changed
creep.memory.path = this.setPathTo(creep, target, distance);
return this.PATH_CHANGED;
} else if ( creep.pos.getRangeTo(target)>distance) { // if not at position
if(creep.fatigue==0) creep.memory.prev_pos = creep.pos;
if(creep.moveByPath(creep.memory.path)<0) {
creep.memory.ticks_stuck = 99999;
return this.PATH_ERROR;
}
if( creep.pos.isEqualTo(creep.memory.prev_pos) && creep.fatigue==0) {
//console.log("stuck ticks" + creep.memory.ticks_stuck);
creep.memory.ticks_stuck++; // increases every move too! Check like (stuck > creep.memory.path.length-2)
} else {
creep.memory.ticks_stuck = 0;
}
return this.PATH_WALKING;
}
// if strage thing happens 0_o
creep.memory.ticks_stuck = 99999;
return this.PATH_ERROR;
},
setPathTo : function(creep, target, distance){
// check if path marked as broken
if(creep.memory.path_target_id == target.id && creep.memory.last_path_broken_wait!==undefined && creep.memory.last_path_broken_wait>0)
{
creep.memory.last_path_broken_wait--;
//console.log("skipping broken path for "+creep.memory.last_path_broken_wait);
return;
}
// create new path
if(Memory.pathCache.length>500) {
console.log("total clean of Memory.pathCache");
delete Memory.pathCache;
}
if(!Memory.pathCache) Memory.pathCache = {}; // ToDo: Startup init
var path,uses;
if(Memory.pathCache[this.getPathKey(creep.pos,target.pos)]!==undefined)
{
path = Memory.pathCache[this.getPathKey(creep.pos,target.pos)].path;
uses = Memory.pathCache[this.getPathKey(creep.pos,target.pos)].uses || 0;
} else {
path = creep.pos.findPathTo(target);
uses = 0;
console.log(creep.name + ' pathfind..' + ' key: ' + this.getPathKey(creep.pos,target.pos));
}
if( path ) // if radius to target very small, than path may be reused
{
Memory.pathCache[this.getPathKey(creep.pos,target.pos)] = { path: path, uses: ++uses };
console.log(creep.name + ' using time ' + uses + ' key: ' + this.getPathKey(creep.pos,target.pos));
if(uses>30) { // clean some cache
console.log("before"+_.size(Memory.pathCache));
delete Memory.pathCache[this.getPathKey(creep.pos,target.pos)];
for (var key in Memory.pathCache) {
var cached = Memory.pathCache[key];
if(cached.uses<5) delete Memory.pathCache[key];
}
console.log("after"+_.size(Memory.pathCache));
}
}
creep.memory.path = path;
//console.log("found path to creep " + creep.id + ", length" + creep.memory.path.length);
creep.memory.path_target_id = target.id;
creep.memory.ticks_stuck = 0;
creep.memory.prev_pos = creep.pos;
if(creep.memory.path && creep.memory.path[creep.memory.path.length-1] && target.pos.isEqualTo( creep.memory.path[creep.memory.path.length-1].x, creep.memory.path[creep.memory.path.length-1].y ) ){
creep.memory.last_path_broken_wait = 0;
creep.memory.broken_attemts = 0;
return creep.memory.path;
}
// if final path does not exist
creep.memory.last_path_broken_wait = 5; // ticks to wait for next check
creep.memory.broken_attemts++;
console.log("creep.memory.broken_attemts for "+creep.name+" = "+creep.memory.broken_attemts);
if(creep.memory.broken_attemts>1) { // Maybe creeps blocked each other, send them home
creep.memory.ticks_stuck = 99999;
this.goFlag(creep, FIND_FLAGS, COLOR_GREEN);
}
return null;
},
getPathKey : function(from, to) {
return this.getPosKey(from) + '$' + this.getPosKey(to);
},
getPosKey : function (pos) {
return pos.x + 'x' + pos.y + pos.roomName;
},
};
@derofim
Copy link
Author

derofim commented Mar 22, 2016 

var _ = require('lodash')
var harvester = require('role_harvester');

var MINE_FIND = 1, // trying to find energy
    MINE_DONE = 2, // trying to deliver collected energy
    MINE_PERF = 3, // trying to mine energy
    MINE_MOVE = 4, // trying to move to energy
    MINE_HIDE = 5; // trying hide from enemy

var getPathKey = function (from, to) {
    //console.log("getPathKey= "+getPosKey(from) + '$' + getPosKey(to));
    return getPosKey(from) + '$' + getPosKey(to);
}

var getPosKey = function (pos) {
    return pos.x + 'x' + pos.y + pos.roomName;
}

var nextTile = function (pos, direction) { // returns position by previous pos and direction to move
    if(direction == TOP) pos.y--;
    else if(direction == BOTTOM) pos.y++;
    else if(direction == RIGHT) pos.x++;
    else if(direction == LEFT) pos.x--;
    else if(direction == TOP_RIGHT) { pos.y--; pos.x++; }
    else if(direction == TOP_LEFT) { pos.y--; pos.x--; }
    else if(direction == BOTTOM_RIGHT) { pos.y++; pos.x++; }
    else if(direction == BOTTOM_LEFT) { pos.y++; pos.x--; }
    return pos;
}
var reverse = {[TOP]:BOTTOM,[TOP_RIGHT]:BOTTOM_LEFT,[RIGHT]:LEFT,[BOTTOM_RIGHT]:TOP_LEFT,[BOTTOM]:TOP,[BOTTOM_LEFT]:TOP_RIGHT,[LEFT]:RIGHT,[TOP_LEFT]:BOTTOM_RIGHT};

// Saves flow graph using target room, origin pos, target pos 
var buildRoads = function (room, from, to) {
        if(!to || !room) return;
        //var cache = Memory.pathCache || {};
        //from.room.memory.flowGraph = {};
        if(!room.memory.flowGraph) room.memory.flowGraph = {};
        if(!room.memory.flowGraph[to.x+"_"+to.y]) room.memory.flowGraph[to.x+"_"+to.y] = {}
        if(!room.memory.flowGraph[from.x+"_"+from.y]) room.memory.flowGraph[from.x+"_"+from.y] = {}
        //console.log( JSON.stringify(room.memory.flowGraph[to.pos.x+"_"+to.pos.y]) );
        //var flowGraph = room.memory.flowGraph[to.x+"_"+to.y];
                var path = room.findPath(from, to, { ignoreCreeps: true, ignoreDestructibleStructures:true, ignoreRoads:true });
                //console.log( JSON.stringify(path) );
                if(!path.length) return false;
                var prev_i;
                for(var i in path) // fix findPath (direction may be not correct, maybe bug)
                {
                    if(prev_i && path[i].x != path[prev_i].x && path[i].y != path[prev_i].y)
                    {
                        if     (path[i].x > path[prev_i].x && path[i].y > path[prev_i].y) path[prev_i].direction=BOTTOM_RIGHT;
                        else if(path[i].x < path[prev_i].x && path[i].y > path[prev_i].y ) path[prev_i].direction=BOTTOM_LEFT;
                        else if(path[i].x > path[prev_i].x && path[i].y > path[prev_i].y) path[prev_i].direction=BOTTOM_RIGHT;
                        //else if(path[i].x < path[prev_i].x && path[i].y > path[prev_i].y ) path[prev_i].direction=BOTTOM_LEFT;
                        //
                        else if(path[i].x > path[prev_i].x && path[i].y < path[prev_i].y) path[prev_i].direction=TOP_RIGHT;
                        else if(path[i].x < path[prev_i].x && path[i].y < path[prev_i].y ) path[prev_i].direction=TOP_LEFT;
                        else if(path[i].x > path[prev_i].x && path[i].y < path[prev_i].y) path[prev_i].direction=TOP_RIGHT;
                        else if(path[i].x < path[prev_i].x && path[i].y < path[prev_i].y ) path[prev_i].direction=TOP_LEFT;
                        //else path[prev_i].direction=-1;
                    }
                    if(prev_i && path[i].x == path[prev_i].x && path[i].y != path[prev_i].y)
                    {
                        if (path[i].y > path[prev_i].y) path[prev_i].direction=BOTTOM;
                        else path[prev_i].direction=TOP;
                    }
                    if(prev_i && path[i].x != path[prev_i].x && path[i].y == path[prev_i].y)
                    {
                        if (path[i].x < path[prev_i].x) path[prev_i].direction=LEFT;
                        else path[prev_i].direction=RIGHT;
                    }
                    prev_i = i;
                }
                for(var i in path)
                {
                    //if( to.isEqualTo(path[i].x,path[i].y) ) continue;
                    room.memory.flowGraph[to.x+"_"+to.y][path[i].x+"_"+path[i].y] = path[i].direction;
                    room.memory.flowGraph[from.x+"_"+from.y][path[i].x+"_"+path[i].y] = reverse[path[i].direction];
                    var result = room.createConstructionSite(path[i].x, path[i].y, STRUCTURE_ROAD);
                }
        //console.log( JSON.stringify(path) );
        //console.log( JSON.stringify(from.room.memory.flowGraph) );
        return true;
};

module.exports.loop = function () {
    PathFinder.use(false);
    var startCpu = Game.getUsedCpu(); 
    for(var name in Game.rooms) {
        var room = Game.rooms[name];
        var sources = room.find(FIND_SOURCES_ACTIVE);
        for(var name in Game.spawns) {
            var spawn = Game.spawns[name];
            for(var num in sources) {
               //console.log(spawn.room, spawn.pos, sources[num].pos);
               buildRoads(spawn.room, spawn.pos, sources[num].pos);
               for(var dx = -1; dx<=1; dx++) // surround spawn with roads
               {
                    for(var dy = -1; dy<=1; dy++)
                    {
                        if(dx==0 && dy==0) continue;
                        //console.log( spawn.room.getPositionAt(spawn.pos.x+dx, spawn.pos.y+dy) );
                        //buildRoads( spawn.room, spawn.room.getPositionAt(spawn.pos.x+dx, spawn.pos.y+dy), sources[num].pos );
                    }
               }
            }
        }
    }

    for(var name in Game.creeps) {
        var creep = Game.creeps[name];
        if (creep.memory.onSpawned === undefined){
            creep.memory.onSpawned = true;
            creep.memory.curTask = MINE_FIND;
        }

        if(!creep.spawning && creep.memory.role == 'harvester') {
            var target;
            target = creep.pos.findClosestByPath(FIND_SOURCES);
            creep.memory.target_key = target.pos.x+"_"+target.pos.y;
            creep.memory.target_id = target.id;
            if(creep.carry.energy >= creep.carryCapacity){
                target = creep.pos.findClosestByPath(FIND_MY_SPAWNS);
                creep.memory.target_key = target.pos.x+"_"+target.pos.y;
                creep.memory.target_id = target.id;
            }

            if( creep.memory.target_key && creep.room.memory.flowGraph && creep.room.memory.flowGraph[creep.memory.target_key] 
                    && creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y] ) // creep on path :)
            {
            } else {
               console.log("creep " + creep.name + " lost path!"); 
            }
            //creep.drop(RESOURCE_ENERGY);

            if(creep.memory.curTask == MINE_MOVE){
                console.log("MINE_MOVE!");
                if( creep.memory.target_key && creep.room.memory.flowGraph && creep.room.memory.flowGraph[creep.memory.target_key] 
                    && creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y] ) // creep on path :)
                {
                    // ToDo: allow creeps with better WORK go forward
                    //console.log("lol!"+JSON.stringify(creep.room.memory.flowGraph[creep.memory.target_key]));
                    var nextDirection = creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y];
                    var nextPosition = nextTile(creep.pos, nextDirection);
                    var nextCreeps = creep.room.lookForAt('creep', nextPosition.x, nextPosition.y);
                    var nextCreep = null;
                    var betterCreep = null;
                    // find better worker and let him go to source
                    if( !Game.getObjectById(creep.memory.target_id).ticksToRegeneration ) // if creep is going to spawn let go better creeps first
                    {
                        for(name in nextCreeps) {
                            if( nextCreeps[name].getActiveBodyparts(WORK) > creep.getActiveBodyparts(WORK) && !nextCreeps[name].spawning && nextCreeps[name].pos.isEqualTo(nextPosition.x,nextPosition.y) ) {
                                betterCreep = nextCreeps[name];
                                break;
                            }
                        }
                    }
                    if(betterCreep)
                    {
                        console.log("found better creep! "+betterCreep.name);
                        creep.move(nextDirection); // swap creeps
                    } else {

                        // find pipeline creep
                        for(name in nextCreeps) {
                            if( nextCreeps[name].getActiveBodyparts(CARRY) > 0 && !nextCreeps[name].spawning && nextCreeps[name].pos.isEqualTo(nextPosition.x,nextPosition.y) ) {
                                nextCreep = nextCreeps[name];
                                break;
                            }
                        }

                        if(nextCreep && nextCreep.carry.energy < nextCreep.carryCapacity){ // try to pipe energy to another creep
                            if(!creep.transfer(nextCreep, RESOURCE_ENERGY))
                            {
                                console.log("Cant transfer energy at"+nextPosition+" to creep "+nextCreep.id);
                            }
                        }
                        else if( Game.getObjectById(creep.memory.target_id).pos.isEqualTo(nextPosition.x,nextPosition.y) ) 
                        { // target reached
                            creep.memory.curTask = MINE_FIND;
                        } else {
                            if(nextCreep && nextCreep.getActiveBodyparts(CARRY) > creep.getActiveBodyparts(CARRY) )
                            {
                                creep.move(nextDirection);
                            } else
                            {
                                if(!nextCreep) creep.move(nextDirection);
                                console.log("ToDo");
                            }

                        }

                    }
                }
            } else if(creep.memory.curTask == MINE_PERF){
                if(creep.carry.energy < creep.carryCapacity){
                            if(creep.harvest(Game.getObjectById(creep.memory.target_id)) == ERR_NOT_IN_RANGE) {
                                //creep.move(nextDirection);
                                creep.memory.curTask = MINE_MOVE;
                                console.log("MINE_MOVE");
                            } else
                            {
                                creep.memory.curTask = MINE_PERF;
                                console.log("MINE_PERF");
                            }
                } else {
                                //console.log("MINE_DONE");
                                creep.memory.curTask = MINE_DONE;
                }
            } else if(creep.memory.curTask == MINE_DONE){
                console.log("MINE_DONE!");
                var nextDirection = creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y];
                var nextPosition = nextTile(creep.pos, nextDirection);
                //console.log( "!!!!!!!!!!!!!"+JSON.stringify(Game.getObjectById(creep.memory.target_id).pos) );
                if( Game.getObjectById(creep.memory.target_id).pos.isEqualTo(nextPosition.x,nextPosition.y) )
                { // target reached

                    var spawn_near = Game.getObjectById(creep.memory.target_id);
                    if(spawn_near.energy<spawn_near.energyCapacity)
                    {
                        if (creep.transfer(spawn_near, RESOURCE_ENERGY) == ERR_NOT_IN_RANGE) {
                            creep.moveTo(spawn_near); // must never happen
                            console.log( "creep moveTo, path lost - check bugs" );
                        } else { // spawn full
                            creep.memory.curTask = MINE_FIND;
                        }
                    }
                } else {
                    //creep.move(nextDirection);
                    creep.memory.curTask = MINE_MOVE;
                }
            } else if(creep.memory.curTask == MINE_FIND) {
                console.log("MINE_FIND!");
                if( creep.memory.target_key && creep.room.memory.flowGraph && creep.room.memory.flowGraph[creep.memory.target_key] 
                    && creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y] ) // creep on path :)
                {
                    //console.log("lol!"+JSON.stringify(creep.room.memory.flowGraph[creep.memory.target_key]));
                    var nextDirection = creep.room.memory.flowGraph[creep.memory.target_key][creep.pos.x+"_"+creep.pos.y];
                    var nextPosition = nextTile(creep.pos, nextDirection);
                    if( Game.getObjectById(creep.memory.target_id).pos.isEqualTo(nextPosition.x,nextPosition.y) ) 
                    { // target reached
                        if(creep.carry.energy < creep.carryCapacity){
                            if(creep.harvest(Game.getObjectById(creep.memory.target_id)) == ERR_NOT_IN_RANGE) {
                                //creep.move(nextDirection);
                                creep.memory.curTask = MINE_MOVE;
                                console.log("MINE_MOVE");
                            } else
                            {
                                creep.memory.curTask = MINE_PERF;
                                console.log("MINE_PERF");
                            }
                        } else {
                                //console.log("MINE_DONE");
                                creep.memory.curTask = MINE_DONE;
                        }
                    } else {
                        //creep.move(nextDirection);
                        creep.memory.curTask = MINE_MOVE;
                    }

                }
                //console.log( JSON.stringify( creep.room.memory.flowGraph[creep.memory.target_id][creep.pos.x+"_"+creep.pos.y] ) );
            }

            // ToDo: path lost or target deleted
        } 
    }
    for(var name in Game.rooms) {
        var room = Game.rooms[name];
        room.memory.flowGraph = {}; // ToDo!!!
    }

    //if(Game.spawns.Spawn1.energy==Game.spawns.Spawn1.energyCapacity) Game.spawns.Spawn1.createCreep( [WORK, CARRY, MOVE], null, {role: '1target_keyter'} );
    // Game.spawns.Spawn1.createCreep( [WORK, CARRY, MOVE], null, { role: 'harvester' } );
    //console.log( Game.getUsedCpu() - startCpu );
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment