nesdev.com

Hello everyone!

So about a year and a half ago, I started brewing up this little demo. I started thinking about it when there was discussion in another thread about ray casters on the NES. I just figured, why not release it and show what progress I made, even if I make no more.

I remember being impressed following the threads regarding tokumaru's raycasting project. He was able to accomplish quite a lot; he had textures and did some palette tricks to allow for colored walls, all at a great frame rate. It seemed to me that the biggest draw back was the low horizontal resolution, but palette tricks would be difficult without the 8-pixel wide columns.

So I thought, what if there was a raycaster on the NES that only used one palette for the walls in a room, and didn't have a limited horizontal resolution? Would sacrificing colors for resolution pay off? And with an increased horizontal resolution, it would probably run a little slower. Plus, how would it even work in terms of pattern table/name table updates? So this got me thinking and pretty soon I'm sitting there, building a raycasting engine.

I took a rather different approach to it. The display area is 21x11 tiles, and is constantly filled with tiles $00-$E6. All graphical updates are done to CHR RAM. In order to make this faster, I reduced the resolution to be 84x88 instead of 168x88 (double-wide pixels). Wall textures are limited to 16x16 resolution. Wall texture slices are also defined with code instead of being .db statements. When the ray casting code runs, it draws a frame that looks more like a wire-frame simulation. After that part is drawn, I use a technique called XOR filling to color the entire screen. This makes handling the graphics MUCH easier. In the demo (this isn't in the video), you can press SELECT to see what the walls look like without XOR filling.

I was beginning to work on objects, but then I stopped. I do have the theory all figured out, I just needed to implement it. Essentially, they would behave exactly like walls, but have higher resolution (32x32 instead of 16x16). I would draw them in RAM and sort of "paste" them over the complete background. It would slow things down considerably, though.

There's a lot I could go on about, but I won't bore anyone to tears unless they ask. Feel free to download, and provide comments/questions!

ROM Link:
http://www.freewebs.com/the_bott/Raycast.nes

YouTube Link:
https://www.youtube.com/watch?v=KcOneF-dLfc

It looks impressive, even for the low frame rate.

I wonder what tricks the Super NES port of Wolfenstein 3D uses to increase frame rate, and how many of those would apply to the NES.

How about the obvious... Mode 7 to enlarge all the pixels...

_________________
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Just tried it. Great stuff.
I think even the "wireframe" mode looks great, and since it runs a bit faster without the colour filling, you may "cheat" by claiming the wireframe mode is what it should look like, which is perfect for a "futuristic neon" setting (you may even use different shades of a colour, such as green instead of the greys).

I know that objects could be hard to implement, but maybe try adding some collision detection, so that it can become a simple maze game?

This looks great! The frame rate might be a bit low, but it's still faster than I though would be possible at this resolution!

The obvious bottleneck on the NES is having to update huge chunks of CHR data, and if you try to get rid of that and update only the name tables you get what can be seen in my raycaster, which is a very blocky representation of the level.

One way I considered using in order to have as much resolution as in this demo without having to update the pattern tables was to have them populated with the 256 possible combinations of 2x8 color bars (4 colors ^ 4 positions = 256 tiles), and change the scroll every scanline (or every 2 scanlines) to squeeze the picture vertically. The obvious drawbacks are the CPU time spent on changing the scroll, and the fact that the vertical resolution is limited to 60 unique lines if you stick to using only 2 name tables. But still, even with the extra overhead, updating 2KB might mean a significant speed increase over updating 8KB.

Other than that, pre-calculating as much of the math as possible always helps. In my demo, all distances (per angle, per fisheye correction angle, per square) were pre-calculated, so that the raycasting itself consisted only in calculating the fraction of the distance to the first intersection (which changed because the player can stand anywhere within a square) and adding distances until a wall was found. A binary search helped find the height of the wall slice based on the distance. The texturing can also be table-driven (it wasn't in my demo, but I was considering re-implementing it that way).

Thanks! The frame rate is lower than I like, but I think with the speed the player walks, it could be bearable during gameplay.



I'd actually thought about this! I just don't know if the player would be able to stand looking at it for very long, especially because there are no vertical lines.



I actually had a maze map that I was experimenting with, and it wasn't too bad. But I'd feel like that would be taking the easy way out. I'd like to make it into a first person shooter

Thanks! I think the trick really was the XOR filling, so that I didn't have to calculate exactly what color every pixel on the screen needed to be.



This is an interesting idea! I was thinking of a similar scroll trick for a movie engine, to have multiple frames of movie data interleaved in the same tiles, but adjust the scroll to show only one frame's data. I think what makes this most difficult is that you would have to perform the adjustments every frame. With both of our methods we've used, you could theoretically perform 5 frames of uninterrupted calculations after rendering a game frame. The player would only notice a slight lag. You would have to break it into segments if you used any scroll tricks. If you performed 5 frames of uninterrupted calculations after rendering a game frame, the player would see these giant lines fill the screen for a split second and then everything would go back to normal. But yes, that could certainly result in a speed increase, if implemented correctly.



I have a ton of tables; almost everything takes advantage of a table in some way. It's funny you mention the binary search, because I haven't had to use one yet. Everything is just indexed right to what it needs to find. But I will need to use one when I put objects in. My plan is to find the slope of the line between the player and the object, and do a binary search through a table to figure out what angle has a slope close to it so I can render the object at that angle.

I'll have to check out how the XOR filling works in your demo! =)


Yes, you'd have to interrupt or at least slow down the calculations for a while every frame. I don't know if that would cancel the improvement of not changing the pattern tables.

Another concern with this method is the double buffering... you'd have to update the name tables all at once, or you'd get tearing. Using 4-screen mirroring might be a good way to avoid this.


The binary search was used to convert the distances into wall heights. Normally that would be a division (Constant / Distance = Height), but since the number of heights is very limited, I made a table indicating the distances at which the height changes, as opposed to storing a height for each of the many possible distances, which would have needed too much memory. The binary search was much faster than the division, so I kept it.


Yes, I thought of using a binary search for this as well. I would divide one of the legs of the triangle that is formed between the player and the object by the other leg and search for the result in a table of angles, with a binary search. I also considered severely limiting the number of bits in this division, so I could look up the angle directly, but that could cause problems when objects are really close and you need the precision to properly detect the angle.

Knowing the angle, you need the hypotenuse of the triangle, which is the distance between the player and the object, which needs to be fisheye-corrected. Like with walls, this distance has to be converted into a height, so you know how big the object has to be, and the scaling can be table-driven. Can you think of any tricks to make these steps faster?

As I see it, there are a lot of calculations involved in rendering objects, so they should be kept to a minimum... something like 2 or 3 per room at most, and preferably well spaced apart to reduce the chance of more than one being rendered in the same view.

I don't know if I mentioned, one of the limitations of my engine is room size. The size you see is as big as it gets (11x11 blocks). The idea is that instead of having a giant map, one would connect "rooms" so that rays didn't have to go so far. Basically, each block is 16x16 "sub" blocks. So if you're standing 1 block away from a wall, you are at a distance of 16 sub blocks. If you stand in the top left corner of a room, and look to the bottom right corner, that 45 degree line is the longest ray that will be cast in that room, assuming an unobstructed view. If I keep the room size limited to 11x11 blocks, the ray will never go a distance of over 255 (use Pythagorean Theorem to calculate the length of a ray in an 11x11 room, is about 249 sub-blocks). Using this makes it very easy to index tables for wall heights and things like that.



Does it need to be fisheye-corrected? My idea was that you would calculate the distance, and scale the object as if it were directly in front of you. The only reason you need to know the angle is to know what ray to line it up with on the screen.



Well, I actually have a pretty quick and dirty set up for object scaling. First, object textures are stored as code, each slice being its own routine. Once I calculate the distance to an object, I have a horizontal scaling table for each distance (32 bytes per distance, as there are 32 slices in an object texture). The table basically shows for each "slice" in an object's texture, how many 2-pixel wide columns that slice will take up on screen. So when an object is close, it will look something like:



But when an object is far away, it will look something like this:



The rendering code will therefore "skip" any of the slices that don't need to be rendered (when the object is far away), which saves time. However, when an object is close, it is difficult to save time, as it takes up most of the screen. But at least I don't have to figure out how to scale an object horizontally; it's all pre-calculated.

For vertical scaling, the texture slice code tells a "PSET" style routine to put a pixel at a relative position (1 of 32 possible relative Y positions). Then knowing the distance, that code uses look up tables to locate where that relative pixel actually falls on the screen. Again, this makes having an 8-bit distance value extremely useful.



Also, don't forget that player projectiles and item drops are "objects", and will need to be rendered appropriately. This of course, sucks.



If you get the chance to emulate it, try pressing SELECT. You'll see what the engine renders before it XOR fills

Ah, this must be a very important optimization. It also explains the slightly jagged walls that appear some times. I still haven't found the ideal amount of precision for distances, but from my tests I've seen you can indeed go very low and still have things look good.


If your walls are fisheye-corrected, I imagine that the objects have to be too. When you don't fisheye-correct the walls, looking at a wall perpendicularly will cause the center of it to bulge towards you, so the same would happen to objects. If the wall has been correct and looks straight, an uncorrected object in the center of the screen will appear larger than another one near the edge of the screen, even if both are positioned the same distance from the wall. I don't know if the difference is so terrible at such low resolutions, but there will be a disparity between the representation of walls and objects.


But that's the fisheye correction (the "as if it were directly in front of you" part), isn't it? Directly in front of you, the distortion is 0, but any other angle to the left of the right will look rounded if you don't correct the distances.


Souns interesting. Can't wait to see it working.


Well, Wolfenstein 3D didn't have visible projectiles as far as I remember, and not all weapons in Doom had them either, so you might get away with not showing bullets. Not much you can do about items though, besides not having rooms full of them like Wolfenstein 3D does.


Yeah, I saw that. I still can't tell exactly how the XOR filling is saving you time just from looking at that, so I still have some research to do. =)

BTW, I have though of a way to render the image that is somewhere between your technique and mine. The amount of detail in your demo looks great, but I'm not sure it can be turned into a game as is. My main concerns are the following:

1- With only 4 colors overall, levels might look very repetitive. That can be minimized by connecting rooms (since that's how you planned to form levels) of different colors.

2- There's no space in the pattern tables for sprites. Are you planning to draw objects using the background? That would make objects blend with the background too much, and it would be weird if they changed colors depending on the room they're in.

3- There's no space in the pattern tables for a status bar. You might be able to get away with showing the status only when the game is paused, but that would hurt the overall presentation of the game, since the average player will not understand why you can't make use of the vast blank space around the gameplay window.

4- Perpendicular walls are not shaded differently. There aren't enough colors to automatically darken textures, but if all your palettes are gradients, you might be able to manually draw darkened versions of all the textures.

To address these concerns, I have though of a different way to render the maze with a resolution that's somewhere between my demo and yours: 4x2 hardware pixels for each pixel. Each tile would have only 2 colors, one in the left and one in the right, which would allow for 16 different colors (using dithering) in 256 pre-calculated tiles (16 ^ 2 = 256). I would actually reduce the color count to 12 or 14, in order to have tiles left for drawing a status bar, and the second pattern table completely free for sprites.

Scroll changes every 2 scanlines (using the MMC3) would squeeze the picture to the desired resolution, creating a gameplay window that's 224x120 hardware pixels big (56x60 software pixels). 2 name tables would be needed for each gameplay frame, so 4 screen mirroring would be necessary to avoid tearing and having a status bar.

The top and the bottom of the gameplay frame could use different palettes, so you could design the textures (as well as the floor and the ceiling) to take advantage of that, and create more colorful scenes.

Objects would be drawn with sprites, and since thay have their own palettes that would bump the color count up a bit more. Having objects drawn with sprites will severely impact the way they are designed and positioned, because you'd have to do your best to prevent the player from getting too close to wide objects.

As I see it, every method has its drawbacks, and they might end up blocky, monochrome or slow, but I believe that the key is to balance all of those aspects and come up with something that isn't so bad in any of them. IMO, having a very high resolution isn't so good if that means a tiny gameplay window and slowness. I'd rather make things a little blockier and improve the other aspects a bit.

Celius, it's fun to see other people attempting to make something like this on the NES. Thank you for showing me what a different approach might look like. You've made me want to try different things, when I was thinking that I had found the only possible way to make a raycaster for the NES. I hope you continue to work on this, and maybe I'll try these new ideas I wrote above in a program of my own too.

Handwave it as lighting differences. It's enough to explain the change in appearance of the player character in Pokémon Red and Blue for Super Game Boy.

Yes, that's always an option. Doesn't keep the scenes from looking dull or monochromatic, though.

You're absolutely right; I wasn't thinking clearly. It's all so much to remember!


I was thinking something along these lines, where different rooms have different colors. Also, you can cleverly mix colors like having dark blue with green highlights, or green walls with blue shadows. All of the colors are closely related, but when used appropriately, can seem to have more versatility.

But I do find as an artist that a monochromatic color scheme can be very powerful. For instance, if everything in a room is red, it can be atmospheric to the player. It looks boring with the greys in the demo, but when you make it a different shade, it can look really cool.


I was planning on having objects be part of the background. Each object has a sort of "masking" plane, which usually is like a silhouette of the object. It erases the background in that shape before "ORing" the object's graphics onto the background. If I don't do this, objects will appear semi-transparent, which is desirable for things like fire. But what it also allows me to do is use black (color 0) in object graphics. So most of the objects would have an outline around them to help distinguish them.

It definitely could look weird if you were changing object colors every room, but if you use really rich palettes, like red for one room, and blue for the next, and green for the next, the player might just view it as the "lighting" in that room. So the red light makes enemies red, or the green light makes enemies green, etc.


Actually, there is a minimal amount of space remaining in the pattern table. Tile $FE and $FF are reserved, but $E7-$FD can be used to store numeric characters, and I don't think the row right below the display area gets blanked during updates, so it can be used. But it's pretty minimal.


This is true, and is one thing I noticed in your demo that looked very nice. I honestly didn't even think of it when building mine.


That is the one reason I chose not to use sprites for objects (well, that and there not being any space left to work with in the pattern table). How would you choose to manage it when the player does get close? I guess you'd just have to flicker the hell out of all the sprites to show the whole thing.


That was my thought process as well: finding the right balance of sacrifices. I'm not so sure yet that the speed and size of the window in my demo is unbearable for gameplay. I'd like to see it turned into a game to see if the experience could be enjoyable. If the overall atmosphere of the game was good enough, maybe the player could look past the frame rate and display window size.


It's one of the reasons I wanted to show this; just giving the same idea a different take. I'd be very exited to see the ideas you've mentioned implemented!

I am absolutely sorry because what I'll just say will pass me for a total asshole. So I apologize in advance, but I'll be very honest.

Both Tokumaru and Celius' demoes are very impressive technically, I don't think I could code something that advanced with pseudo-3D graphics. However, also consider a gamer point of view, for a person who don't care about the inner working of the console, but just cares about retro games in general. Both of those demos looks absolutely terrible.

Tokumaru's demo is so low resolution that you cannot distinguish anything, it makes you feel like you have a serious eye problem. Celius' demo doesn't look quite as horrible, but it's still extremely low resolution and extremely poor framerate, which would basically make any game unplayable. Displaying anything else than walls would solw it down even more, and that'd lead to frustration if any action/reflexes based game.

Now please don't hate me for this I was just trying to be realistic. For a tech demo this is awesome, in a game it'd be really terrible. However I don't think it's completely useless, it could be part of a mini-game in a greater game that is otherwise in 2D, such as Level-2 and 4 of Contra, the labyrinths of Goonies II, or that 3D train minigame in Final Fantasy 6 when exiting the magitek factory, that also looked absolutely terrible.

I understand what you are saying Bregalad, and I don't think you're a dick for saying it.

I know, and I'm pretty sure Celius knows too, that the NES isn't suited for this (hell, most attempts on the SNES and Genesis sucked), and whatever we manage to code will serve mostly as experiments. None of us expects to make the ultimate NES game, but bringing something new to the platform is always fun, even if it's not perfect.