Sangman, on 13 December 2020 - 03:53 PM, said:
In situations where a while loop isn't appropriate I use a control variable that I set to a certain value, and only execute the code in the loop if the variable is not set to that value... Not quite the same as breaking the for loop but it works
eg
Thanks. I was doing basically this as well. I decided to swap them out for while loops, since I wanted to remove as many loop iterations as possible when possible. Even if the for loop is doing nothing, it's still using a non-zero amount of CPU time. Each node only has 8 neighbors, so after all 8 neighbors have been found, I know I can safely exit the loop. Under normal, sane conditions this wouldn't matter, but when I'm trying to reduce hundreds of thousands of total iterations on a given game tic, every CPU cycle counts.
Sangman, on 13 December 2020 - 03:53 PM, said:
Yup, I had a similar situation a while ago and I spread the workload out by giving each actor a random chance to execute its code depending on a tic count (that I reset back to 0 after calculating). Like first 30 tics have a 10% chance of calculating, next 30 have a 20% chance etc until finally at 120 tics the calculation is forced.
You could also account for player distance/visibility.. An easy performance improvement is to restrict the amount of times calculations are run against/by things that the player can't see.
But I don't know how compatible all of that would be with the A* stuff.
The A* system is locked to a single actor each tic, partially for performance reasons, but also because gamearrays are global only and actors can't share the path data that is stored in the arrays. Also as mentioned previously, they aren't trying to run A* on every single tic, they only do it once every "occasionally", and they store their path data locally as well to reduce the number of calls they need to make to the expensive A* functions.
There's also a lot of other AI considerations and A* is just one part of their overall behavior - an AI doesn't need to pathfind if they have direct line-of-sight with the player, for example. It's not a magic bullet, it's just one tool in the toolbox, and is meant to replace any instance of "seekplayer" to keep them from getting stuck in rooms or running into walls and sprites more than anything else.
So anyway, after working on this the past few days, I've been able to drastically improve the performance of the search. I've cut the number of iterations down from 500k to 11k, and the number of expensive operations down from 258k to just over 1000. There's still some minor things I want to try and improve, and of course there's lots of real-world testing that needs to be done, but I think I've found just about all of the shortcuts that can reasonably be found. Thank you everyone for the feedback and suggestions!