Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (491)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (556)
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  
  indexing transparently across multiple sequential arrays  (Read 1495 times)
0 Members and 1 Guest are viewing this topic.
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Posted 2007-04-10 01:48:28 »

Hello. I have a problem where a body state is represented by a small vector (my own implementation), and a world state is a vector comprised of all the body states concatinated.

I need to lookup values in the world vector by an index (to be a vector), which must work out which body state that index lies on, and then work out the local body vector index to find the right value.

At first things were easy becuase each body vector was the same size. So if body vectors were four elements each, and the wrold comprsed of 3 bodies, then to find element 7 of the world vector I could:-

7/4  = 1 (integer division)     get the 1st body (element 0 of an array)
7%4=3                                     get the 3st element(element 2 of an array)


So lookup body[1] and get element[2] out of it. (this is implemented as arrays so rememeber the 0 element is a valid index for both bodies and elements)

Which is great as it is super fast, direct and no searching invloved. However, things have got more complicated and I would like variable length vectors that can be concatinated to form a world vector, and also be super fast. Any ideas?

One idea I am thinking about is that probably there will not be alot of varience in the different sizes. So perhaps I could add all vectors of the same size next to each other, then concatinate all elements of a different size netxt to them, and increase upwards like that. Then a sequential search would only take as long as there are different sizes, rather than the number of vectors.

Tom

 

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2007-04-10 03:09:13 »

After quite some pondering (and working out solutions) I came to the conclusion, that if you have a bit of RAM to spare, this will be fastest:

A chunk of data, with all bodystates of all bodies in it, and an array that gives you the offset for each body:




Implementation:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
int[] body2offset = ...; // or a short[], if you are really short on RAM
float[] data = ...;

int index = 0;
int last = 0;

public void nextBody()
{
    body2offset[index++] = last;
}

public void nextState(float[] src)
{
   for(int i=0; i<stride; i++)
      data[last+i] = src[i];
   last += stride;
}

public void getState(int body, int state, float[] dst) // read-back
{
   int off = body2offset[body] + state * stride;
   for(int i=0; i<stride; i++)
      dst[i] = data[off+i];
}




Usage:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
// fill the data-structure
nextBody();
nextState(...);
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

// read-back

int bodyIndex = ...;
int stateIndex = ...;

float[] dst = new float[stride];
getState(bodyIndex, stateIndex, dst);

for(int i=0; i<stride; i++)
   float value = dst[i];


The way you described the problem, I assumed the state-length for a body is fixed - if that's not the case, I can give it another try.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #2 - Posted 2007-04-10 12:15:20 »

Yeah sorry. It was late last night an I lost my ability to articulate myself. The bodies were fixed length and everyhting was easy. Now they are not.
The code that worked for fixed sized vectors was:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
public class CompositeVector implements Vector {
    int vectorSize = -1;//indicate we don't know how big the vectors are going to be yet with a -1

    ArrayList<Vector> vectors = new ArrayList<Vector>(); //list of sub vectors that are components of this vector

    /**
     * appends a vector to the end of this vector. So the size of this CompositeVector increases by the size of the
     * argument
     */

    public void addVector(Vector v) {
        if (vectorSize == -1) vectorSize = v.size(); //set the vectorSize if this is the first vector added
       assert vectorSize == v.size() : "vectors must be same size";
        vectors.add(v);
    }

    public void set(int index, float val) {
        vectors.get(index / vectorSize).set(index % vectorSize, val);
    }

    public float get(int index) {
        return vectors.get(index / vectorSize).get(index % vectorSize);
    }
}

Note that the get and set methods work out how to get to the correct sub vector with modulus and divide. No extra memory overhead and extremely quick.
I am not trying to work out a new method for doing this which will work for variable sized subvectors. I do not expect to get quite such an elagant way, but I am trying to avoid having to copy everything to a buffer. The problem with using a buffer or something is that you then need to add an update method to write the buffer back into the originals. Basically I really want the underlying storage for the values in the composite vector to be the underlying vectors. I also want the access time to be near constant.

One definite solution would be to create a HashMap that contained an entry for every large vector index. This entry would contain two values indicating which subvector and which local index to use. This hashmap can be generated as the sub-vectors are appended to the composite vector. I feel like this is a bit crude though (and not very gc freindly).     



Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2007-04-10 13:38:20 »

Ideal solution for this would be structs - but well... nevermind.

The alternative is that you make a Vector backed by a FloatBuffer (no data copies)

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
ComposedVector
{
   FloatBuffer backing; // sliced from 'main' backing-buffer in World? (to get rid of the 4K malloc for each floatbuffer)

   public Vector add(int elements)
   {
      return new Vector()
      {
         int off = backing.position();
         public final int size() {return elements};
         public final float get(int i) { backing.get(off+i); }
         public final float set(int i, float f) { backing.put(off+i, f); }
      };
      backing.position(backing.position() + elements);    
   }

   // ultra-fast setters/getters
  public final void set(int off, float val) { backing.put(off, val); }
   public final float get(int off) { backing.get(off); }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #4 - Posted 2007-04-13 18:47:48 »

Oh yeah thats nice.

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
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.

Nickropheliac (15 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

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

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

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

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

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

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

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

BurntPizza (48 views)
2014-08-09 21:09:32
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!