JohnPCAE

It took a lot of changes to power and ground distribution, but I finally have stable color output! The previous screenshot was a very rare stable frame. Most of the time it was all over the place. The next step is brightness. I need to make the output much brighter. After that it's on to the graphics-mode daughtercard, memory interface to the Master Component, and finalizing capabilities.

I haven't seen any notification of a refund, at least on AA. If he sent it to my email it could have become lost in the endless spam it gets.

I haven't yet come up with a foolproof method for eliminating the missing corner lines without really killing performance, but in the meantime I added an instruction to my multiplication routine to improve its accuracy. It simply rounds the result instead of just chopping off the lower 8 bits. It seems like the missing corner lines happen a lot less often now. raycast_20190214.zip

EDIT: never mind. I finally noticed the flashing counter when you get hit.

When this eventually goes CIB it will be beyond epic.

Looks amazing. One question: maybe add an indicator the boss' health in boss fights?

I understand the math. I should point out that I'm using similar math in my distance calculation: rayDirX is cos(angle) and rayDirY is sin(angle). In calculating the distance above, it divides by rayDirX or rayDirY, respectively, which is equivalent to multiplying by sec(angle) or csc(angle) respectively -- which is exactly what my code does. The only major difference is in how the code steps from one block to the next: I'm tracing two rays at once whereas the algorithm above alternates on which ray to trace based on distance traveled. That aspect is probably something I should look at. A few months ago I couldn't have used that approach because I wouldn't know which face a ray impacted -- as is the case above. However, with everything broken out now into special cases based on the direction of the ray, I should now be able to determine it by implication.

It is using the DDA approach: after that initial calculation for the two rays, it then always increments by one X unit or one Y unit. Everything I described above relates to the part midway down the page where he calculates the step and initial sideDist values (that page was actually my starting point for the algorithm). The major difference is in how I represent walls in the WorldMap array. The algorithm you linked to has every square as completely solid, which only requires a single 2D array to represent the map (I actually started out with the same scheme at first). My map is represented as four *separate* arrays, with each array representing the walls only along a certain edge of each square (top, bottom, left, and right edges). This allows a square to have walls of different colors depending on what edge you're viewing, as well as potentially making doorways possible. This approach requires that the initial collision check calculate the actual position along the X or Y step value instead of just the distance to that point. It also is why I have to use two rays instead of just one. Maybe the answer lies in revisiting how walls are represented?

I hate it when my allergies keep me up. I especially hate it when I'm supposed to work the next day. Until the Allegra-D kicks in, I decided to do some sleuthing. I hand-calculated the values it's using for the screenshot you posted and it's indeed due to roundoff error. These are the values in the screenshot: X 0DEE Y 0E66 A 010A I should probably point out what coordinate values really mean here. All position values are represented in signed 8.8 fixed-point format: the high 8 bits represent the integer part of the value and the low 8 bits represent the fractional part of the value. The meaning of these values with respect to the source code is as follows: XPos 0DEE (in fixed-point form it equates to 0D.EE, or 13.9296875 in decimal) YPos 0E66 (in fixed-point form it equates to 0E.66, or 12.3984375 in decimal) Angle 010A (266 decimal, which equates to 199.5 degrees) The column on the screen with the problem is column 22 (the left edge is column 0 and the right edge is column 39). The way the individual column angles are calculated is as follows: the exact center of the screen corresponds to the A value given above (199.5 degrees in this case). This leaves 20 columns on either side of that angle. In the engine, there are 480 angle "units" to a full circle, or in other words each unit equals 0.75 degrees (that's how I go from A=266 to 199.5 degrees -- multiply by 0.75). Starting from the center of the screen, the column immediately to the left is at angle A - 1, or in degrees, the central angle minus 0.75. Therefore, column 19 represents an angle of 199.5 - 0.75 = 198.75 degrees. Likewise, column 20 represents an angle of 199.5 + 0.75 = 200.25 degrees. For each subsequent column, the angle unit value increments by TWO. The reason for this is that the angle units are scaled for rendering a bitmap that is 80 pixels wide with a 60-degree field of view (the bitmap-mode view that initially displays). That's where the 0.75 multiplier comes from. However, in colored-squares mode the bitmap has only half the pixels, so the units must increment by two from one column to the next to represent the same 60-degree field of view. Putting all this together, the angle units range from A - 39 for column 0 to A + 39 for column 39, or in degrees, Angle - 29.25 to Angle + 29.25 (giving a 58.5-degree field of view). Given this, column 22 (the problematic one in this case) represents a ray angle of A + 5, or 203.25 degrees. When casting rays, the engine actually casts two rays: one that tests at integer X values and one that tests at integer Y values. Testing at integer X values lets it detect walls that face east or west, and testing at integer Y values lets it detect walls that face north or south. It does this by maintaining two pairs of coordinates: (XNext, YEdge) coordinates where XNext is an integer, i.e. XNext & $00FF = 0 (XEdge, YNext) coordinates where YNext is an integer, i.e. YNext & $00FF = 0 For the first pair of tests, the engine has to look at the viewer's position and calculate where the rays would be at the edges of the "box" that the viewer is currently occupying (the maze is 16 boxes by 16 boxes, where the fixed-point representation of position essentially subdivides each box into a 256x256 grid). In this particular example, the viewer's X position is 0DEE, which means box #13 and a fractional position of $00EE. So for a test where XNext is an integer (0D00), it has to calculate what the Y value would be. Likewise, since the viewer is at Y position 0E66, if the ray is to be at Y = 0E00, it has to calculate what the X value would be. This is where roundoff error becomes a problem. When looking along this angle (west-northwest), the formulas for XEdge and YEdge are as follows: XEdge = XPos - frac(YPos) * cot(CurAng) YEdge = YPos - frac(XPos) * tan(CurAng) So each formula takes the fractional part of the position (which determines the distance to the edge of the box -- get it?), multiplies it by the slope (or the inverse of the slope, depending on which coordinate we are calculating), and then adjusts the coordinate accordingly. Pretty simple. So what actually happens? The program has tables for lots of trigonometric functions, including tan and cos. Each table contains 480 entries, which correspond to the 480 possible angular values. Like everything else, they contain values in 8.8 fixed-point format, which introduces the first level of roundoff error -- limited precision. In this example, cot(CurAng) and tan(CurAng) are: cot = 0253 (02.53 if you think in fixed-point terms, or 2.32421875) tan = 006E (00.6E if you think in fixed-point terms, or 0.4296875) By comparison, the actual values that Calculator returns are: cot(203.25) = 2.3275630393965955716880472651463 tan(203.25) = 0.42963390596683602666819711641139 Then it has to multiply them by the fractional parts of YPos and XPos, respectively: frac(YPos) * cot(CurAng) = 00.66 * 02.53 frac(XPos) * tan(CurAng) = 00.EE * 00.6E We can hand-calculate the result by ignoring the decimal points and just multiplying the raw values together, then shift the result right by 8 bits: 0066 * 0253 = 00ED 00EE * 006E = 0066 Subtracting from XPos and YPos, respectively, we get the final values: XEdge = XPos - 00ED = 0D01 YEdge = YPos - 0066 = 0E00 So the coordinates to be tested for the two rays are: (XNext, YEdge) = (0D00, 0E00) (XEdge, YNext) = (0D01, 0E00) If you look at the map definition at the bottom of the source, neither of these coordinates results in a wall hit. They also don't match, which is a red flag. The first ray is landing exactly at the corner (which is problematic in and of itself and can be a separate cause of a blank column). However, that's not the problem in this case. The problem is that it *shouldn't* be landing at that position at all. The second ray is landing just to the right of it. That's the ray that will move up in integral values of Y. If that is the correct ray, it implies that the first ray should be landing somewhere above Y=0E00. We can get a hint by increasing our precision. Instead of shifting the result right by 8 bits when multiplying, let's see what happens when we keep the entire result: 0066 * 0253 = ED12 00EE * 006E = 6644 We can think of it in fixed-point terms as this: 00.66 * 02.53 = 00.ED12 00.EE * 00.6E = 00.6644 Now if we subtract those from XPos and YPos, we get something different: XEdge = XPos - 00ED[12] = 0D00[EE] (think of it as 0D.00EE) YEdge = YPos - 0066[44] = 0DFF[bC] (think of it as 0D.FFBC) XEdge shifted left a tiny bit, but the "box" is still 0D, which doesn't give a wall hit. However, YEdge moved up a tiny bit, enough to move it up to the next "box", which DOES give a wall hit. The extra precision basically brought the two rays closer together. So precision is a problem here.

Yeah that phenomenon has been driving me batty for years. I think it might be due to roundoff error. If anyone can find a solution, I'm all ears!

*sigh* I was simplifying some of the macros and found another bug that I had to fix. However, I also squeezed out a few more unnecessary instructions from the raycaster, so it's not all bad... raycast_20190117.zip

Fixed a couple of bugs and squeezed some more speed out of the raycaster. raycast_20190116.zip

Potentially dumb question here, but how do we know if we got one? Should I expect a PM? As for myself, I haven't been active on this or the Rocketeer thread because I gave up on expecting one long ago.

My RAM carrier boards came today The large chip is a 16k x 16-bit dual-port SRAM. Now my project has all the memory it needs. My pure-graphics-mode daughterboards also arrived today but I haven't assembled one yet. First, I have to deal with a bunch of noise that cropped up in the output signal. Nevertheless, the bird's nest is looking a lot less bird's-nesty now.

I found a couple more optimizations in the drawing code that I frankly can't believe I missed So here's a slightly faster version: raycast_20190109a.zip