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.