Uses a modified variant of Lazy Theta* to reach performance goals while still being accurate.
The algorithm itself is in pathfind.rs, is relatively small, and is extensively commented. If you're curious how the crate or algorithm works I'd recommend reading through the comments in that file.
The benchmark relies on a fixed-seed random state.
To run the benchmarks, run cargo bench --features rand in shorai/
The demo involves time as part of the pathfinding algorithm, just to show that it's possible to.
All paths are precalculated and not modified on-the-fly. This means that the obstacle movements need to be known when the algorithm runs, which is the case for this demo.
To run the demo, run cargo run --release -- --help in demo/render/. Running without --release takes a long time.
As an example command, try cargo run --release -- --missiles 100 --seed 6424138677911309346:
out.mp4
The output ends up as individual files in an out/ folder to simplify debugging.
To merge them into a video using ffmpeg, run ffmpeg -r 20 -i out/step_%03d.png -c:v libx264 -vf fps=25 -pix_fmt yuv420p out.mp4.