So with limited time, I decided to laser focus on just one thing, and that was optimizing my radial pathfinding. Honestly, probably didn't need to be the focus, but when you don't have a boss, or a time frame, might as well follow your passions.

So, first thing of course, was to profile things. Which is relatively easy to do in Unity, though their profiler's UI is really awful, after going about 10 calls deep, it starts to choke. And this is 100% the ui, not the recording, as it's while digging into an already recorded trace while the game is not running. I even ended up moving some of my code around to avoid the problem, which is sad.

Anyway, some easy fixes stood out. For checking a dubin's curve, which consisted of a start arc, a line and an end arc, I was checking in that order to determine whether they crossed any tiles. And well, arcs are more expensive to check than lines, and if one is blocked anywhere, the path is invalid, so I swapped my if to check the line first. I also noticed that there was a lot of memory allocations happening, and moved many of my smaller classes that were mostly data to structs. That had a consequence though, structs of structs in the crappy version of mono that Unity uses (seriously Unity, why don't you update, I also would like to use C# 6.0 features), cause a str.memcpy to show up in the profiler every time there is a copy. Now it might just be an artifact, as it's not showing up as taking a large percentage of time, just annoying that it's showing up at all.

Also, to improve memory, I moved to pooling my visited nodes. I also decided to dig into the priority queue I was using. It's Blue Raja's Queue. Which is mostly good, it just has a lot of features that I don't really need. For example, each queue node has a double priority, a long for 'InsertionIndex' and an int for the QueueIndex. The InsertionIndex is to prevent ties. You're supposed to then inherit from his structure and have your own data for the visited node.

I simplified that down to a float Priority and a unsigned int for the QueueIndex, and an int for an index into my visited node pool instead of inheriting. For tie breakers, since I always start at 0 in the node pool, I multiply my priority value by 10.0f and add nodeIndex/NodePoolSize. It's crude, and if my floats got big enough, could possibly run into issues, but that's unlikely considering the size of my navgrid. So my PriorityQueueNodes are more compact and take less comparisons when doing cascades up/down:return (higher.Priority < lower.Priority || (higher.Priority == lower.Priority && higher.InsertionIndex < lower.InsertionIndex));Mine is:return higher.Priority < lower.Priority
I also moved away from an array of Nodes, which contained all sorts of data about them, to simple boolean array of Open/Closed nodes. Eventually I may need to change that to something more complex, to more accurately reflect nodes that cost different amounts to move through, and to take account of different costs between Node0 To Node1 and Node1 to Node0. (aka, not just nodes, but edges) but for now, what I have is good enough. I also trimmed out unnecessary data, ie, don't keep the index of the node in the array, that's just wasteful, I also dropped keeping the position coordinate, and calculate it every time I need it, as it's relatively cheap to calculate on a uniform grid.

Anyway, so on a Deep Profile, which is really slow, I am able to pathfind across my map in about 300-400 ms in the Editor. Considering I started around 1200-1400 ms, that's a pretty decent improvement. And outside of the editor, a windows 64 bit executable is screaming fast to calculate. WebGL is still slow, I'm guessing the conversion isn't as good, and there are other oddities as well, like my camera controls don't work the same.

I'm tempted to try it as a C++ DLL and see if I get any further improvements. There would be some small benefits to doing so, and the managed to unmanaged barrier would be minimal, since it's only at the start of the pathfind.