Hero6 icon indicating copy to clipboard operation
Hero6 copied to clipboard

Pathfinder: Reduce Node Count

Open persn opened this issue 9 years ago • 0 comments

I think we could benefit greatly from reducing the amount of nodes the pathfinder has to work with. Currently the pathfinder is working pixel-by-pixel, this results in:

node count = width * height
node count = 320 * 240
node count = 76 800

However I believe that if we modify our code to make every 5x5 (or something) grid of pixels to represent a node we can reduce the workload greatly

node count = (width * height) / (node width * node height)
node count = (320 * 240) / (5 * 5)
node count = 3072

Keeping in mind that the A* pathfinding algorithm has exponential complexity in not only CPU usage, but also memory consumption, I believe we'll get great performance improvements as there'll be less swapping between cache and RAM.

I also have a hunch that this will give us smoother and better looking paths as there should be less fidgety movements of the characters than it would be a pixel-by-pixel paths. Currently our character animations swap a lot back and forth between the directions the characters are facing.

persn avatar Sep 05 '16 02:09 persn