[Back to EGAVGA SWAG index] [Back to Main SWAG index] [Original]
(*
> Can anyone recomend any books/source/reference/people that would be
> necessary to read/talk to to learn how to do 3 dimensional graphics for
> 1st person game programming similar to the Wolfenstein/Doom/Flight
> simulator type games.
If you can read "C", you should look out for ACK3D (a "3D" shareware
graphic engine) which comes with some sources. Note however, that
neither ACK3D nor Wolfenstein or Doom are true 3D games: They all use
a clever technique called "raycasting".
The underlying idea of raycasting is quite simple: use a 2D program
and just paste in a 3rd dimension, only for the screen display. Just
take a 2nd look at DOOM at you'll notice that there is no single
location in the map where you may have two different height-positions
throughout the game. Or more mathematically: There is no coordinate
(x,y) in the plane for which there are more than one z-coordinate. The
basic map of such games is a normal 2D map: the player moves within
this plane (which is divided by a grid into basic "blocks") and his
view will be computed for each animation frame. For example, say his
angle of view is 60 degrees. Then from his actual position, imaginary
rays will be sent out from -30..+30 degrees through the 2D (!) map.
Each ray is traced until it hits a block of the grid. The according
object will then be drawn to the screen at the proper position; the
length of the ray from the player's position to the hit-point is a
measurement how far the object is from the viewer and thus, how big
(and bright) the object should be drawn.
As the player only moves within the (x,y) plane, there is no change of
information in the z-coordinate. Therefore, for each screen column,
there is only one single computation necessary! (Even small changes in
the z-coordinate could be simulated easily by shifting the column data
a bit). The profits are dramatic: for a screen resolution of 320x200,
you only have 320 computations (instead of 64000) --that's an
improvement of 99.5%!
The problem with this method is the exact detection where the rays hit
the grid blocks. Instead of decreasing the mesh size of the grid, one
may think that the original blocks consist of a second "subgrid"
(ACK3D uses a 64x64 subgrid for each block). If you start counting
blocks row-wise, starting with zero, then you can compute the block
number and the relative coordinates (rx1,ry1) of a point P with
absolute corrdinates (x1,y1) by
b = (y1 DIV 64)*gridwidth_in_blocks + (x1 DIV 64)
rx1 = x1 MOD 64
ry1 = y1 MOD 64
See the profits of powers of two for the subgrid size here?:
b = (y1 SHR 6)*gridwidth_in_blocks + (x1 AND 63)
rx1 = x1 AND 63
ry1 = y1 AND 63
Computing the collision points rays <-> blocks is pure trigonometry:
Given are the position of the player P = (x1,y1) and his viewing angle
alpha (measured from the x-axis, for example). If he is looking with
angle of 20 degrees, one would have to compute all rays from 20-30=-10
degrees up to 20+30=50 degrees. If your screen has a width of 320
columns, then a simple algorithm would look something like this:
column:=0
FOR beta:=alpha-30 TO alpha+30 STEP 60/320
cast ray from P=(x1,y1) with angle beta
IF ray hits nontransparent block b
THEN draw block columns which we hit
at screen position "column";
compute distance to hit location and
darken graphic accordingly
ELSEIF ray leaves the plane edge
THEN draw complete column black
ELSE {ray runs through empty/transparent block}
trace ray further
INC(column)
ENDFOR
As we do have a fixed size of the game area, we do know the maximum
length of a ray in before. If the ray's length is bigger than this
maximum, you may stop tracing the ray any further. Using a bit college
math trigometry, one can optimize this even further to compute the
last point Q = (x2,y2) on the ray which must be checked:
x2:=x1+cos(beta)*diag; y2:=y1+sin(beta)*diag; (diag:=length of
diagonal of the (x,y) plane).
Now just use some standard line-algorithm like Brensenham's on the
line between P and Q and check the points if they hit a block and if
so, where. Note that you don't have to check every point, but only
those which lie on the grid edges!
> Can this type of program be created with Pascal or are they Assembler/C
> only areas?
I once saw a small piece of (buggy) PASCAL code, but didn't try to
debug it more than necessary; however, it should suffice for a start:
*)
PROGRAM RayCast2;
USES DOS, CRT;
TYPE
{ Map : 10 * 10 squares - 1 square consists of 64 * 64 units !! }
TMap = ARRAY[1..10] OF ARRAY[1..10] OF BYTE;
TPlayer= OBJECT
x ,
y : SHORTINT;
ViewPoint : INTEGER;
MapX ,
Mapy : SHORTINT;
PROCEDURE Init;
END;
HeightTab = ARRAY[0..90] OF BYTE;
WallBmp= ARRAY[0..63] OF BYTE;
CONST Up = 1;
Down = 2;
Right =3;
Left =4;
VAR Map : TMap;
P : TPlayer;
ch : CHAR;
xAtt ,
yAtt : BYTE;
Angle : REAL;
Height ,
Width : BYTE;
Distance: INTEGER;
yDis ,
xDis ,
Hyp : REAL;
DeltaX ,
DeltaY : REAL;
DeltaKX,
DeltaKY: LONGINT;
WMapX,
WMapY: INTEGER;
Column ,
XColumn,
YColumn: SHORTINT;
HeightTabTable : HeightTab;
Wall : WallBmp;
sinus, cosinus:ARRAY[0..359] OF REAL;
i:INTEGER;
PROCEDURE Modus(m:WORD); ASSEMBLER;
ASM
MOV AX,m
INT $10
END;
PROCEDURE TPlayer.Init;
BEGIN
MapX:=2; MapY:=2;
x:=32; y:=32;
Angle:=0;
END;
FUNCTION init:BOOLEAN;
VAR x,y : BYTE;
HeightTabF : FILE OF HeightTab;
BEGIN
Modus($13);
{ Erase Map }
FOR x:=1 TO 10 DO
FOR y:=1 TO 10 DO
Map[x,y]:=0;
{ Draw a few walls }
FOR x:=1 TO 10 DO BEGIN
Map[x,1]:=129;
Map[x,10]:=129;
END;
FOR y:=1 TO 10 DO BEGIN
Map[1,y]:=129;
Map[4,y]:=129;
Map[10,y]:=129;
END;
Map[2,3]:=129;
{ Build Character }
P.Init;
FOR x:=0 TO 90 DO
HeightTabTable[x]:=90-x;
{ Different Palette }
{ JansPalette; }
{ Init Wall Bitmap }
FOR x:=0 TO 31 DO
Wall[x]:=100+x;
FOR x:=32 TO 63 DO
Wall[x]:=100-(x-32);
END;
PROCEDURE Clear; ASSEMBLER;
ASM
CLD
MOV AX,$A000
MOV ES,AX
MOV CX,32000
XOR AX,AX
REP STOSW
END;
PROCEDURE deInit;
BEGIN
Modus( 3 );
END;
PROCEDURE DownProc; { looking down }
BEGIN
yDis:=907;
{ Step through each square }
FOR Height:=P.MapY+1 TO 10 DO BEGIN
Distance:= 65-P.Y + 64 * (Height-P.MapY-1);
Hyp := Distance / cosinus[Round(angle)];
DeltaX := sinus[Round(angle)] * Hyp;
IF DeltaX>MaxLongInt THEN DeltaX:=MaxLongInt;
{ Subtract when looking to the right , else add}
IF xAtt=Right THEN
DeltaKX:= (P.MapX-1)*64+P.X - Round(DeltaX)
ELSE
DeltaKX:= (P.MapX-1)*64+P.X + Round(DeltaX);
WMapX:= DeltaKX DIV 64+1;
XColumn:= DeltaKX MOD 64;
WMapY:= Height;
Hyp:=Abs(Hyp);
{ If out of bounds or wall found }
IF (WMapX<1) OR (WMapX>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
BEGIN
yDis:=Hyp;
Height:=10;
END
END;
IF (xDis>906) AND (yDis>906) THEN BEGIN
Distance:=906;
Column :=0;
END ELSE
IF yDis<xDis THEN BEGIN
Distance:=Round(yDis);
Column:= xColumn;
END ELSE BEGIN
Distance:=Round(xDis);
Column :=yColumn;
END;
END;
PROCEDURE UpProc;
BEGIN
yDis:=907;
FOR Height:=P.MapY-1 DOWNTO 1 DO BEGIN
Distance:= -P.Y - 64 * (P.MapY-Height-1);
Hyp := Distance / cosinus[Round(angle)];
DeltaX := sinus[Round(angle)] * Hyp;
DeltaKX:= (P.MapX-1)*64+P.X- Round(DeltaX);
WMapX:= DeltaKX DIV 64+1;
XColumn:= DeltaKY MOD 64;
WMapY:= Height;
Hyp :=ABs(Hyp);
{ If out of bounds, or wall struck }
IF (WMapX<1) OR (WMapX>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
BEGIN yDis:=Hyp;
Height:=1;
END
END;
IF (xDis>906) AND (yDis>906) THEN BEGIN
Distance:=906;
Column:=0;
END ELSE
IF yDis<xDis THEN BEGIN
Distance:=Round(yDis);
Column:=xColumn;
END ELSE BEGIN
Distance:=Round(xDis);
Column:=YColumn;
END;
END;
PROCEDURE RightProc(angle:WORD);
BEGIN
xDis:=907;
FOR Width:=P.MapX+1 TO 10 DO BEGIN
Distance:= 65-P.X + 64 * (Width-P.MapX-1);
Hyp := Distance / cosinus[angle];
DeltaY := sinus[angle] * Hyp;
IF DeltaY>MaxLongInt THEN DeltaY:=MaxLongInt;
DeltaKY:= (P.MapY-1)*64 +P.Y -Round(DeltaY);
WMapX:= Width;
WMapY:= DeltaKY DIV 64 +1;
YColumn:= DeltaKY MOD 64;
Hyp := Abs(Hyp);
{ If out of bounds, or wall struck }
IF (WMapY<1) OR (WMapY>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
BEGIN Width:=10;
xDis:=Hyp;
END;
END;
{ Now check yRay }
CASE yAtt OF
Down : DownProc;
Up : UpProc;
END;
END;
PROCEDURE LeftProc(angle:WORD);
BEGIN
xDis:=907;
FOR Width:=P.MapX-1 DOWNTO 1 DO BEGIN
Distance:= -P.X - 64 * (P.MapX-Width-1);
Hyp := Distance / cosinus[angle];
DeltaY := sinus[angle] * Hyp;
DeltaKY:= (P.MapY-1)*64 + P.Y - Round(DeltaY);
WMapX:= Width;
WMapY:= DeltaKY DIV 64 +1;
YColumn:= DeltaKY MOD 64;
Hyp := Abs(Hyp);
{ If out of bounds, or wall struck }
IF (WMapY<1) OR (WMapY>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
BEGIN Width:=1;
xDis:=Hyp;
END;
END;
{ Now check yRay }
CASE yAtt OF
Down : DownProc;
Up : UpProc;
END;
END;
PROCEDURE Proc0; { Angle = 0 degrees }
BEGIN
WMapY:=P.MapY;
Column:= 0;
Distance:=907;
FOR Width:=P.MapX+1 TO 10 DO BEGIN
WMapX:=Width;
IF Map[WMapX,WMapY]>128 THEN BEGIN
Distance:=65-P.x + 64 * (Width-P.MapX-1);
Width:=10;
Column:=P.y;
END;
END;
END;
PROCEDURE Proc18; { Angle = 180 degrees }
BEGIN
WMapY:=P.MapY;
Column :=0;
Distance:=907;
FOR Width:=P.MapX-1 DOWNTO 1 DO BEGIN
WMapX:=Width;
IF Map[WMapX,WMapY]>128 THEN BEGIN
Distance:=Abs( -P.X - 64 * (P.MapX-Width-1) );
Width:=1;
Column:=P.Y;
END;
END;
END;
PROCEDURE Proc27; { Angle = 270 degrees }
BEGIN
WMapX:=P.MapX;
Distance:=907;
Column :=0;
FOR Height:=P.MapY+1 TO 10 DO BEGIN
WMapY:=Height;
IF Map[WMapX,WMapY]>128 THEN BEGIN
Distance:=65-P.y + 64 * (Height-P.MapY-1);
Height:=10;
Column:=P.Y;
END;
END;
END;
PROCEDURE Proc90; { Angle = 90 degrees }
BEGIN
WMapX:=P.MapX;
Column:=0;
Distance:=907;
FOR Height:=P.MapX-1 DOWNTO 1 DO BEGIN
WMapY:=Height;
IF Map[WMapX,WMapY]>128 THEN BEGIN
Distance:=Abs( -P.Y - 64 * (P.MapY-Height-1) );
Height:=1;
Column:=p.Y;
END;
END;
END;
PROCEDURE VLine(x,y1,y2:WORD; c:BYTE); ASSEMBLER;
ASM
MOV CX,y2
MOV DI,y1
SUB CX,DI
JCXZ @ende
JG @doit
NEG CX
MOV DI,y2
@doit:
MOV AX,320
MUL DI
ADD AX,x
MOV DI,AX
CLD
MOV AL,c
MOV DX,320
@l1:
MOV ES:[DI],AL
ADD DI,DX
LOOP @l1
@ende:
END;
PROCEDURE Draw;
VAR counter: INTEGER;
intAngle:WORD;
BEGIN
{ 70 degree viewfield (not just 60) }
angle:=(70*160 / 320) + P.ViewPoint;
IF angle>=360 THEN angle:=angle-360;
FOR counter:=0 TO 319 DO BEGIN { loop each column }
intAngle:=Round(angle);
IF intAngle=90 THEN { xDirection }
xAtt:=90
ELSE
IF intAngle=270 THEN
xAtt:=27
ELSE
IF (intAngle<90) OR (intAngle>270) THEN
xAtt:=Right
ELSE
xAtt:=Left;
IF intAngle=180 THEN { y Direction }
xAtt:=18
ELSE
IF intAngle=0 THEN
xAtt:=0
ELSE
IF intAngle<180 THEN
yAtt:=Up
ELSE
yAtt:=Down;
CASE xAtt OF
Right : RightProc(intAngle);
Left : LeftProc(intAngle);
0 : Proc0;
18 : Proc18;
90 : Proc90;
27 : Proc27;
END;
{ Draw Line }
VLine(counter,99,99-HeightTabtable[Distance DIV 10],Wall[Abs(Column)]);
{ decrease angle }
angle:=angle- (70 / 320);
IF angle<0 THEN angle:=angle+360;
END; { next column }
END;
BEGIN
FOR i:=0 TO 359 DO
BEGIN
cosinus[i]:=cos(i*Pi/180);
sinus[i] :=sin(i*Pi/180);
END;
ch:=#1;
IF Init THEN BEGIN
P.ViewPoint:=90;
REPEAT { Loop until ESC pressed }
Clear;
Draw;
ch:=ReadKey;
CASE ch OF
'a' : BEGIN { Left turn }
Inc(P.ViewPoint,5);
IF P.ViewPoint>359 THEN P.ViewPoint:=P.ViewPoint-360;
END;
's' : BEGIN {right turn }
Dec(P.ViewPoint,5);
IF P.ViewPoint<0 THEN P.ViewPoint:=P.ViewPoint+360;
END;
'w' : BEGIN { Move forward }
Dec(P.y,2);
IF P.y<1 THEN BEGIN
Dec(P.MapY);
P.y:=64+P.y;
END;
END;
'y' : BEGIN {Move backward }
Inc(P.y,2);
IF P.y>64 THEN BEGIN
Inc(P.MapY);
P.y:=P.y-64;
END;
END;
END;
UNTIL ch=#27;
DeInit;
END;
END.
[Back to EGAVGA SWAG index] [Back to Main SWAG index] [Original]