# How to code a raycasting engine with angled walls?

## Recommended Posts

robertgamble    122
I've been trying to code a raycasting engine with angled walls (more Doom than Wolfenstein) by modifying an old Wolfenstein style engine of mine. Instead of my maps looking like this: 1,1,1,1,1, 1,0,0,0,1, etc.. My wall blocks contain a list of lines. It works just like a normal wolfenstein engine except that when it hits a wall block instead of just drawing the wall slice it loops through the list of lines contained within the wall block and checks intersections with those. I have this working pretty well (there's a few bugs but it works, http://www.elephantsneverforget.co.uk/rg/raycast2.html (wasd)), but it isn't very fast so I'm trying to come up with ways of speeding it up. I've tried only casting a single ray (instead of horizontal & vertical intersection checks) which works like this:
function raycast(angle,ColumnX,OriginX,OriginY){
//how far to move the ray
var stepX = (cos[angle] * MapSize);
var stepY = -(sin[angle] * MapSize);
//center point of current block
var rayX=(((OriginX+stepX)>>6)<<6)+(MapSize>>1);
var rayY=(((OriginY+stepY)>>6)<<6)+(MapSize>>1);
//length of the ray
var rayLen=Infinity;

while(1){
//see whats in the current block
block=MapPeek(rayX,rayY);
//if the ray has gone out of bounds then exit
if(block[0]==OUT_OF_BOUNDS)break
//if it's hit a wall then...
else if(block[0]==WALL){
//get the lines stored within this block
segments=block[1];

i=0;  //and loop through them
while(i<segments.length){
//check an intersection between this line and the ray
intersection=GetIntersection(OriginX, OriginY, rayX+(stepX), rayY+(stepY), segments[i][0], segments[i][1], segments[i][2], segments[i][3]);
//if there was an intersection then..
if(intersection!=null){
//see how far away it is
tmp=(Abs(intersection[0] - OriginX)*abscos[angle]) + (Abs(intersection[1] - OriginY)*abssin[angle]);
//if it's nearer than the last intersection then keep it
if(tmp<rayLen)rayLen=tmp;
}
i++;
}
}
//if an intersection was found then stop checking
if(rayLen!=Infinity)break;
//extend the ray
rayX+=stepX;
rayY+=stepY;
}

This is super fast and runs at 50fps or so on a P3 600 in Internet Explorer, however because of the way I'm extending the ray it is sometimes completely missing out blocks so from certain angles/distances sections some things don't appear. Is there anything I can do to fix this? What would be the quickest (framerate wise) of doing an engine like this?

##### Share on other sites
noisecrime    817
<deleted original post>

Doh, just read through the code properly and the issue I thought you were facing and which I replied to doesn't appear to be the case.

Glancing over the code it looks to me like you're accounting for the issues that would arise from intersections missing wall lines so its a puzzle as to why its not working correctly.

Did the block/wall code work with normal maps, where a wall was defined as an actual block? If not that suggests an issue with the raycasting.

If it worked fine before then, what about your intersection function, does that work corectly? I see you're just adding the ray step to the ray position, could this lead to missing some intersections?

Anyway your best alternative is to read up on 2D BSP trees since thats how Doom did it.

##### Share on other sites
robertgamble    122
I read up on bsp trees a while ago and know how to generate them, etc.. But I don't understand how to use them for actually determining visibility. How do you determine where you are in the tree and which way to read it based on the player coordinates & angle?

##### Share on other sites
wolverine    358

The missing columns seem to be at the intersection of wall. The corners!! Could this be the problem?

And again, if you start going back you'll see the columns being drawng wrong when you step away from the center.

##### Share on other sites
smr    2468
Instead of casting rays step by step over the map, use lines and intersect them against your wall sections. Divide your field of view by the number of columns on the screen. For each ray, one vertex will be at the position of the eye and the other vertex will be on the line at a hugantic distance away from the eye, say, maxint for example. Now, calculate the intersection point between the line you've made and each wall section. If it intersects, then keep this value. Continue checking for each wall in the sector. If the line intersects with another sector, and the intersection is closer than the one that has been kept for that column, then exchange the old for the new value.

You will probably want to divide your map into sectors to reduce the number of walls you need to test for intersection. Certain walls will be portals instead of actual walls. When you intersect with a portal wall, instead of recording that point, continue to check that ray against the walls in the sector that the portal leads. This will reduce the number of walls you need to check for intersection with. It also enables you to attribute your sectors with different values for lighting, fog, etc.

here's some pseudocode that will hopefully not confuse you too much ...

function cast_through_sector(LINE ray, SECTOR sector) returns nothing    for each wall in sector        intersection = intersect_line(ray, wall)        if intersection then            if wall is portal then                cast_through_sector(ray, wall.portal_sector)            else                length = line_length(ray.point1, intersection)                if length < ray.length then                    ray.length = length                end if            end if        end if    next wallend functionfunction raycast(POINT eye, ANGLE eye_angle, ANGLE fov, INT columns) returns nothing    LINE rays[columns] = create_rays(eye, eye_angle, fov, columns)        for each ray in rays        ray.length = INFINITE        cast_through_sector(ray, eye.current_sector)        ray.length = correct_fish_eye(ray.length, ray.angle)    nextend function

EDIT: corrected glitch in pseudocode

##### Share on other sites
robertgamble    122
Thank you smr, that's a great help.

My only question is how would I define sectors? I understand how a sector would be made up of walls and portals, but is it something the map "compiler" would have to work out or would sectors be manually created in the level editor (this would be how stairs, etc are created right?)? I'll take a look at a Doom or Duke3D editor to see how they do it :)

Also would it be better to transform & project (just casting two rays to clip against) the wall points rather than raycast them? I think if I did that and then draw the walls as polygons using something like VML I could also draw stairs, etc..

Thanks for you help :)

##### Share on other sites
wolverine    358
Quote:
 Original post by robertgambleI'll take a look at a Doom or Duke3D editor to see how they do it :)

In doom/duke nukem 3d editors, it was the responsability of the level designer to define sectors. And if i'm not mistaken, the sectors the level designer defined could be non-convex (this might be a problem, depending on what you want to do). In making a level for doom you were always doing something like:
create 4 lines so that they define a closed space like a square(it was 2d, seen from above. i.e. -> lines mean walls)
select those 4 lines, if i recall correctly, in clock wise order.
make a sector for those selected lines.

Then you could mess up with thinks like texture for each wall (there were 3 kinds of textures), the height of the floor/ceiling of the sector, type of lightning of the sector, putting things like players monsters on the sector, etc, etc.

The more 'wheird' detail was when 2 sectors joined each other. Imagine 2 squares and now you overlap one of the walls, so to make a rectangle. The wall that was overlapped becamed a special 2-sided wall with, by default, no texture (kind of a portal). The reason a wall could have 3 textures is that when u united 2 sectors with different floor/ceiling heights they you needed to define the textures for the missing gaps or you would up ending with the famous Hall of Mirrors effect.

I said all this from memory since it makes a *few* years since i made some levels for doom, so there could be one or other detail not completely correct, but this was the main idea.

By the way, one things really cool about the level editor supplied by 3d-realms for duke nukem was the ability to preview how the level was from inside the editor (although the height you had was bigger then what you would have in the game and the textures were with few colours). In doom level-editors, you had to compile the level to wad and then run it with doom.