0

Context:

Hello, I am making a Java game with terrain as chunks. (3d chunks but that's not crucial and I would like to focus on single dimension to make the questing simpler)

I was thinking about how to store chunks without a HashMap but some kind of array as this is performance sensitive code and HashMap is not the ideal thing for that. I came to the conclusion that an array with a start/offset would be ideal. Why? Chunks are usually in a group but this group could start on a really large or/and negative number.

Example of situation:

Now what I mean with start/offset is best described with an example.

Positions/Elements

100000 / foo
100001 / bar
100002 / foobar

Instead of creating an array with size of 100003 I could create one with size of 3 and have an offset of 100000. The get method would look like:

int offset=...; //set as items are added but in this example it would be 100000
T[] data;

<T> T get(int pos){
  if(pos<offset || pos>=offset+data.length)return null;
  return data[pos - offset];
}

Question:

I have experienced that the task of implementing this in an efficient way is quite hard. Now I am wondering if there is any way that this could be done with existing classes in java or a library.

To be honest I do not trust myself with this kind of performance sensitive code. (mainly handling array size and offset)

LapisSea
  • 83
  • 1
  • 9
  • Have you implemented this with a HashMap, and observed that it's too slow? I don't know your exact use-case, but I'd suspect that the time spent _using_ a chunk is going to dwarf the access time, regardless of whether you store it in a map or array, so I'd go with the easier-to-use implementation first. If you profile your code and see a major slowdown here, swapping out a HashMap for something that implements the `Map` interface should be trivial. – Andrew Rueckert Aug 22 '17 at 20:07
  • @AndrewRueckert Yes I did and the access time worsened by ~800% from a buggy version of the array with offset that I "tried to implement". – LapisSea Aug 22 '17 at 20:45
  • 1
    Sure, the `HashMap` is maybe ten times slower than an array. That's a lot but doesn't your processing take even much more? +++ If not, then something like you did is fine. Don't worry about performance much, as you can't really predict it (nobody can). If needed, measure the performance using JMH (nearly every homemade benchmark is terribly broken). +++ If you write a *working* `OffsetArrayList`, the consider it for https://codereview.stackexchange.com/. A trie may be just fine or too general / too slow. – maaartinus Aug 23 '17 at 00:59
  • @maaartinus no processing does not take long at all. (except for loading/creating a chunk) For example simply calling an opengl draw call takes very little time and I experienced unacceptable fps drop when using hash map. – LapisSea Aug 23 '17 at 11:09

1 Answers1

1

This is more or less the requirement of sparse Matrices.

See e.g. Sparse matrices / arrays in Java

milbrandt
  • 1,438
  • 2
  • 15
  • 20
  • Oh wow, I never thought of doing that. This is pretty good solution alough not a perfect on. Still, thank you! – LapisSea Aug 22 '17 at 19:58