Raycaster Experiment

Use this forum to share and discuss Uzebox games and demos.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Raycaster Experiment

Post by uze6666 »

I guess that could work, though at 20 cycles/pixel that will be pretty low res. That mock up looks enticing though! Such a mode would really be cool. :)
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

Yeah 20 just seems too low, I think removing textures does make lower resolution more forgivable in general though. I will redo what I had before, but I was pretty sure it worked out with just branching...but there is the last awkward leg that there is no way to hit 18. I take some stabs at this once annually, so I had to see if something bit me but nope. If 80 is achieved, I was pretty careful to craft that image, and should look exactly like it which I think is enough. The higher vertical resolution at least allowed something that looks like a doom shotgun to be, even if horizontally pixels are very wide you can vertically dither a bit.

There is probably about enough flash for 8 rotations of a couple walking, hurt, shooting and 1 always front facing dying sequence plus some weapons for the space marine, blood splats, shot puffs, ammo sprites and other front only facing things. Something like calculating sound falloff, even if a sound should be hearable at all, is expensive. Any enemies that need to pathfind or run sight checks, forget about it, I think dedicated to only drawing and basic movement 10fps would be an accomplishment. Doom used blockmaps for all possible sector combinations to quickly determine if things had any possibility of having a straight line to points in sectors because it was so expensive...so I mean dumb rendering terminal, and game logic handled on a PC, just column calculating and sprite blitting on Uzebox, streamed over Uzenet. Sounds pretty far fetched.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

Bah, I give up, 18 cycles seems to work, but not with 4bpp ram columns AND ram columns that only start as high up as a sprite does. That is pretty critical, even though at 80x100 @ 4bpp you could damn near have a ram column on EVERY column where it takes the ENTIRE column(even for something that is only say the gun sprite), you really have to double buffer them to avoid terrible tearing. So you can only have them on less than half the columns. Still might work out with some flicker priorities, but I'll try again next year :roll:
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

I had a few thoughts about a custom renderer for a raycaster style renderer that I wanted to share:

Firstly, ignoring any sprites and assuming that the walls are solid colour (no textures). We have to somehow determine whether the current pixel is ceiling, wall or floor. One way to do this would be to have a lookup table that conceptually looks a bit like this:

Image

The table would be 256 bytes long, (in the image, the table spans from top to bottom, ignore the width of the image). In the example: green indicates floor, blue is ceiling, and grey is the wall.

For each screen column, we have a buffer which stores the 'wall size', which would be in the range of 0-64. For the top half of the display, we have a 'scanline' register which increments for each line from 0 to 63. For the bottom half of the display, the 'scanline' register decrements each line, starting at 191 down to 64.

The trick is this: to find the colour during the render loop, you can just ADD together the 'wall size' value from the buffer and the 'scanline' register. This is now an index into the look up table for the correct colour.

The inner loop might look a bit like this:

Code: Select all

; preamble:
; look up table is 256 byte aligned in RAM
; ZH is the base address for the LUT
; r16 is the 'scanline' register that is incremented from 0->63 for the top half of the screen, decrements from 191->64 for the bottom half
; Y is the pointer to the wall size buffer

ld ZL, Y+    ; Load the 'wall size' from the buffer [2 cycles]
add ZL, r16    ; Add together wall size + scanline to get LUT position [1 cycle]
ld r17, Z    ; Load the colour from the table [2 cycles]
out r17     ; Display the pixel [1 cycle]
In this most basic form, we have only one wall colour but have squeezed it into 6 clock cycles. The effective resolution would be 240x128.

For multiple wall colours, there needs to be multiple look up tables. It might be sensible to store them in program memory, so the loop might look more like this:

Code: Select all

ld ZL, Y+   ; Load the 'wall size' from the buffer [2 cycles]
ld ZH, Y+   ; Load which LUT to use [2 cycles]
add ZL, r16   ; Calculate the LUT position [1 cycle]
lpm r17, Z  ; Load the colour from the table [3 cycles]
out r17;  Display the pixel [1 cycle]
In this case, 9 clocks per pixel so a resolution of 160x128.

For displaying sprites, one option would be a 1bpp buffer which covers the whole display, which is overlaid during the rendering loop. This would mean all sprites would only have a single colour, but walls could be different colours. I think this could be possible to fit into 13 cycles, which is about 110 pixels wide resolution. There should be plenty of RAM for a 1bpp buffer this size. Also room to double buffer the overlay if the buffer's vertical resolution is halved.

Thoughts?
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

I think the bare minimum is 2 wall colors, at least that way you can make visual depth sense of close corridor walls leading to large open room walls far away. Better would be 4 though. Also, increasing the horizontal resolution proportionally decreases the temporal resolution. I would expect 240 columns raycaster would be about 1/2 the speed of one at 120, and in the end I'd bet money it will be a struggle for 15fps with full asm+fixed point engine anyway. The offset to that is, it is very easy to double up columns(so cut column calculations by 1/2) while moving, then you would still have the ability of a crisper image while standing still at 240...so more about ram considerations maybe?

I do think non-textured is the right direction and your LUT method seems the best possible cycles wise, nice. It gives up multi-height walls, but upon further research they are too slow to calculate anyway(...which sucks...because non-instant open doors are nice to have). I think a vertical resolution of 96 would allow a little more smooth walls and help with sprites details though. I would adopt your method if I was ever to work on something like this again, hopefully you have a little more steam for this idea than I have left and can take it forward.

I think the sprites need a minimum of 3-4 colors personally, though I think you would have to add a number of cycles to implement it. At least, I would think either the walls and/or the sprites need to be double buffered depending on how you handled things(only start blitting sprites at the start of a fresh frame we will have time to finish on. On previous frames, let wall calculation take as long as it needs and precalculate where sprite lines will go?). As soon as you double buffer and add more colors I think it starts to approach the ~14 cycle range. As soon as you want to only use ram for areas that have a sprite you start creeping to 18 cycles, but I would be happy to see something that works out to avoid that pitfall.

Edit-for a couple extra cycles, perhaps you could have shorter walls point to a different slightly darker version of the color. That way you would get a "free" lighting depth effect which might make 2 wall colors look pretty good. Also I am interested to see what you come up with for your 1bpp overlay.
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

I think you are right about 2 wall colours being the bare minimum. I was thinking again about the wall colour look up table, and it would actually be possible to support two colours in a single table. Instead of storing both the floor and ceiling colours in the table, store two different wall colours in the table. The 'wall size' buffer could then offset by 128 if using the alternate colour. (This works out quite nicely, as just setting the most significant bit on an entry sets the alternate colour). For rendering the bottom half of the display, just decrement the 'scanline' counter, which effectively mirrors the output. To make the floor a different colour to the ceiling, just switch to a different look up table when half way down the display.

You mentioned about doors: there is no reason why we couldn't do doors in the style of Wolfenstein 3D, where they slide horizontally to open. Doors could be indicated by a striped pattern to make them stand out.

So on the subject of calculating the size of each column in the display: with a traditional raycaster, you can halve the resolution to halve number of calculations for speed, as you mentioned. I've been developing a port of Wolfenstein 3D to the Gamebuino (an AVR based 8-bit handheld console) and my first iteration I found that my raycaster was too slow and lost too much precision. I then saw a simple demo which took a different approach, and was much faster (even though the code was using floating point!) I adapted the method to my Wolf3D port, but rewrote it using 8/16 bit integer maths.

The alternative to raycasting works like this:
- For each solid map cell in the view frustum (within a certain range):
- For each wall in the cell that is facing the camera:
- Rotate the two points of the wall into 'view space'
- Apply perspective projection (i.e. divide by Z) on the two points. (You now have screen position X, and the 'size' of the wall at the two edges)
- Step between the two points, linearly interpolate the wall size.

For the linear interpolation, I used something a bit like Bresenham's line algorithm. I did actually try making a Uzebox version using the 2bpp bitmap video mode, but it was too slow as I was burning most of the cycles on drawing to the bitmap buffer. However, if the column rendering is done in the video mode, I'm optimistic that it could run at 30Hz, maybe even 60!

So here is my idea for what the inner render loop would look like with a 1bpp sprite overlay:

Code: Select all

;;;;;;;;
; XH = wall lut
; Y = bitmap pointer
; Z = wall buffer
; r17 = current scanline
; r19 = 'tiles' left

loop:
ld r16, Y+			; Load the bitmap byte [2]

; pixel 1
ld XL, Z+			; Load the wall height [2]
add XL, r17			; LUT offset from scanline [1]
ld r18, X			; Load the wall colour from LUT [2]
sbrc r16, 0			; If bit 0 set in bitmap: [1]
ldi r18, SPRCOLOUR	; 	then set output colour to sprite colour [1]
out r18				; Output pixel [1]

; pixel 2
ld XL, Z+			; Load the wall height [2]
add XL, r17			; LUT offset from scanline [1]
ld r18, X			; Load the wall colour from LUT [2]
sbrc r16, 1			; If bit 1 set in bitmap: [1]
ldi r18, SPRCOLOUR	; 	then set output colour to sprite colour [1]
out r18				; Output pixel [1]

; etc for another 6 pixels 

dec r19 [1]
brne loop [1/2?]
There would have to be some shuffling around and perhaps some padding of NOPs to ensure each pixel was the same width, but I think that it would work out around 10 clocks per pixel, or a horizontal resolution of about 144 pixels. With a resolution of 144x128, it requires 2304 bytes for the 1bpp sprite overlay buffer. It might be sensible to double buffer the overlay by halving the vertical resolution, in which case the overlay buffer is reduced to effectively 144x64.

Although 1bpp for sprites is quite limiting, I think that it could be possible to create something quite compelling within the limitations. It might even be possible to pre-scale the sprites in flash (as each frame could be quite small), and then the blitting could be really simple (and fast!)

This is a snippet from an early version of my Wolf3D port before I added any game logic, but it shows what is possible with an 84x48 1-bit screen:
Image

For reference, here is the original Gamebuino demo that I mentioned (not very optimised, but easy to read):
http://gamebuino.com/wiki/index.php?tit ... _rendering
My Wolf3D port is on my github:
https://github.com/jhhoward/Wolfenduino

Another thought: with a custom video mode, it would even feasible to have 2 player split screen! :lol:
User avatar
Gosma
Posts: 68
Joined: Thu Oct 24, 2013 7:31 pm
Location: Santos, Brazil

Re: Raycaster Experiment

Post by Gosma »

So cool.. :D reminds me the first gameboy! :D
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

Cool screenshot I wasn't expecting that quality from monochrome. Seems like you are pretty far a long with your engine too. I think you can pull it off; quite interested in this.
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

D3thAdd3r wrote:Cool screenshot I wasn't expecting that quality from monochrome. Seems like you are pretty far a long with your engine too. I think you can pull it off; quite interested in this.
Thanks! The engine would need a fair bit of reworking to work with the uzebox / new video mode, probably some asm in places to keep things running smoothly.

I put together some mockups, this is what it might look like based on the 2 colour walls + 1bpp overlay idea:
Image

And what split screen could look like:
Image

The choice of colours isn't great but I think illustrates the point. The top / bottom borders of the screen could have flash tiles like mode 3 for displaying health, score, etc without causing any extra impact on performance.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Raycaster Experiment

Post by uze6666 »

Very cool! Even with a mono overlay it's going to rock if it can run at 30 or 60 fps. Great idea too for the pre-scaled sprites. :)

Uzenet death matches! :twisted:
Post Reply