When I did the scene with forest, I added character there (btw, I got it here), I thought that he cannot just stay on the map, he must know how to move. Not just from point A to point B but with regarding obstacles. Since our beloved character is in forest, he must know how to go around trees. This is complete new exeprience for me, and perhaps game developer guys will find this text amateurish, but it was fun for me to dig into WebAssembly and A* algorithm.
A*
If you imagine that The Surface as a grid, then all you're gonna do to find tha way is to search the in graph. One of the most optimal ways to do so is to use 62-years old algorithm. Each grid cell has passabilty factor (the higher it is the harder is the way). Some cells (the ones with trees) are impassable at all. The goal is to find the fastest path. We will use heuristic for that, and it will be indicating how good the decision to choose one or another direction will be.
I'm a frontender and it turns out I'm interested in web platform features, so the right start point will be to use javascript implementation. There's a magnificent library PathFinding.js which contains a lot of heuristics and implementation variants. For me it looks like Best First Seacrch with Octile heuristic is the most optimal. Additionaly it can reduce the way to several critical points where the turns are. Link to source code
Performance profile
I want more power
Javascript has one thread and if your map is big enough or tricky enough, the calculations may affect UI responsivness. The browser is busy enough by performing a bunch of rendering work in 16ms and we could possibly help him by using a web worker. Doing so will free the main thread for some more important stuff. Link on the same code as above but hidden inside web worker (Github).
Performance profile
I said more power
I'm sure that js version uses all the optimization tricks like hidden classes and inline caching, and by using TypeScript you can be somehow sure that the parameters passed in Pathfinding.js methods always will be the same type (and it won't cause deoptimization). But what's more interesting for me is to move this process to WebAssembly and to enjoy near-native speed.
WebAssembly can be compiled from a dozen of languages including C++, Go and Rust. Since I can't use any of those, I chose to find a ready solution and compile it for my needs. Thanks to Aaron Powell's great explanation it took me like a day. The thing is (and it mentioned in the article) that Wasm that is compiled from Go behaves as a program rather than a library, so there's possibility to use state in it and not to initialize grid with obstacles every time you want to use it. Keeping in mind that in this particular WebGL scene wasm module will be invoked on mouse move event, this may save some resources. On the other hand, this could possibly be a problem:
- if a module throws an exception, then the thing that won't let Go script end closes itself and thus subsequent calls will be impossible;
- Go doesn't export any functions, instead it registers them in global scope;
- it can use global scope to modify DOM, which frightens me a bit.
Performance profile
More!
Since I went so far, why not to implement A* myself using AssembyScript? I'm very excited about it's possibilities. AssmeblyScript is more strict TypeScript version with some difference in basic types (ex. Map.keys() returns an array and not an iterator). By the way, it's always possible to convert AssembyScript to regular TypeScript pretty easy. Result
Performance profile
What to do with all this?
I hoped that a simple migration from browser level to WebAssembly gives me performance boost. But as you may see from performance profiler sceenshots, there's no much difference. Sometimes Wasm works even worse when you move the pointer to fast or move the camera around the scene. FPS may be 1-2. In the end, I'd prefer JS version because it's simpler, more stable and more convenient.
Update
Simple build optimizations may speed up WebAssembly version up to 4 times. ¯\_(ツ)_/¯
P.S.
Yeah, I know that he doesn't go anywhere. But he doesn't hurry :)
13 july 2020