• entries
298
1135
• views
231449

# Diversions

117 views

RayCasting 101

I was originally going to keep my mouth firmly shut about this, but after EasilyConfused posted his nifty little "Box World" and set the bar, I had no choice but to shake my fist and reveal one of my other side projects: a raycaster. Not as flashy as EC's, but we'll see who can develop theirs faster. ;)

If you aren't familiar with the term, then you still surely know of it. Anyone who has played the wonderful iD legends such as Wolfenstein 3D, DooM, or Rise of the Triad* already know of raycasting and its historical glory.

Raycasting was the traditional way of simulating a first-person 3D view using a purely 2D map at reasonably fast speeds, given the hardware of the time. The idea was to 'shoot' out rays from the player's view-point and extend them until they hit a wall or somesort of opaque obstacle. It would then render a single pixel-wide sliver of wall, with its size dependent on how far away the wall was. Repeated for as many pixels across as the display is, this technique yields a final image that's fairly convincing of a true 3D environment. Here's the one I've been hacking away at for the last few days:

I know this isn't very impressive in the grand scheme of things, but I, for one, am literally beaming with pride at this accomplishment on my behalf. My math not being as strong as I would like, I've been attempting to create raycasters for literally years now. For years it remained the holy grail of programming feats, that I was never able to get to work properly. Whether it was faulty intersection-detection or the dreaded fish-bowl effect, I was just never able to get it looking anything like the classics like Wolfenstein 3D. So once my Linear Algebra course picked up a little this term, and I dusted off my Discrete Math notes from Grade 12, I finally hunkered down and decided that I'd make one: for reals! [smile]

It's still not quite perfect, but I don't think most people can notice. With wall textures especially it's hard to see the flaws.

One of the most exciting parts about a raycaster (or any "3D" engine) is that there's no shortage of cool potential features to add. I'm extremely excited about getting in floor/ceiling textures, distance fogging, skymaps, lighting, decals, and anything else implemented. I'll probably start with optimizations, however. [smile]

Luckily this adventure also technically satisfies one of my New Years' resolutions: that being that I get started on learning 3D math/programming this year. I fully plan on getting into OpenGL/Direct3D in more depth than I have been at some point, but in case I don't make it this year, I'm now still covered!

You may be wondering how exactly I have time for all of these side projects. I don't really think I do! Currently I'm trying to finish Membrane Massacre, working on a Scheme-like scripting language, writing a raycaster, rewriting a 2D collision system for Stencyl, and y'know, doing full-time university student stuff. Hopefully I can get MM out the door really soon and trim that list down a little. I'm aiming to beat Stompy to a release because I -- well, no reason really. I had had to plug his journal for all of his great progress. Darn moral obligations! [smile]

EDIT: Oh yeah. Raycasting Demo for sure.

One thing to note is that I don't think Doom used a raycaster; it was a portal engine.

Stencyl looks totally awesome; I'd love to help out with OS X support.

That's awesome. I don't think that a race between me using Direct3D without any understanding of the maths and you hand-writing a ray caster is exactly fair on you, so I reckon you are way in the lead.

If you start to implement collision detection on a 3D map like this, I'll be interested to hear your thoughts. I've got a very basic system working on mine, but I can't figure out how to let the player slide along walls when strafing smack face up to a wall but at a slight angle into the wall.

Quote:
 Ravuya sagt: Stencyl looks totally awesome; I'd love to help out with OS X support.

Register away on the forum. I'm sure that Eliwood undoubtedly would be able to find a place on-board for you.

Quote:
 Original post by EasilyConfused If you start to implement collision detection on a 3D map like this, I'll be interested to hear your thoughts. I've got a very basic system working on mine, but I can't figure out how to let the player slide along walls when strafing smack face up to a wall but at a slight angle into the wall.

Ie. Get the vector representing where the player will be after one step forward. Then make a new vector with (NewX, OldY, OldZ) and check it for a collision. If it happens, keep OldX. Then make a new vector with (OldX, NewY, OldZ), and repeat for Y, and then Z. This way only the axes that are responsible for collisions will be reset to their old location, and the others will make the character 'slide' across the surface.

EDIT: Worth noting that this solution really only works for maps whereas all collide-able map 'things' are squares aligned along the X, Y, or Z axis. Something more complicated like Scet's method below would be needed for a more complex map format.

Quote:
 I don't think that a race between me using Direct3D without any understanding of the maths and you hand-writing a ray caster is exactly fair on you, so I reckon you are way in the lead.

I was just playing around. Yours is going to whoop mine's arse. [smile]

Rav is right that Doom doesn't use raycasting. Instead it uses a simple 2D BSP tree that sorts the sub-sectors from front-to-back and then just draws them in order. It also has functions to test if a wall is even on screen and if the screen is "full" so there's no overdraw. Basically there's a 1D array the size of the players FOV and you compare any visible lines angles from the start and end points against the player. Floor and ceilings use a flood-fill algorithm that uses the portals between sectors and any solid lines.

As for the "sliding wall" thing, I have a different approach, although it requires a format similar to Dooms. Basically if you have a line going from 0,0 to 0,100 then its angle is 90 degrees and it has two normal angles of 180 and 0. When the player hits the line you move them backward along whichever normal angle based on what side of the line they're on.
Repell( Distance - ( Properties.Radius * 0.8f ), Line.Angle + ( 90.0f * Functions.SideOfLine( SubSector.Sector, Line ) ) );


Distance is the distance from the center of the player to the nearest point on the line, when the players radius is subtracted it should become negative. Using the line menthioned before, Line.Angle would be 90, Functions.SideOfLine returns 1 for the right side and -1 for the left side.
public void Repell( float Distance, float NormalAngle )
{
X += (float)( Math.Cos( 0.0174532925 * NormalAngle ) ) * Distance;
Y += (float)( Math.Sin( 0.0174532925 * NormalAngle ) ) * Distance;
return;
}


of course you'd want to change it to radians instead of degrees. For me it's easier to create functions if I can visialize it, so I use degrees.

Anyway this looks awesome, but it still looks more like Wolf3D than Doom. ( Needs more Doom! )

Edit: The collision code might not be 100% correct, I still have a few odd collision bugs in Escalation, but it works most of the time.

## Create an account

Register a new account