WarpField: portal-casting field-of-view algorithm

Here's WarpField, a "portal-casting" field-of-view algorithm.  This goes beyond the usual field-of-view mechanism by adding support for portals.  A portal basically connects an edge between tiles in one map with an edge in a (possibly different) map.  WarpField computes the field of view through the portal, and also returns what the player can see at each location.  This could be useful for:

Going up (or down) stairs.

• Continuous overworld movement from zone to zone
• Over/under pathways, such as bridges and tunnels
• Smooth transitions of elevation changes, like stairs
• Crazy magical effects, like portals to alternate dimensions.

In a previous post, I discussed WallyFOV, my implementation of a 2d grid-based field-of-view algorithm using shadow-casting.  For games that don't need portals, that algorithm is a better choice, since it's simpler and faster.  Unlike many field-of-view implementations, WallyFOV supports walls, which is a prerequisite for adding portal support.

"Portal-casting" is basically an extension of shadow-casting.  Shadow-casting tracks contiguous ranges of angles of rays that are visible from the player.  When a wall is encountered, we simply cut that range of angles out (causing a shadow).  For portals, instead of cutting that range out, we split it off into a new, separate range.  For each range we track which map the range "sees", and the relative tile offset into that map.

Entering a tunnel.

For each location that isn't completely in a shadow, we now have to decide which map we're seeing at that location, and which tile in that map goes there.  This can be tricky, because we might see the location more than one way at a time.  Maybe some rays reach the location after passing through a warp to map A, while others reach it after a warp to map B, and some reach it without passing through any warps at all.  In a 2D tile-based game we don't really want to show slices of a tile, we want to just pick one to show.  To resolve this ambiguity, WarpField has an order of preference: rays closest to the center are preferred, followed by rays that go through fewer warps, and finally ties are broken by the map with the lowest "id".

There are a lot of edge cases to consider, and most of them are touched upon in the algorithm overview.  I did a lot of testing and benchmarking, and I'm pretty sure it works according to spec, but there are some asymmetries that I'd like to remove (due to the order in which locations are visited).  I think I can clean that up by switching to fractional math instead of floating-point math.  Nevertheless, it's fairly robust, you can throw crazy cases at it like warps into the same map (such that the player can see themself through it), and rays that pass through many warps at once.

I think this could add a lot of potential to roguelike games.

WarpField (demo)

(github repo)