The 0,1 & 2 conundrum!

Game Mechanics
#1

I’m working on a little light casting algorithm for my 4k entry (yes, starting early :D).

These rays (actually just bounds of a 2d light cone [sector]) are being projected through a mesh of triangles.

When the ray hits an edge, it either drops a clip vertex & moves along the edge, or it passes into the next triangle.
This is all done through a neat recursive algorithm to minimize code size.

When passing into the next triangle, it passes with it knowledge (the index) of the edge from which it entered.
Thus each triangle will be just a single intersection “enters from edge0; does it intersect edge1? no. Must intersect edge2 then.”

This is an optimization over my previous O(n) intersection tests when using convex polygons; though the reasons for my optimization are code size motivated, not performance.

Anyhow, this is all entirely besides the point.
My question is quite trivial really; I’m struggling to think of a ‘code size optimal’ way of alternating between the values 0, 1 & 2 using just 2 operations.
e.g.

If:
entering from edge ‘0’, I want to check edge ‘1’ or ‘2’ for collision and use the other if appropriate.
entering from edge ‘1’, I want to check edge ‘0’ or ‘2’ for collision and use the other if appropriate.
entering from edge ‘2’, I want to check edge ‘0’ or ‘1’ for collision and use the other if appropriate.

Doing “(x+1)%3” twice works of course, but that’s 2*2 operations and was hoping for something a little smaller/smarter.

  • The operations could work off the initial input, or the result of the first op.
    e.g.
    input -OP1-> output1 -OP2-> output2
    or
    input -OP1-> output1
    input -OP2-> output2

  • OP1 and OP2 do not have to be the same operation (though extra points if they are!).

#2

I’m not clear what you mean…maybe this: (1 << x) & 3

#3

Two independent operations (i.e. 1 instructions) that will do the following:

0 OP1 = 1
0 OP2 = 2

1 OP1 = 0
1 OP2 = 2

2 OP1 = 0
2 OP2 = 1

So this for example:

OP1 = (x+1)%3
OP2 = (x+2)%3

Would work, but is suboptimal as each operation is 2 instructions (addition & modulo).
:edit:
Having thought about it a little more, I’m not entirely sure it’s possible.

OP1 requirements:
0->1
1->0
2->0

OP2 requirements:
0->2
1->2
2->1

#4

So ordering is important?

#5

Nope, so long as OP2 gives the other number to the one OP1 gives me.

:edit:

Hmm, I think I’ve got the best that’s possible.

OP1: (x&1)^1

0->1
1->0
2->1

OP2: (x&2)^2:

0->2
1->2
2->0

If only we had an “&^” operator and bytecode instruction :slight_smile:

I suppose it is marginally better as it’s the same operand being pushed onto the stack, so might compress a little better.
Though by that logic, chaining 2 invocations of (x+1)%3 will probably be just as good.

I should probably stop thinking about this; it’s a horrible distraction.

#6

how about passing the index as an enum instead of an int. Something like this (I haven’t checked to make sure the syntax is correct)

public enum Edge {
    ZERO( 0, ONE, TWO ), ONE( 1, ZERO, TWO ), TWO( 2, ZERO, ONE );

    Edge( int i, Edge op1, Edge op2 ) {
        index = i;
        output1 = op1;
        output2 = op2;
    }

    public final int index;
    public final Edge output1;
    public final Edge output2;
}

and then using it would look something like this

Edge ip; //input edge passed in

...

ip.output1.index //check edge output1
ip.output2.index //check edge output 2

I guess it’s a bit more verbose than using (x+1)%3 and I have no idea about efficiency but that’s another way you can do things.

#7

you need to xor the incoming edge with 3 beforehand:


x^=3;
op1=x&1;
op2=x&2;

but i dont know, if the ^= translates to two bytecode instructions eating up the savings in op1 and op2…

#8

Premature optimisation much… :point:

But anyway, bitwise operations should be faster than normal arithmetic, though not by much.

#9

Try understanding the question before posting an over quoted (often out of context) quotation much :point:

#10

Ah of course, nice finesse.

That might actually come in handy as in my implementation x will be a method parameter, so I can ^3 it beforehand.

#11

Sorry Roquen, your suggestion is good too.

I was being dim :slight_smile:

#12

[quote][quote]
Try understanding the question before posting an over quoted (often out of context) quotation much :point:
[/quote]
Sorry Roquen, your suggestion is good too.
[/quote]
I was tweeking HeroesGraveDev here.

[quote][quote]
I’m not clear what you mean…maybe this: (1 << x) & 3
[/quote]
I was being dim :slight_smile:
[/quote]
It’s one of those expressions that is either immediate obvious or doesn’t make any sense unless you think it through.

I’ve no knowledge of that the various 4k related tools will do in terms of bytecode transformation and assuming I remember by JVM bytecodes what we roughly have is:

ILOADn, ICONST1, IADD, ICONST3, IREM -> 10 (5x2) bytes for both
ILOADn, ICONST1, ISHL, ICONST3, IAND -> 10 (5x2) bytes for both
ILOADn, ICONST3, IXOR, DUP, ICONST1, IAND … ICONST2, IAND -> 8 bytes for both

Abuse’s is likely to be best unless the REP of the compression wins out. Otherwise option that comes to mind is to put the four data values at the start of data or state array and do the array lookup. Test these combos at the end is my suggestion.

#13

(++x)%3
(++x)%3

will certainly compress well, even though IINC is 3 bytes wide.