3. PathFinder.search giving strang results.

PathFinder.search giving strang results.


  • Hey folks,

    So I'm playing around with the new PathFinder module and it is giving me some bizarre results.

    When trying to path between two adjecent rooms. which are directly connected, MY roomCallback is called 13 times, for different rooms.

    I'm pathing from RoomPosition(43, 44, 'W5N1') to RoomPosition(17, 31, 'W6N1') and this is the result I get, when printing which roomName roomCallback is called with: 

    W5N1 <- Search from here
    W4N1 <- Not even directly accessible from W5N1.
    W6N1 <- To here
    W6N2 <-- To get here you pass through W6N1 (The target room)
    W5N0
    W6N0
    W5N2
    W5S0
    W6S0
    W6S1
    W4N0
    W7N1
    W7N0

    Now, I do assume that the roomCallback are called in the order the rooms are visited by the A* and therefore it makes no sense to me that it should look at all those rooms. It should look at W5N1, W5N0 and W6N1, at max and stop as soon as it reaches the target room.

    Because of this, I can't use PathFinder.search() to go from W5N1 to W5S1, as it hits 16 rooms long before it gets close to W5S1.

    Now, I suppose my question is, am I doing something wrong, or is the PathFinder module bugged?

    Some additional detail:

    I'm calling the function like this:

    PathFinder.search(from, {pos: to, range: 1}, {
        plainCost: 2,
        swampCost: 10,
        roomCallback: module.exports.staticCostMatrix,
        maxRooms: 16,
     });
    Number of ops: 1347
    And the path it creates: 88111111111188888811887777778877777767778887777777776663666665556565556666666777777777887888888111
     
    Converted to directions from start to end, for compactness. The path is correct, though and is 98 steps.
     
    Edit: Added the staticCostMatrix code:
    module.exports.staticCostMatrix = function(roomName) {
        var room = Game.rooms[roomName];
         console.log(roomName);
         if(!room) {
             return;
         }
     
         Memory.pathfinder = Memory.pathfinder || {};
         Memory.pathfinder[roomName] = Memory.pathfinder[roomName] || {};
     
         if(Memory.pathfinder[roomName].costMatrix && (Game.time - Memory.pathfinder[roomName].updated) < 100) {
             return PathFinder.CostMatrix.deserialize(Memory.pathfinder[roomName].costMatrix);
         }
     
         var costMatrix = new PathFinder.CostMatrix;
     
         var structures = room.find(FIND_STRUCTURES);
         for(var i = 0; i < structures.length; i++) {
             var structure = structures[i];
     
             if(structure.structureType == STRUCTURE_ROAD) {
                 costMatrix.set(structure.pos.x, structure.pos.y, 1);
             } else if(structure.structureType !== STRUCTURE_RAMPART || !structure.my) {
                 costMatrix.set(structure.pos.x, structure.pos.y, 0xFF);
             }
         }
     
         Memory.pathfinder[roomName].costMatrix = costMatrix.serialize();
         Memory.pathfinder[roomName].updated = Game.time;
         console.log("Recalculated costMatrix for " + roomName);
         return costMatrix;
    };
  • Culture

    For completeness sake, what is your 

    module.exports.staticCostMatrix

    method doing?


  • Doh, updated the first post with the code. 🙂


  • Yes it seems that the path finder is venturing into other rooms too frequently. This isn't costing a whole lot of CPU time, but it is counting against `maxRooms` which will make it so you can't find longer paths. I have a fix ready that will reduce the number of rooms the path finder looks at. Be on the look out for that later.

    However, there are some changes you can make to your code right now to help out. This will also be helpful after the fix is live. First is { plainCost: 2, swampCost: 10 }. In the case that no road exists, this will increase the search area of your path exponentially as the path's length increases. I notice that your transport creeps have equal parts MOVE & CARRY. In this case you can set { plainCost: 1, swampCost: 5 } and drastically reduce the path finding complexity (by not searching for roads). Additionally if you set `heuristicWeight` (a good starting point is 1.2) you can really improve search speed without much loss of accuracy.

  • Dev Team

    The patch has been deployed.


  • Awesome, this is a lot more reasonable and with heuristicWeight set to 1.9, it finds a path that's shorter than the first one. (It did that before the patch too)


    W5N1 <- Start
    W6N1 <- Target
    W6N2 <- Above target
    W6N0 <- Below target

    ops: 594; len: 97;

    Thanks for the great work! Now I can use the PathFinder module in my second version of my code! 😄


  • Path length is the wrong metric to be looking at, you should be looking at path cost. Increasing `heuristicWeight` will, by design, return non-ideal paths. If you don't care about walking on roads or walking over swamps you should adjust those costs accordingly.


  • Well, I don't get the path cost returned(Feature request, right there.), so it's hard to look at that. However, the only difference in the path that's 98 and 97, is that at some point along the way it moves in direction 8, instead of moving 1 and then 7, all of it is on road, but since moving 1 step diagonally is both faster(tick wise) and costs the same as moving up and then left, the difference in cost would be 1.