GG Pathfinding – Path Occupancy Bitmask

20 Aug

64 bit to flag node occupancy:

One of the first items I have experimented adding to help improve pathfinding was to add a ulong to each nodes.  Each bit represents a slice of time. I flag the bits based off unit speed, noting when it would occupy this node. This seems to help movement with few entities:

great with 8


The first unit to move gets priority. Each path calculation the unit requesting a path shifts the nodes bitmasks based off the time it was set, to the current time and checks if it’s occupied when it would arrive.  If it is, it adds the cost of moving diagonally to the total cost (or whatever one want’s.)  This seems to be a good indication if the unit should avoid this nod or if its cheaper to wait.



Mass MovementAug 16, 2015 13:30

With several units many started to go backwards before going forwards and/or take very inefficient paths when they should wait.  Search time is also increased.