Can I write a game in 3 weeks?

[deimos]

I'd like to change 2 colours 2/3 of the way through each line in the area of my instrument panel where the artificial horizon is shown, because, well, I want more colours.

I should have no problem writing the copper instructions to do this, but, what impact is it likely to have? There'll be 2 waits and 4 moves on each of the 40 lines affected, which are in 3 bitplane mode.

If I change the two colours once more, to make three sections with different colours, will that just ruin everything?

And if I try and be clever and write it as an actual loop with skips and jumps, will that impact things significantly worse?

[roondar]

When you talk about impact, do you mean the impact in lost performance?
If that is the case, don't worry about it - a Copper move only takes up 2 DMA slots out of about 70.000 per frame. A wait is 3, so still not a lot.

So, for your colour changes we're looking at 160 moves and 40 waits. This corresponds to about ~1,5% of the total available time in a frame.

[deimos]

Originally Posted by roondar

When you talk about impact, do you mean the impact in lost performance?
If that is the case, don't worry about it - a Copper move only takes up 2 DMA slots out of about 70.000 per frame. A wait is 3, so still not a lot.

So, for your colour changes we're looking at 160 moves and 40 waits. This corresponds to about ~1,5% of the total available time in a frame.

Thank you. Those numbers help put things into perspective.

[deimos]

The end has come. Could I write a game in 3 weeks? No.

But I'm not going to stop. I have a forced break of a couple of weeks at least, but then I'll get back into it, albeit at a slower pace.

I'm going to finish the graphic design of the instrument panel before I write any more code, as I think it will be easier to be motivated if I'm looking at something that looks good and finished, and it will also allow me to alternate major bits of work with the minor bits of making another part of the panel work.

I've currently got 10 colours on my 3 bit planes, but I'm going to try and make that more, both with more colour changes, cleverly done so I don't have to change two colours at the same time, and with an overlay of sprites (which I still have to learn about).

Regarding the actual game? When implementing full screen mode I found I couldn't access the bottom inch of the screen with the (an, dn) addressing mode I was using (which was fine before I changed to interleaved bitmaps). At around the same time I noticed that F/A 18 Interceptor never draws in that bottom inch, even in full screen mode. That's led to a lot of thoughts tumbling around my head. Maybe there's a shortcut that I've missed that relies on interleaved mode.

Also, I've learnt that the rotation transforms I've used are great, until you want to use them. The yaw, pitch, roll system I've used does that, but once you can actually control your object interactively, it just doesn't. I've done a lot of reading and watched a lot of youtube videos over the last couple of days, and apparently the answer is "quaternions". Fine. Just more maths, but can I do it in fixed precision? Is 2:14 enough? I'll probably start another thread about that, but it might be another "follow along while he repeats everyone else's mistakes again" thread.

And, the coordinate system I've chosen seems to be different to what everyone else uses in 2019. I'm not sure if I should fix that now - the maths is at the edge of my limits already, having to convert between coordinate system while trying to understand new things like quaternions might break me.

[sandruzzo]

@deimos

Hell of Job, and keep going on! Try to keep your world from 1 to -1, maybe you can gain a lot of precision whitout using more bits for you numbers. I used this way on Pc, since Floating point precision issue.

https://blog.demofox.org/2017/11/21/...int-precision/

[saimon69]

Originally Posted by deimos

Regarding the actual game? When implementing full screen mode I found I couldn't access the bottom inch of the screen with the (an, dn) addressing mode I was using (which was fine before I changed to interleaved bitmaps). At around the same time I noticed that F/A 18 Interceptor never draws in that bottom inch, even in full screen mode. That's led to a lot of thoughts tumbling around my head. Maybe there's a shortcut that I've missed that relies on interleaved mode.

You could "cheat" and use the trick that Obliterator seems to do, with two screens - the second one down to 75%? (not a coder so my suggestion might just be inappropriate)

[Steve]

Quaternions aren't so bad. Just 4D vectors really. I use them in my 3D engine (on PC).

[Hannibal]

First up, great progress on your ambitious goal, Deimos, it's inspiring reading about how far you came in such a short time. Best of luck finishing it some time

Here is my take on the original questions.
1. Whether 2.14 is precise enough, it depends on what you are building, but that's definitely what I would use if writing a 68k 3d engine. If you were building a game like Frontier, maybe higher precision may be needed, but that seems prohibitively expensive. How you choose to transform worldspace coordinates impacts how much precision you need, as the larger coordinates you transform, or the more transforms multiplied together (normal or inversed) the worse the impact. I've shipped a game with a flying section, where the cockpit shakes more as you fly away from the 0,0,0 :-) This was due to using a matrix stack with multiple 4x4, but as you do translation separate from rotation (a must on 68k/fixed point IMO), you should be fine.

2. How often you need normalization to remove accumulated errors: again (and as Thomas said) it depends. For the camera transform, or giant rotating object, errors are much more noticable than for a small object. If you have a hierarchy of objects with multiple transforms multiplied, the error is worse. So no real answer other than see what works for you.
In one game engine I believe we renormalized camera transform every frame, and one other game object transform per frame. This felt like overkill, but renormalization was not too expensive, so we left it like that.

My experience: commercial game dev since Amiga days, mostly working on 3d engine development, including 5 years of working on a character animation system, which means quaternions for breakfast, lunch, and dinner.

My comments about the topics not discussed in the initial post:
3. As for HOW to normalize: I maybe wouldn't actually do square root and multiply, but just shift the squared length (4.28) down by, say, 20-22 bits, clamp it, and use a lookup table to see what it should multiply with to approximately normalize. It's not as precise, but the goal of renormalization is not perfection, but to keep the error from drifting over time. This may be good enough

4. Agreeing with Dan, I am not sure I would be using quaternions on 68k - the benefit of quaternions in my experience are mostly interpolation, fast multiplies and fast renormalization, but converting the quaternion to matrix may be slower than just using matrix multiplies. Deimos, I'm also curious what part of the job rotation matrices can't do (other than interpolation). I'm obviously not talking about just using absolute Euler angles, but using euler angles to generate an angular velocity matrix that is multiplied onto the accumulated matrix each frame.
That said, now I'm curious about the perf difference between the two options now.

[deimos]

Originally Posted by Hannibal

3. As for HOW to normalize: I maybe wouldn't actually do square root and multiply, but just shift the squared length (4.28) down by, say, 20-22 bits, clamp it, and use a lookup table to see what it should multiply with to approximately normalize. It's not as precise, but the goal of renormalization is not perfection, but to keep the error from drifting over time. This may be good enough

I read this as: generate a look up table of inverse square roots that are indexed by the first n bits of the squared length, where n is around 10 - 12, then do a straight fixed point multiply. I can try this and share the results.

Originally Posted by Hannibal

4. Agreeing with Dan, I am not sure I would be using quaternions on 68k - the benefit of quaternions in my experience are mostly interpolation, fast multiplies and fast renormalization, but converting the quaternion to matrix may be slower than just using matrix multiplies. Deimos, I'm also curious what part of the job rotation matrices can't do (other than interpolation). I'm obviously not talking about just using absolute Euler angles, but using euler angles to generate an angular velocity matrix that is multiplied onto the accumulated matrix each frame.

The justification behind using quaternions is the belief that the errors they accumulate are less than if matrices are used, due to there being less multiplications involved. Plus, there is a way to recover from the accumulated errors, to at least get back to a "legal" state. If the equivalent for matrices exists, I'm not aware of it.

The ability to interpolate with them is also attractive, and could make the game feel more polished when switching between camera views, for instance.

There's also a lot of talk online about matrices and gimbal lock. I don't know whether that would be a problem for me, but it made sense to avoid it anyhow.

The conversion from quaternion to matrix does not look like an expensive operation, 12 multiplications, and it is only done once (per object) per frame.

Originally Posted by Hannibal

That said, now I'm curious about the perf difference between the two options now.

No measurable difference, the quaternions are well outside the performance critical sections.

[Tigerskunk]

Like I stated a couple of times already in Deimos thread about 3D stuff in the coding section, I am so happy someone is starting to work on 3D engine game stuff on the Amiga.

It was so prevalent back then, and my favourite genre. If I were not so bad a t math, I'd love to do it myself a bit..

So, looking forward to what you come up with, Deimos!

[deimos]

Originally Posted by deimos

I read this as: generate a look up table of inverse square roots that are indexed by the first n bits of the squared length, where n is around 10 - 12, then do a straight fixed point multiply. I can try this and share the results.

So, I've done this and here are the results:

           = (1054, 0B90, 22EC, CE3C) [10007430]
           = (0DDD, 09D5, 2372, CD7E) [100044CA]
           = (0B5E, 0814, 23E2, CCDF) [100035D9]
           = (08D8, 064E, 243C, CC60) [10000814]
           = (064C, 0484, 247F, CC01) [0FFF99A2]
index = 1023, inverseSquareRoot = 4004
normalised = (064C, 0484, 2481, CBFD) [1001CBAA]
           = (03BC, 02B8, 24AE, CBBE) [10019D98]
           = (012A, 00EA, 24C4, CB9F) [10017399]
           = (FEE9, FF55, 24C5, CB9E) [10019767]
           = (FCFB, FDFA, 24B8, CBB1) [1001AADE]
           = (FB5F, FCDB, 24F6, CC09) [1001C54F]
           = (FA12, FBFD, 2582, CC9F) [1001E212]
           = (F910, FB63, 265E, CD71) [10019FAE]
           = (F857, FB12, 278A, CE7C) [10021D49]
index = 1025, inverseSquareRoot = 3FFC
normalised = (F857, FB12, 2787, CE7F) [10000707]
           = (F7E5, FB0D, 28FF, CFC8) [0FFFEBC3]
index = 1023, inverseSquareRoot = 4004
normalised = (F7E4, FB0C, 2901, CFC4) [10022BB1]
           = (F7B6, FB59, 2AC0, D14E) [10025E19]
index = 1025, inverseSquareRoot = 3FFC
normalised = (F7B6, FB59, 2ABD, D150) [1000A2DE]
           = (F784, FBB5, 2CB4, D331) [100097FA]
           = (F750, FC20, 2ED8, D570) [10006440]
           = (F722, FC8E, 30E0, D7C9) [10007F19]
           = (F6F9, FCFE, 32C9, DA3B) [1000359F]
           = (F6D6, FD70, 3493, DCC4) [10000E5D]
           = (F6B8, FDE3, 363D, DF63) [1000065B]
           = (F6A0, FE58, 37C5, E216) [0FFFB9BD]
index = 1023, inverseSquareRoot = 4004
normalised = (F69F, FE57, 37C8, E214) [10019622]
           = (F68D, FECD, 392E, E4DA) [100147BA]
           = (F680, FF44, 3A71, E7B0) [100148F1]
           = (F679, FFBB, 3B90, EA95) [10014383]
           = (F678, 0032, 3C8A, ED87) [10011999]
           = (F67D, 00A9, 3D5F, F085) [1000F6F4]
           = (F686, 0111, 3DFA, F32B) [1000B2A2]
           = (F691, 016A, 3E68, F575) [1000AFBE]

For each frame that I draw I output the current quaternion (the lines starting with an =). I then attempt to normalise. This function only outputs a log entry if it makes a change to the quaternion, and it outputs the index into the table as well as the value from the table. And index of 1024 is 0x4000 = exactly one, so the function returns early in that case.

Only around 1 in 10 frames end up with a change to the quaternion, and those changes always and up with an index into the table of 1023 or 1025.

I think that tells me I need to use more bits in my lookup and narrow my table more (I already cut down to inverse squares between 0.5 and 1.5 to fit in 2:14, but it's now obvious that I need a tiny fraction of that range). And perhaps because my numbers are all positive I can use 1:15 for a bit more precision.

I'm kind of winging it now, if you can't tell.

[deimos]

Originally Posted by deimos

I think that tells me I need to use more bits in my lookup and narrow my table more (I already cut down to inverse squares between 0.5 and 1.5 to fit in 2:14, but it's now obvious that I need a tiny fraction of that range). And perhaps because my numbers are all positive I can use 1:15 for a bit more precision.

I've made these changes and the look up table is still way bigger than it needs to be. Looking back at the spreadsheet I used to generate it, I can see it only ever looks up inverse squares for values between 0.999573 and 1.000244, which must correspond to the arbitrary maximum error of 0x10000 I've allowed in my code:

BOOL NormaliseQuaternion(Quaternion * q) {
    extern UWORD inverseSquareRoots [];

    LONG lengthSquared = QuaternionLengthSquared(q);
    if (lengthSquared == 0)
        return FALSE;

    if (ABS(0x10000000 - lengthSquared) < 0x10000)
        return FALSE;

    UWORD index = (lengthSquared >> 14) - 16384 + 1024;

    if (index == 1024)
        return FALSE;

    UWORD inverseSquareRoot = inverseSquareRoots[index];
    KPrintF("index = %ld, error = %ld\n", index, ABS(0x10000000 - lengthSquared));

    q->value[A] = (((LONG) q->value[A])  * ((ULONG) inverseSquareRoot)) >> 15;
    q->value[B] = (((LONG) q->value[B])  * ((ULONG) inverseSquareRoot)) >> 15;
    q->value[C] = (((LONG) q->value[C])  * ((ULONG) inverseSquareRoot)) >> 15;
    q->value[D] = (((LONG) q->value[D])  * ((ULONG) inverseSquareRoot)) >> 15;

    return TRUE;
}

Also, the area of the lookup table we seem to end up in seems very linear. Makes me wonder whether I can just approximate it as a straight line:

        dc.w    32775
        dc.w    32774
        dc.w    32773
        dc.w    32772
        dc.w    32771
        dc.w    32770
        dc.w    32769
        dc.w    32768 ; one
        dc.w    32767
        dc.w    32766
        dc.w    32765
        dc.w    32764

I can go a long way before I find a pair of numbers that aren't different by exactly 1.

[grond]

Originally Posted by deimos

Only around 1 in 10 frames end up with a change to the quaternion, and those changes always and up with an index into the table of 1023 or 1025.

I think that tells me I need to use more bits in my lookup and narrow my table more

I assume the base vectors still cripple away with this approach, i.e. become skewed? If so, I think you could always recalculate the third base vector from the renormalised first two and change on each iteration which vector you recalculate from the other two. The recalculated base vector should always be orthogonal to the plane defined by the other two. In this way I guess you should be able to keep the angles OK over time and the simplified renormalisation could work well enough to keep the errors within a reasonable boundary.

[deimos]

Originally Posted by grond

I assume the base vectors still cripple away with this approach, i.e. become skewed? If so, I think you could always recalculate the third base vector from the renormalised first two and change on each iteration which vector you recalculate from the other two. The recalculated base vector should always be orthogonal to the plane defined by the other two. In this way I guess you should be able to keep the angles OK over time and the simplified renormalisation could work well enough to keep the errors in a sensible boundary.

The base vectors don't become skewed with a quaternion approach, as the rotation matrices are always calculated fresh from the quaternion. All effort goes into keeping the quaternions good instead, and they can't get skewed as they are really just a twisty vector.

[Hannibal]

(Sorry I posted my reply in the wrong thread - if there's an admin, feel free to move my comment and replies to it to the fixed point maths thread.).

Yeah, you should be able to approximate as a straight line.

gimbal lock - that would only be a problem if you were rebuilding the matrix from euler angles every frame, but if you have a matrix and you multiply it onto an angular velocity matrix, it wouldn't be a problem.

Interpolating - if you have a camera offset matrix built with euler angles, and multiply the camera matrix onto it, you can interpolate the euler angles.

Error accumulation and normalization - you may be right that matrices accumulate more errors, I'm not sure. In the past I've normalized my matrices using 6 steps: normalize row 0, row 1, row 2, and then column 0, column 1, column 2. i.e normalize the vectors at 0/1/2, 3/4/5, 6/7/8, 0/3/6, 1/4/7, 2/5/8. That said, I don't know 2.14 is so imprecise this will cause visible shakiness with this method, and in that case, quaternions is probably better.