How to program DOOM on MSX.


The whole hype about first person perspective started with Wolfenstein. This program introduced the regular user to free-maze-walking. Ofcourse there were already RPG's who allowed the player to walk trough mazes, but it was a step-by-step affaire and the enemies were static pictures drawn in front of the tunnels you wandered through. This genre is turn based and realtime graphix weren't important

How to make a FPS

We are not intrested here in the AI of the enemies, nor the number of weapons nor bullet-enemy-player collesion detection. The point of interest here is the drawing of the gamearray itself, be it outdoors or indoors.

Static tunnel traveling

This type is relative easy to make, and doesn't use that much CPU power. It probably the oldest way to make tunnels.

Voxel landscape

This effect got very populair in the demo scene and got widespread by the use of it in the arcade-like helicopter emulator Commanche (C 1994).

 It is used to produce glowing surfaces , so it's ideal for creating outdoor scenes.

The main idea about this technique is the fact that for each point on screen you trace the lightrays from the eye trough the screenplane just untils it hits the ground. On uses a 2-dimennsional heightmap were he vamlues at coordinates (x,y) represent the height of the groundlevel.
In practice using a simple optimalisation you trace a lighbeam for each column on screen. You start with a point that's at the x,y coordinates of the player and has a height z. you make incremental steps trough the map changing x,y and z until you notice you hit the ground. Once the ground has been hit you can determine the colour by directly relating it through the height of the point hit or by loking up its colors in a colormap.
If you use the height for coloring the pixel you can make the points with Z-coordinate zero to be blue and then start a gradient going from yellow (the beach) over green (grass) to brown/grey (rocks of the mointans) into white (the eterna snow on top of thos montains).
Using a seperate colormap you can create a much better effect. Now you can have different colored arrays on the same height (like making a mountainlake) and its much easier to have precalculated shadows from the heigher arreas on your map. Note that in the screenshot they use the colormap as a topview radar to indicate enemy positions, here you can clearly see the precalculated shadowvalues.


This uses also a raytracing engine. for every collumn on screen a ray is traced until it hits a wall. Using the distance the ray has travelled before coliding with the wall, on can calculated the necessary scaling that has to be done when drawing this wall. Using the fraction part of the X and Y coordinates one has as immediate bonus value the offset in the wall-texture one uses.
All the distant values are stored in an array so that it is easy to compare the collumns of the sprites to the distance of the walls. If a wall is closer to the player than the distance of the sprite this means that this column of the enemy sprites is hidden behind a wall.



How to make FPS on an MSX

Static tunnel traveling

Like stated above it's one of the simplest ways of producing FPS games. It has been used in some MSX games also. The MSX lightgun had a game shipped with it that used this method.
Altough it's a simple methode wich looks rather good, it remains a static method. This is because of the fact that you're always placed in the midle of the tunnel, and the field of view always turns in steps of 90 degrees.

Voxel landscape

I once made this type. Problem is however that it still takes rather lot CPU time to trace all the columns. I used screen 3 because of its resolution of 64x48 blocks. And altough it was written in optimized assembly code it still was rather slow, and the visual effect wasn't pleasing enough.

An other problem with this type of approach is the space consuming size of the map. Since the code has to be fast the overhead in decoding the map datastructurebefore a map position can be checked must be kept as low as possible. Therefore the most simple thing to do is to keep the datastructure a simple twodimensional array in memory. For further optimisation the x and y coordinates should be byte alligned. This gives us the oportunity to say something like
LD L,X-value
LD A,Y-value
OR %10000000 ; to align the map on #8000
LD A,(HL) ; A contains the height of the map at coordinates (x,y)
If we use a 16 kB mapperpage for this one mapper page can contain a map of 256x64 pixels. You see that this method needs a lot of memory. Having a map of 256x256 pixels means once has to sacrifice 4 mapperpages only to the map alone. One could use bit 6 and 7 of the Y-value to chose the mapperpage in this example


Good news. The raycasting is a lot simpler here then it was when making the voxel landscape engine on the msx. You only trace x and y and the z component isn't used anymore!
Using a lookup table for scaling the trayced distance to a height of the wall is simple and fast.
By using screen3 again this is rather feasable. The problems however are :

The Secret Of Doom on MSX

And now, ladys and gentlemens, here is how I figured out the way to program a DOOM like engine on the MSX. This engine would be good enough to make a doomlike 2D environment with height alterations in it. And it wouldn't take up as much memory as a wolfenstein engine or a voxelspace. What is this secret than ? Well .....

Portal rendering

Instead of tracing each column like we used to do in Wolfenstein / Voxel-landscapes or using the paintersalgorithm we now go into the simpler, faster and verry good indoor rendering  method which is also known as portal rendering.

A different approach

Instead of using lightrays (Wolfenstein) or using the simplest matematical design (paintersalgorithm) were we see the whole world as one great mathematical space, were we have to pick the right pieces to get to the full 3D image we us the following  approach : PORTAL RENDERING

The main idea to portal rendering is that we change from a from describing on entire gamemap in one giant 2D/3D space into several little spaces, in effect these are our rooms. Every room is its own universum and some sides of the room are gatways to the other universums. A portal into the other room.
The normal maps used in games are drawn in one plane The same map now made of rooms were some walls are portals (green) who are connected to other rooms. The connections are indicated in purple.

 For simplicities sake let's set the following criteria : Walls are always vertical. No curved walls, no walls leaning inward or outward. As an extra criteria, although this isn't really necesary, we can say that in such a room the floor and ceiling are perfectly horizontal, this way we can use just two numbers to tell the height of floor and ceiling. If we take these criteria into account we get the same constraints as used in DOOM. We can describe our room in a 2D map where each room has two extra atributes, a floor and a ceilling height.

Let's look at the simplest room we can draw. Instead of heaving to sort all the walls according to depth so that the farst wall can be drawn first, it would be much faster if we could draw all the walls in random order, disregarding their screendepth. This would eliminate the need for CPU expensive sorting. The rooms which fullfill this criteria are convex rooms, simply meaning that if we draw all the lines of the walls, no two lines will cross in the room, but all the intersections will be outside of the room. In such case it doesn't matter which wall we draw first, because no matter where our point-of-view is whitin the room, never will two walls overlap each other. Hence, we dont need to sort our walls anymore before rendering.

Having a game with only one room wont make a great First Person Shooter. However, let's look at a normal everyday room. Besides walls we are verry likely to see something else, and I dont mean the objects in the room. An everyday room also contains doors and Windows(tm) which enables to look into the adjendant rooms. They give us a portal into the other rooms.

On MSX this method has an incredible amount of advantages. These make it possible to do stunning things on our humble, beloved system.

  1. The space needed to describe a room is very small. You need for each room with n walls you need just n+1 pair of (x,y)-coordinates for all the wall-intersections plus some extra info like the ceiling and floor height, portal or wall flags, some data to help us optimize our renderer and maybe some enemys and objects in the rooms and that's it.
  2. We all know that for a rotation function f(x)  we can say that for a translation of point a to point b we can say that f(a+b)=f(a)+f(b). Not only is this usefull for the rotation arround our player, but also for the rotation of  the rooms wich are visible trough the portals.

  3. We can define everyroom in its own axis, with its own origin. I will go into detail later on.
  4. Clipping of the enemy sprites is extremely simple. In a room you can first draw all the walls, and recursivly all the portals, and then draw all the sprites in the room.
  5. Since we have all vertical walls, this means that even after perspective correction we still have vertical clipping boundaries. Therefore our clipping is simpel an if (x<x1) or (x>x2) test. Which is fast.
  6. If we don't texturemap the floor and ceiling, and all floor and ceiling heights are constant,  than we can simply draw a gradient background and our clipping in the horizontal isn't needed. Besides real floor/ceiling texturemapping takes too much time. The helicopter and floormapping routines in Calculus are very optimized routines and you can notice the speed of that one. Otherwise you can calculate it yourself, it's a not done on MSX.
  7. Empty background After drawing our rooms
There are some minor disadvantages.They can be overcome if one takes them into account when designing the maps.

The effects of clipping

As stated earlier clipping is time consuming. To speed up our rendering we will have to deviate from perfect clipping to a simplified version. This however has to be a good studied decision, because simplifying will cause certain glitches in the rendering of a 3D environment.
Let's demonstrate this. We have small room with a heightened floor and lowered ceiling, this small room seperates two bigger, normal sized rooms. If our routine draws the all the ceiling and floor lines then we could create a window effect, lets draw an enemy in the orther room and illustrate the effect of some clipping.

Here is our enemy that walks in the other room.
Soldier sprite

If we combine this sprite with a window then we can have some of these effects.
best, no extra clipping involved This is the best result, this is automatically correct if after drawing the sprites in the other room, we return to the first room and draw the heightdifference between the ceilling of the two rooms. If our sprite would be bigger then maybe his feet could be sticking out from beneeth the wall. If we would really texuremap the floor and ceiling afterwards this wouldn't be a problem either. Clipping in this case could be used to draw just a part of the sprite so that drawing of the sprite would be just that litle faster.
no clipping on the screen Y axis Since our MSX isn't that fast and we didn't plane on much drastic height changes (like the fake window creation), we could as well drop the routine who would fill in the height difference. If we dont use any Y-clipping, this means that we would draw the entire sprite. This definitely destroys our wanted window effect, if we would have made a staircase then the effect wouldn't be that great. Besides building such a big sprite will take up a lot of time on our 3.5 MHz MSX's.
With minimal drawing The window/portal is ,if not look straight upon, a parallellogram. If we take the greatest inclosed rectangle we could clip our sprite drawing up on this region. This would give us the smallest look upon the sprite so our humble CPU/VDP combination will be able to draw this verry fast. If in extremis we use a verry long window this effect could have some strange effects, small enemys could be clipped completely out of view.
maximal clipping If we would chose to take rectangle witch would surround our parallellogram than drawing will be a little slower than the previous solution, but still much faster than with no clipping wat-so-ever and we still have eliminated the need for heightfilling. Out sprite still sticks out of theire respective real-world-windows, but who needs perfection, hm ;-)

Suggested extra's

Portal rendering enables us to do some great looking things witch can be done using some things that are implicitly build in into portals.
We all have played by now Duke3D, Half Live and Quake3. Weren't we all amased with the cameras in Duke3D who gave us a view into an other part of the gamemap. Our the teleports in Quake3 were we can see already were we will end up, or the colored transparent windows in Half Live. Maybe you were thinking about using simpler effects like hidden rooms or one way doors in your games. Here is the simplest solution: PORTAL RENDERING

Datastructure and optimisations

Remember my point about the fact that a translation with vector b followed by a rotation equals the rotation of the point follwed by a translation according to the rotated vector b. Also recall the fact that every room is a singular unit.
In our datastructure this can be used to enhance the size of the map, the speed of calculation and eliminate double calculations.

Use implicit data

We could store every data we can conceive into an explicit field of our datastructure. However if we bring some structure in our datafields we can use a lot of this structure later on to optimize our code. We talked already about the fact that every room with n-walls must have n+1 points to describe were the walls start end end. Our data model will be constructed so that every point and it's following point will make up a wall. We could store al our points in a random order, but in such case we need a list to tell us wich two points are the side of the wall. With this implicit data structure, we can optimize our roomdrawing algorithm because now with a simple loop we can walk trough all the points and start drawing the walls, without having the need to write complex,extra code just to find out which points are connected to form a wall.

The size of the map

If we would describe the entire map in a single plane this would mean that by using a 8 bit value our entire map would be constrained into a map of maximal 256x256 gridpoints. If we use 16 bits we would have a total mapsize of 65536x65536 grids.
If we dont want to bother with scaling the map coordinates to player coordinates this would mean that a 256x256 mapdescription isn't big enough to be interesting. So we would have to use 16 bits values. This will make the rotation function rather hard, we would be oubliged to use 16 bits math routines and there is always the overflow problem to take into account. If we rotate point (65000,6500) over 45 degrees the result will be a point (0,) which doesn't fit anymore in our 16 bits.
So instead of describing all rooms in one plane, we will describe every room in its own coordinatesystem. If we do so we can easilly use the same scale for the player coordinates as for the roomdescription and we can use 8 bits values for each room.
As extra info we need to store for each portal not only the room to witch it is a portal, but also the translation needed to map the coordinate system of the other room into the coordinate system used by the current room.
When using this last approach one imediately notices the fact that we dont have an absolute set of coordinates but all coordinates became relative to the current room were the player is standing. So the only boundary we know have is the fact the rooms and the adjendant rooms we draw have to limited to our maximum size of rotation/translation numbers.
We can in effect make a map which its total combined size being a 32bits X 64bits map, and we still only use 8 bits coordinates for each room.

Bringing some height into our maps

For simplicities sake and to need a litle less memory, I suggested that the height of ceiling and floor is constant within a room. This height is used when translating to screen coordinates. For our rendere for every wall intersection we need to calculate the Y-coordinates on screen, it isn't very hard to use for every intersection its proper height value, but it would complicate the rotines needed for player movement, It would be possible the have a not horizontal floor for example. Even worse nobody will garuanty that we still have a perfect mathematical plane. Also our clipping routine will be simpler if we dont have to look at the height of the actual wall drawn, but if we just can look at the global floor/ceiling height.

There are two options we can use to store the height of every room.

  1. As an absolute value, so all rooms will have an height set against an absolute sea-level.
  2. As a relative offset against the height of the room to which the portal is connected
Method one is simple, the routine who deal with transforming the height data to screen-Y coordinates are simple. And for map builders it's more easy t o keep track of the height level of every room, in case of method two they would need to assure that they don't make mistakes when calculating the relative heights. Method two has the disadvantage that when looking through multiple portals at the same time, you will have some overhead becuase you need to add al the relative height differences to have the height difference between the room drawn and the room were the player is located.

Bare in mind that no matter which method you use you are able to construct a level with multiple niveaus, you can have two rooms above each other !!
If you would draw the map in one single big plane you could even have cases were two rooms would overlap in absolute coordinates. Since you draw only the room you are in and the ones visible trough the portals, you wouldn't even notice during gameplay.
If you use method two you could even recreate the always climbing stair that Escher produced one, since every room would be relative heigher to its predecesor.

Creating an elevator floor is now a simple effect. You will have a subroutine that alters the floorheight of a given room. For example let's say that way have a hallway divied in 3 rooms.Room A has a low floor, room C has a heigher floor and B will act as elevator. Our subroutine will alter the floorheight of room B, if the floor is almost the same as floor A then the portal A->B will be passable, otherwise you will set the flag to nonpassable. You shouldn't e able to pass from room  A to room B if the elevator is already to high compared to room A. Same goes for the protal B->C. Notice that the portals C->B and B->A will always be passable. You can always fall down upon a lower section.

Using the same idea, you could make a small room were you will raise the ceiling height, as soon as the ceiling is high enough you can walk trough this door. Ofcourse you could create doors who slide down into the floor or combine both into something like those fancy airlocks you find in most SF televisionseries.

Calculating speed

By using 8 bits values we can use faster multiplication routines.
A rotation will be calculated as follows
since x and y are 8 bit values we can use for the sinustable a fixedpoint list. If we want this list to hold the values 1 to -1 we will have to uses 2.6 fixed numbers, meaning bit 0-5 are the fraction part of the number and bit 6-7 are the integer part of the represent number. The real number  0.5 will be in this case %00100000 were the number -0.75  will be represented by 11010000. This means that if we use an 8 bit signed X 8 bit unsigned routine giving the result in HL, we just have to shift two places (add hl,hl;add hl,hl;) to have the integer part in register H.
This we first rotate the room around its own local center and then translate it into the correct coordinate system for our room. This makes it possible to use 8 bits add instructions to do the translation instead of using the more demanding 16 bit add instructions.
I toughed already the fact that implicit data can help us a lot. Well here are some very nice hints to incorporate into our datamodel.

Eliminate double calculations

Above we stated already that we can skip the first point because no mather in which direction we rotate the result will always be (0,0). This is ofcourse already an elemination but we can go much further.
room with two pilarsHave a look at the last disadvantage in my list. If we render room E we would calculate it 3 times. Once from the portal B-E, once for portal C-E and a thirth time from portal D-E. Each time we would rotate room E and translate it to the coordinates of the 3 rooms.
Since we already made it possible to have the translation calculated as a simple 8 bits addition,the CPU intensive rotations are our second point of attention. Every rotation we can skip, the happier we are. If the position of the player changes we can calculate the new screen only using the cached rotation coordinates and translating these to the correct new position. If we walk forward our backward or stribe through the room this can be calculetd verry fast.
The simplest way to build such a rotation cash is to expand the data structure so that we can store the rotated coordinates beside the not-rotated points. The problem with caching is the eternal question: "Is the cache still valid ?". If we stribe to one side and a new portal enters the viewcone, how do we know if the chached coordinates of the new room can be used ? The solution is simple: as an extra we need to store the viewdirection of the player into every room. The rotation is valid if the chached rotation matches the viewdirection of the player.

The recursivenes problem

If you read the text up until know and you would set off to implement it, you would run into a rather anoying little problem. We always taked about recursively drawing the rooms, and having the possibility to draw all the walls because they didn't overlap. If it wasn't a solid wall we would follow the portal and draw the room. Using only this appoach we have a small problem, Let's say our entire game is just two rooms and one portal connecting room A with room B and a portal in room B to get back into room A. Here is wat is going to happen if we don't take any precautions :
  1. We are in room A, so we start drawing walls of room A
  2. We encounter the portal so we recursively start drawing room B
  3. We start drawing the walls of room B until we find a portal
  4. We recursively follow the portal and start drawing this room,

  5. the catch is that we have ended up again in room A.
  6. Draw walls of room end follow portal, so we get  back in room B
  7. etc. ending again in room A
  8. etc. room B
  9. etc.
  10. ...
  11. ..
  12. .
So we are stuck in an infinte loop. There are some ways around this problem.

The simplest way would be ofcourse to use a counter and limit the number of portals we will recursively trace. Verry simple to implement, but way to
slow to be usefull. We would benefit from to chached rotations ofcourse but our slow drawing routines would still redraw all the walls, and there is no sure way to cache the screen x/y projection so this extra math will be repeated over and over and over again. If we were stupid and all used cray-computers then this could be used without having a bad consionnes about it, but we rather want to be proud of our code, and our target computer , the MSX, is way to slow. Therefore we ban this bad solution from our minds and continue.

A more usefull way could be to pass a reference to the original room that we started from when we did the recusive call, if a portal of the room would bring us back to our recurse-routine-calling-room, we could simply skip it. This is almost as simple to implement as the previous solution (which we have already forgotten!!) and saves us tremendious on wasted CPU/VDP-cycles. However it means that a lot of the suggested extra's I mentioned earlier on, can't be implemented anymore. For example the trap-the-player-in-a-room-trick can't be used. You would alwaays draw the full steel door, even when we were supposed to be able to still look into the room. Also the transport-with-preview should become inpossible, or teleport must be aligned with a portal that goes back into the current room, so in efect we just have a simple door from room A to room B. It wont be posibble anymore to have multiple teleporters ending up in the same room.

The best solution is to draw the walls only if we look at the walls from the right angle, if we look at the "back" of the wall we don't draw it. People who already have some background on this kind of rendering pricinples will start to yell: 'normal vectors, he is talking about normal vectors'. Indeed I am. In the more complex, more mathematical approach we would take the normal vector of the plane describing the wall and a vector representing our direction of view. We would calculate the vectorproduct of these to 2 vectors which would yielld the cosine of the angle between the vectors. If this number is negatiev we would be loking at the backside of the plane if it is possitive we would be able to see the plane. The number could be used to darken the wall, because it is a messurement of the reflected light. This is excatly how the shading is calculated in Calculus and SandStone. O Stn higher end machines you could simply take the coordinates of the points and calculate the normal vector on this plane. On our beloved MSX this approach is again to slow, so some of you will now opt for storing the normal vector also in the data structure describing the rooms. Still, you would have to calculate the vector product, which is slow !ut the yes/no question of visibility
Let's cloud ourself in the illusion that we are smart and optimize further uppon the normalvector idea.
The main idea here is that we use the the angle between our vectors. The great thing about the vector product is that it also tells us what the light-reflection is given the fact that our lightvector and viewdirectionvector are the same. However since we aren't that interested in lightreflectionness of the surface but only about the yes/no question of visionability, this means that in effect we are only interested in the question. :
Is the angle between the normalvector and our viewdirection so that the wall is visible ??
So why bother with complex math if we can handle the question with some simple angles ? Let us just store the angle of the normal vector of the walls in our datastructure. Or even  better, let us store the angle of the vector opposite to the normal vector. This means that if viewangle and this aangle are the same that we are looking directly at the wall. So a wall will be visible if :
abs ( angle_of_viewdirection - angle_wall ) < 90 degrees.
this is exactly the same question as would be answered by the vectorproduct question.
So far we overlooked a simple side-effect of our screen projection.
If the angle between the two vectors is 90 degrees whe would see a line representing the plane, if the angle is greater then we would say that the plane isn't visible. However we overlooked the fact that  our projection-to-screen will place points farther away closer to the center of the screen. So walls having an angle-difference from more than 90 degrees will still be visible.So We need to adjust our equations. In the vectorproduct question we would need to say that the result must be greater than some (small) negatieve number and in our solution we would say :
abs ( angle_of_viewdirection - angle_wall ) < (90 + safety marge ) degrees.
The mathematically correct way would be to test after screen projection or integrate our screen projection formula into calculating the normal vectors. the safety margins approach isn't completely correct, a point further away will be projected differently then a closer point while the mathematical normalvector would be the same. However this approach will probably be the best method to use on an MSX.
Also note that using this approach doesn't conflict with our rotatedpoints caching, since for a given directionangle always the same points should be calculated as visible.

The pseudo code

Let's take all the info I have given until now and put it into some pseudo C-ish code.
In this way you can see it all come together (and if someone wants to implement it , they can just port this pseudo code to real code)

byte X; // coordinates relatieve the axis of current room
*room currentroom;
byte viewingdirection;
byte currentheight;
byte wapeonholding
byte ammoleft

byte X;
byte Y;

type WALLS{
byte type; //0=portal otherwise is the number of texturemap for the wall
byte iswalktrough;
.. extra info like recoloring of the wall
..animation step if portal is a door sliding open before it's set to iswalktrough

*ROOM nextroom; //if portal this points to the next room
byte xtrans; // this are the offsets to translate the points of
byte ytrans; // nextroom into coordinates of this room

type ROOM {
byte nr_wallpoints;
byte rotation_angle;
byte floorheight;
byte ceilingheight;
byte nr_enemy;

void Main(void){
while (not game over){
  drawroom( player.currentroom,
  check collision between bullets and player;
  check collision between bullets and enemy;
  check collision between enemy and player;

void drawroom (*ROOM room,
                            byte viewdirection,
                            byte xtrans,
                            byte ytrans,
                            byte ztrans,
                            byte clipx1,clipy1,clipx2,clipy2){
    if (room.rotation_angle != viewdirection) {
            room.rotation_angle = viewdirection;
            calculate rotation of all points for which NORMALANGLE tells us they are visible, and update the ISVISIBLE;
    // the screens view goes from -64 to + 64 , nul is the center of the screen
    // this is don so that the x correction dependeing on the screen depth of
    // the object can be easily calculated by a simple multiplication. This factor is
    // precalced and stored in a lookuptable, the screen depth is the index
    screenx1=2*( (room.POINTS[0].ROTATEDX-xtrans)
    //since the first point is always (0,0) you better optimize this ;-)
for (byte i = 1 ; i<room.nr_wallpoints ; i++ ){
        next if !ISVISIBLE;
        screenx2=2*( (room.POINTS[i].ROTATEDX-xtrans)
        if (prevvisible){
            if (
                    (screenx1<clipx1) && (screenx2<clipx1) )
                 || (screenx1>clipx2) && (screenx2>clipx2) )
                ) {
                        // walls are completely left or right from visible array so skip next drawing part
                        clip if needed to part in visible range
                        if (room.ROOMSIDES[i-1].type==0){
                                    drawroom (room.ROOMSIDES[i-1].nextroom,
                                                room.ROOMSIDES[i-1].xtrans + xtrans,
                                                room.ROOMSIDES[i-1].ytrans + ytrans,
                                    draw effect, like bars or colorfilter, if needed
                                } else {
                                     draw wall of type room.ROOMSIDES[i-1].type
                        draw sprites