_A RAYCASTING ENGINE IN C++_
by Mark Seminatore

Listing One

//  Copyright (c) 1994 by Mark Seminatore, all rights reserved.
//  Data.c: This module instantiates all the global data.

    #include "pcx.h"
    #include "ray3d.h"

    char *face[NUM_FACES];
    int MapWidth,      // run-time map width
        MapHeight;     // run-time map height
    char *map,         // raw map data
         *xzWalls,     // xz wall boundary map
         *yzWalls;     // yz wall boundary map
    unsigned VideoRow[200];           // Video row memory offsets
    unsigned char volatile ScanCode;  // modified by int 9 handler
    unsigned int volatile FaceIndex;  // current face bitmap to display
    unsigned int Frames=0;            // number of frames generated
    Pov_t Pov;                        // current Point-of-View
    long CosAngle,                    // movement trig values
         SinAngle;
    int HeightScale=10000;            // The wall-height aspect ratio
    PcxImage pcx;                     // structure for loading bitmaps
    int HeightTable[MAX_DISTANCE+1];  // table of height vs. distance
    long ScaleTable[MAX_DISTANCE+1];  // table of bitmap scaling factors
    char *bitmap[NUM_BITMAPS+1];      // array of bitmap tiles
    char *ScreenBuffer,               // pointer to frame memory buffer
         *screen;                     // pointer to video memory
    long RayX,RayY;                   // last coordinates of x and y
    int  iRayX,iRayY;                 // ...raycasts
    int FarthestWall;                 // distance to farthest wall in frame
    View_t View[VIEW_WIDTH];          // raycasting data
    long *Sine;                       // pre-calc'd trig tables
    long *Tangent;
    long *InvTangent;
    long *InvCosine;
    long *InvSine;
    long *Cosine;
    long *dxTable;        // pre-calc'd table of 64*tan(angle)
    long *dyTable;        // pre-calc'd table of 64/tan(angle)



Listing Two

//  Copyright (c) 1994 by Mark Seminatore, all rights reserved.
//  Ray3d.h: This header file declares all global data structures and constants

#ifndef __RAY3D_H
#define __RAY3D_H

    #define FP16          16
    #define FP20          20
    #define ROUND20       ((1L<<20)/2)

    #define CHECK_DIST    48L      // minimum distance from wall

    enum {NO_WALL,X_WALL,Y_WALL};  // wall struck codes

    #define MAX_DISTANCE	2048
    #define MIN_DISTANCE  10

    #define BITMAP_WIDTH	64
    #define BITMAP_HEIGHT	64

    #define MAP_SIZE	  64
    #define MAP_WIDTH	  64
    #define MAP_HEIGHT	64
    #define MAP_MAX	    MAP_WIDTH*MAP_HEIGHT
    #define MAP_XMAX	  MAP_WIDTH*MAP_SIZE
    #define MAP_YMAX	  MAP_HEIGHT*MAP_SIZE

    #define MAP_XMAXLONG	(MAP_XMAX*(1L<<FP16))
    #define MAP_YMAXLONG	(MAP_YMAX*(1L<<FP16))

    enum {FALSE,TRUE};

    #define CEILING_COLOR    0
    #define FLOOR_COLOR      8

    #define SCREEN_WIDTH   320
    #define VIEW_WIDTH     240
    #define VIEW_HEIGHT    120
    #define VIEW_ANGLE      60
    #define NUM_BITMAPS     16
    #define NUM_FACES        5
    #define MAX_HEIGHT	  1024
    #define MIN_HEIGHT	    16

    #define BITMAP_BYTES (BITMAP_WIDTH*BITMAP_HEIGHT)

    #define Degree_6  	(int)(6L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_30   (int)(30L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_45   (int)(45L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_90   (int)(90L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_135  (int)(135L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_180  (int)(180L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_225  (int)(225L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_270  (int)(270L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_315  (int)(315L*VIEW_WIDTH/VIEW_ANGLE)
    #define Degree_360  (int)(360L*VIEW_WIDTH/VIEW_ANGLE)

    typedef struct
    {
      int Style,
          Column,
          Distance;
    } View_t;

    typedef struct
    {
      int x,
          y,
          angle;
    } Pov_t;

#ifdef __cplusplus
extern "C" {
#endif
    void Blit(char*,int,int,int,int);
    void DrawFrame(void);
    void GetSineAndCosine(int);
    char RayXZ(int,int,int);
    char RayYZ(int,int,int);
    int InitTables(void);
    void FreeMem(void);
    void InitTimer(void);
    void RestoreTimer(void);
    void CleanUp(void);
    void InitMap(char*);
    void InitBitmaps(char*);
    void InitHeightTable(void);
    void Initialize(void);
    void GenView(void);
    int HitTest(int,int,int);
    void EventLoop(void);
    void InstallKeybd(void);
    void RestoreKeybd(void);
#ifdef __cplusplus
  }
#endif

#endif


Listing Three

//  Copyright (c) 1994 by Mark Seminatore, all rights reserved.
//  Main.c:  This module calls the initialzation routines, then jumps into
//           the animation loop, and lastly shows some statistics.

    #include <stdlib.h>
    #include <time.h>
    #include <alloc.h>
    #include <stdio.h>
    #include <limits.h>
    #include "ray3d.h"
    #include "globals.h"
    #include "keys.h"

    void GenView(void)
    {
        int i,distance,RayAngle;
      unsigned char yStyleCode,StyleCode;
        unsigned long RayLength,yRayLength;
      unsigned int WallColumn,yWallColumn;
        long dx,dy;

      RayAngle=Pov.angle-Degree_30;  // Start by looking 30 to our left
      if(RayAngle < 0)               // Keep angle within table bounds
        RayAngle+=Degree_360;
      FarthestWall=0;                 // No farthest wall yet
      for(i=0;i<VIEW_WIDTH;i++)       // Cast two rays for each video column
      {
        RayLength=LONG_MAX;        // Start with an impossible distance
//  Don't cast an XZ ray if it is not possible to hit an XZ wall
        if(RayAngle!=Degree_90 && RayAngle!=Degree_270)
        {
            StyleCode=RayXZ(Pov.x,Pov.y,RayAngle);  // cast XZ ray
            if(StyleCode)                             // Did we hit a wall?
            {
//  Use y-intercept to find the wall-slice column
            WallColumn=(unsigned)(RayY>>FP16)&0x3F;
            if(iRayX < Pov.x)               // if looking west
              WallColumn=63-WallColumn;  // reverse column
            dx=iRayX-Pov.x;                 // get ray x-component
            RayLength=(dx*InvCosine[RayAngle]) >> 14;  // calc distance
          }
        }
//  Don't cast a YZ ray if its not possible to hit any YZ walls
        if(RayAngle!=0 && RayAngle!=Degree_180)
        {
          yStyleCode=RayYZ(Pov.x,Pov.y,RayAngle);   // cast YZ ray
          if(yStyleCode)                              // was a wall found?
          {
//  Use the x-intercept to find the wall-slice column
            yWallColumn=(unsigned)(RayX >> FP16)&0x3F;
            if(iRayY > Pov.y)                  // if looking south
              yWallColumn=63-yWallColumn;   // reverse column
            dy=iRayY-Pov.y;
            yRayLength=(dy*InvSine[RayAngle]) >> 14;

            if(yRayLength < RayLength)   // use the shorter ray
            {
              RayLength=yRayLength;
              StyleCode=yStyleCode;
              WallColumn=yWallColumn;
            }
          }
        }
        if(WallColumn < 64)   // A wall was found (either X or Y)
        {
          RayLength*=Cosine[i];             // cosine correct distance
          RayLength+=ROUND20;               // round up fixed point
          distance=(int)(RayLength>>FP20);  // convert to an int
          if(distance < MIN_DISTANCE)       // check for min distance
            distance=MIN_DISTANCE;
          if(distance >= MAX_DISTANCE)      // check for max distance
            distance=MAX_DISTANCE-1;
//  Save the wall-slice data
          View[i].Distance=distance;
          View[i].Style=(StyleCode&0x3F);
          View[i].Column=WallColumn;
          if(distance > FarthestWall)      // is new distance the farthest?
            FarthestWall=distance;         // update farthest distance
        }
        RayAngle++;                        // get next ray angle
        if(RayAngle >= Degree_360)         // keep angle within tables
          RayAngle-=Degree_360;
      }
      DrawFrame();           // Use View[] to draw the entire screen
      Blit(face[FaceIndex],266,133,50,45);  // draw the new bitmap
    }  // end GenView()
//  This routine validates player moves
    int HitTest(int x,int y,int angle)
    {
      int wall;
      unsigned long distance,ydistance;
      int dx,dy;
      distance=LONG_MAX;        // Set to a very large distance
//  Correct for angles where sin=cos, push the angle to one side otherwise
//  we can get false readings.
      if(angle==Degree_45 || angle==Degree_135 ||
      angle==Degree_225 || angle==Degree_315)
        angle++;
//  Don't cast a XZ ray if it can't possibly hit an XZ wall!
      if(angle!=Degree_90 && angle!=Degree_270)
      {
        if(RayXZ(x,y,angle))                     // cast an xz-ray
        {                                        // we hit something
          dx=iRayX-x;                           // get ray x-component
          distance=(dx*InvCosine[angle])>>14;    // calc distance
            wall=X_WALL;                           // set wall struck code
          }
      }
//  Don't cast a YZ ray if it can't possibly hit a YZ wall!
      if(angle!=0 && angle!=Degree_180)
      {
        if(RayYZ(x,y,angle))                      // can a yz-ray
          {                                         // we hit something
            dy=iRayY-y;                            // get ray y-component
          ydistance=(dy*InvSine[angle])>>14;      // calc distance
            if(ydistance < distance)                // use the shorter ray
            {
              distance=ydistance;                   // use y ray distance
              wall=Y_WALL;                          // set wall struck code
            }
          }
      }
      if(wall)                              // a wall was hit
      {
        distance*=Cosine[VIEW_WIDTH/2];     // cosine correct distance
        distance+=ROUND20;                  // round-up fixed point
        distance>>=FP20;                    // convert back to integer
        if(distance > CHECK_DIST)           // check distance
            wall=NO_WALL;                     // its OK to move
      }
      return wall;                          // return wall code
    }
//  This is the main program loop.
    void EventLoop(void)
    {
      int dx,dy,RevAngle,result;
      while(ScanCode!=ESC_PRESSED)    // do until ESC is hit
      {
        switch(ScanCode)
        {
        case 0:                   // no keys pressed
          break;
        case PLUS_PRESSED:
          HeightScale+=1000;      // increase aspect ratio
          if(HeightScale > 20000) HeightScale=20000;
            InitHeightTable();    // recalc height/distance table
          break;
        case MINUS_PRESSED:
          HeightScale-=1000;      // decrease aspect ratio
          if(HeightScale < 1000) HeightScale=1000;
          InitHeightTable();      // recalc height/distance table
          break;
        case LEFT_ARROW_PRESSED:
          Pov.angle-=Degree_6;           // turn left 6 degrees
          if(Pov.angle < 0)              // keep angle within tables
            Pov.angle+=Degree_360;
          GetSineAndCosine(Pov.angle);   // get trig values
          break;
        case RIGHT_ARROW_PRESSED:
          Pov.angle+=Degree_6;           // turn right 6 degrees
          if(Pov.angle >= Degree_360)    // keep angle within tables
            Pov.angle-=Degree_360;
          GetSineAndCosine(Pov.angle);   // get trig values
          break;
        case UP_ARROW_PRESSED:           // move forward
          dx=(int)(CosAngle >> 12);      // get x-component
          dy=(int)(SinAngle >> 12);      // get y-component
          result=HitTest(Pov.x,Pov.y,Pov.angle);  // check for all walls
          if(result == X_WALL)
          {                                 // we hit an x-wall
            dx=0;                           // can't move in x-dir
            if(Pov.angle < Degree_180)      // so check for y-walls
              RevAngle=Degree_90;           // check north
            else
              RevAngle=Degree_270;          // check south
            result=HitTest(Pov.x,Pov.y,RevAngle);  // check for y-walls
          }
          if(result == Y_WALL)
          {                                   // we hit a y-wall
            dy=0;                             // can't move in y-dir
            if(Pov.angle>Degree_270 || Pov.angle<Degree_90)
              RevAngle=0;                     // look east
            else
              RevAngle=Degree_180;            // look west
            result=HitTest(Pov.x,Pov.y,RevAngle);  // check for x-walls
          }
          if(result==NO_WALL)
          {
            Pov.x+=dx;        // no walls were hit so we can move
            Pov.y+=dy;        // ...update POV
          }
          break;
        case DOWN_ARROW_PRESSED:          // move backward
          dx=(int)(CosAngle >> 12);       // get x-component
          dy=(int)(SinAngle >> 12);       // get y-component
          RevAngle=Pov.angle+Degree_180;
          if(RevAngle >= Degree_360)
            RevAngle-=Degree_360;
          result=HitTest(Pov.x,Pov.y,RevAngle);
          if(result == X_WALL)
          {
            dx=0;                       // can't move in x-dir
            if(RevAngle < Degree_180)
              RevAngle=Degree_90;
            else
              RevAngle=Degree_270;
            result=HitTest(Pov.x,Pov.y,RevAngle);
          }
          if(result == Y_WALL)
          {
            dy=0;
            if(RevAngle > Degree_270 || RevAngle < Degree_90)
              RevAngle=0;
            else
              RevAngle=Degree_180;
            result=HitTest(Pov.x,Pov.y,RevAngle);
          }
          if(result == NO_WALL)
          {
            Pov.x-=dx;
            Pov.y-=dy;
          }
          break;
        default:     // handle unrecognized keys
          break;
          }
        GenView();   // cast some rays and draw screen
        Frames++;    // update frame counter
      }
    }
//  This is the main program start
    void main(void)
    {
      clock_t begin,fini;
      unsigned memleft;
      Initialize();     // setup video, read bitmaps, etc.
      Pov.x=Pov.y=96;      // set starting player location
      Pov.angle=0;
      GetSineAndCosine(Pov.angle);          // get sin/cos values
      GenView();                            // draw initial view
      memleft=(unsigned)(coreleft()>>10);   // get free memory kbytes
      begin=clock();                        // start timing the program
      EventLoop();                          // the animation loop
      fini=clock();                         // finish timing the program
      CleanUp();                            // free up all memory
      printf("Raycasting Performance\n----------------------\n");
      printf("Memory: %uk\n",memleft);      // show free memory
      printf("Frames: %u\n",Frames);        // show frame count
      printf(" Ticks: %u\n",(fini-begin));  // show clock count
      printf("Frame rate: %6.2f f/s\n",Frames*18.2/(fini-begin));
      printf("\n\nRayCastr: A raycasting demo for Dr. Dobb's Journal.\n\n");
      printf("Written by: Mark Seminatore\n");
      printf("            CIS: [72040,145]\n");
    }



Listing Four

//  Copyright (c) 1994 by Mark Seminatore, all rights reserved.
//  Draw.c:  This module contains the DrawFrame() routine which texture
//           maps the wall-slices in View[].

    #include <stdio.h>
    #include <mem.h>
    #include "ray3d.h"
    #include "globals.h"

    void DrawFrame(void)
    {
      unsigned hceil;
      long ScaleFactor,BmpOffset;
      char *Display,*p,*Bmp;
      int i,j,h,row;

      h=HeightTable[FarthestWall];   // lookup smallest height on screen
      if(h < VIEW_HEIGHT)            // is it still > viewport height?
      {                              // if not then draw floors/ceilings
        row=(VIEW_HEIGHT-h)>>1;
        hceil=VideoRow[row+h];
        Display=ScreenBuffer;
        for(i=0;i<row;i++)
        {
          memset(Display,CEILING_COLOR,VIEW_WIDTH);      // draw ceiling row
          memset(Display+hceil,FLOOR_COLOR,VIEW_WIDTH);  // draw floor row
          Display+=VIEW_WIDTH;
        }
      }
      for(i=0;i<VIEW_WIDTH;i++)
      {
        Display=ScreenBuffer+i;        // init display pointer
        Bmp=bitmap[View[i].Style];     // get ptr to bitmap
        Bmp+=(View[i].Column<<6);           // add in column offset
        h=HeightTable[View[i].Distance];    // find wall-slice height
        row=(VIEW_HEIGHT-h)>>1;        // calc starting row
        BmpOffset=0;                   // start with first pixel
        ScaleFactor=ScaleTable[View[i].Distance];  // get scaling factor
        if(row < 0)
        {
          h+=row<<1;                  // adjust wall-slice height
          for(j=row;j<0;j++)          // loop until on screen
            BmpOffset+=ScaleFactor;   // update position in bitmap
        }
        else
          Display+=VideoRow[row];     // point to starting row
        for(j=0;j<h;j++)              // texture mapping loop
        {
// Copy bitmap pixel to ScreenBuffer
          *Display=*(Bmp+(unsigned)(((0xffff0000L&BmpOffset)>>(16))));
          Display+=VIEW_WIDTH;       // get next ScreenBuffer row
          BmpOffset+=ScaleFactor;    // update position in bitmap
        }
      }
      Display=ScreenBuffer;          // get source pointer
      p=screen+20+SCREEN_WIDTH*40;   // get destination pointer
      for(i=0;i<VIEW_HEIGHT;i++)     // copy each row
      {
        memcpy(p,Display,VIEW_WIDTH);   // copy row to screen
        p+=SCREEN_WIDTH;
        Display+=VIEW_WIDTH;
      }
    }



Listing Five


;  Copyright (c) 1994 by Mark Seminatore, all rights reserved.
; Xray.asm: This module implements the optimized assembly version of the
;           RayXZ() function.
    ideal
    smart
    p386
    model compact,c
    dataseg
    include "rayasm.inc"
    codeseg

    proc RayXZ
    ARG  x:word,y:word,angle:word
        push    si                    ; save Turbo C register vars
        push    di

        mov     ax,[x]                ; get x
        and     ax,0ffc0h             ; calc (int)(x/64) * 64
        les     di,[dyTable]          ; get full ptr to table
        mov     bx,[angle]            ; get ray angle
        shl     bx,2                  ; multiply by the size of a long
        mov     edx,[es:di+bx]        ; get value from table

        cmp     bx,4*Degree_270       ; compare angle with 270 degrees
        jg      short LookingRight    ; jump if greater than
        cmp     bx,4*Degree_90        ; compare angle with 90 degrees
        jl      short LookingRight    ; jump if less than

        mov     [word cs:dxPos-2],-MAP_SIZE   ; dx=-MAP_SIZE
        neg     edx                           ; dy=-dy
        jmp     short Continue1
LookingRight:
        add     ax,MAP_SIZE                   ; xLocation=xBeg+MAP_SIZE
        mov     [word cs:dxPos-2],MAP_SIZE    ; dx=MAP_SIZE
Continue1:
        mov     [dword cs:dyPos-4],edx      ; store dy inside loop
        mov     cx,ax                       ; cx contains xLocation
        sub     ax,[word x]                 ; xLocation - x
        cwde                                ; xLocation - x
        lfs     di,[dword Tangent]          ; get ptr to table
        imul    [dword fs:di+bx]            ; (xLocation-x)*Tangent[angle]
        movsx   edx,[word y]
        shl     edx,16
        add     edx,eax
        lgs     di,[xzWalls]                ; get ptr to xzWalls
GiantLoop:
        cmp     cx,0                        ; is xLocation < 0?
        jl      short OuttaHere
        cmp     cx,MAP_MAX                  ; is xLocation > MAP_MAX?
        jg      short OuttaHere
        cmp     edx,large 0                 ; is yLocation < 0?
        jl      short OuttaHere
        cmp     edx,large MAP_YMAXLONG      ; is yLocation > MAP_YMAXLONG?
        jg      short OuttaHere

        mov     eax,edx
        shr     eax,16
        and     eax,0ffc0h
        movsx   ebx,cx
        shr     ebx,6
        add     ebx,eax
        mov     al,[byte gs:di+bx]          ; get xzWalls[bx]
        cmp     al,0                        ; was a wall found?
        jne     short Continue2             ; then quit

        add     cx,100h                     ; add imm16 value
dxPos:
        add     edx,1000000h                ; add imm32 value
dyPos:
        jmp     GiantLoop
Continue2:
;       and     cx,0ffffh
        mov     [iRayX],cx                  ; iRayX=xLocation
        mov     [RayY],edx                  ; RayY=yLocation

        pop     di                          ; clean up and return
        pop     si
        ret
OuttaHere:
        xor     al,al                       ; no wall was found
        pop     di                          ; clean up and return
        pop     si
        ret
    endp    RayXZ
    end