search

bgrins / javascript-astar

A* Search / Pathfinding Algorithm in Javascript
https://briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated/
MIT License
1.36k stars 325 forks source link

Replacing Binary Heap's indexOf #31

Open agentx-cgn opened 10 years ago

agentx-cgn commented 10 years ago

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?

bgrins commented 10 years ago

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.

agentx-cgn commented 10 years ago

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

agentx-cgn commented 10 years ago

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!

bgrins commented 9 years ago

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

agentx-cgn commented 9 years ago

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