can you explain why a* is slow in bl? is it the heap? sounds like the issue is less a* and more no good heap implementation, but that seems like it could be easily fixed via a binary heap array implementation
the heuristic is meant to greatly reduce the spread + make the algo go in the right direction so i cant imagine why dfs would perform better, especially on big nodemaps where it’s likely for the dfs to go the wrong way for a long time. unless you aren’t searching for shortest path in which case i *guess* it would be faster than a* at the cost of making the bot possibly taking nonsensical paths
if i were to take a guess it would for sure be that heap implementation. i didn't really brown townyze the algorithm all too much, i just measured its runtime over a few hundred nodes. calculations involving more than like 100 nodes would take about 1 ms to compute on my laptop iirc, which for me was too slow to use it in-game. i imagine that if you take some hints from how carbon zypher implemented his tree stuff, you could probably re-implement the heap to be way more performant. then, you'd be able to use the heuristic which would be super nice since you could do stuff like factor in the crouch/jump nodes into your distance calculations and pick the truly fastest route from point a to b
my solution in comparison to carbon's was to implement a* in python and then have that asynchronously calculate and then communicate the path using sockets. but, for a pure TS solution that would be problematic obviously lol
while (%enqCurrent > 0)
{
%enqParent = (%enqCurrent - 1) >> 1;
if (%frontierPriority[%enqCurrent] > %frontierPriority[%enqParent])
break;
// There's about half a million variable assignments going
// on here. How can this be improved?
%enqTempItem = %frontierItem[%enqParent];
%enqTempPriority = %frontierPriority[%enqParent];
%frontierItem[%enqParent] = %frontierItem[%enqCurrent];
%frontierPriority[%enqParent] = %frontierPriority[%enqCurrent];
%frontierItem[%enqCurrent] = %enqTempItem;
%frontierPriority[%enqCurrent] = %enqTempPriority;
%enqCurrent = %enqParent;
}
looks like a heap deletion operation in port's spatial a*. doesn't look too fast for me, lol. obviously some work would have to go into finding out the best way to do something like this. TS is weird when it comes to variable assignment/access speed lol. globals might be faster here, but idk. i've long since forgotten the quirks of torque