Pathfinder Speed

[Pazaz]

@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.

[dginovker]

If you can break down the inputs/outputs of pathfinding like a Leetcode question I can write a hyper efficient algorithm

[thedaneeffect]

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.

[Pazaz]

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.

[ultraviolet-jordan]

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.

The Hardware

AMD Ryzen 9 3900X 12-Core Processor 3.80 GHz

Testing Location

The Command

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;
            }

TypeScript Results (Before)

[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

WebAssembly Results (After)

[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