In the previous post I discussed how to  code an efficient tile engine running on Apple II computers that can be used to write a Rogue-like game.

This engine is neat but, alas, the player can see the entire portion of the dungeon that surrounds him: he gets the magic ability to see through walls. Getting lost in the dungeon and being surprised by enemies is important for such a game to be fun. Thus, we have to complete the engine with a convincing “line of sight” algorithm!

All the code is available on Github.

A better sense of immersion

Here are two versions of the engine:

No field of view

This one does not handle the line of sight. It is the very same presented in the previous post.

With Field of view

This one however, hides the tiles that cannot be viewed by the player

As you can see, it will be easier to get lost in the dungeon and to stumble upon hidden enemies. The sense of immersion will be way better.

Raycasting

The easiest way to obtain a “realistic” line of sight from a point in the world is to perform “raycasting”. Imaginary “rays” are casted away from the player and sent in every direction. If they cross a new tile, it is displayed. If this tile is an obstacle, the rays stop here. Otherwise, it goes through the next tile, and so on

8 rays casted to the top.

Eight rays (red) casted from the player (green), going to the edge of the view.

8 rays casted to the top.

Ten rays going to the top edge of the view. No obstacle.

The same rays, five of which are blocked by a non-transparent tile.

This algorithm is easy to program and systematic: there is no special case. A tile either is transparent or is not. Quite simple!

But there are two drawbacks, which are apparent in the illustrations above.

  1. Many rays can traverse the very same tile, resulting in useless transparency tests. In our case of programming for Apple II, however, it is faster to accept it than to code something trying to avoid it.
  2. When the view sports a very low resolution, such as our 10×10 grid, the path taken by some rays may appear a little bit counter-intuitive.

 Ray-casting is a very common technique. For instance, it is often the basis for pseudo 3D game engine such as Wolfenstein 3D. Rays are casted away from the screen and the distance traveled until bumping into an obstacle will be used to scale it, resulting in an impression of distance and perspective.

Implementation

Computing the rays

We know that we will project the rays from the player to the edge of the screen, but how will we devise their path?

Fortunately there is an algorithm perfectly suited for this task: the Bresenham’s line algorithm. Its purpose is to approximate a straight line in a raster space (aka a grid of pixels).

 Alas, it would require a non-negligible amount of computing power, at least at the scale of the Apple II (remember: an 8-bit 6502 @1MHz!). But, in our tile engine, the player’s position is fixed in the screen. This is our saving grace: the rays will only have to follow a unique path that may be computed in advance. And that’s is exactly what we will do! A Python script will compute the 36 rays that are required and save them into a structure written in assembly that can be pasted into the code.

 And the cherry on top is that there is a Python package implementing the Bresenham’s algorithm. When they say there is a Python package for everything, they don’t lie!

 A ray will be represented as a list of offsets: the 8-bit offset from the upper left corner of the view, and the 16-bit offset corresponding to the same tile in the “World”. Note that we only need an 8-bit offset (thus an 8-bit addition) in the case of the View, because the view is 256-byte aligned and is less than 256 long.

 Here is an extract of the python code generating the rays in assembly to be pasted into the engine’s code:

Resulting in:

Casting the rays

The cast function is quite simple.  The only things it has to do are:

  1. Initialize all the tiles of the view as “non-visible” tiles.
  2. Iterate over the rays.
    • For each tile of the ray read its value in the “world”
    • If it’s a “visible” tile, copy its value into the view and process the next tile of the ray
    • If it’s a “non-visible” tile, go to next ray

Computing the pointers to the source tile from the “World” and the destination in the “View” is only a matter of adding the 16-bit offset to the address of the World and the 8-bit offset to the start of the view.
Those offsets being constants, pre-calculated by our Python script, casting the rays is fast enough. Even on the 1MHz CPU.

ACTORS::NOT_TRANSPARENT is declared in the same enumeration as the TILES of the World. Every TILE inferior to ACTORS::NOT_TRANSPARENT is transparent. It is a floor, an opened door…

The time required to “build the view” using this code will be highly dependent of the player’s environment as the inner loop breaks on any non-transparent TILE.

This variability can be foreseen by counting the cycles.

  • Max time:
    • The player lies in open-space, such as a hall or a garden:  around 20ms
  • Min time:
    • The player is surrounded by walls. Not very realistic regarding the gameplay 😉 : around 6ms
  • “Realistic” Min time:
    • The player is in the middle of a long corridor : around 8ms

By the way, manually counting the cycles is a pain in the ass. Sometime I’ll have to find a way to properly profile my code 😉 !


3 Comments

Mark D. Overholser · July 25, 2019 at 23:55

Did you have a Link to the Python Script for Ray Casting???

Leave a Reply

Your email address will not be published. Required fields are marked *