Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (552)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  The 0,1 & 2 conundrum!  (Read 1125 times)
0 Members and 1 Guest are viewing this topic.
Offline Abuse

JGO Knight


Medals: 12


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

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
Online Roquen
« Reply #1 - Posted 2013-10-09 15:50:18 »

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

JGO Knight


Medals: 12


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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #3 - Posted 2013-10-09 17:31:20 »

So ordering is important?
Offline Abuse

JGO Knight


Medals: 12


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 Smiley

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.

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

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

JGO Ninja


Medals: 43



« 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!
Offline HeroesGraveDev

JGO Kernel


Medals: 246
Projects: 11
Exp: 2 years


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


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

Premature optimisation much... Pointing

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

Online 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  Pointing
Offline Abuse

JGO Knight


Medals: 12


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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Abuse

JGO Knight


Medals: 12


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  Pointing

Sorry Roquen, your suggestion is good too.

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

I was being dim Smiley

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

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


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

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (23 views)
2014-08-22 19:31:30

atombrot (34 views)
2014-08-19 09:29:53

Tekkerue (30 views)
2014-08-16 06:45:27

Tekkerue (28 views)
2014-08-16 06:22:17

Tekkerue (18 views)
2014-08-16 06:20:21

Tekkerue (27 views)
2014-08-16 06:12:11

Rayexar (65 views)
2014-08-11 02:49:23

BurntPizza (41 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (41 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!