javascript-astar
javascript-astar copied to clipboard
bgrins
Replacing Binary Heap's indexOf
Hi,
I've chosen this implementation for a RTS game, optimized it for Mozilla's SpiderMonkey and got very promising results with weighting thousands of nodes in a matter of one digit millisecond. So even full map scans run in an acceptable time frame. IonMonkey compiles all hot function into native code and spends now most time inside the internal indexOf of the BinaryHeap.
Has there been an attempt to replace the content array with a key/value store to avoid continuously searching in an tens of thousands entries array?
Interesting, what changes did you make to optimize it for SpiderMonkey? I'd be curious to see how the optimized version does in other engines as well. Could you maybe make a jsPerf to compare the original vs. the optimized one?
Regarding changes to BinaryHeap, I haven't really looked into any optimizations so there may be some low hanging fruit there.
Well, it's not exact science, but hardcoding diagonal and neighbors, replacing branching with ternary when possible seem to help. Initialization profits heavily from reusing the graph.
You'll find the current thing around here: https://github.com/agentx-cgn/Hannibal/blob/master/ai.js#L297 Sorry, won't have the time for a stand-alone at jsperf.com
I gave the non indexOf a quick try, but didn't replace the array instead let the nodes keep track of their index.
// this.sinkDown(this.content.indexOf(node));
this.sinkDown(node.index);
It's now 5-6 times faster!
Interesting, I'm not sure how each node is keeping track of its index, but if you had a PR or a code sample I'd be happy to take a look at this if it is this much faster. I'd be specifically interested in this index tracking change, not the smaller optimizations like ternaries instead of branching
Had to adapt path structure, heap with index tracking starts now around here: https://github.com/agentx-cgn/Hannibal/blob/master/source/simulation/ai/hannibal/ai.js#L381