Step II: Defining Worlds

INTRODUCTION:
Raycasting isn't technically a 3D process, as can be proved by the way maps are implemented. It's merely a clever illusion. The image that is displayed on-screen gives a 3D appearance, but to simplify the rendering and mathematics, all calculations are done in 2D (the screen is 2D also, it's just that the image has perspective, which tricks the eye). The rest of this page will explain how the raycaster's world will be represented.

RAYCASTER WORLDS:
A raycasting world (or map; whichever you prefer -- I use the two terms interchangeably) is just a grid of variable size; basically like a sheet of graph-paper (thus, it's flat and has no ability to have different layers; no rooms above rooms) making it 2-dimensional. Each square in the grid (cells as I'll refer to them from now on) is either empty or it has a wall or object in it. For example, consider the diagram below:
images/fig5.jpg
fig5: A few cells of a sample map

The above shows a section of a map, as would be drawn on a sheet of graph-paper. The shaded areas are cells that are occupied by walls. Notice that the walls are square blocks and don't go over cell boundaries (the black lines). This is one of the geometric constraints of raycasting, used to simplify the mathematics behind the rendering process. Now, to simplify the rendering even more, we'll split the world into two different areas: the lines that go horizontally across the grid, and the lines that go vertically up/down the grid. If you wish, you could have two arrays, one for holding walls that run along horizontal intersections, and one for storing walls that go along the vertical intersections, but this isn't necessary; however, it does allow the walls to be represented as individual lines rather than square blocks.

fig5 also shows why we chose to ignore the negative values on the X and Y axes. It allows us to place the origin at the top-left of the map, which eliminates the need for us to handle negative coordinates (thus simplifying array indexing, etc.) If you start with the top-left cell of the map, it's coordinates are (0,0). The next cell is (1,0), then (2,0), etc. Now, instead of increasing the Y axis upwards, we changed it so that it was increasing downwards. This also fits with how we index arrays. For example, the square underneath the origin is (0,1), then (0,2) etc. If we didn't swap the Y axis around, the square underneath the origin would be (0,-1); just try accessing a negative element in an array :)

THE CELLS:
The cells are all uniformed in size. You don't get one cell that's 20 units square and another that's 30 units square. They've all got to be the same size (which makes the calculations slightly easier, and speeds up the casting of rays). The general size is usually 64x64 units. This is chosen for a number of reasons. Firstly, it's a power of 2, which means that instead of dividing by 64 you can logically shift right 6 places (2 ** 6 = 64), and instead of multiplying by 64 you can logically shift left by 6 places, thus speeding up calculations involving the size of cells. The other reason is that it looks right. The blocks aren't too chunky and they aren't too small. The smaller the blocks, the better the world looks when it's displayed; unfortunately, it also means that the rendering process is somewhat slower. The bigger the blocks are, the quicker they render; bigger blocks also produce blockier results. So, 64x64 is a good size because it balances looks with speed.

The cells also have to be stored in memory and a data file (the data-file isn't necessary, but it allows your engine to be more flexible and modifiable). However you wish to store the world information is up to you and your needs. In my engine, which uses variable height walls, I've got a structure defined for holding cell information in memory, with similar elements to the following:

define structure {
        integer   height;       /* Height of wall (if this cell has one) */
        texture  *floor;        /* Pointer to floor texture */
        texture  *wall;         /* Pointer to wall texture */
        texture  *ceiling;      /* Pointer to ceiling texture */
        integer   flags;        /* Set of flags (ie. cell is a door) */
} world_cell;

world_cell        cells[64][64];/* Array holding the wall data */

I use an array of world_width * world_height 'world_cell' entries, but you need not have anything remotely similar to that above. For example, you might not want walls that can be different heights -- which speeds up the engine significantly -- which would mean that you don't need the 'height' field. The same goes for floor and ceiling textures; you might decide that you don't want the floors and ceilings to be textured, so you could omit their fields from the structure also.

CONCLUSION:
This file only covered the simple aspects of world representation. There are extensions, such as adding objects and doors, but these will be covered later. The next step is to talk about the projection plane, which holds the viewing attributes.

Last updated:

02/11/00

Menu

Step II: Defining Worlds