Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (754) Games in Android Showcase (229) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 2D & 3D Spline (think smooth curve through n points) function  (Read 34609 times) 0 Members and 1 Guest are viewing this topic.
tusaki

Junior Devvie

Medals: 1

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

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

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 points;      private Vector xCubics;   private Vector 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();         this.xCubics = new Vector();      this.yCubics = new Vector();            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 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 points;      private Vector xCubics;   private Vector yCubics;   private Vector 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();      this.xCubics = new Vector();      this.yCubics = new Vector();      this.zCubics = new Vector();            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 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));   }}`
javazoid

Junior Devvie

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

tusaki

Junior Devvie

Medals: 1

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

Junior Devvie

Where's Flender?

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

Cheers!

Mik

tusaki

Junior Devvie

Medals: 1

 « 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)
javazoid

Junior Devvie

Where's Flender?

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

Very good. I'll stay tuned...

Mik

darkprophet

Senior Devvie

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

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
darkprophet

Senior Devvie

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

Senior Devvie

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   Cool topics.  It's up to you which to program

GameLizard.com
Play Rimscape!    |    Play Conquer!
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

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

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Amos Wenger

Senior Devvie

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"
anarchotron

Junior Devvie

...precious bodily fluids.

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

Does the above code require the control points to be uniformly spaced?
Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

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

 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)`

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

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

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!
weston
 « Reply #13 - Posted 2005-09-23 22:53:18 »

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « 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!
weston
 « Reply #15 - Posted 2005-09-24 06:58:28 »

cool, thanks

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « 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 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 splineVector3f pos = spline.getPositionAt(...); // 0.0F --> "spline.pointCount()"   -  for drawing the spline`

Sorry for the messy post-layout

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

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « 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 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();      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!
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

Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

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

Sorry

 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!
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

Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

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

Hansdampf

Senior Devvie

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

Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « 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!
0kb

Innocent Bystander

 « Reply #26 - Posted 2017-12-17 17:23:38 »

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

@Riven Do you still have the code for this? The link is broken.
Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « Reply #27 - Posted 2017-12-17 17:31:39 »

https://github.com/riven8192/LibBase/blob/a70af645e9b35df824b9214b0ef2749bfb2b5df0/src/craterstudio/math/Spline3D.java

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: [1]
 ignore  |  Print

 DesertCoockie (20 views) 2018-05-13 18:23:11 nelsongames (68 views) 2018-04-24 18:15:36 nelsongames (65 views) 2018-04-24 18:14:32 ivj94 (749 views) 2018-03-24 14:47:39 ivj94 (79 views) 2018-03-24 14:46:31 ivj94 (595 views) 2018-03-24 14:43:53 Solater (95 views) 2018-03-17 05:04:08 nelsongames (168 views) 2018-03-05 17:56:34 Gornova (378 views) 2018-03-02 22:15:33 buddyBro (1038 views) 2018-02-28 16:59:18
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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