Path cache for screeps

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

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;
    },
};

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 );
}