I needed fast any angle path finding. I implemented it in pure JS using only typed arrays but it ended up being to slow. So I re-implemented it in C / Webassembly and it's 60x faster. Enjoy.
Implementation based on Alex J. Champandard's article: http://aigamedev.com/open/tutorial/lazy-theta-star/
The output .wasm
file is around 4kB.
You can find an interactive demo running directly from git here: https://md5crypt.github.io/thetastar/
You need to install upstream emscripten to compile the Webassembly part
git clone https://github.com/emscripten-core/emsdk.git
./emsdk install sdk-upstream-64bit
./emsdk activate sdk-upstream-64bit
source emsdk_env.sh # set up env
After that is should be a simple make all
but emscripten changes their s*it so often that it probably will not work when you try it :)
To build the demo first do a npm install
and then make demo
You have to options:
- get the pre-compiled
.wasm
file from the demo folder and use it with thetastar.ts in your project. See the demo code for a good example how do do it. - if you already are using Webassembly just dump the c source to your project. The only dependency is malloc.
A single class named ThetaStar is exported. It's constructor is private and instances should be created via ThetaStar.create
factory function.
An async factory function.
wasm
is an ArrayBuffer, Resource or a url to the wasm file.
memorySize
is the amount of memory to allocate. This should be about 24 * max pixel count. For the demo that runs on 1024x1024 bitmaps thats 24 * 1024 * 1024.
The function returns a promise that resolves to the created instance object.
Load an input bitmap into the Webassembly memory. Only one bitmap can be loaded at a time, calling this function again will replace the old bitmap with a new one.
data
is a Uint8Array with byte per pixel. Any value other than 0
is a "walkable" surface.
width
/ height
are bitmap dimensions
Run theta* on pre-loaded image data.
start
, goal
are coords of the start and end point represented as input bitmap indexes (x + y * width)
opt
is the theta* heuristic scaler. Use 1 for best paths (no scaling) and values 1 - 2 for faster sub-optimal results. You can play with this value in the interactive demo.
The function returns an array of points (bitmap indexes) that should be connected with lines to create the path or null
when not path was found.
This is a simple function that finds the closest non-zero bitmap pixel to any arbitrary point. It executes a linear search which should be faster for small bitmaps than any smarter solution.
The function return the found point in form of the input bitmap index.
Two functions are exported that do the same thing as their JavaScript conterparts in thetastar.ts
:
uint32_t find_closest(grid_t* grid, int32_t x0, int32_t y0);
uint32_t* theta_star(grid_t* grid, uint32_t start, uint32_t goal, double opt);
The only difference it the grid
argument which is a pointer to the following structure holding the bitmap data:
struct grid_t {
uint32_t xsize;
uint32_t ysize;
uint8_t data[0];
};