Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (602) Games in Android Showcase (171) games submitted by our members Games in WIP (649) 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 1715 times) 0 Members and 1 Guest are viewing this topic.
Abuse

JGO Knight

Medals: 28

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

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Roquen
 « Reply #1 - Posted 2013-10-09 15:50:18 »

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

JGO Knight

Medals: 28

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

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Roquen
 « Reply #3 - Posted 2013-10-09 17:31:20 »

So ordering is important?
Abuse

JGO Knight

Medals: 28

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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
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 Wizard

Medals: 89

 « 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: 360
Projects: 11
Exp: 3 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
 « 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 Knight

Medals: 28

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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Abuse

JGO Knight

Medals: 28

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

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Roquen
 « 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
« League of Dukes »

« JGO Overlord »

Medals: 1019
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

You cannot reply to this message, because it is very, very old.

 Jesse (15 views) 2015-07-29 04:35:27 Riven (37 views) 2015-07-27 16:38:00 Riven (18 views) 2015-07-27 15:35:20 Riven (21 views) 2015-07-27 12:26:13 Riven (12 views) 2015-07-27 12:23:39 BurntPizza (30 views) 2015-07-25 00:14:37 BurntPizza (42 views) 2015-07-24 22:06:39 BurntPizza (24 views) 2015-07-24 06:06:53 NoxInc (31 views) 2015-07-22 22:16:53 NoxInc (18 views) 2015-07-22 22:13:39
 theagentd 48x wessles 46x basil_ 35x orangepascal 28x KaiHH 26x Riven 19x ags1 17x mooman219 17x bornander 13x KudoDEV 13x princec 11x CelestialCreator 11x klaus 11x Jesse 11x Zaneris 9x Spasi 8x
 List of Learning Resourcesby gouessej2015-07-09 11:29:36How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21
 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