Pathfinding with collision detection, any tips?

  • I am using the room objects pathfinding function to navigate my creeps. Is there any way to figure out right away if any other creep might be blocking the way on any point along he path? The room.findPath function has a parameter that either avoids or ignores other creeps. Is there a callback or event?

    I am playing in a room where one of the sources is only accessible through a crack that is one single field in width only, which of course results in a massive jam of creeps if not beeing resolved correctly. Ideally, I want my creeps to intelligently avoid this source while beeing harvested by another creep and move to the second source, but which is further away. Maybe the creeps could wait in line until the way is cleared? 😁

    Any ideas, suggestions?

  • I've just started investigating and using paths a bit more in my code to cut down on cpu usage. At present I am auto generating and storing needed/predicted paths in memory once rather that generating paths when they need to get A-B which is still itself still more efficient than creep.moveTo() but not optimal. Issues like you describe I have encountered. In truth not many creeps need to be using the same path as the colony progress's(Maybe haulers/repairers and moving into position creeps) but I'm trying to get everything as fully automated and cpu light as I can from the start even though I think that this issue only really effect the start-up colonies in their initial growth mostly.

    I'm NO expert but have a number of workarounds to test.

    I plan to give a creep that's harvesting/in-range to a source or travelling a path or in-range to the problem area a memory tag that other creeps could see and know. They could then go elsewhere or stop for a duration/detour if on the path and wait till the other creep drops its memory tag, meaning it's all clear. This might be a little cpu intensive though as each creep will have to either search all creeps memory so this could be bad. Maybe global memory could be used and when each creep on a specific path they could update this with their present movements, meaning path free/not…Cpu testing needed.

    ….or, and I think might be the best cpu usage…any creep that’s likely to be using that path could have its own memory changed by the creep that’s starting on that path, so the creep only has to check its own memory to see if another has allocated that resource/path for themselves. If this works ok then it might be possible to drop the 'using path tag' prior to actually coming off the path dependant on how far away the other creep is from the problem area. But which creep gets priority then of being the path controller??

    I'm sure there's a much more elegant approach someone knows and hopefully will tell 🙂

  • The default behaviour of the moveTo function for creeps is to reuse the same path for 5 ticks. You can change the tick count with the reusePath option.

    My own strategy is to generate a path with other creeps ignored and to keep the path for 100 ticks. If the creep is stuck, then I let it get a new path where other creeps are treated as obstructions. This is crude, but suprisingly effective.

  • There's probably a few ways to accomplish what your looking to do. Part of the fun is figuring out what works for you and refactoring or developing new ways.

    You could have creeps check before traveling the area around / the jam location for an obstruction, then change target as needed.

    You could cap the amount of creeps for that source specifically and balance it so not too many are getting jammed up.

    More dynamically similar to how @SandGrainOne said, recently I started using something that @Orlet had mentioned on slack which is to simply have the creep detect when its not moving but not yet at its goal, then find the obstruction and move it.

  • I have a trick I particularly like. I track all creeps for stalls. When I detect a creep is no longer moving add that to my cost matrix with a weight of 50. Then my creeps naturally try to avoid stalled creeps. I use the same stall tracking to detect when a creep is stuck and repath.

  • I have monkey-patched Creep.move() and Creep.moveTo() methods, first one to save the creep's intended move direction, and second one to inject different defaults (reusePath: 50 and ignoreCreeps: true), as well as use custom CostMatrix callback so I can mark some specific creeps as unwalkable at some specific situations.

    Then after all the creep logic has run its course I run another loop of collision resolver, that checks if there's a creep in the creep's intended move direction, whether it is moving or not, and tries to move the blocker creep out of the way, with some role-specific overrides provided, too.

    Took me a few hours to code, a couple of days to iron all the edge cases, but now it works pretty well for 99.8% of cases. The remaining 0.02% result in some weird creep dancing, but tend to resolve themselves in a few ticks on their own.