{"id":3188,"date":"2026-03-01T23:00:59","date_gmt":"2026-03-01T23:00:59","guid":{"rendered":"https:\/\/timallanwheeler.com\/blog\/?p=3188"},"modified":"2026-03-14T16:51:29","modified_gmt":"2026-03-14T16:51:29","slug":"into-depth-shadow-casting-portals","status":"publish","type":"post","link":"https:\/\/timallanwheeler.com\/blog\/2026\/03\/01\/into-depth-shadow-casting-portals\/","title":{"rendered":"Into Depth – Shadow Casting & Portals"},"content":{"rendered":"
\n
\"\"<\/figure>\n<\/div>\n\n\n

A debug view showing shadow cast segments from the vantage point of the actor.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Last month we covered the unified action system, in which we built some basic things players can do with their heroes, and set the stage for fancier futures and actions for enemy agents. The most significant action was moving, which was built based on a GridView<\/em> of what the actor sees from their current vantage point. As noted in that post, we eventually wanted to expand the grid view to include edge information, such as thin little walls and platforms, but also portals<\/em> that act as non-Euclidean connections to other parts of the map.<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

Here we have a simple two-tile room with a loop-back portal on either end. The result – the hero can see a bunch of versions of themselves!<\/p>\n\n\n\n

In the last post, I said I’d be adding other entities in and adding more actions, but I decided that the map representation was so fundamental that prioritizing getting these portals in was more important. Any changes there would affect most other systems, so I wanted to get that done first.<\/p>\n\n\n\n

Grid Representation<\/h1>\n\n\n\n

Prior to this change, the underlying level geometry representation, the Grid,<\/em> was just a 2D array of cells:<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

<\/p>\n\n\n\n

After this change, I wanted to represent both the cells as well as the edges between them:<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

<\/p>\n\n\n\n

This was achieved by adding two additional 2D arrays, one for the horizontal edges and one for the vertical edges. There are definitely other ways to do this, but I felt that (1) this was simple, and (2) there are differences between those edge types. A player might stand on a platform but have a door that they can open, for example.<\/p>\n\n\n\n

The edges are single-bit entries, to keep things efficient. If we need more information, we can index into a separate array. I’m currently using the first two bits to identify the edge type, and the remaining 6 bits, if the edge is a portal, index into a Portal<\/em> array. The Portal stores the information necessary to know which two edges it links.<\/p>\n\n\n\n

This change has the immediate consequence that getting the cell neighbor in a given direction does not necessarily produce the Euclidean neighbor. Its second consequence is that cells no longer need to be solid or not — the edges between cells can instead be solid. This slightly simplifies cells.<\/p>\n\n\n\n

Grid View Representation<\/h1>\n\n\n\n

The Grid View<\/em>, introduced in the last post to represent the level geometry as seen by an actor from their vantage point, can now represent views where the same underlying cell might show up multiple times due to portal connections. Furthermore, we might have weird cases where one square cell might contain slices from different areas of the map:<\/p>\n\n\n

\n
\"\"<\/figure>\n<\/div>\n\n\n

The green arrow points at a view cell which, due to the portal (magenta), has two sections of different grid cells.<\/p>\n\n\n\n

Before, the grid view was a simple 2D array with one cell per tile. Now, that is no longer the case.<\/p>\n\n\n\n

The updated grid view is organized around ViewNodes<\/em>, ShadowSegments<\/em>, and ViewTransforms<\/em>:<\/p>\n\n\n\n

struct GridView {\n    \/\/ The grid tile the view is centered on\n    CellIndex center;\n\n    \/\/ The first ViewNode in each view cell.\n    \/\/ 0xFFFF if there is no view node in that cell.\n    u16 head_node_indices[GRID_VIEW_MAX_X][GRID_VIEW_MAX_Y];\n\n    u16 n_nodes;\n    ViewNode nodes[GRID_VIEW_MAX_NODES];\n\n    \/\/ Shadowcast sectors.\n    u16 n_shadow_segments;\n    ShadowSegment shadow_segments[GRID_VIEW_MAX_NODES];\n\n    \/\/ The transforms for the view as affected by portals.\n    u8 n_view_transforms;\n    ViewTransform view_transforms[GRID_VIEW_MAX_TRANSFORMS];\n};<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
Most of the time, a given cell in the grid view will contain a single cell in the underlying grid. However, as we saw above, it might see more than one. Thus, we can look up a linked list of ViewNodes<\/em> per view cell, with an intrusive index to its child (if any). Each such node knows which underlying grid cell it sees, whether it is connected in each cardinal direction to its neighbor view cells, and what sector of the view it contains:<\/p>\n\n\n\n
struct ViewNode {\n    CellIndex cell_index;\n\n    \/\/ Intrusive data pointer, indexing into the GridView nodes array,\n    \/\/ to the next view node at the same ViewIndex, if any.\n    \/\/ 0xFFFF if there is no next view node.\n    u16 next_node_index;\n\n    \/\/ Whether this view node is continuous with the view node in the\n    \/\/ given direction.\n    \/\/ See direction flags.\n    u8 connections;\n\n    \/\/ The sector this view node represents.\n    Sector sector;\n\n    \/\/ The stencil id for this view node.\n    \/\/ Identical to the transform_index + 1.\n    u8 stencil_id;\n};<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
We can now represent cases like the motivating portal scenario:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
I’ve given the region on the other side of the portal different tile backgrounds to make it more obvious.<\/p>\n\n\n\n
In the last post, we constructed the grid view with breadth-first search (BFS) from the center tile. Now, since we’re working with polar segments that strictly expand outwards, we can actually get away with the even simpler depth-first search (DFS). Everything is radial, and the farther out we get, the narrower our beams are:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
A debug view showing the final shadow cast segments.<\/p>\n\n\n\n
The search logic is a bit more complicated given that we have to narrow down the segment every time we pass through a tile’s edge, we’re saving view nodes in the new intrusive linked list structure, and edge traversals have to check for portals. Solid edges terminate and trigger the saving of a shadow segment.<\/p>\n\n\n\n
Portal traversals have the added complexity of changing physically where we are in the underlying grid. If we think of the underlying grid as one big mesh, we effectively have to position the mesh differently when rendering the stuff on the other side of the portal. That information is stored in the ViewTransform<\/code>, and it is also given its own stencil id.<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
A debug view of the view nodes. We fully see many cells, but some cells we only partially see. The origin is currently split into four views in order for view segments to never exceed 180 degrees. <\/p>\n\n\n\n
Above we can see an overlay of the resulting view nodes. There is a little sliver of a cell we can see for a passage off to the left, and there are the two passages, one with a portal, that we can see on the right. The platforms (little brown rectangles) do not block line of sight.<\/p>\n\n\n\n
The Stencil Buffer<\/h1>\n\n\n\n
Now that we have the grid view, how do we render it? It is pretty easy to render a square cell, but do we now have to calculate the part of each cell that intersects with the view segment? We very much want to avoid that!<\/p>\n\n\n\n
Clean rendering is accomplished via the stencil buffer<\/em>, which is a feature in graphics programming that lets us mask out arbitrary parts of the screen when rendering:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
<\/p>\n\n\n\n
We’ve already been using several buffers when rendering. We’re writing to the RGB color buffers, and 3D occlusion is handled via the depth buffer<\/em>. The stencil buffer is just an additional buffer (here, one byte per pixel), that we can use to get a stenciling effect.<\/p>\n\n\n\n
At one byte (8 bits) per pixel, the stencil buffer can at first glance only hold 8 overlapping stencil masks at once. However, with our 2D orthographic setup, our stencil masks never overlap. So, we can just write 255 unique values per pixel (reserving 0 for the clear).<\/p>\n\n\n\n
We simply write the shadow segments to the stencil buffer, setting the buffer to the appropriate stencil ID:<\/p>\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n
The stencil buffer has four stencil masks – the red region in the main chamber, the little slice of hallway to the left, the green region through the portal leading back into the same room, and the yellow region through a different portal to an entirely different room.<\/p>\n\n\n\n
Our rendering pipeline now needs to support masking with these stencil IDs. In January we covered the render setup<\/a>, which involved six different types of render commands that the game could send to the backend:<\/p>\n\n\n\n