nesdev.org

Okay, I thought that raycasts were computed every vertical line of pixels. And this is very difficult to do on the NES, because you have very limited math. There really is no division that won't result as a whole number. So really complicated math is hard, because you have to round and whatnot. And you have to calculate the distance between you and a wall so many times (I've only read a little about raycasting). So yeah, I have to think for a while.

Celius wrote:Okay, I thought that raycasts were computed every vertical line of pixels.

It should be every column of pixels, not rows. A screen is rendered from left to right, not top to bottom. It makes sense, since a column can only display one wall, while a row of pixels would span across many walls at diferent distances.

And this is very difficult to do on the NES, because you have very limited math. There really is no division that won't result as a whole number. So really complicated math is hard, because you have to round and whatnot.

I spent a lot of time refining the basic raycasting algorithm, until I found a solution that uses no division (only multiplication, bit shifting and one binary search) and produces an 100% glitch-free image. I timed everything and this algorithm can run at around 12 frames per second, wich is enough for such a thing. The hardest part is the texture mapping (stretching a texture to fill the whole column). I have a bresenham algorithm ready, but althout it is very fast, it may drop the fps a little. I'm still looking for an optimal solution here.

And you have to calculate the distance between you and a wall so many times (I've only read a little about raycasting). So yeah, I have to think for a while.

I reduced my resolution to 28 columns (each one is 1 tile wide). It's a very low resolution, but considering the machine we're working on, it looks OK.

For each column I have to load from a table the distances to the next vertical wall and the next horizontal wall, based on the angle. They are both multiplied and shifted, to find the first distances (the player is in the middle of a block so we should use only part of the distances at first). Then I keep looking at the level map and adding the full distances, until a wall is hit. When it's hit, I have the distance ready. This distance is already fish-eye corrected from the table (wich makes the table quite big). with the distance at hand, I do a binary serach for it to find the heigh of the wall (saves me a division). If not using textures, the wall can be drawn already. To use texture, the exact point where the wall was hit must be calculated, wich costs 2 more (low-precision) multiplications, I think. then comes bresenham for scaling the texture to the size of the wall.

It's a lot of calculation, but it's all very optimized. The distances must be handled with quite a lot of precision (I think I'm using 24 bits), but many operations (multiplications, mostly) done to them can be of low precision (6 or 8 bits) wich makes everything a lot faster.

Well, enough about that. Hopefully one day I can release this thing and everyone will understand! =)

Hey, sorry to bring this up again, but I've been working on a raycasting engine, and might as well not start another thread for it...

Okay, so I've been thinking of how one might go about raycasting on the NES. I was thinking of a method that only allows 8x8 maps, but it allows for a lot of moving space. Every square on the map has 64 possible locations you can be in. It's like a graphics tile. Your position can be any pixel in that tile. I'd have a table that would define every ray slope for every 2 degrees (My resolution is 32x240, and my FOV is 64 degrees). And when you cast a ray, it follows the slope pattern within the 64 possible positions. So, instead of being high precision like this:



It's low precision like this:




It may not seem like there's much of a difference, but it really does effect the resolution. If there were a ray cast in the high precision mode, it may hit the middle of a square, and you do the pythagorean theorem, and it's whatever length it is, and you plug that number into the raycasting equation. But then you cast another ray, and it hits a little right of the previous ray, but it still hits the same square. Do the pythagorean theorem, and the number will be slightly different than the last. Plug it in to the raycasting equation, and you'll draw a wall slice that's slightly lower than the previous one. It looks very nice that way. It looks a lot more resolute. But in the low precision method, every time that square is crossed with a ray, it will be the same distance, because it only checks if the square was hit, not where it was hit. Do you understand?

Sorry, got a little sidetracked there explaining that. But as I was saying... Say I cast a ray. It hits a wall. Now I have to find the distance. I was thinking of have the square roots predefined in a table, because it'd be alot faster. The table would be 4 kilobytes. 4096 bytes. That's a BIG ASS table. I don't think I'd even have the square roots predefined, I'd just have the wall height predefined. So say the nearest wall was 3x away, and 4y away. I could look in my table for the ray length like this:

.db $x $x $x $x $x $x..... ;Square roots predefined. Go 4 rows down.
...
.db $x $x $5 $x $x $x .... ;And 3 to the right. There's the ray length.

Or I could just have the wall height defined there. Because if I had a ray length of 5, the wall would be X high. It would always be that same height.
So yeah, maybe I'll do that.

Or I could do LONG ASS Division, and LONG ASS square root finding routines, which would take SO MANY CYCLES, you don't even want to think about it. I know of a way to find unwhole square roots, but to transfer that to 6502, it'd take a Binary to Decimal routine, and a Decimal To Binary routine, because it involves long division. And I don't have that. I think I'll just go with the table. I really don't want to make it though... I think I'll just make a NES program that will make the table for me, and I'll have to come up with a Decimal to Binary routine.

Do you need the square root at all? In many cases all you need is the ability to find which of two distances is greater, in which case you can work in distance squared just the same as plain distance.

Hi Celius.

I've been messing with raycasts for quite some time now. And I learned a lot about it. I managed to come with ways to handle EVERY possible glitch you see in bad coded raycasters. Let me share with you some things I learned.

Most documents about raycasters tell you to cast 2 rays, one looking for vertical walls and another one looking for horizontal walls. After that, you pick the closest distance and consider that your hit. The problem is that this method will result in glitchy corners (sometimes, even if only for one column, the program may detect that the wrong wall is closer, 'cause they are so closer to each other), no matter how high is the resolution you use. A while ago I coded a raycaster for windows (right-click to download, change extension to "zip") wich suffered from this bug. I managed to avoid it, but not fix it back then.

The trick to NEVER missdetect walls is to trace both rays at once, as seen in this guy's tutorials. These are much cleaner than the more well known tutorial found here. The tutorials on the first link are very good, but the guy uses many mathematically complex things that should be overlooked when working on a NES version. Anyway, the part of his code that traces the rays is pure gold.

I managed to get rid of all divisions, and only kept a few (low precision) multiplications. My current design uses a table a bit smaller than yours. But my table is a table of distances. It holds the distance from one grid to the next, for all angles (half, actually, as the other half uses the same values). So instead of calculating the distance to the next grid, I just pick it from a table, and keep adding it to the total distance as the rays go. That way, when I get a hit, I already have the distance to the wall, with no further calculation (slow suare roots and all).

Another problem you usually find is that "fisheye lens" effect. To correct it, you have to multiply the distance by the cosine of the reletive angle (center of the screen is 0º). To get rid of that multiplication, I pre-fixed all values in the table, for the 14 possible relative angles. That's what makes the table so big. But this is another big gain: not only after I hit the wall may ray is ready, but it's also fisheye corrected!

The only catch with this table, is that you have to decimate the first distance, as the player will often be in between grids. For that I'll take the distance from the table, multiply by a low resolution (8-bit) version of the player's position withing the grid and then divide that by 256 (throw away the last byte). That is pretty quick.

With the distance in hands, you'd usually have to perform a division of a constant by that distance, to find the height of the wall. But since there are only a few possible heights (in my case, 128 for each half of the wall), I made a table containing the distance values that represent changing points in the height. A quick binary search in this table would give me the height of the wall. A division with the required precision would need something around 48 subtractions (shift-and-subtract division), but the binary search will take at most 7 subtractions. Much quicker.

The tough part, in my opinion, would be the texturing of walls. I made a very quick implementation of a bresenham scaling algorithm, but all the bit shifting would still make it a bit too slow on the NES. I'm still thinking of ways to improve that. Without the textures I'm sure the raycaster would be REALLY fast (more limited by the small ammount of stuff you can write to VRAM than by the speed of the raycasting algorithm itself).

Anyway, I have designed all sorts of tricks to make NES raycasting possible, but I haven't had the time to work on it. I don't even know why I wrote that huge ass post now... I guess it's because I never had anyone to talk about raycasters with.

These are all prototypes of NES raycasters. I don't have a prototype for my current design, as I haven't had time for that at all lately... If you want to take a look at my work on raycasters (again, rename to "zip"):

http://www.nesstuff.kit.net/nesray02.jpg
http://www.nesstuff.kit.net/nesray04.jpg
http://www.nesstuff.kit.net/nesray10.jpg
http://www.nesstuff.kit.net/nesray14.jpg

In spite of beeing made on a PC, these use the same logic and structure that would be used on the NES, as far as I can remember.

Anyway, I wish you good luck on the project, but i'll let you know it's not easy. If you want to talk about it, I'm here.

blargg wrote:Do you need the square root at all?

Yes, if you use the pythagorean theorem. The raycasting equation is:

H = B/X * P

H - Height of wall slice
B - Block size (Like my blocks are 8x8x8)
X - Distance to block
P - Distance to the projection plane

And in order to find the distance, I find out the X distance, and the Y distance, and use the pythagorean theorem to find the average distance. But if you think about saving time, the square root actually IS NOT neccissary. Most raycasters just find the distance, and calculate the height of the wall with the equation. But this is unneccissary for a raycaster running on such a resolution, because you can just look up what the height of the wall would be if it was a certain distance away, since there aren't a billion distances. There are about 4096, though, and that is low considering that's every single distance on the map.

And if I was making a raycaster in something like C, or C++, I could probably save the space and use the equation, and probably make it look alot nicer. Besides, the resolution wouldn't be so bad because we wouldn't be dealing with tiles.

Sorry, if that doesn't answer your question, I'm not really sure what you meant...

blargg wrote:Do you need the square root at all? In many cases all you need is the ability to find which of two distances is greater

After finding the smaller distance, the hipotenuse, you'd need to find the other sides of the triangle, to know what column of texture to use on that wall slice you hit, for example. If you don't use textures, the square root is not needed, I guess.

Celius wrote:since there aren't a billion distances. There are about 4096, though

I use 3 bytes for the distance! That's 16777216 distances. If you go much lower than that you'll get jagged walls, I'm pretty sure. I don't think 4096 values is enough to produce clean walls.

Well, yes, actually, the walls are going to look much like the "Stuck in castle Nessenstein" demo on that one site (By the way, if you want to download it, you have to change the url to "whateverthesiteis/sicn.nes", because the link they have to the download is shot.). The game is actually going to resemble SICN alot. If you play the tech demo, the walls don't change shape as you turn. They just shift whats on the screen, and update a column. I was planning to just do that, and build detail off of that. Do you know what I mean? Like, I don't really mind having a not-so-hot looking raycaster, I will build off of it. I have to have the raycaster before I can add detail.

Oh, and by the way. Your raycasters were pretty cool. You could have really fooled me with that first one. I would've never guessed it wasn't real 3D. The maze one, that is. Oh, yeah, that was quite the maze actually. And your other ones, those should look pretty nice when they are on the NES...

The way I did it in SICN was to save the result of the casting into a buffer in RAM (the tiles that should be drawn). Once I had finished updating the buffer I would signal that by changing a variable and during the next vblank I write the buffer contents to the PPU.

It's been a while since I've talked about raycasting on the NES with anyone. But I have been thinking. Now that I have math routines for multiplying and dividing, this is SOOOO much easier.

Tokumaru, didn't you say yours was 12 FPS? That gives you 5 frames to do stuff. That is plenty of time. I'd say that's a decent looking frame rate as well. Frick man, I've made cartoons running at about 7 FPS, and you can hardly notice.

But, I've been thinking that I would use mirroring to my advantage. I'd calculate several columns, and put the tile values into RAM. I'd take a few frames to completely put the values on screen. If you store parts of the next frame on a name table that's off screen, then it will not be noticable. When you've finished putting the values down on the name table, set the scroll to that name table, and just put the values on the previous name table for the next frame.

When you write data to a name table that's off screen, will it still glitch during rendering?

Celius wrote:But, I've been thinking that I would use mirroring to my advantage. I'd calculate several columns, and put the tile values into RAM. I'd take a few frames to completely put the values on screen. If you store parts of the next frame on a name table that's off screen, then it will not be noticable. When you've finished putting the values down on the name table, set the scroll to that name table, and just put the values on the previous name table for the next frame.

When you write data to a name table that's off screen, will it still glitch during rendering?

Writing to off-screen areas of the nametable is exactly how Super Mario Bros. does its glitch-free scrolling. But you still have to write the data while PPU rendering is turned off. For a 3D game, I think you can turn rendering off a few lines early with sprite 0, and nobody will care.

Celius wrote:Tokumaru, didn't you say yours was 12 FPS?

I calculated that based on the number of columns I had to draw and the ammount of calculations for each one. I don't remember if this takes into account the texture mapping though... it's been a while! I didn't code much of the raycaster, I think it went as far as calculating the distance to one column, but no rendering was ever done.

That gives you 5 frames to do stuff. That is plenty of time.

I had 28 columns in my engine, and I think I could get about 7 of them ready in a frame. But those were perfect, no fisheye effect, no misdetected corners, or weird stuff like that.

I'd say that's a decent looking frame rate as well. Frick man, I've made cartoons running at about 7 FPS, and you can hardly notice.

Yeah, for a 3D view on the NES, 12fps is good.

But, I've been thinking that I would use mirroring to my advantage. I'd calculate several columns, and put the tile values into RAM. I'd take a few frames to completely put the values on screen. If you store parts of the next frame on a name table that's off screen, then it will not be noticable. When you've finished putting the values down on the name table, set the scroll to that name table, and just put the values on the previous name table for the next frame.

I had that in mind for my engine too. The frames alternated between the 2 name tables.

When you write data to a name table that's off screen, will it still glitch during rendering?

Yes. That means that the only real advantage of alternating the name tables is that you don't see the screen being rendered from left to right, you see it all at once.

tokumaru wrote:

Celius wrote:I'd say that's a decent looking frame rate as well. Frick man, I've made cartoons running at about 7 FPS, and you can hardly notice.

Yeah, for a 3D view on the NES, 12fps is good.

What objects will you be placing in the 3D view, other than walls?

tepples wrote:What objects will you be placing in the 3D view, other than walls?

Me? None, for a long while, 'cause I'm not working on this until my current project is finished (or close to). I'm tired of switching from project to project and never finishing anything.

But objects were the main reason I put my raycaster aside. For the walls I was able to come up with formulas and tables that made everything much faster. No division at all was performed for the walls. The texturing would be done with an algorithm similar to Bresenham's line algorithm, with a few shortcuts for my particular case.

However, I wasn't so lucky with the enemies/objects. They'd each require at least 2 very long divisions, plus they'd have to be clipped by walls, and I couldn't think of any type of look-up table that would make these tasks faster.

I know raycasters aren't actually 3D, but they look and feel like 3D. I think 12 fps is a good framerate when I think of raycasters such as the one used in the Jurassic Park game for the SNES, which is quite slow. Of course that the one for the NES would be much less detailed.

Anyway, even if it isn't possible to add other objects, there are a few types of gameplay that can take place in a 3D maze that do not require any other objects to be present. Doors are pretty easy to make, as they are just a special case of walls.