Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (548)
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  
  2D & 3D Spline (think smooth curve through n points) function  (Read 13213 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 2005-06-05 20:40:10 »

Another day, another shared code. (Although I actually have to finish and polish all my other little projects... I know... I know...)

According to Mathworldthe definition of a spline is: "A piecewise polynomial function that can have a locally very simple form, yet at the same time be globally flexible and smooth. Splines are very useful for modeling arbitrary functions, and are used extensively in computer graphics."

Here is the page on Cubic Splines, the kind of splines we will be constructing.

but a picture says more than a thousand words:
Click to Play


Basically, you define a number of points in 2D or 3D space, and using these points to create a "spline", a curve which smoothly goes through all points. What you can use this for, I will leave to your own imagination.... (hint: the missile-movement in this game is created using splines) Using this code, you can define a "spline", and get any point on that line (between [0..1].. where 0 is the start and 1 is the end point of the line)

How to use
1  
2  
3  
4  
5  
6  
7  
8  
    Spline3D spline = new Spline3D();
    spline.addPoint(new Vector3f(5.0f, 7.0f, 8.0f));
    spline.addPoint(new Vector3f(2.0f, 11.0f, 6.0f));
    spline.addPoint(new Vector3f(9.0f, 4.0f, 3.0f));

    spline.calcSpline(); // call everytime a point on the spline has changed

    Vector3f pointAtTwoThirds = spline.getPoint(2.0f / 3.0f); // getPoint is valid for 0.0f through 1.0f.


Easy, no? for 2D points, just replace Spline3D with Spline2D and add/get Vector2f points. In the missiles example, I create a Spline with 3 points, one at the origin (the space ship), one behind the space-ship (a bit randomized), and one at the target. After that, every time the enemy ship moves, I re-calculate the spline, while the missile continues along the spline's trajectory.

Here follows the source code:
based on: http://www.cse.unsw.edu.au/~lambert/splines/

Cubic: holds and solves a Cubic Equasion
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public class Cubic {
   private float a,b,c,d;
   
   public Cubic(float a, float b, float c, float d) {
      this.a =a;
      this.b =b;
      this.c =c;
      this.d =d;
   }
   
   public float eval(float u) {
      return (((d*u) + c)*u + b)*u + a;  
   }
}


BasicSpline: The backbone, abstract class holding the function to solve a 1D spline (which is used to solve 2D and 3D splines)
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  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
public abstract class BasicSpline {
   public static final Object[] EMPTYOBJLIST = new Object[] { };
   
   public void calcNaturalCubic(List valueCollection, Method getVal, Collection<Cubic> cubicCollection) throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
      int num = valueCollection.size()-1;
     
      float[] gamma = new float[num+1];
      float[] delta = new float[num+1];
      float[] D = new float[num+1];

      int i;
      /*
           We solve the equation
          [2 1       ] [D[0]]   [3(x[1] - x[0])  ]
          |1 4 1     | |D[1]|   |3(x[2] - x[0])  |
          |  1 4 1   | | .  | = |      .         |
          |    ..... | | .  |   |      .         |
          |     1 4 1| | .  |   |3(x[n] - x[n-2])|
          [       1 2] [D[n]]   [3(x[n] - x[n-1])]
          
          by using row operations to convert the matrix to upper triangular
          and then back sustitution.  The D[i] are the derivatives at the knots.
      */

      gamma[0] = 1.0f / 2.0f;
      for(i=1; i< num; i++) {
         gamma[i] = 1.0f/(4.0f - gamma[i-1]);
      }
      gamma[num] = 1.0f/(2.0f - gamma[num-1]);

      Float p0 = (Float) getVal.invoke(valueCollection.get(0), EMPTYOBJLIST);
      Float p1 = (Float) getVal.invoke(valueCollection.get(1), EMPTYOBJLIST);
           
      delta[0] = 3.0f * (p1 - p0) * gamma[0];
      for(i=1; i< num; i++) {
         p0 = (Float) getVal.invoke(valueCollection.get(i-1), EMPTYOBJLIST);
         p1 = (Float) getVal.invoke(valueCollection.get(i+1), EMPTYOBJLIST);
         delta[i] = (3.0f * (p1 - p0) - delta[i - 1]) * gamma[i];
      }
      p0 = (Float) getVal.invoke(valueCollection.get(num-1), EMPTYOBJLIST);
      p1 = (Float) getVal.invoke(valueCollection.get(num), EMPTYOBJLIST);

      delta[num] = (3.0f * (p1 - p0) - delta[num - 1]) * gamma[num];

      D[num] = delta[num];
      for(i=num-1; i >= 0; i--) {
         D[i] = delta[i] - gamma[i] * D[i+1];
      }

      /*
           now compute the coefficients of the cubics
      */

      cubicCollection.clear();

      for(i=0; i<num; i++) {
         p0 = (Float) getVal.invoke(valueCollection.get(i), EMPTYOBJLIST);
         p1 = (Float) getVal.invoke(valueCollection.get(i+1), EMPTYOBJLIST);

         cubicCollection.add(new Cubic(
                        p0,
                        D[i],
                        3*(p1 - p0) - 2*D[i] - D[i+1],
                        2*(p0 - p1) +   D[i] + D[i+1]
                      )
                  );
      }
   }
}


Spline2D: Defines a 2D Spline
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  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
public class Spline2D extends BasicSpline{
   private Vector<Vector2f> points;
   
   private Vector<Cubic> xCubics;
   private Vector<Cubic> yCubics;
   
   private static final String vector2DgetXMethodName = "getX";
   private static final String vector2DgetYMethodName = "getY";
   
   private Method vector2DgetXMethod;
   private Method vector2DgetYMethod;
   
   private static final Object[] EMPTYOBJ = new Object[] { };
   
   public Spline2D() {
      this.points = new Vector<Vector2f>();
   
      this.xCubics = new Vector<Cubic>();
      this.yCubics = new Vector<Cubic>();
     
      try {
         vector2DgetXMethod = Vector2f.class.getDeclaredMethod(vector2DgetXMethodName, new Class[] { });
         vector2DgetYMethod = Vector2f.class.getDeclaredMethod(vector2DgetYMethodName, new Class[] { });
      } catch (SecurityException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (NoSuchMethodException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      }      
   }
   
   public void addPoint(Vector2f point) {
      this.points.add(point);
   }
   
   public Vector<Vector2f> getPoints() {
      return points;
   }
   
   public void calcSpline() {
      try {
            calcNaturalCubic(points, vector2DgetXMethod, xCubics);
            calcNaturalCubic(points, vector2DgetYMethod, yCubics);
      } catch (IllegalArgumentException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (IllegalAccessException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (InvocationTargetException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      }
   }
   
   public Vector2f getPoint(float position) {
      position = position * xCubics.size(); // extrapolate to the arraysize
     int      cubicNum = (int) position;
      float   cubicPos = (position - cubicNum);
     
      return new Vector2f(xCubics.get(cubicNum).eval(cubicPos),
                     yCubics.get(cubicNum).eval(cubicPos));
   }
}


Spline3D: Defines a 3D Spline
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  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
public class Spline3D extends BasicSpline{
   private Vector<Vector3f> points;
   
   private Vector<Cubic> xCubics;
   private Vector<Cubic> yCubics;
   private Vector<Cubic> zCubics;
   
   private static final String vector3DgetXMethodName = "getX";
   private static final String vector3DgetYMethodName = "getY";
   private static final String vector3DgetZMethodName = "getZ";
   
   private Method vector2DgetXMethod;
   private Method vector2DgetYMethod;
   private Method vector2DgetZMethod;
   
   private static final Object[] EMPTYOBJ = new Object[] { };
   
   public Spline3D() {
      this.points = new Vector<Vector3f>();

      this.xCubics = new Vector<Cubic>();
      this.yCubics = new Vector<Cubic>();
      this.zCubics = new Vector<Cubic>();
     
      try {
         vector2DgetXMethod = Vector3f.class.getDeclaredMethod(vector3DgetXMethodName, new Class[] { });
         vector2DgetYMethod = Vector3f.class.getDeclaredMethod(vector3DgetYMethodName, new Class[] { });
         vector2DgetZMethod = Vector3f.class.getDeclaredMethod(vector3DgetZMethodName, new Class[] { });
      } catch (SecurityException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (NoSuchMethodException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      }      
   }
   
   public void addPoint(Vector3f point) {
      this.points.add(point);
   }
   
   public Vector<Vector3f> getPoints() {
      return points;
   }
   
   public void calcSpline() {
      try {
            calcNaturalCubic(points, vector2DgetXMethod, xCubics);
            calcNaturalCubic(points, vector2DgetYMethod, yCubics);
            calcNaturalCubic(points, vector2DgetZMethod, zCubics);
      } catch (IllegalArgumentException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (IllegalAccessException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      } catch (InvocationTargetException e) {
         // TODO Auto-generated catch block
        e.printStackTrace();
      }
   }
   
   public Vector3f getPoint(float position) {
      position = position * xCubics.size();
      int      cubicNum = (int) position;
      float   cubicPos = (position - cubicNum);
     
      return new Vector3f(xCubics.get(cubicNum).eval(cubicPos),
                     yCubics.get(cubicNum).eval(cubicPos),
                     zCubics.get(cubicNum).eval(cubicPos));
   }
}
Offline javazoid

Junior Member




Where's Flender?


« Reply #1 - Posted 2005-06-06 07:34:03 »

very nice indeed!

Can you also add a method that gets the angle at a given point ?

Mik
--

Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #2 - Posted 2005-06-06 08:10:04 »

Well, in my game (For the missile direction) I just calculate the angle for the vector between point (n) and point (n + 0.0001f) on the spline.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline javazoid

Junior Member




Where's Flender?


« Reply #3 - Posted 2005-06-06 09:58:19 »

..So you could "officially" add the method in your class..

Cheers!

Mik

Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #4 - Posted 2005-06-06 10:06:01 »

Yes, I could, but in my game I use my own "Vector2D" class instead of LWJGL's Vector2f class. Its a little different... I will rewrite my game code using the Vector2f class (was planning to do this anyway) and post the solution here. (my own vector2d class has more utility functions, but I can easily make them static functions in a "VectorTool" class or something)
Offline javazoid

Junior Member




Where's Flender?


« Reply #5 - Posted 2005-06-06 13:30:58 »

Very good. I'll stay tuned...

Mik

Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #6 - Posted 2005-06-06 14:15:00 »

It looks superb and the game/demo is very good.

However, couldn't you have just achieved the same effect by appling a force that is proporitional to the displacement between the vectors?

1  
2  
3  
4  
5  
6  
7  
Vector3f f1 = object1.getPosition();
Vector3f f2 = spaceship.getPosition();

Vector3f distance = f1.subtract(f2);
distance.normaliseLocal();
distance.multiplyLocal(MISSILE_COMMANDER.MISSILE_POWER);
missile1.addForce(distance);


That will pretty much do what you have done using your splines (with a little tweaking).  Roll Eyes

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #7 - Posted 2005-06-06 14:24:17 »

Oh yer, you need an initial force so that it can start it off...A simple constant would do for each type of missile...

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline Malohkan

Senior Member




while (true) System.out.println("WOO!!!!");


« Reply #8 - Posted 2005-07-03 05:58:40 »

and thus we can see why the principle of Least Action can be used to describe what Newtonian Physics also describes Smiley  Cool topics.  It's up to you which to program Grin

Admin and Game Developer at
GameLizard.com
Play Rimscape!    |    Play Conquer!
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #9 - Posted 2005-07-03 12:21:28 »

Good stuff, but does it only provide calculating a position from a given t value (0, 1)? Just smoothly interpolating t will give you a bursty movement with variable speed which isn't much good for missiles etc

Curves really need a calcPositionAtLength() to be practical, unfortunatly thats a right pain to write. Shocked

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #10 - Posted 2005-08-01 11:26:59 »

very nice indeed!

Can you also add a method that gets the angle at a given point ?

Mik
--
That is needed to use that with a physic engine with an object that is in the direction of its displacement.

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline anarchotron

Junior Member




...precious bodily fluids.


« Reply #11 - Posted 2005-08-01 15:50:44 »

Does the above code require the control points to be uniformly spaced?
Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2005-09-23 20:42:51 »

I gave the code a big overhaul to support calculating the position at a certain distance from the origin, following the spline.

The initial version was "quite fast" but after some intelligent caching I managed to make the code 200x faster. Note that I'm not caching the calculated values, as they are not likely to be reusable, but I cache the values in the intermediate steps. In a reasonably large spline, containing 16 control-points measuring 3750 units, a position lookup for a random distance takes only 0.09ms on a 2.4GHz machine! (was 24.0ms when walking along the spline)

Tiny javadoc:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
Spline3D


 Spline(Vector3f[] vecs)



 public int pointCount()
 public float getLength()

 public void setAccuracy(float accuracy)
 public void setMargin(float margin)

 public void getPositionAt(float t, Vector3f r)
 public Vector3f getPositionAt(float t)

 public void getPositionAtDistance(float distance, Vector3f r)
 public Vector3f getPositionAtDistance(float distance)

 public float getDistanceAt(float distance)


Source-code (a bit messy) Spline3D.java 7.7kb


Now you can create objects that follow the spline at a custom speed!



I hope somebody has as much fun with this as I have Smiley



Note that the extremely sharp curve isn't that sharp, because it's 3d and moves straight into the screen. Smiley


Anarchotron: The control-points do not have to be uniformly spaced.

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

Junior Member





« Reply #13 - Posted 2005-09-23 22:53:18 »

sounds good, but your link doesn't work Smiley

for(int i = 1; i > 0; i++)
{
System.out.println(i+" cups of java downed");
}
Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2005-09-23 23:39:16 »

Here you go, works again

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

Junior Member





« Reply #15 - Posted 2005-09-24 06:58:28 »

cool, thanks  Grin

for(int i = 1; i > 0; i++)
{
System.out.println(i+" cups of java downed");
}
Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2005-09-24 12:40:31 »

1. Changed step-algorithm to be 99.9% consistent for random intervals, instead of roughly 97% in previous version. This caused shaky spline-traversal..

2. 600% faster: random distance calc, now 15us, not ms, even 6.2us with server VM Shocked on 2.4GHz P4, first (uncached) calculation takes 36.3ms. After traversing a very long spline very slowly with high accuracy, only 512 float values are cached over time, so no need to worry about RAM consumption.



3. Changed constructor:

public Spline(Vector3f[] vecs, float accuracy, float margin)
accuracy works very smooth when using 0.001-0.010. the higher the rougher, cheaper in first calc, same speed (!) when cached.
margin defines the margin-of-error the actual answer. measured in units.


Source-code (still a bit messy) Spline3D.java 8.2kb


1  
2  
3  
4  
5  
6  
7  
8  
Vector3f[] vecs = ...;

float accuracy = 0.001f;
float margin = 0.01f;
Spline3D spline = new Spline3D(vecs, accuracy, margin);

Vector3f pos = spline.getPositionAtDistance(...); // for moving along the spline
Vector3f pos = spline.getPositionAt(...); // 0.0F --> "spline.pointCount()"   -  for drawing the spline




Sorry for the messy post-layout  Tongue

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

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #17 - Posted 2009-05-06 22:15:30 »

For anybody using my previous code (and today I found out somebody was actually using it!) and wondered where the heck that initial lag came from, here is an update!

It has a main method, which acts as a nice visualizer.


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  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
/*
 * Created on Sep 23, 2005
 */


package craterstudio.math;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.SystemColor;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class Spline2D
{
   public static void main(String[] args)
   {
      final float[][] points = new float[16][2];
      Random r = new Random(123456L);
      for (int i = 0; i < points.length; i++)
      {
         points[i][0] = 32 + r.nextInt(384);
         points[i][1] = 32 + r.nextInt(384);
      }

      final Spline2D growingSpline = new Spline2D(points);
      final Spline2D fixedSpline = new Spline2D(points);
      growingSpline.enabledTripCaching(16.0f, 0.001f);
      fixedSpline.enabledTripCaching(16.0f, 0.001f);

      for (int i = 0; i < 8; i++)
      {
         while (fixedSpline.travelCache.size() > 1)
            fixedSpline.travelCache.remove(fixedSpline.travelCache.size() - 1);
         long t1 = System.currentTimeMillis();
         fixedSpline.getTripPosition(4000.0f);
         long t2 = System.currentTimeMillis();
         System.out.println("full trip took: " + (t2 - t1) + "ms");
      }

      JPanel panel = new JPanel()
      {
         float travelled  = 0.0f;
         float travelStep = (float) Math.PI;

         @Override
         protected void paintComponent(Graphics g)
         {
            super.paintComponent(g);

            g.setColor(SystemColor.control);
            g.fillRect(0, 0, this.getWidth(), this.getHeight());

            // draw full spline

            g.setColor(Color.BLUE);

            float d = 0.0f;
            while (d < points.length)
            {
               float[] at = fixedSpline.getPositionAt(d);

               this.drawCircle(g, at[0], at[1], 2);

               d += 0.002f;
            }

            // draw GROWING cache
           g.setColor(Color.RED);

            for (CacheItem item : growingSpline.travelCache)
            {
               this.drawCircle(g, item.xpos, item.ypos, 3);
            }

            // draw GROWING spline
           g.setColor(Color.GREEN);

            float[] xy;
            for (int i = 0; i < 25; i++)
            {
               xy = growingSpline.getTripPosition(this.travelled * i / 25.0f);
               this.drawCircle(g, xy[0], xy[1], 3);
            }

            this.travelled += this.travelStep;

            this.repaint();
         }

         private void drawCircle(Graphics g, float x, float y, int r)
         {
            g.fillOval((int) x - r, (int) y - r, r * 2, r * 2);
         }
      };
      panel.setPreferredSize(new Dimension(512, 512));
      JFrame frame = new JFrame();
      JPanel cp = (JPanel) frame.getContentPane();
      cp.setLayout(new BorderLayout());
      cp.add(panel, BorderLayout.CENTER);
      frame.pack();
      frame.setResizable(false);
      frame.setLocationRelativeTo(null);
      frame.setVisible(true);
      frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   }

   public Spline2D(float[][] points)
   {
      this.count = points.length;

      float[] x = new float[count];
      float[] y = new float[count];

      for (int i = 0; i < count; i++)
      {
         x[i] = points[i][0];
         y[i] = points[i][1];
      }

      this.x = Curve.calcCurve(count - 1, x);
      this.y = Curve.calcCurve(count - 1, y);
   }

   //

   final int count;
   private final Cubic[] x, y;

   /**
    * POINT COUNT
    */


   public final int pointCount()
   {
      return count;
   }

   /**
    * POSITION
    */


   public final float[] getPositionAt(float param)
   {
      float[] v = new float[2];
      this.getPositionAt(param, v);
      return v;
   }

   public final void getPositionAt(float param, float[] result)
   {
      // clamp
     if (param < 0.0f)
         param = 0.0f;
      if (param >= count - 1)
         param = (count - 1) - Math.ulp(count - 1);

      // split
     int ti = (int) param;
      float tf = param - ti;

      // eval
     result[0] = x[ti].eval(tf);
      result[1] = y[ti].eval(tf);
   }

   /**
    * CURVE CLASS
    */


   private static class Curve
   {
      static final Cubic[] calcCurve(int n, float[] axis)
      {
         float[] gamma = new float[n + 1];
         float[] delta = new float[n + 1];
         float[] d = new float[n + 1];
         Cubic[] c = new Cubic[n + 0];

         // gamma
        gamma[0] = 0.5f;
         for (int i = 1; i < n; i++)
            gamma[i] = 1.0f / (4.0f - gamma[i - 1]);
         gamma[n] = 1.0f / (2.0f - gamma[n - 1]);

         // delta
        delta[0] = 3.0f * (axis[1] - axis[0]) * gamma[0];
         for (int i = 1; i < n; i++)
            delta[i] = (3.0f * (axis[i + 1] - axis[i - 1]) - delta[i - 1]) * gamma[i];
         delta[n] = (3.0f * (axis[n] - axis[n - 1]) - delta[n - 1]) * gamma[n];

         // d
        d[n] = delta[n];
         for (int i = n - 1; i >= 0; i--)
            d[i] = delta[i] - gamma[i] * d[i + 1];

         // c
        for (int i = 0; i < n; i++)
         {
            float x0 = axis[i + 0];
            float x1 = axis[i + 1];
            float d0 = d[i + 0];
            float d1 = d[i + 1];
            c[i] = new Cubic(x0, d0, 3.0f * (x1 - x0) - 2.0f * d0 - d1, 2.0f * (x0 - x1) + d0 + d1);
         }
         return c;
      }
   }

   /**
    * CUBIC CLASS
    */


   static class Cubic
   {
      private final float a, b, c, d;

      Cubic(float a, float b, float c, float d)
      {
         this.a = a;
         this.b = b;
         this.c = c;
         this.d = d;
      }

      final float eval(float u)
      {
         return (((d * u) + c) * u + b) * u + a;
      }
   }

   private List<CacheItem> travelCache;
   private float           maxTravelStep;
   private float           posStep;

   public void enabledTripCaching(float maxTravelStep, float posStep)
   {
      this.maxTravelStep = maxTravelStep;
      this.posStep = posStep;

      float x = this.x[0].eval(0.0f);
      float y = this.y[0].eval(0.0f);

      this.travelCache = new ArrayList<CacheItem>();
      this.travelCache.add(new CacheItem(x, y, 0.0f));
   }

   public float[] getTripPosition(float totalTrip)
   {
      CacheItem last = this.travelCache.get(this.travelCache.size() - 1);

      // build cache
     while (last.travelled < totalTrip)
      {
         if (totalTrip == 0.0f)
         {
            // don't even bother
           break;
         }

         float travel = Math.min(totalTrip - last.travelled, maxTravelStep);

         CacheItem curr = this.getSteppingPosition(last.position, travel, posStep);

         if (curr.position >= this.count)
         {
            // reached end of spline
           break;
         }

         // only cache if we travelled far enough
        if (curr.travelled > this.maxTravelStep * 0.95f)
         {
            this.travelCache.add(curr);
         }

         curr.travelled += last.travelled;

         last = curr;
      }

      // figure out position

      int lo = 0;
      int hi = this.travelCache.size() - 1;

      while (true)
      {
         int mid = (lo + hi) / 2;

         last = this.travelCache.get(mid);

         if (last.travelled < totalTrip)
         {
            if (lo == mid)
               break;
            lo = mid;
         }
         else
         {
            if (hi == mid)
               break;
            hi = mid;
         }
      }

      for (int i = lo; i <= hi; i++)
      {
         CacheItem item = this.travelCache.get(i);

         if (item.travelled <= totalTrip)
         {
            last = item;
         }
         else
         {
            break;
         }
      }

      float travel = totalTrip - last.travelled;
      last = this.getSteppingPosition(last.position, travel, posStep);
      return new float[] { last.xpos, last.ypos };
   }

   private CacheItem getSteppingPosition(float posOffset, float travel, float segmentStep)
   {
      float pos = posOffset;
      float[] last = this.getPositionAt(pos);

      float travelled = 0.0f;

      while (travelled < travel && pos < this.count)
      {
         float[] curr = this.getPositionAt(pos += segmentStep);
         travelled += Spline2D.dist(last, curr);
         last = curr;
      }

      CacheItem item = new CacheItem(last[0], last[1], 0.0f);
      item.position = pos;
      item.travelled = travelled;
      return item;
   }

   private static float dist(float[] a, float[] b)
   {
      float dx = b[0] - a[0];
      float dy = b[1] - a[1];

      return (float) Math.sqrt(dx * dx + dy * dy);
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #18 - Posted 2009-05-07 00:32:27 »

Wow, this looks very cool, thanks. Have you got a class file for CacheItem, it's not compiling on its own without it. Cheers

Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #19 - Posted 2009-05-07 08:28:31 »

Sorry persecutioncomplex

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
class CacheItem
{
   public CacheItem(float xpos, float ypos, float zpos)
   {
      this.xpos = xpos;
      this.ypos = ypos;
      this.zpos = zpos;
   }

   float position;
   float xpos, ypos, zpos;
   float travelled;
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #20 - Posted 2009-05-07 22:18:41 »

Thanks. I think i get how it works now. When you call getPosition(float param) it returns the point that is (param / pointCount) along the spline.

I tried using this to add nice curvy paths to the path finding code (http://www.java-gaming.org/topics/a-pathfinding-through-2d-polygons/19539/view.html), and it works but it sometimes makes weird little knot loops that look a bit strange. I'll look into how I can get rid of these. Thanks for posting these changes/optimisations  Cool

Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #21 - Posted 2009-05-08 06:06:14 »

spline.getPosition(3.5f) ends up roughly between point 3 and 4

It's very fast to calculate, but not really useful.



spline.getTripPosition(123.0f) returns the point after you traveled 123 units.

You have to step through the spline, which is a very heavy operation, so I cache as much as possible, and look a binary search to find the right entry in the cache.


Those 'weird knots' are caused by the influence of nearby controlpoints. Could you add a screenshot / demo?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #22 - Posted 2009-05-11 07:09:09 »

Ah thanks Riven, that getTripPosition method's much better then.

Sorry for the late reply, I've been moving house. Here's a demo of how I'm using it: http://keithphw.freehostia.com/PathFinderSpline2D/AStarPathFinder.jnlp
source: http://keithphw.freehostia.com/PathFinderSpline2D/src.zip

The player doesn't follow the path of the spline yet but I made the program draw the spline from the points and it looks like it would make a nice natural-looking path. If you can think of a neat way to smooth out those knots it'd be cool to know.

Thanks for the code!
keith


Offline Hansdampf

Senior Member


Projects: 3


too offending?


« Reply #23 - Posted 2009-05-11 07:52:59 »

Quote
If you can think of a neat way to smooth out those knots it'd be cool to know.

I'm pretty sure you have 2 (or more) control points at the same position per knot.
Like
... <0,0><1,0><1,0> ...

lots of sillystupid games: http://www.emaggame.com
Offline CommanderKeith
« Reply #24 - Posted 2009-05-11 08:25:42 »

Good idea. But they're not at the same position, just very close. The walls in the maze are thin rectangles. Maybe if i scan for points that are too close I can average them into one point. Thanks hansdamph

Online Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #25 - Posted 2009-05-11 13:18:24 »

The problems indeed seems to be that there are control points very near to eachother -- probably the diff is sometimes very close to 0.0f, as the spline gets very instable (jumping around) at some points. Remember that the accuracy of float is maybe not sufficient here. Try rewriting the darn thing to use doubles, and your spline will be less jumpy in the 'problem areas', although it would be much better to simply fix the problem of control points that are probably within the same pixel.

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.

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

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

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

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

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

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

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

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

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
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!