jj101k/pathfind

An attempt to produce a simple, low-memory, low-cost pathfinding algorithm. For fun.

pathfind's Issues

Evaluate updating to WebAssembly

WebAssembly will be closer to the expected code, and may run faster.

Drop x/y

Relating to path nodes or positioned nodes: drop the directly introspectible position.

WASM file should have an internal build

At the moment, the build action is:

../wabt/build/wat2wasm core.wat -o core.wasm

It should at least be an NPM thing

Larger sizes are unexpectedly likely to fail

For 1000 this is a 100% failure rate, and it reliably fails in 1ms - far less than it takes to succeed on smaller maps.

I don't see why this would happen disproportionately.

Some off-path nodes are no longer marked

Not sure what happened here, but the image now has "dandruff" in the form of white nodes inside the pathing area. While this might be nothing, it might be an indication of a real problem

Drop backwards checks if possible?

I don't remember exactly what this was, but it was something about walking backwards through nodes to get their total cost or something.

WASM core unexpectedly fails for sizes > ~320px

Example error at 400:

RuntimeError: index out of bounds index.js line 823 > WebAssembly.Module:566:1

It should not do that

Add an explicit zero test

Having a test with no obstructions and opposite corner points will produce a stable performance test

The display should be able to show arrows instead of direction numbers

The numbers are only useful when debugging the direction numbers

Try actual LS maps?

This is currently using completely random noise, which is computationally tough in its own way but not representative of the target scenario

Replace cost sort with plain min

            let route = possible_routes.sort((a, b) => a.getCost(this.gridMap) - b.getCost(this.gridMap))[0]

That's not what should be done, we just want the smallest one. It still needs to examine all of them but it should be O(n) not O(n log n)

Regression: Display updates "on" no longer works

The display just freezes anyway

The display needs a legend

This is to communicate what the colours mean

Get 250x running fast

Oh hey, past me. Just think how times change.

At 250x250 this takes something like 400ms to do produce a path of length ~800. In other words, ~500us per path step, although it doesn't work out as a constant number. At the time when this TODO was first added, it might have taken 1000ms, I don't really know.

While an actual Laser Squad map is only 50x100 (so 5,000 nodes not 62,500), demonstrating that this is at all viable means showing a low cost on modern hardware for a high workload. In 400ms there's time to do >1bn operations on modern hardware, ridiculously expensive.

Default node colour has been lost

They used to default to black or grey, are now white.

Implement true 4-bit mode

Use a grid of 4-bit values. At the moment this uses objects with some approximation of 4-bit storage but should really use a contiguous sequence of bytes.

Start/finish points are no longer visible

They're just white on white

Evaluate expressing the route stepper itself in WASM

The big problem here is dynamic storage