Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (788) Games in Android Showcase (234) games submitted by our members Games in WIP (860) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 The 0,1 & 2 conundrum!  (Read 5695 times) 0 Members and 1 Guest are viewing this topic.
Abuse

JGO Ninja

Medals: 71

falling into the abyss of reality

 « Posted 2013-10-09 15:42:50 »

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

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!).
Roquen

JGO Kernel

Medals: 518

 « Reply #1 - Posted 2013-10-09 15:50:18 »

I'm not clear what you mean...maybe this: (1 << x) & 3
Abuse

JGO Ninja

Medals: 71

falling into the abyss of reality

 « Reply #2 - Posted 2013-10-09 16:22:15 »

I'm not clear what you mean[/tt]

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
Roquen

JGO Kernel

Medals: 518

 « Reply #3 - Posted 2013-10-09 17:31:20 »

So ordering is important?
Abuse

JGO Ninja

Medals: 71

falling into the abyss of reality

 « Reply #4 - Posted 2013-10-09 18:06:04 »

So ordering is important?

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

Quote
OP1 requirements:
0->1 (or 0->2)
1->0 (or 1->2)
2->0 (or 2->1)

OP2 requirements:
0->2 (or 0->1, if OP1 gives 0->2)
1->2 (or 1->0, if OP1 gives 1->2)
2->1 (or 2->0, if OP1 gives 2->1)

: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

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.

Jack Ammo

Junior Newbie

 « Reply #5 - Posted 2013-10-09 19:01:29 »

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)

 1  2  3  4  5  6  7  8  9  10  11  12  13 `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
 1  2  3  4  5  6 `Edge ip; //input edge passed in...ip.output1.index //check edge output1ip.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.

fading away until all that's left is but a distant memory
cylab

JGO Kernel

Medals: 194

 « Reply #6 - Posted 2013-10-09 20:12:34 »

you need to xor the incoming edge with 3 beforehand:
 1  2  3 `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...

Mathias - I Know What [you] Did Last Summer!
HeroesGraveDev

JGO Kernel

Medals: 382
Projects: 11
Exp: 4 years

┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻

 « Reply #7 - Posted 2013-10-09 20:23:37 »

Premature optimisation much...

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

Roquen

JGO Kernel

Medals: 518

 « Reply #8 - Posted 2013-10-09 20:31:43 »

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

JGO Ninja

Medals: 71

falling into the abyss of reality

 « Reply #9 - Posted 2013-10-09 23:20:45 »

you need to xor the incoming edge with 3 beforehand:
 1  2  3 `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...

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.
Abuse

JGO Ninja

Medals: 71

falling into the abyss of reality

 « Reply #10 - Posted 2013-10-09 23:30:01 »

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

Sorry Roquen, your suggestion is good too.

Quote
I'm not clear what you mean...maybe this: (1 << x) & 3

I was being dim
Roquen

JGO Kernel

Medals: 518

 « Reply #11 - Posted 2013-10-10 07:45:53 »

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

Quote
Quote
I'm not clear what you mean...maybe this: (1 << x) & 3
I was being dim
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, 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.
Riven

« JGO Overlord »

Medals: 1357
Projects: 4
Exp: 16 years

 « Reply #12 - Posted 2013-10-10 08:10:54 »

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

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: [1]
 ignore  |  Print

 hadezbladez (2129 views) 2018-11-16 13:46:03 hadezbladez (809 views) 2018-11-16 13:41:33 hadezbladez (2101 views) 2018-11-16 13:35:35 hadezbladez (418 views) 2018-11-16 13:32:03 EgonOlsen (3453 views) 2018-06-10 19:43:48 EgonOlsen (3680 views) 2018-06-10 19:43:44 EgonOlsen (2274 views) 2018-06-10 19:43:20 DesertCoockie (3003 views) 2018-05-13 18:23:11 nelsongames (3075 views) 2018-04-24 18:15:36 nelsongames (3852 views) 2018-04-24 18:14:32
 Deployment and Packagingby philfrei2019-02-17 20:25:53Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org