Ray-casting for the tile visibility table

The pre-populated tile visibility table that helps speed up landscape drawing

Drawing the landscape in The Sentinel is a big effort; there's an awful lot of complicated maths involved, and if there's one thing that's time-consuming on an 8-bit computer, it's complicated maths.

One way of speeding things up is to do as much maths as you can in advance, and then cache the results so you don't have to continually repeat those calculations. The problem is that the BBC Micro only has 32K of memory, so there isn't a lot of space for caching large amounts of data. The game tries to address this problem by implementing a set of drawing tables to store just the more recent results that we need for the task currently at hand, and then discarding those results when they are no longer needed (see the deep dive on the drawing tables for details).

There is one proper, old-fashioned cache table in The Sentinel, though, and that's the tile visibility table. We'll take a detailed look at the table in a moment, but let's start with some visualisations that should make things a bit easier to understand.

Visualising tile visibility
---------------------------

I love it when code mirrors reality, and the tile visibility table is a great example. To show you what I mean, look at this heatmap of the BBC Micro's memory when the game is drawing landscape 0000 for the first time:

This is a memory heatmap, and it shows the entire computer's memory, from &0000 at the top to &FFFF at the bottom, with one pixel per byte. The colours indicate recent activity: red indicates a data byte being written, green indicates a data byte being read, blue indicates an instruction byte being read, and black indicates no recent activity. Combinations of these colours show two operations happening close together in time, so, for example, yellow indicates a data read and a data write happening in quick succession (as yellow is red and green combined).

I'll explain exactly what's going on here at the end of the article, once we've analysed the algorithm, but for now just take a look at the left-hand side, about halfway down, where you can see this strange burst of activity:

On the right, you can clearly see something that looks like a kind of radar screen, almost as if a lighthouse is casting a beam of light across a landscape of some kind. Which, of course, is no coincidence...

As we'll discover in this article, the tile visibility table records which tiles are visible from the player's position, and we calculate this using a technique called "ray-casting" or "ray-tracing". In a sense, we actually do turn the player into a lighthouse that casts its light over the landscape; we want to work out which parts of the landscape it lights up, and which parts are in darkness, as that will tell us which tiles are visible to the player and which are hidden.

Astonishingly, we can actually see this algorithm working in the above animation - the right-hand part literally shows the beams of light as they sweep around the landscape.

To explore this further, let's have a deeper look at the visualisation and see if we can tie it to the actual shape of the landscape. To make this work, we need to flip the image vertically, like this:

This produces a layout that matches the landscape orientation that we normally see in the landscape preview, with row 0 at the front (i.e. the bottom of the heatmap image) and row 31 at the back (i.e. at the top of the heatmap image).

As a further enhancement, let's reduce the heatmap to just the green component, as it's a bit intense with the red and yellow flashes, and let's slow down the ray-casting process a bit. We can then compare the algorithm's in-memory activity with the layout of the landscape.

Here are a couple of contour maps of landscape 0000, along with the heatmap; the blue colours in the contour maps indicate lower altitudes while the brown colours indicate higher ground. The player's position is shown in red, and if you look at the slowed-down heatmap, you can see that it shows beams being shot out from the player's location as the algorithm "feels" the shape of the landscape. Each beam is traced from the player towards the tile being processed, and the progress in the left part of the heatmap shows the algorithm working through the landscape, row by row and from top to bottom, tracing the beam from the player's position to each tile in turn.

Here are the contour maps and heatmap for landscape 0278, which is a pretty flat landscape so the radar sweep does detect quite a number of tiles, though the hill to the left of the player blocks quite a lot of the bottom-left quarter from view:

Here are the contour maps and heatmap for landscape 1122, where the player's starting position is in a deep valley with a really restricted view of the landscape (almost all of which is looking upwards, out of the hole):

Here are the contour maps and heatmap for landscape 3073, where the player is at the back of the landscape and can only see tiles along the rear strip of landscape and in a vertical line towards the front row of tiles:

And finally, here are the contour maps and heatmap for landscape 9999, which has some interesting diagonal view lines from the player in the bottom-left corner of the landscape, all the way to the top-right:

We'll come back to these visualisations at the end of this article, and will look at exactly how the algorithm relates to the heatmap and how it is that we can visualise the algorithm in memory in the first place. But before we can do that, we need to explore the algorithm itself, so let's do that next.

The tile visibility algorithm
-----------------------------

As we've discussed above, the game calculates the visibility of every tile in the landscape, from the perspective of the player, and stores this in the tile visibility table. The idea is that this will save time when we have to draw the landscape, which we need to do when panning the screen or performing a U-turn. If we know in advance that a part of the landscape isn't visible to the player and never gets seen by them, then we know we don't have to draw it, and that saves a lot of time.

Specifically, the GetTileVisibility routine populates the tileVisibility table with one bit for each tile, storing a 1 if the tile is visible from the player's point of view, or a 0 if the tile is not visible. When we come to draw the landscape tile by tile, part 3 of GetTileViewAngles takes this visibility value and applies it to the tileViewData drawing table by zeroing the entry when a tile is not visible, and this then determines whether the DrawTileAndObjects routine draws the tile or not. In this way, tiles that the player can't see don't get drawn.

When populating the tileVisibility table, the GetTileVisibility routine makes use of the two transitory drawing tables at oddVisibility and evenVisibility. These store the visibility of individual tile corners in the most recently processed odd and even tile corner rows, and they use the drawingTableOffset and drawingTableIndex variables to manage access to the cached data, just as with the other drawing tables. For a full description of how the drawing tables work, check out the deep dive on the drawing tables.

So it's the GetTileVisibility routine that populates the tileVisibility table and produces the heatmaps we looked at above, so let's dive in further. Here's a top-level summary of this routine, which we will explain in detail below:

• Set drawingTableOffset = 0 so the call to first call to GetRowVisibility (for tile row 31) will populate the table at oddVisibility with the tile visibilities of the row being analysed.
• Zero all 128 bytes of the tileVisibility table, so by default all tile corners are marked as hidden.
• Call GetTileAltitudes to calculate tile corner altitudes and maximum tile corner altitudes for each tile in the landscape.
• Set zTileRow = 31 and call GetRowVisibility to calculate whether each tile corner in the rearmost row is obscured from the player by any intervening landscape, putting the results into 32 entries in the drawing table at oddVisibility (as drawingTableOffset = 0) as follows:
  • Store %00000000 if the tile corner is not visible from the player's position.
  • Store %11111111 if the tile corner is visible from the player's position.
• Loop through each tile row, stepping forwards from the rear row to the front row and doing the following for each row:
  • Decrement zTileRow to move forwards by one row (so we start this loop with zTileRow = 30, for the rear tile row).
  • Flip the value of drawingTableOffset between 0 and 32 with an EOR #32 instruction, so that it points to evenVisibility (if the previous row's results were stored in oddVisibility) or oddVisibility (if the previous row's results were stored in evenVisibility). This means the current row will be stored in the different drawing table to the previous row, and we flip between the two as we work through the rows.
  • Call GetRowVisibility to calculate whether each tile corner in the current row is obscured from the player by any intervening landscape, putting the results into 32 entries in the drawing table pointed to by drawingTableOffset, storing %00000000 for not visible and %11111111 for visible.
  • Work through the 31 tiles on this row from right to left, and do the following:
    • If this tile is flat and at a higher altitude than the player, then this tile is not visible to the player, so capture this in the table by clearing the tile's bit in the tileVisibility table.
    • Otherwise mark this tile as being visible (i.e. a set bit in tileVisibility) if any of the tile corners in this tile are visible, or mark this tile as being not visible (i.e. a clear bit in tileVisibility) if none of the corners are visible.
  • Loop back to process the next row forward until we have processed all tiles in the landscape.

Once we populate the tile visibility table, it will be usable whenever we have to draw the landscape, and its contents will remain valid until the player moves to another tile. If the player performs a U-turn, then we don't have to recalculate the tile visibility settings, as the player hasn't moved to a new tile, they've just turned around, and that doesn't affect tile visibility from the point of view of the player, as the player is still in the same place; this is why performing a U-turn is a quicker process than transferring to a new tile, as the latter process needs to repopulate the entire tile visibility table from scratch.

The two key parts of this process are the routines at GetTileAltitudes (which fetches tile altitude data) and GetRowVisibility (which calculates tile corner visibility). We'll look at both of the main routines next, but first a quick note on the structure of the tileVisibility table.

Structure of the tileVisibility table
-------------------------------------

The position of a tile's bit within the tileVisibility table is calculated in a rather complicated manner, presumably to make it harder to follow what's going on (there's quite a bit of this kind of thing in The Sentinel - see the deep dive on anti-cracker checks for more of them).

To get the position of a tile's individual visibility bit within the table, we take the tile's column and row numbers, each of which are in the range 0 to 30, and we calculate both the index of the relevant byte within the table (in the range 0 to 127), and the index of the relevant bit within that byte (in the range 0 to 7).

The calculation is as follows. We get the index of the byte within the tileVisibility table by constructing a number in the range 0 to 127 where:

• Bit 7 is clear.
• Bits 4-6 contain bits 2-4 of the column number.
• Bits 0-3 contain bits 1-4 of the row number.

Then the index of the bit within that byte is given by a number in the range 0 to 7 where:

• Bit 0 contains bit 0 of the of the tile row.
• Bits 1-2 contain bits 0-1 of the column number.

There could be a method to this madness, but if there is, I haven't worked out what it is! But what is does mean is that every time we want to read or write a visibility bit in the table, we have to calculate the byte and bit indexes from the tile coordinates in this manner.

Calculating tile altitudes and shapes
-------------------------------------

The first major stage in the GetTileVisibility process is to fetch tile altitude data by calling the GetTileAltitudes routine, which we'll look at here. This routine calculates the altitude for each tile corner in the landscape, and the maximum tile corner altitudes within each tile in the landscape. The results are stored in screen memory from &6000 onwards, though this is hidden from the player because at this point the screen has an all-blue palette, so anything we poke into screen memory will appear as blue and the player won't see a thing (see the deep dive on colours and palettes for more about palettes).

The first thing that's extracted is the altitude for each tile corner in the 32x32-corner landscape, as well as a single bit that records whether or not the tile anchored by the corner is flat (though this latter value is ignored for corners along the rear and right edges of the landscape, as those corners don't anchor any tiles). This data is calculated for each corner by the GetTileAltitude routine, which we call with bit 7 of considerObjects clear so the calculation ignores any objects on the tiles.

This data is then encoded into a single byte, one for each tile corner, like this:

• Bit 0 = clear if the tile anchored by this corner is flat, set if it isn't
• Bits 1-4 = the tile corner's altitude (1 to 11)

This is then stored in screen memory from &6000 onwards, as follows, starting with the front row (when zTile = 0) and working towards the back row as we progress forwards through memory:

• &6000 to &601F for tile corner row zTile = 0
• &6100 to &611F for tile corner row zTile = 1
  
  ...
• &7E00 to &7E1F for tile corner row zTile = 30
• &7F00 to &7F1F for tile corner row zTile = 31

The next step is to use these tile altitudes to calculate a maximum altitude for each tile, which is just the altitude of the highest corner in each tile. We work this out by simply working through the altitudes that we just stored, checking all four corners in each tile to extract the maximum altitude. This is then stored alongside the altitude data, interleaved as follows, with one byte for each tile in the 31x31-tile landscape:

• &6020 to &603E for tile row anchored by zTile = 0
• &6120 to &613E for tile row anchored by zTile = 1
  
  ...
• &7D20 to &7E3E for tile row anchored by zTile = 29
• &7E20 to &7F3E for tile row anchored by zTile = 30

This also leaves the following variables set to point to the two sets of altitude data, which we can use in the next step to fetch the correct values for calculating the tile visibility:

• (Q P) = &6000, which points to the altitude and shape data
• (S R) = &6020, which points to the maximum altitude data

Having extracted the altitude data, we move on to the visibility calculation itself, so let's look at that next.

Calculating tile visibility by row
----------------------------------

The second major stage in the GetTileVisibility process is to calculate the visibility of all the tile corners in a row by calling the GetRowVisibility routine. We can then convert the results into a sequence of tile visibility bits to store in the tileVisibility table once we return back to the GetTileVisibility routine, using the encoding technique described above.

The GetRowVisibility routine loops through each tile corner in the row, from right to left, in a loop that's split over part 1 and part 2 of the routine (there's an anti-cracker interlude in the middle that has nothing to do with the visibility checks, which is the only reason for there being two parts). The end result of this routine is to populate the 32 entries in the drawing table at drawingTableOffset (i.e. oddVisibility or evenVisibility), storing %00000000 if the tile corner is not visible from the player's position and %11111111 if it is visible from the player's position.

The process of working out whether a tile corner is visible is pretty involved, but essentially we take the vector from the player's eyes to the tile corner and step along it all the way from the player to the corner, checking as we go whether the vector hits any landscape. This technique is called "ray-casting" or "ray-tracing" because it's typically used to trace rays of light as they are cast between light sources and the eye, so a picture of a 3D scene can be built up one light ray at a time.

In our case we're not building up a picture from light rays, but we're effectively tracing the path of a straight line gaze from the player's eye to the tile corner, to see if that gaze hits any landscape in the process. You can think of it as shining a torch from the player towards the tile corner: if the light reaches the tile corner without hitting anything in-between, then the player can see the corner and we mark it as visible, but if the light hits a part of the landscape instead, then the player's view of that corner is blocked and we mark it as not visible.

Here's a breakdown of the most important steps in this process in the GetRowVisibility routine, starting with a few initialisation tasks:

• Set traceStepCounter = 255 to record the number of steps we perform as we work along the gaze vector (though we may change this below).

• Call GetObjectCoords to fetch the Cartesian coordinates of the player object.
• Work through all three axes in turn (i.e. z-axis, y-axis and x-axis) and calculate the distance along each axis from the player to the tile corner, and then divide this by 256. This gives us 1/256 of the 3D vector from the player to the tile corner, which is effectively the vector of a small step along the full vector (so starting at the player's eyes and performing 256 of these steps would trace along the full vector).
• If the tile corner is within 1.5 tile distances of the player along the longest axis, then we automatically mark this tile corner as visible and move on to the next tile corner (so close-by tiles are always considered potentially visible).

We now do an optimisation step. We could trace along the vector from the player to the tile corner in 256 steps by starting at the player's eyes and adding the 3D vector we calculated above, which would step us along the gaze vector in 256 steps, so each step would be 1/256 of the whole vector from the player to the tile corner. If, at each step, we check whether we have hit any landscape, then this process will work.

But given that the landscape is only 32 tile corners across in each direction, this would mean that most of the time we would be stepping along the vector while staying above the same tile. Instead we can scale up the size of our steps and do fewer of them, and as long as each individual step is smaller than a tile width, we can still check every landscape tile along the line of sight.

We therefore increase the size our 1/256 vector, doubling it as many times as we can so that it's as big as possible while still fitting into one byte (where one byte represents a fraction of a tile width). At the same time as we double the length of the vector, we halve the step count in traceStepCounter. This reduces the number of steps in the ray-casting process as far as possible while keeping the size of each step to less than one tile (so that the tracing process still steps through each tile en route).

So, to recap, we have taken the "gaze vector" from the player to the tile corner, divided it by 256 and scaled it up as far as possible while still keeping the vector within the dimensions of a tile, and traceStepCounter contains the number of times this "step vector" fits into the original vector from the player to the tile corner. We can therefore trace the gaze vector from the player to the tile corner by taking the player's coordinates and adding the scaled step vector traceStepCounter times, knowing that together, these steps will stop over every tile between the player and the tile corner in the process. We may stop over some tiles more than once, but that's OK.

We do this process one axis at a time, starting at the player's coordinate and adding the scaled step vector to step along the gaze vector from the player to the tile corner. (It's worth noting that the accuracy when stepping along the x- and z-axes is 16-bit, with one fractional byte, but the accuracy for the y-axis is 24-bit, with two fractional bytes).

At each step we fetch the maximum altitude for the tile that we are currently passing over in our gaze-tracing process, and then check it against the altitude of our current position along the gaze vector.

If the altitude of our current position along the gaze vector is lower than the altitude of the highest point of the landscape on the tile over which we are passing, this means the gaze vector has hit the landscape before reaching the end, so we mark the tile corner as not visible, stop tracing the beam and move on to the next tile corner.

If the altitude of our current position along the gaze vector is equal to or higher than the altitude of the highest point of the landscape on the tile over which we are passing, then the gaze vector is passing over the current part of the landscape, so we keep stepping along the gaze vector until we either hit the landscape or reach the tile corner at the end of the full vector (in which case the tile corner is deemed to be visible).

If we repeat this process for all the tile corners in the specified row and store the results in the relevant oddVisibility or evenVisibility drawing table, then we can return to the GetTileVisibility routine to calculate the final visibility for each tile in the row, and then the tile visibility table will be populated and usable whenever we have to draw the landscape.

This ray-casting approach is also used in-game when working out whether the player and enemies can see specific tiles, but that's implemented using an even more sophisticated algorithm, as it has to work out whether individual tile shapes or objects are getting in the way of the crosshair sights. See the deep dive on following the gaze vector for details.

Tying the algorithm to the heatmap
----------------------------------

Now that we know how the tile visibility table gets populated, let's take another look at the heatmap we saw earlier and see if we can tie its features into the algorithm:

I've used the b-em emulator to capture these heatmaps, and luckily the default heatmap in b-em shows the computer's memory in a grid, showing one pixel per byte in 256 rows of 256 bytes per row. This means that each row starts at &xx00 in memory, so it just happens to show each table row on a new pixel line, so the tables appear in the same shape as the landscape itself.

The heatmap is showing two tables in memory: the one on the left is at address &6000 and contains the altitude and shape data for all the tiles in the landscape, and the one on the right is at address &6200 and contains maximum altitude data for each tile. Both these tables are populated by the GetTileAltitudes routine that we analysed above.

So the heatmap starts with both tables flashing red as they are zeroed with a write (as red = write, green = read). Then the left table is populated with the tile altitudes and flatness bit, which keeps the table red, and then the right table is populated with the maximum altitudes by reading the altitudes from the left table, so the right table flashes red at the same time as the left table is read, so the left table turns yellow as red + green = yellow in the heatmap.

Next up, the algorithm works through the landscape, one tile at a time, and calculates that tile's visibility. This is done by the GetRowVisibility routine, and as we discussed above, it works along each tile row in the landscape from right to left, calculating each tile's visibility as it goes. We call this routine for each row, stepping through the rows from the back row to the front, and then we're done.

The amazing thing is that you can literally see GetRowVisibility's ray-casting process in the heatmap. As the routine works through the landscape, calculating each tile corner's visibility in turn, it does two things:

• It reads the altitude of the tile from the left table, which lights up the individual tile we are processing in green.

• It traces the gaze vector from the player to the tile corner that we are processing, and as the vector passes over each tile, the algorithm fetches the maximum altitude of that tile from the table on the right, to see whether the vector is hitting the landscape or passing overhead. So as we trace the vector, the heatmap lights up for each tile beneath the vector, until we either reach the tile we are processing or the vector hits the landscape.

So over the course of the entire algorithm, we get the following:

• The left table lights up the relevant tile entry as each tile is processed, and because we work through the landscape row by row, this gives us the sweeping effect we can see in the heatmap.

• For each tile that is processed, the right table in the heatmap traces out the gaze vector from the player to the tile, so over the course of the whole algorithm, we get a sweeping lighthouse radar effect that literally maps each of the traced lines from the player to every tile corner on the landscape.

And that's why we can visualise the tile visibility ray-casting algorithm using a memory heatmap. It's a fascinating glimpse into the way The Sentinel works under the hood...