Hero6
Hero6 copied to clipboard
Pathfinder: Reduce Node Count
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.