Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (489)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (555)
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  
  Optimized Interpolation Set?  (Read 1345 times)
0 Members and 1 Guest are viewing this topic.
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Posted 2006-01-29 12:09:30 »

Hia, for various purposes I've created an Interpolation Set class. A picture explains better than words, so let met start with that:



The Interpolation set contains a series of key/value floats. What I want to be able to do is to query the set for any key-value in the interpolation and get a corresponding result. So, in the example above, the data set contains the following key-value pairs:
KeyValue
0160
0.4160
0.62598
1.055

When I query this set for key-value 0.5, I want the set to return the interpolated value.
  • In this case, 0.5 is in between keys 0.4 and 0.625. To calculate the interpolated value
  • First I determine the distance between the keys. The distance between the keys in the set is (0.625-0.4) = 0.225.
  • The distance between the queried key and the lowest-nearest key (the first key to the left of the queried key...) is 0.5 - 0.4 = 0.1.
  • 0.1 is 44.44% (0.1 / 0.255) of the way of the distance between the two known keys.
  • So finally we have to calculate what 44.44% of the way of the distance between the values is.  The distance between the values is 98-160 = -62
  • .... 44% of -62 = -27.55.
  • The final value and the value I wanted to get from the set is the leftmost value (160) plus the interpolated value (-27.55) so finally : 160 + -27.55 = 132.45.

Now the question for this forum is: what would be an (the most?) optimized way of approaching this problem? attached to this message is one way of doing this. But I have the gut feeling that it can be done in a better way.

When quering for a key lower than the lowest key in the set, the set should just return the first value. In case you query for a key higher than the highest key in the set, just return the last value.
Offline Ask_Hjorth_Larsen

Junior Member




Java games rock!


« Reply #1 - Posted 2006-01-29 13:44:08 »

So, if the nearest key/value to the left is (x1,y1) and the nearest key/value to the right is (x2,y2) you want to calculate the weighted average, i.e.

1  
2  
3  
y1 * (x2-x) + y2 * (x - x1)
--------------------------------
          x2 - x1


Something like that?

EDIT: where x is the query value
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #2 - Posted 2006-01-29 15:10:17 »

Yes, indeed.

1  
2  
3  
160 * (0.625-0.5) + 98 * (0.5 - 0.4)
----------------------------------------------   = 132.45
0.625-0.4


Now the main problem is not actually this final step. The main problem is finding x1 and x2, when given x, in the set. It is not actually a problem per-se, but I need the most optimized way of setting up the data structure to contain the interpolation and to quickly find x1/x2.
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 2006-01-29 16:40:03 »

Well  you are already finding the right index by recursion. That method will be the bottleneck here. I have the feeling there are a too much checks. Then you enter the recursive method, your are checking if the values are between v[0] and v[v.length-1]. You do this check every recursion. That is not needed, as you've checked this before, and are only calling the method *if* you have valid input. So IMHO, without running the code, I'd say you can get rid of 2 if-statements.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2006-01-29 16:46:26 »

And ehm... your normalize-methods don't make much sense Smiley


You have to find the min/max values, then
1  
2  
foreach(value)
   value = (value-min) / (max-min);


Your current code just scales them, not transforming them into the range 0..1 like the documentation says.

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

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #5 - Posted 2006-01-29 16:59:14 »

And ehm... your normalize-methods don't make much sense Smiley


You have to find the min/max values, then
1  
2  
foreach(value)
   value = (value-min) / (max-min);


Your current code just scales them, not transforming them into the range 0..1 like the documentation says.

that's on purpose. but perhaps I shouldn't call it 'normalize'... ;-)
basically I use it to scale things like color information. so, I might have an interpolation containing the values 124,2,54,230 for example. I scale them to 0.0f - 1.0f , knowing that the maximum value is 255.0f (which is not in the set). A true normalize method would pick 230 as the maximum value (and take into account the minumum value, 2), because that is the maximum value present in the set.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2006-01-29 17:05:20 »

Ah, you're working on that particle-engine.

You know, when you have less than like 8 keys/values (I don't know the threshold), it's actually much faster to do everything in a plain loop.

1  
2  
3  
4  
5  
int index = -1;
for(...)
   if(searchVal >= v[i])
      index = i;
      break;

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

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #7 - Posted 2006-01-29 17:48:37 »

Yeah, I thought about that.  Undecided

However, I've been researching Binary Search Trees today as an alternative to the arrays of floats. And my new version has a 600% increase in speed.  Grin

To be specific, I've implemented Splay Trees .

Quote
A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time. For many non-uniform sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Sleator and Robert Tarjan.
http://en.wikipedia.org/wiki/Splay_tree

When I've finalized my testing and cleaned up & commented the code a bit, I will post the splaying version to this thread.
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 (12 views)
2014-08-31 22:59:12

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

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

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

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

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

Tekkerue (24 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 (47 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!