Another Raycasting Demo

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...

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.

I definitely understand. Come to think of it, I had a hard enough time playing Doom 1, and that was on PC, and went way beyond normal raycasting. Perhaps it'd be entertaining for like 1 level, but sitting down to a full blown game could be exhausting. Probably the only people that would want to play it are really hard core, old school FPS players. And masochistic gamers who like to be tortured by insanely hard games.



OK now, both of our demos look way better than that piece of shit! =) The game had no excuse displaying something that awful; they could have done much better.

I absolutely agree with you. It's really great you guys can bring something new, I am not denying that. I'd just that that the idea to base an entiere game in those graphics mode would be a terrible idea.


Well I don't remember exactly but I remember it was looking absolutely terrible. Even back in 1994 it would not have been impressive I think.


I don't think the usage of such a pseudo-3D raycasting is automatically restricted to FPS. Think how it could just be that "different" level in an otherwise 2D game. Even if it was just a room to explore or something. It could suit lots of different games, RPG, platformers or even investigation games.

In Portopia (that investigation game Enix made before Dragon Quest) there is a giant 3D maze, and you have to traverse it at least once entirely to beat the game. Because you can only advance one "section" at once and do 90° turns, this part has aged extremely badly and looks terrible. However, if it was remade with a raycaster, this part of the game would be much better.

Or do outdoor scenes in an overhead view and indoor scenes with the raycaster, like in Phantasy Star for Sega Master System or Jurassic Park for Super NES.

You know, this could make a lot of sense in something like my Castlevania style game (not yet in development). While it's normally a platformer, it could be cool for the player to have to go through some catacomb style maze to get to another area. I had wanted to put some other fake 3D effects in the game, so it would lend itself well to this.

I really want to play that game, even if you didn't start yet to develop it

I saw this in the side link bar: https://www.youtube.com/watch?v=ZQRFBmGdvUQ
Might be able to do something like that (an adventure game or 3D town for an RPG, etc).

This looks surprisingly good... I'd expect the cardboard cutout effect to be more distracting, but it actually feels like you're walking around in a town. What is distracting though is that it feels like you're a giant, because the textures are all centered on the horizon. I know it needs more computation, but the walls really need to be shifted up according to their distance so that the player doesn't appear to be so tall.

What takes more CPU time: casting the ray for each pixel column or drawing the textures? Because if the ray casting itself takes a lot of time, I think I know how to speed it up with a run-length technique related to portal engines. Ray casting itself is just a special case of portal casting.

From my own experience, scaling the textures is slightly slower, but the 2 tasks were balanced enough that casting a long ray and drawing a small wall wasn't that much different than casting a short ray and drawing a big wall, which kept the performance somewhat constant.


I guess it's still worth speeding up, even if it's not the slowest task. I remember reading about how Doom used BSP (binary space partitioning) for rendering its graphics but I never really understood how that worked. What's the portals approach like?

RLE ray casting starts with a visible sector with a left and right side. You scan the visible sector in strips from nearest to farthest. When you hit a wall, you schedule the wall to be drawn, and then you divide the visible sector into the interval to the left of the tile and the interval to its right. After you've finished enumerating all walls in this strip, you scan the next farther strip. Repeat until all visible sectors have been cleared.

• Orange: Sides of initial visible sector
• Green: Visible wall segments
• Blue: Floor within visible area
• Light gray: Sides of subsectors
• Light blue: Subsector sides extended toward camera origin
• Black: Floor areas that are skipped

The difference here is that each cell in the map is visited once, not once for each pixel column that intersects it. And for the typical 90 degree FOV, you'll never have more intervals active at once than max(width, height) of your map.

Sounds interesting, but I didn't quite understand it yet. I'm a little confused when you talk about nearest and farthest strips... Is a "strip" in this case the same as a wall strip, which is painted with a scaled texture in the end? How do I know which one is the nearest before casting a ray? And how would I go about deciding which texture column to use for each screen column if I don't have rays hitting them at coordinates I can check?

I think I follow you. But I'm not sure how to implement that, exactly. So once the ray hits that tiled block (wall/edge/whatever), you calculate angle of the wall, and render out that tile for that angle, then proceed to the next tiled block/wall the ray hits? Or at least, something along those lines? I wonder if that's what gasega68k did for his Wolfenstein 3D port for the Genesis.

By "strips", I was referring to horizontal strips of potentially visible tiles in the map, colored dark blue in the illustration. "Nearest" is such a strip of tiles that is closest to the camera position (the intersection of the orange line segments). When facing north, the closest strip is the southernmost strip. The left and right side of each strip is determined by projecting the rays at the corners of already-drawn map tiles backward. When the camera is facing west or east more than north or south, use vertical strips in the map instead of horizontal strips in the map.

The procedure is sort of a hybrid between the ray casting of Wolf3D and the arbitrarily shaped sectors of Build, the Duke 3D engine.

Do I need to expand the illustration to an animated GIF of the entire rendering process, or produce a renderer myself in Python?

I was wondering about the effectiveness of simplifying calculations by restricting angles?

For instance, a 90-degree restriction is fairly straightforward; all walls are box-shaped and you rotate at 90-degree angles. What if we did it at 30 degrees? Everything would turn at 30 degree increments, and all walls could only be at a 30 degree angle.

Maybe this offers no improvements, but it feels like you'd be able to calculate things a little faster and have smaller tables, or higher resolution tables.

Also, an animation would be helpful, Tepples.

Coding an example seems overkill if you don't plan on using it for a project of your own... but I'll definitely take you up on that GIF! =)

Animation of RLE ray casting, the intermediate between Wolf3D and Build engines

Key:

• Orange lines: Edges of viewport
• Light blue lines: Edges of area not yet deemed to be obscured
• Light blue blocks: Sectors containing visible walls
• Dark blue blocks: Sectors determined to contain visible floor
• Green at end: Visible walls

Oh, now I see what you meant by "strips". Cool idea! I still don't know how to properly select a texture slice for each rendered column though...

This is a cool idea. I'd always thought about how something like this would work.

If you had solid walls, you could theoretically just find the on-screen coordinates of a wall side's 4 corners, and use a line drawing algorithm to connect the dots. Then after that, use something like XOR filling to fill them in. Though, this would get more complicated when you have partial walls sicking out from behind another wall in the distance. But if implemented correctly, this might make for a fast, high resolution raycaster.

I have always considered something like this. I thought about defining rooms as polygons (which could result in worlds more complex than those built with boxes), and finding the angle and distance to all the corners relative to the player (much like is done with objects) in order to render the graphics. A line drawing algorithm would be used to interpolate the wall heights between adjacent corners, like you said.


Yeah, but I bet there's a decent algorithm that can be used to sort the distances out and avoid wasting processing power on stuff that's not visible. We just have to think carefully.

It's still unclear to me how the textures would be rendered. How to "stamp" the texture without messing up the perspective on walls that are being interpolated? I'm sure there's something about that in 3D literature, but is it feasible on the NES? I'm talking about this:


With typical raycasting, that fires one ray for each screen column, you get the correct perspective for free, but if you only detect the edges of the wall and use a line drawing algorithm (linear) to interpolate between them, you'd get what's shown on the left side.

There's an interesting Game Boy demo called Back to Earth that has slanted walls and decent texture mapping. Maybe their algorithm is worth checking out.

To get perspective correct texture mapping, instead of interpolating texture coordinates u, v linearly across space, divide the endpoints by depth z, then interpolate u/z, v/z and 1/z linearly as you rasterize. To recover the perspective correct u, v divide the interpolated u/z, v/z by the interpolated 1/z.

It's probably faster than trying to trace a ray for every pixel, but can you do it fast/accurate enough on the NES? At least you only have to perspective correct the horizontal texture coordinate for the walls.

You can also compromise by subdividing, i.e. break the rasterized object into two parts with perspective correction at the break, but linearly interpolate from there. This way you can trade speed for accuracy by choosing how many times to subdivide.

I also wondered about this. Assuming you still have strictly vertical walls, you can get the perspective for free for the "Y" axis of the textures. Picture that all of your textures were just walls with horizontal stripes. You would be able to find where these stripes land on each end of the wall, and connect the dots using line drawing. But that only takes care of 1 dimension.

This might defeat the purpose of the method tepples suggested, but what if you performed those checks against sub-cells instead of the entire cell (assuming 1 wall is a cell, and each texture slice is 1 subcell)? So you would determine the end points for each color in each texture slice, and connect the dots. That would take care of the perspective issue. But it would probably defeat the purpose, as doing that many checks and drawing all those separate lines could get really slow.

Another way to think of it is, if you know how tall a given texture slice should appear, how can you find the point at which the apparent distance between the top and bottom of the wall are equal to that apparent height? If you can find the X position of that point, that must be where the texture slice has to go. I'll try and post a picture later with what I'm trying to say.

EDIT: So I tried to draft up some images to explain what I was getting at earlier. Not sure if it's a good idea, or even a new idea (I'm sure it's been thought of already and refined). This is just what I came up with on my own.





Then again, you still have to know the texture slice height. I'm not sure if this would be easy to figure out by itself.

Huh. Interesting!

Many first-person dungeon crawlers used a similar method to prevent using up too much processing time. The optimal method was to read map cells from the foreground, towards the background, and set flags, disabling other cells from being tested. Freeing up memory, and speeding up draw time.

Very good! You really pushed up the NES's power. What I'd like to see is enemy sprites for an RPG battle like Orcs and Elves.

Wow, this is pretty impressive considering the hardware!!!

Without using trig, how is it that you're able to get the texture x-coordinate for mapping in your demo? Is that even possible without a look-up table?!?!
From reading about tokumaru's raycaster, he gets the distance from precomputed tables and adding and even that doesn't lend itself well to getting a precise x-coordinate...

If either of you have any input I'd be interested to hear it.

Since you mentioned my raycaster, I can tell you how I did it:

Like you said, I have a table of pre-computed ray lengths, which are the distances between one block boundary to the next, for each angle. To calculate distances, I start with only a portion of the distance (calculated from the player's position within the block) to find the first boundary, and then I add the whole distance over and over until a solid block is hit.

Once I know the orientation of the wall, I find the side of the triangle the exact same thing I did to find the hypotenuse. I have a table of sides for all angles, I use a portion of the side for the first intersection (based on the player's position within the block), and add the full side as many times as I added the full distance. From that I can easily extract the X coordinate of the texture.

EDIT: Figure I'd try to illustrate it:


Here's a ray starting at the "O", moving upwards to the right until it hits a wall "X". "H" is the hypotenuse (ray length), which comes from a table. "S" is the side, which also comes from a table. The other side is always 1 (i.e. a full block). As I extend the hypotenuse, I also extend the side, and you can see that when the ray hits the all at the very top, the side tells me exactly where within that block the wall was hit, and that's where I get the texture's X coordinate from.

That's actually quite brilliant, tokumaru. Thanks for your in-depth response and diagram!

"Grid Puzzle" on DataGenetics is relevant to raycasting.

Where in the world would the 3D example be useful? That is, unless real 3D TVs exist, like if there was a somehow 1920x1080x1920 pixel television. That would be awesome. (although the framebuffer for a hypothetical 3D system running on it would be nearly 120GB. I'm really weird for thinking of this kind of stuff...)

I'm assuming the way texture mapping is done is by looking at a pixel of the inside of where the polygon or whatever is being drawn in some sort of framebuffer, and undoing the equation that transformed the polygon and seeing where that ends up on the texture? It would be like if you flipped the image 90 degrees to the right when rendering it, it would (presumably) look first at the top left pixel, kind of swing that pixel around from the center of the square, left 90 degrees (some sine and cosine stuff would probably be done) and render whatever the result was in the top left corner, essentially taking the bottom left pixel and putting it in the top left spot. Because it's not always going to match up perfectly, on systems like the PS1, I guess it just renders the pixel it landed closest to (I wonder what would happen if it landed perfectly between pixels. I guess it would just choose whatever one then) while on a system like the N64, it averages the pixels together.

I guess the thought of doing non Wolfenstein texture mapping is completely ridiculous on just about any system that wasn't several hundred dollars from the time period, or latter when the PS1 came out. Isn't the SNES's mode 7 layer done just about like how the PS1 renders polygons? Both don't seem to average colors together, and they both only use 2D coordinates. (Although the SNES can fake it horizontally with hdma.) Now, this isn't even related at all really (not like any of the other stuff I said was) but why is there only 1 layer in mode 7? I assume both PPUs are maxed out doing the transformations, but not all the vram bandwidth is being used, which I thought was mainly what slowed it down (instead of processing). Actually, I guess it would still have to check priorities and stuff, and at that point, there wouldn't be enough CPU time. Well, really, is it a vram bandwidth problem or a processor speed problem? One odd thing I noticed is that the GBA seems to take a bigger hit in rendering "mode 7 layers", as it losses 2 8bpp BG layers instead of 1 8bpp and 1 4bpp BG layer like on the SNES.

Voxel rendering, perhaps. Minecraft anyone?


Pretty much. It just has a lot of precalculated stuff to make it go fast.


They're conceptually similar, the major difference being that the PlayStation GPU renders triangles rather than planes, and it renders to a frame buffer rather than directly to a layer compositor.


In addition to VRAM bandwidth, there's a unit to calculate texture coordinates, and the Super NES has only one of those.


The GBA PPU can also retrieve multiple pixels at once from VRAM because VRAM is word-wide rather than byte-wide. It can't do this in mode 7 (layer 2 of mode 1 or layers 2 and 3 of mode 2).

That's still insane. I guess by the way it's done like this, texture size doesn't matter, only how much of the screen is covered. By precalculated stuff though, is it similar so how the position of pixels in sprite shrinking is precalculated on the Neo Geo? It seems way, way simpler on the Neo Geo though, as if you're only scaling, for making a sprite more narrow, the system I guess just kind of looks at a precalculated table or something that says how the sprite is to be drawn based on the horizontal scaling value, and for making a sprite shorter, it also goes through a precalculated table thing that says what lines of pixels are to be drawn instead of pixels per line, and you can easily put both of them together. The fact that polygons on just about anything that isn't the Sega Saturn are triangles seems to make everything more complicated. Unlike what I said earlier, I don't think sine and cosine could be used, because we aren't always talking about rotation always making a perfect circle.

You know, isn't transparency achieved in a similar (although more complicated) way? I heard it's like you every pixel on the mirror, create an imaginary line between the camera and the mirror, and then have that line reflect of the mirror and follow the reflected line until it hits something, and then go back and draw the result on the mirror. I always warned to know what would happen if you got two mirrors to look glood


I mean, I know that there's no way you could ever have two mode 7 layers, but just one and an extra, regular 4bpp layer. I think this would work according to vram bandwidth, and it isn't going to use the multiplication and division unit.


Doesn't this have to do with the fact that two neighboring pixels aren't guaranteed to be next to one another like they are in a regular tiled layer? It seems like 16bpp Mode 7 layers should have been an option, although then you start to worry about vram space. I guess the reason the GBA can get so much more data from vram is because it is word based instead of byte based, so it's transferring twice the data? That would explain why the SNES doesn't take a dramatic a hit when rendering a mode 7 layer than the GBA.

Super NES VRAM allows one low-byte read and one high-byte read per pixel. The addresses of the two reads are the same except for mode 7 backgrounds. In mode 7, eight map reads and eight texture reads completely fill the time allotted to one sliver of eight pixels. One extra 4bpp layer would be one extra low-byte read and one extra high-byte read for the map entry and two extra low-byte reads and two extra high-byte reads for the pattern data for every eight pixels, for a total of eleven, which exceeds eight by three.

The GBA's PPU is connected to faster memory (four 16-bit reads per pixel) and thus you can have two tiled layers and one "mode 7" layer in mode 1.


Yes.

How about a 1bpp layer? (admittedly, this could work for stars.) Oh yeah, the graphics format always assumes that the color depth is some multiple of 2bits. It was a silly idea anyway.


By this logic, do affine sprites take up twice as many sprite pixels per line, even not in the double sized (for avoiding clipping) mode?

You know, because we're talking about 3D graphics, how exactly does z buffering work? It seems the most logical thing to do would be to order all the polygons from farthest away to closest, but that's probably way harder than it sounds. What I imagine would be the best thing to do although you could only draw polygons in software if it isn't a hardware feature (which it probably is) would be to have every single pixel in the framebuffer have a "depth value". What this would do is if you were drawing a polygon, it would look at every single pixel in the polygon, and before it would look to map the texture on it, it would see if the depth number is below the number of the pixel currently occupying that spot. If the what is to be drawn pixel is below, it just doesn't draw anything and doesn't even bother looking to find the texture for that pixel. If the value is above, it actually looks for the texture for that pixel and draws it into the framebuffer. This could actually explain the "glitchines" that occurs when two textures are very close to one another, but aren't as large as each other (so their coordinates aren't exactly the same) It's like in that example thing you showed,there are "fluctuations" in how the line is drawn (because it can't be a perfect line)

Like in this picture below I made, if you're viewing the picture as if you were from the bottom (as apposed to the "aerial" view you're actually seeing it) it should be pretty obvious that the blue texture is just a hair closer to you, but if you were only looking at one pixel, you'd have no clue on certain pixels. The purple is where the blue and the red texture overlap. On the bottom of the image, it shows kind of what is actually drawn, because say if in a situation where two pixels two different textures are on the exact same spot, the GPU makes the pixel of the newly drawn texture have priority and overwrite the other, the red texture is the newly drawn texture.


You know what would kind of make sense? Why not just blend the colors together like in the example above? It's still not pretty, but it's at least better than nothing.

Speaking of transparency, I just realized that this whole ideology I came up with completely falls apart when transparency is used... Actually, now that I think about it, I've seen in several games where if two transparent things are drawn over one another, only the one with the highest priority is displayed. That actually makes sense, as if it draws the higher priority thing first and then the lower priority, it will see the priority of the pixel is high, and it can't tell that there are two pixels being blended together because it's already been done and the result is in the framebuffer, so it might as well be any color. I guess there actually is some sorting for transparent objects?

A little more than twice, probably because of time spent to set up the coordinate transform. A sprite n pixels wide takes n sprite cycles if not affine or 10 + 2n sprite cycles if affine according to GBATEK.