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.