Open Pazaz opened 1 year ago
If you can break down the inputs/outputs of pathfinding like a Leetcode question I can write a hyper efficient algorithm
I'm wondering how much of a speed improvement using a different JavaScript engine would give. Bun for example instead of Node. I don't know how incompatible that change would be though.
Definitely curious about Bun as well, but only supporting WSL on Windows is a no-go for contributors right now (can't guarantee everyone is on macOS/Linux!). It might be worth writing a small experiment to compare the different engines still.
We've just converted the RSMod PathFinder from TypeScript to WebAssembly and these are the final before and after results doing 100,000 path requests in a single tick as the benchmark.
AMD Ryzen 9 3900X 12-Core Processor 3.80 GHz
We perform 100,000 path requests from this spot to a tile +10 tiles North.
case 'bench': {
const start = Date.now();
for (let index = 0; index < 100_000; index++) {
World.pathFinder.findPath(this.level, this.x, this.z, this.x, this.z + 10);
}
const end = Date.now();
console.log(`took = ${end - start} ms`);
break;
}
[0] took = 3858 ms
[0] took = 3855 ms
[0] took = 3828 ms
[0] took = 3820 ms
[0] took = 3833 ms
[0] took = 3852 ms
[0] took = 3844 ms
[0] took = 1534 ms
[0] took = 1540 ms
[0] took = 1544 ms
[0] took = 1519 ms
[0] took = 1533 ms
[0] took = 1522 ms
[0] took = 1527 ms
@ultraviolet-jordan notes that supporting a full 2k world won’t be ideal due to pf speed (note that in real world cases not every player is generating a path every tick). We’re not expecting more than double-digit players and local development, which runs without issue.
Napkin benchmark: 100k paths, 10 tiles away - ~3000ms in TS, ~434ms in reference Kotlin implementation.
I think we can figure out JS/TS-specific optimizations and/or move pathfinder to native code. Jagex did client-side pathfinding at the time and evaluated steps from those generated paths on the server instead.