Commander X16

26 minutes ago, Ed Minchau said:

I'm not being clear. Can the player be pointing in any of those 3600 directions? Or is he limited to 16 (ie N, NNE, NE, ENE, E, etc)? Because if it's the latter, you can avoid doing a bunch of multiplications by looking up variables (indexed by player direction and pixel column) rather than calculating them each time. 

Ah right. I think its around 40 directions. But im not sure. I just took Wolf3D and tried to turn around.

It sounds like a lot of data you want to store, but I havent done the math on it. Right now I spend a lot of RAM on the generated texture-draw code. 

30 minutes ago, Jeffrey said:

Ah right. I think its around 40 directions. But im not sure. I just took Wolf3D and tried to turn around.



It sounds like a lot of data you want to store, but I havent done the math on it. Right now I spend a lot of RAM on the generated texture-draw code. 

Yeah, if it's more than 16 directions (or at most 32) it wouldn't be practical.  But if it is 16 and you keep it at 304 columns, then that's 19 pages of RAM for each lookup. I was suggesting squashing it down to 256 columns so that lookups for 2 variables could be stored in one RAM bank, or if it's 32 directions then one per RAM bank.

Short update:

Now running at 10+ fps ?

The optimizations I did (on top of the previous ones that got me to 7.5 fps) are:

• 
  inlining the fast multipliers, so less copying of values, no jsr and rts
  


• 
  re-using the somewhat "static" parts of the multiplications, so it won't be re-loaded each time (this was harder than it sounds, quite of bit of refactoring done)
  
  
  
  • 
    Cosine and Sine fractions are player-related, and even though they are negated sometimes, they (that is their squares) could be reused for (almost) each ray
    
  
  
  • 
    The (square of the) fraction of the tile the player is standing in -to be used for calculating the initial x/y interception for each ray- could be reused
    
  
  
  
  


• 
  cleaned up the main loop and several other parts
  


• 
  replaced the 16-bit slow divider with a 512-entry table: distance2height (major improvement!!) ?
  

I am quite happy with the speed. The demo plays quite nicely now.

New version released:


 

@Jeffrey - I've managed to dig up the locations of the AdLib music data from the original game files. Fortunately, it's not compressed in Wolf3d so loading it will be easy enough. I've been making a few notes for myself, and tonight's project is going to be a quick and dirty player routine with my "first best guess" at a naive 'translation' between OPL and OPM and see if anything resembling the actual Wolf3d music comes out of the box. Hopefully, all of my time is not spent reading the register layouts for the OPL w/o any sort of code being written. ?

We did catch a very lucky break as far as the game music is concerned - OPL has 9 voices, and Id seems to have always reserved voice 0 for SFX by convention, so that means no more than 8 music voices in the data. Woot!

If it works, then I'll re-write it in assembly and donate the player code to you for your project. The playback rate is strange tho - 700Hz. Not sure how easy that will be to generate amidst the frenzied raycasting. ?

Update:

I wasn't able to get far enough to get actual sound out of the program yet, but I did make a lot of progress. I've got the IMF traversal going (which was trivial I must admit) and I've wired a bunch of registers together, but didn't get as far as freq. / keyon registers. Those work pretty differently. Unfortunately, there's just no way the YM is going to sound super-close to the OPL, depending on what features the tunes use because the OPL has several features the OPM just doesn't have - most notably it can use different waveforms than sine waves. There's also the matter of the percussion voice mode, which I think can be kludged using the VERA PSG.

Hopefully I'll have a demo to post tomorrow night.

7 hours ago, ZeroByte said:

@Jeffrey - I've managed to dig up the locations of the AdLib music data from the original game files. Fortunately, it's not compressed in Wolf3d so loading it will be easy enough. I've been making a few notes for myself, and tonight's project is going to be a quick and dirty player routine with my "first best guess" at a naive 'translation' between OPL and OPM and see if anything resembling the actual Wolf3d music comes out of the box. Hopefully, all of my time is not spent reading the register layouts for the OPL w/o any sort of code being written. ?



We did catch a very lucky break as far as the game music is concerned - OPL has 9 voices, and Id seems to have always reserved voice 0 for SFX by convention, so that means no more than 8 music voices in the data. Woot!



If it works, then I'll re-write it in assembly and donate the player code to you for your project. The playback rate is strange tho - 700Hz. Not sure how easy that will be to generate amidst the frenzied raycasting. ?



Update:

I wasn't able to get far enough to get actual sound out of the program yet, but I did make a lot of progress. I've got the IMF traversal going (which was trivial I must admit) and I've wired a bunch of registers together, but didn't get as far as freq. / keyon registers. Those work pretty differently. Unfortunately, there's just no way the YM is going to sound super-close to the OPL, depending on what features the tunes use because the OPL has several features the OPM just doesn't have - most notably it can use different waveforms than sine waves. There's also the matter of the percussion voice mode, which I think can be kludged using the VERA PSG.



Hopefully I'll have a demo to post tomorrow night.

Cool!! Thanks in advance! ? It would be so cool to have some music.

I need to do a little further digging, but I think I can speed up the math.  John Carmack mentioned in the documentation that there was a better solution staring him in the face.  It's probably staring the rest of us in the face too.

Ok, I thought of one possible speedup. Right now you're doing each column of pixels in order, casting out a ray and eventually hitting a wall; from that spot you're determining the image to use and the column of pixels within that image and what distance (in the direction the player is facing), then pushing that to VERA. Same as Id did back in the day, basically. 

But what if when you push the column of pixels to VERA, you also kept note of the source column of pixels and the distance, and most importantly the map block and the side of the block seen?  

You wouldn't need to cast the rays in a specific order. Instead you could cast a ray to the far left side, another to the far right side, and one to a column in the middle. Then you can keep dividing the image in half and casting rays.

The advantage here is when two rays hit the same block on the same face. All the rays between those two rays will hit the same visible face as those two, evenly spaced between them. So for any given ray to cast, you look at the existing rays to the left and right and if they are both on the same visible face, then you can very quickly fill in all the rays between them without casting at all, just a linear interpolation. 

You could actually fill in that little table first, and then use it to send all of the columns to VERA in order. I think this will more than double the speed; the total number of rays cast will be much less.

42 minutes ago, Ed Minchau said:

Ok, I thought of one possible speedup. Right now you're doing each column of pixels in order, casting out a ray and eventually hitting a wall; from that spot you're determining the image to use and the column of pixels within that image and what distance (in the direction the player is facing), then pushing that to VERA. Same as Id did back in the day, basically. 



But what if when you push the column of pixels to VERA, you also kept note of the source column of pixels and the distance, and most importantly the map block and the side of the block seen?  



You wouldn't need to cast the rays in a specific order. Instead you could cast a ray to the far left side, another to the far right side, and one to a column in the middle. Then you can keep dividing the image in half and casting rays.



The advantage here is when two rays hit the same block on the same face. All the rays between those two rays will hit the same visible face as those two, evenly spaced between them. So for any given ray to cast, you look at the existing rays to the left and right and if they are both on the same visible face, then you can very quickly fill in all the rays between them without casting at all, just a linear interpolation. 



You could actually fill in that little table first, and then use it to send all of the columns to VERA in order. I think this will more than double the speed; the total number of rays cast will be much less.

Thanks! ? I think this a sound idea. Maybe a binary search approach would go well with this.

Not sure how much overhead vs gains would be with this technique. Will have to investigate.  

6 hours ago, Jeffrey said:

Thanks! ? I think this a sound idea. Maybe a binary search approach would go well with this.



Not sure how much overhead vs gains would be with this technique. Will have to investigate.  

Here is what I see for overhead for every column:

1) 2 bytes to point to which column of pixels to check

2) 2 bytes to point to the column to the left which has already been checked

3) 2 bytes to point to the column to the right which has already been checked

4) 1 byte to indicate which map block was intersected by a ray

5) 1 byte (actually just two bits) to indicate which face of the block was hit by the ray

6) 1 byte (actually just 6 bits) to indicate which column of the map block's pixel image is displayed

7) 2 bytes for the distance in the direction the player is pointing (or the value between 0 and 511 corresponding to the bespoke draw routine)

So that's ten or eleven bytes of data that have to be stored for each column.  The first six bytes listed can be generated ahead of time and wouldn't change.

You can set the high byte of the distance to FF for all rays to begin with, and then when you are testing a ray the first thing you do is see if that byte is FF; if not, then you've already linearly interpolated that column and can skip to the next entry on list 1.  If it is FF then you can check the one to the left and the one to the right, and if they have the same group 4 and group 5 you can linearly interpolate the entire range between them.  If they're not the same, then you cast a ray as before.

Column 0 and column 303 would be raycast as before and would be the only two you'd absolutely have to cast.  After that, the third entry on list 1 would point somewhere in the middle and its left pointer would be 0 and its right pointer 303.  Suppose you choose column 256 for the third entry on the group 1 list and column 288 for the fourth entry; after that you've got one group of 256, one group of 32 and one group of 16, so it's all binary splitting from there.  All the linear interpolations would have a power of two in the denominator.  If you wanted to make these interpolations bespoke routines like you did with pushing data to VERA, then there would only be a maximum of 8 of these subroutines. Or you could cast a ray every 16 columns and then try linear interpolations, and have at most 4 linear interpolation subroutines (filling in 1, 3, 7 or 15 entries).

The group 2 value for each column would be the largest value less than the current column number in the group 1 table above the current entry, the group 3 value would be the smallest value greater than the current column number in the group 1 table above the current entry; you can probably generate the first three groups of data with a spreadsheet.  Groups 4 through 7 would be generated on the fly with every image you draw.  If you really need to cram the memory, group 5 and 6 can be combined, both values in a single byte.

At a rough estimate, you'll be able to linearly interpolate 80 to 90 percent of the rays.