Written by Coelurus Homepage: coelurus.thorntwig.tk E-Mail: thorntwig@telia.com ICQ: 102114962 AIM: groenkaal Programmers help: BLARGH -------------------------------- The name of this file might seem weird, but the reason will be clear after you've started reading this doc. Your head will really go 'blargh' some times ;) Anyway, onto the facts. This doc tries to explain some interesting things I learnt during the development of GEMINI. I hope it will be of use to some of you ti83(+)- programmers out there :) Unlimited doors --------------- One thing I really wanted was to make sure doors were handled in a very simple manner. I didn't want to keep a full record of all available doors, then loop through all doors every frame to update them... of course, we could only check the doors the player sees when raycasting, but then doors behind a newly turned player wouldn't close properly... Also, I wanted to doors to be very easy implemented when creating the maps. So, the best way I could think of was this: Reserve data for 3 doors in RAM. I should be able to read if the door is open, how much AND, the key to this, a pointer to a door in the level. All doors in the level should reserve 2 bits telling which of the above info "slots" are used (2 bits are enough for null and 3 slots). So, let's try a scenario where the player opens a door: The player opens a door. Finding the door is really simple, we know where the player is and where he looks. So, we now the offset in the level where the door is. Then we check the four slots. As fast as we find an empty one, we set it to be open, the slider is set to be closed and the pointer to the offset to the door the player just opened! Got it? So, every frame, we only check 3 slots! If one is active, we update the info in that slot, which is all we need. When the door has closed, we take the pointer and reset the door in the level at that offset. That door is no longer pointing at the door data slot. When in the raycasting routine, and we hit a door, we check the 2 bits that index to one of the 3 door slots. If these bits are 0, no slots are used. But if they were not 0, we got to the door slot the bits tell us and get the data from there. We just scaled down 34 doors to 3 :) It might be a lil' weird, but it's a very clean way of allowing unlimited doors in the level. I did a similar thing with the pushable walls, but since they are very rare, I only had one slot for all of them. The drawback might be the use of 2 bits. I use another 2 bits for the keys, and "whoops", we only have indeices to 8 textures. But that's far enough for doors. Unlimited objects ----------------- This is much the same as the doors, but simpler. We don't want to create a new record for every obj, so all extra storage that might be used by the raycaster is stored along the obj declaration. For example, the position of an obj must remain intact in the data files, but we must also be able to alter them. All I do, is make space for another position and at startup, I copy the original position to the extra. Then, the raycaster ONLY alters the extra position, and we don't need to create a record for all objects. Perfect! The bad thing is that all objects must be looped through every frame, there is no escape from that :/ But there is a golden rule: "What you don't see, doesn't hurt you" So, as fast as we see that an object is not to be handled, we go to the next. "Early exclusion" It goes quick in my game anyway... Compression ----------- Everybody seem to be using RLE these days in the TI-community... It might be good for linear run-lengths of equal data, but otherwise, it's crap! The raycasting levels have very varying tiles, due to paths, walls, doors, all kinds of different textures and stuff like that. If I'd want to have two-textured walls beside each other, RLE would just enlarge the sizes of the levels. And very, very few people doing compression actually had another method than RLE, so I wanted too :) So, I decided to try a widely used technique, the LZSS technique, which is actually used, in a modified form, for practially ALL compressed file formats, such as ZIP, RAR etc. I settled for it, due to its simplicity and proof to have a very good compression ratio. The theory behind it is: patterns. So, instead of searching for run-lengths of equal data, one searches for sub- strings that occur many times in the data. Or more specifically, we search for a matching sub-string behind the current position in the data to compression and the data right after the current position. To keep down processing power, we set some restrictions to the compressor, so that we don't compress too much and it just becomes a time-consuming business. The program I used compresses a 32x32 level faster than you can blink, and the ratio MAY go down to below 10%! Mostly, the levels for this raycaster goes some under 40%. That's enough for me anyway :) You may take the code for the LZSS compression-things. Please give some credit (read readme.txt) to me, and perhaps even the founders of LZ. Raycasting itself ----------------- I can write a book about this, but some people already have, so to speak. There were numerous docs on the net about this, but sadly, most are gone today. My greatest sources of raycasting are: PXDTUT (7 & 8, NOT 1) The original Wolfenstein source code by ID software www.permadi.com/ (everybody else seem to learn from this, so I included it) And some ancient Pascal-sources I had, showing off some raycasting. I don't have them anylonger... Note that my raycaster tends to be very slow some times. Only you noticing should fix it, so that you know what to fix. I'm sure there are loads of opz to implement, but I'm getting fed up with this game (bugs, bugs, bugs, I see them everywhere! ;) ) Texturing --------- The concept of texturing won't be explained here, as there are many (still today), MANY docs on this subject on the net. It's really simple, the hard thing is to make it quick... Which is where this section comes in. As quick as you do texturing, the raycaster will slow down like heck... I don't know how quick it will run if I remove the textured walls. Anyway, how did I do it? Normally, you do something like this (assume fpm is handled correctly): [ C-CODE ] x = column; y = wallCoordinate; v = 0; vs = TEXTURE_HEIGHT / wallHeight; for (y = y0; y < y1; y++) { display[x][y] = texture[u][v]; v += vs; } [/ C-CODE ] That divide must be replaced with a LUT (LookUp Table), divisions are awful! The first opz coming to mind, is: Use pointers for the display and texture Yup, and that would give: [ C-CODE ] x = column; y = wallCoordinate; disp = display[x][y]; v = 0; vs = TEXTURE_HEIGHTS[wallHeight]; tex = texture[u][v]; for (y = y0; y < y1; y++) { *disp = *(tex + v); disp += DISPLAY_WIDTH; v += vs; } [/ C-CODE ] Where the v's in the LUT have already been multiplied by TEXTURE_WIDTH, so that we get direct V-coordinates. It's still a little slow, so I had a look on Wolfenstein's texturizer. Their optimization was very clever, but needed LOTS of memory. They stored every single wall-height possibility as code. So, if the wall heights could be min 1 and max 100, they stored 100 code- segments, all specialized for just that height of wall! The texturizer will be lightning fast this way, but there is not enough memory on the TI-83(+)s. So, I had to simplify their code a little. Instead of storing each possible wall-height as code, I stored each possible change in v for every wall-height. This means, that for every pixel on the screen, we already know how much to increment the V-coordinate by. Sure, this takes a lot of mem too, but not as much. This is one of the things that make GEMINI as big as it is :) Later, I found that this method was also used in Maze3D. So, I assumed this was an acceptable idea, and kept it. The code for it became very little in z80: [ C-CODE] x = column; y = wallCoordinate; disp = display[x][y]; v = 0; tex = texture[u][v]; vss = vs[wallHeight]; for (y = y0; y < y1; y++) { *disp = *tex; disp += DISPLAY_WIDTH; tex += *vss; vss++; } [/ C-CODE ] Only simple pointers, no fpm-handling at all in this function. In asm, it can be packed together into a VERY small packet of code, check it out. I used some self-modifying code for the bits. Instead of having 'or's and 'and's, I used 'bit's and 'set's and 'res's. They're faster than using masks, because the masks have to be restored. If you store the bit-commands directly, you'll get an almost awesome speed-boost. Coupled with shadow registers (instead of pushs and pops)... woohoo! I don't think the texturizers need much more opz, but feel very free to fix them. Hmm, not much more to say in this doc. You got the source code, and it contains numerous comments. Contact me for any questions, but keep them in reasonable limits (don't ask me what 'ld' does... ;) ). You can find the contacts at the top of this doc.