Pathfinding
Getting an agent to navigate a space may be one the the greatest challenges for any programmer with enough gall to accept it. The amount of bullshit you have to account for is insane, it's no wonder most people use prebuilt solutions. But to honor a specific use case I decided to attempt tackling the challenge on my own.
I decided to go with a flowgraph (or something approximating it) reasoning being the algorithm would be easier to implement and it would scale well with higher number of units (as compared to A* which calculates the path for each unit individually). The downside is that the computing time grows with map size more so than unit count, I figured it was a worth while deal so I proceeded.
The graph is made up of points, each point knows it's own neighbours (cardinal and diagonal). That's all they know, nothing else. I figured working like this would make for an elegant solution, not having to bother with storing the whole grid of their positions or anything, all they would need is an array of their neighbours (technically 2), don't even need to know which direction those neighbours are in!
But then, how do I get a path to a point? Simple: Every point has a reference to another point called "direction". From this, the destination point simply takes all it's neighbours and sets their direction to be itself (the destination). Now all of the points around the destination are "pointing" to the destination. After this, each of these points do the same to their neighbours, and then those points do the same to their neighbours etc. This creates a sort of wave of points, stepping further away from the destination and direction the outer points towards the center. It is an elegant solution in the sense that the algorithm is exceedingly simple, I added some additional logic to make it prefer cardinal connections over diagonal connections just to make corridors not crowd one edge.
Imagine my surprise when calculating a flow graph took MULTIPLE SECONDS. That's intolerable, so I went to see what I can mend in the code. First, I replaced one of the lists with arrays, this just about cut the time in half (as expected from previous experiences, NEVER USE LISTS). After this I decided to try changing up the algorithm slightly. At first , in order to get this wavy behavior, I had implemented a static queue (first-in-first-out list) where I would add each newly "directed" point and take out the point which was done "directing". I figured an alternative would be making a static delegate function that would trigger a function of every point, this function would then check if the step (the index of the wave or whatever you wanna call it) belongs to the wave currently being calculated. This is basically a function that gets run on 300 points for every point, so yeah, you do the exponentially increasing math. YET SOMEHOW STILL It was faster than using a single fucking queue. <- have a load of this shit. This brought me to about 60ms to calculate a flow graph of 300 points. Not great but probably tolerable with multithreading (not that I know how to do that), I then tried doubling the points to 600 and got a computing time of
350ms. This is what we call exponential suffering. Adding more points not only means more points need to be calculated, but that every calculation is more demanding due to the function that is being called on
every single point. The function itself isn't demanding for any point not in the current wave, for most points it's just an integer comparison. But evidently, doing 600 integer comparisons 600 times gets a little fucking demanding.
Well at least it seems like it would have a simply solution, minimize the amounts of times this function is being called. I tried to do this by dynamically subscribing the function to the delegate only when it needs to be called, and unsubscribing it when it's no longer needed. BUT THIS MADE IT WORSE! It went to about 380ms! I guess the delegate's list of subscribers is itself some sort of list, so any gains I get by not calling the function unnecessarily get trumped by editing the list.
(none of this is including the garbage time which increases the computing time by about 70~80%
![[angry]](/data/assets/smilies/angryyyyy.png "Angry [angry]")
)
I was hoping to somehow bandaid a way to "block" certain directions (this would kinda ruin the elegance because I would have to start checking for positions), so I can make certain corners sharp, or even add cover, but I highly doubt I can do that with the current atrocious performance. There's other little peculiarities like figuring out when a path is no longer being used and disposing of it and what not, but one foot after the other, kinder.
At this point I'm shit out of ideas for optimizing this thing. I was hoping to have thousands of points for the paths but I dread even attempting something like that. The performance hit wouldn't be as drastic if the graphs were divided into two, because the exponentiality decreases, so that's a silver lining for whatever use case that would fit.
I do plan to rewrite this into ECS code (entity component system) which should make it a lot faster or some shit, but I would first need to learn ECS, as well as learning multithreading for ECS
for deterministic multiplayer and I do not like the sounds of that one bit
(mind you I still haven't tackled the actual navigation agent AT ALL)
If anyone is interested I can share the code, it's basically a single class with some 200 lines of code (elegance or something). Would be great if anyone had a clue as to what gear could be greased for better performance.
now excuse me as I go back to stare at it and ponder
