A breadth-first search path finder.
npm install @2004scape/rsmod-pathfinderA breadth-first search pathfinder.
(The fastest in all the land)
Ported from Kotlin: 🔗 https://github.com/rsmod/rsmod/tree/main/engine/pathfinder
----
> 🔗 https://www.npmjs.com/package/@2004scape/rsmod-pathfinder
>
> npm i @2004scape/rsmod-pathfinder
> 🔗 https://crates.io/crates/rsmod-pathfinder
>
> cargo add rsmod-pathfinder
----
I have created main.js and main.rs for synthetic examples of performance.
They load in a full reconstruction of the Lumbridge mapsquare (64x64) tiles
with full clipping flags set. Then in a loop it runs through 100k pathfinder
requests to a destination +10 tiles North with a single access point to the destination.
--
AMD Ryzen 9 3900X 12-Core Processor 3.80 GHz
- All tests below were done on the same machine with the same hardware.
Ran in Release mode on Windows x64 OS.
``
100k paths took: 279.3573ms; time per call: 2.793µs
100k paths took: 280.2238ms; time per call: 2.802µs
100k paths took: 281.206ms; time per call: 2.812µs
100k paths took: 278.8223ms; time per call: 2.788µs
100k paths took: 277.9747ms; time per call: 2.779µs
100k paths took: 279.5909ms; time per call: 2.795µs
100k paths took: 277.8473ms; time per call: 2.778µs
100k paths took: 281.0326ms; time per call: 2.81µs
Ran in Release mode on Windows x64 OS with NodeJS.
This typically takes about 850ms on average in a real world scenario tested
on a server also using TypeScript.
`
100k paths took: 703ms; time per call: 7.03µs
100k paths took: 702ms; time per call: 7.02µs
100k paths took: 701ms; time per call: 7.01µs
100k paths took: 702ms; time per call: 7.02µs
100k paths took: 699ms; time per call: 6.99µs
100k paths took: 705ms; time per call: 7.05µs
100k paths took: 701ms; time per call: 7.01µs
100k paths took: 702ms; time per call: 7.02µs
`
100k paths took: 1534ms; time per call: 15.34µs
100k paths took: 1540ms; time per call: 15.40µs
100k paths took: 1544ms; time per call: 15.44µs
100k paths took: 1519ms; time per call: 15.19µs
100k paths took: 1533ms; time per call: 15.33µs
100k paths took: 1522ms; time per call: 15.22µs
100k paths took: 1527ms; time per call: 15.27µs
`
100k paths took: 3858ms; time per call: 38.58µs
100k paths took: 3855ms; time per call: 38.55µs
100k paths took: 3828ms; time per call: 38.28µs
100k paths took: 3820ms; time per call: 38.20µs
100k paths took: 3833ms; time per call: 38.33µs
100k paths took: 3852ms; time per call: 38.52µs
100k paths took: 3844ms; time per call: 38.44µs
--
cargo bench
`
pathfinder/find_path time: [6.8195 µs 7.1890 µs 7.4884 µs]
thrpt: [133.54 Kelem/s 139.10 Kelem/s 146.64 Kelem/s]
`
----
`shell``
wasm-pack build --target nodejs --out-dir dist --out-name rsmod-pathfinder # Builds the wasm bundle.
~/IdeaProjects/wabt/bin/wasm2wat dist/rsmod-pathfinder_bg.wasm -o src/rsmod.wat # Generates the wat file.
npm publish --access public # Publishes the version of this to npm.