Monday, May 15, 2017

WallyFOV: Shadow-casting field-of-view implementation with walls

I've been working on a field-of-view algorithm for 2d tile-based games (e.g. roguelikes).  There's a particular killer feature I mean to include in the algorithm, which I won't reveal in this post, but I decided to go ahead and release the slightly simpler version because I think it might be useful on its own.

It's called WallyFOV.  It's basically an implementation of recursive shadowcasting in TypeScript, but with support for walls.

Go ahead and check out the demo.  (and thanks to EasyStar.js for the pathfinding algorithm used in that demo, and from which I kindof copied the demo page style)

Recursive shadowcasting works by scanning outwards from the player looking for obstructions.  When something is found, a shadow (represented by two angles) is added to a shadow list.  Overlapping shadows are merged to keep the algorithm running quickly.

In this particular variant, a tile is considered visible if there exists any line from the center of the player's tile to any point within the target tile.  There are some complications around dealing with diagonally-adjacent bodies, which you can read about in the algorithm overview, but overall it's a pretty simple algorithm to understand.  It's a bit tricky to implement and optimize, however.

I spent a little extra time optimizing it to run in V8 (at least the version of V8 in node.js 7.9).  Along the way I learned how to use node's --trace-deopt, and discovered some very unexpected optimization tips, mainly having to do with newer ECMAScript features.

For instance, this version of V8 doesn't optimize "compound let/const assignment".  Meaning if you declare a variable with let or const, and then use something like X += Y, your function will be deoptimized.  Simply using X = X + Y instead avoids that trap.  The general lesson here is that JavaScript is apparently changing too rapidly to rely on the engine optimizing things according to your intuition.  This is probably true with any language, to a certain extent.  But, come on, X = X + Y?

No comments:

Post a Comment