lagrange interpolation - GameCreators Forum

Author

Message

nz0

AGK Developer

17

Years of Service

User Offline

Joined: 13th Jun 2007

Location: Cheshire,UK

Posted: 5th Apr 2013 02:26 Edited at: 5th Apr 2013 02:28

Link

I finally managed to implement one of the many spline movements I was looking into and lagrange is the one I think will work best for me. However, I have a problem with reversing the prediction.

The lagrange works on a set of waypoints (my use of this is waypoints) but when I want to reverse the system, it "bounces" rather than reverses the wave.

I thought it would be easy to make a variation for a reverse case, but it has stumped me. I'm sure others will benefit from this great interpolation system, but I really need it to be reversible... can anyone help?

Here's an implementation:

I set up an array of co-ordinates which works ok until I need to return in the other direction.

SetVirtualResolution (960,640)

global TestSprite as Integer

global x# as float

type vector2
 x# as float
 y# as float
endtype

global dim path[10] as vector2

TestSprite=createSprite(0)
setSpriteScale(TestSprite,4,4)

a=createSprite(0)
SetSpriteColor(a,255,0,0,255)
setSpriteScale(a,2,2)
SetSpritePositionByOffset(a,100,160)
path[0].x#=100
path[0].y#=160
a=cloneSprite(a)
SetSpritePositionByOffset(a,200,170)
path[1].x#=200
path[1].y#=170
a=cloneSprite(a)
SetSpritePositionByOffset(a,300,180)
path[2].x#=300
path[2].y#=180
a=cloneSprite(a)
SetSpritePositionByOffset(a,400,130)
path[3].x#=400
path[3].y#=130
a=cloneSprite(a)
SetSpritePositionByOffset(a,500,220)
path[4].x#=500
path[4].y#=220
a=cloneSprite(a)
SetSpritePositionByOffset(a,600,210)
path[5].x#=600
path[5].y#=210
a=cloneSprite(a)
SetSpritePositionByOffset(a,700,230)
path[6].x#=700
path[6].y#=230

x#=100.0
xdir#=3.3

do
 print("x="+str(GetSpriteX(TestSprite)))
 print("y="+str(GetSpritey(TestSprite)))

if xdir#<0
  y#=lagrangerev(x#)
 else
  y#=lagrange(x#)
 endif

SetSpritePositionByOffset(TestSprite,x#,y#)
 x#=x#+xdir#

if x#>700.0 then xdir#=xdir#*-1.0
 if x#<100.0 then xdir#=xdir#*-1.0

Sync()

loop

end

function lagrange(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+t#*path[j].y#
 next j
endfunction y0#

function lagrangerev(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+(t#*path[j].y#)
 next j
endfunction y0#

+ Code Snippet


SetVirtualResolution (960,640)


global TestSprite as Integer

global x# as float

type vector2
 x# as float
 y# as float
endtype

global dim path[10] as vector2

TestSprite=createSprite(0)
setSpriteScale(TestSprite,4,4)

a=createSprite(0)
SetSpriteColor(a,255,0,0,255)
setSpriteScale(a,2,2)
SetSpritePositionByOffset(a,100,160)
path[0].x#=100
path[0].y#=160
a=cloneSprite(a)
SetSpritePositionByOffset(a,200,170)
path[1].x#=200
path[1].y#=170
a=cloneSprite(a)
SetSpritePositionByOffset(a,300,180)
path[2].x#=300
path[2].y#=180
a=cloneSprite(a)
SetSpritePositionByOffset(a,400,130)
path[3].x#=400
path[3].y#=130
a=cloneSprite(a)
SetSpritePositionByOffset(a,500,220)
path[4].x#=500
path[4].y#=220
a=cloneSprite(a)
SetSpritePositionByOffset(a,600,210)
path[5].x#=600
path[5].y#=210
a=cloneSprite(a)
SetSpritePositionByOffset(a,700,230)
path[6].x#=700
path[6].y#=230


x#=100.0
xdir#=3.3

do
 print("x="+str(GetSpriteX(TestSprite)))
 print("y="+str(GetSpritey(TestSprite)))

 if xdir#<0
  y#=lagrangerev(x#)
 else
  y#=lagrange(x#)
 endif

 SetSpritePositionByOffset(TestSprite,x#,y#)
 x#=x#+xdir#

 if x#>700.0 then xdir#=xdir#*-1.0
 if x#<100.0 then xdir#=xdir#*-1.0

 Sync()

loop

end

function lagrange(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+t#*path[j].y#
 next j
endfunction y0#

function lagrangerev(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+(t#*path[j].y#)
 next j
endfunction y0#

You can see I set up another version of the function to test reverse scenarios

My Robotron remake
My I,Robot remake WIP

Back to top

Profile PM Email Website

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 5th Apr 2013 09:48

Link

you can better see what happens if you paint the positions:

SetVirtualResolution (960,640)

global TestSprite as Integer

global x# as float

type vector2
 x# as float
 y# as float
endtype

global dim path[10] as vector2

TestSprite=createSprite(0)
setSpriteScale(TestSprite,1,1)

a=createSprite(0)
SetSpriteColor(a,255,255,255,255)
setSpriteScale(a,2,2)
SetSpritePositionByOffset(a,100,160)
path[0].x#=100
path[0].y#=160
a=cloneSprite(a)
SetSpritePositionByOffset(a,200,170)
path[1].x#=200
path[1].y#=170
a=cloneSprite(a)
SetSpritePositionByOffset(a,300,180)
path[2].x#=300
path[2].y#=180
a=cloneSprite(a)
SetSpritePositionByOffset(a,400,130)
path[3].x#=400
path[3].y#=130
a=cloneSprite(a)
SetSpritePositionByOffset(a,500,220)
path[4].x#=500
path[4].y#=220
a=cloneSprite(a)
SetSpritePositionByOffset(a,600,210)
path[5].x#=600
path[5].y#=210
a=cloneSprite(a)
SetSpritePositionByOffset(a,700,230)
path[6].x#=700
path[6].y#=230

x#=100.0
xdir#=3.3

do

setspritecolor(TestSprite,0,255,0,192)
 for x#=100.0 to 700.0 step 10.0
  y#=lagrange(x#)
  SetSpritePositionByOffset(TestSprite,x#,y#)
  drawsprite(TestSprite)
 next

setspritecolor(TestSprite,255,0,0,192)
 for x#=700.0 to 100.0 step -10.0
  y#=lagrangerev(x#)
  SetSpritePositionByOffset(TestSprite,x#,y#)
  drawsprite(TestSprite)
 next

Sync()

loop

end

function lagrange(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+t#*path[j].y#
 next j
endfunction y0#

function lagrangerev(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+(t#*path[j].y#)
 next j
endfunction y0#

+ Code Snippet

SetVirtualResolution (960,640)

global TestSprite as Integer

global x# as float

type vector2
 x# as float
 y# as float
endtype

global dim path[10] as vector2

TestSprite=createSprite(0)
setSpriteScale(TestSprite,1,1)

a=createSprite(0)
SetSpriteColor(a,255,255,255,255)
setSpriteScale(a,2,2)
SetSpritePositionByOffset(a,100,160)
path[0].x#=100
path[0].y#=160
a=cloneSprite(a)
SetSpritePositionByOffset(a,200,170)
path[1].x#=200
path[1].y#=170
a=cloneSprite(a)
SetSpritePositionByOffset(a,300,180)
path[2].x#=300
path[2].y#=180
a=cloneSprite(a)
SetSpritePositionByOffset(a,400,130)
path[3].x#=400
path[3].y#=130
a=cloneSprite(a)
SetSpritePositionByOffset(a,500,220)
path[4].x#=500
path[4].y#=220
a=cloneSprite(a)
SetSpritePositionByOffset(a,600,210)
path[5].x#=600
path[5].y#=210
a=cloneSprite(a)
SetSpritePositionByOffset(a,700,230)
path[6].x#=700
path[6].y#=230


x#=100.0
xdir#=3.3

do

 setspritecolor(TestSprite,0,255,0,192)
 for x#=100.0 to 700.0 step 10.0
  y#=lagrange(x#)
  SetSpritePositionByOffset(TestSprite,x#,y#)
  drawsprite(TestSprite)
 next

 setspritecolor(TestSprite,255,0,0,192)
 for x#=700.0 to 100.0 step -10.0
  y#=lagrangerev(x#)
  SetSpritePositionByOffset(TestSprite,x#,y#)
  drawsprite(TestSprite)
 next

 Sync()

loop

end

function lagrange(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+t#*path[j].y#
 next j
endfunction y0#

function lagrangerev(x0#)
 y0#=0.0
 for j=0 to 6
  t#=1.0
  for i=0 to 6
   if i<>j then t#=t#*(x0#-path[i].x#)/(path[j].x#-path[i].x#)
  next i
  y0#=y0#+(t#*path[j].y#)
 next j
endfunction y0#

Back to top

Profile PM Email

Marl

13

Years of Service

User Offline

Joined: 19th Nov 2011

Location: Bradford, UK

Posted: 5th Apr 2013 21:37 Edited at: 5th Apr 2013 21:39

Link

Looks to work ok to me.

(offsetting the return journey by 100 so it doesn't hide the green)

+ Code Snippet

SetSpritePositionByOffset(TestSprite,x#,y# + 100)

or am I not understanding the problem. (or indeed did Markus fix the problem with the recode?)

Edit: wait are you wanting it to continue down as it comes back?

Attachments

Login to view attachments

Back to top

Profile PM Email

nz0

AGK Developer

17

Years of Service

User Offline

Joined: 13th Jun 2007

Location: Cheshire,UK

Posted: 5th Apr 2013 21:48

Link

Yes, I think painting them misses the point.
Look at my first one again and see that the movement bounces back.
I would want the return journey to be a smooth interpolation, so when going through the last point, it should curve back up.

I think this might be impossible with lagrange now, as it uses the whole set of points, so the solution may be to replot the points for the reverse journey.

I would want to do this anyway if I was going to use it in pathing, but I think messing with the points would interfere with the flow as soon as you did it?

My Robotron remake
My I,Robot remake WIP

Back to top

Profile PM Email Website

nz0

AGK Developer

17

Years of Service

User Offline

Joined: 13th Jun 2007

Location: Cheshire,UK

Posted: 6th Apr 2013 01:58

Link

On further investigation, this isn't any good for what I want. The lagrange formula is useful if you *must* intersect the points, but it has a couple of fails:

can't use the same Y value on the set or it breaks
uses the whole set of X to plot the Y.

After messing with beziers, this seems to be better and more flexible (but harder to implement)

My Robotron remake
My I,Robot remake WIP

Back to top

Profile PM Email Website

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 6th Apr 2013 11:06 Edited at: 6th Apr 2013 11:55

Link

maybe you can add a last point that the curve go flat.

here a bezier interpolation in agk example but the control points are different.

rem
rem AGK Application 1.08B9

rem Bezier Curve Example
rem MR 06.04.2013

SetDisplayAspect(4/3)
SetVirtualResolution(800,600)

type TVector3
    x as float
    y as float
    z as float
endtype
global VectorMax=6
global dim path[VectorMax] as TVector3 //vector list
global bezret as TVector3 //return from Bezier until AGK can handle types correct

global TestSprite as Integer
TestSprite=createSprite(0)
setSpriteScale(TestSprite,1,1)

path[0].x=100
path[0].y=300

path[1].x=200
path[1].y=300+50

path[2].x=300
path[2].y=300-100

path[3].x=400
path[3].y=300+50

path[4].x=500
path[4].y=300+200

path[5].x=600
path[5].y=300-200

path[6].x=700
path[6].y=300-50

do
 Print("Hello Bezier Curve")

setspritecolor(TestSprite,255,255,255,255)
 for i = 0 to VectorMax
  SetSpritePositionByOffset(TestSprite,path[i].x,path[i].y)
  drawsprite(TestSprite)
 next

setspritecolor(TestSprite,0,255,0,128)
 for mu#=0.0 to 1.0 step 0.01
  Bezier(mu#)
  SetSpritePositionByOffset(TestSprite,bezret.x,bezret.y)
  drawsprite(TestSprite)
 next

Sync()
loop
end

Function Bezier(mu as float)

//MR 06.04.2013

//General Bezier curve
 //mu 0.0 to 1.0

k as integer ,kn as integer,nn as integer,nkn as integer
 blend as float,muk as float,munk as float

px as float,py as float,pz as float

n=VectorMax //< global

bezret.x=0.0
   bezret.y=0.0
   bezret.z=0.0

muk = 1.0
   munk = pow(1.0-mu,IntegerToFloat(n))

For k=0 To n
      nn = n
      kn = k
      nkn = n - k
      blend = muk * munk
      muk =muk * mu
      munk = munk / (1.0-mu)
      While nn => 1
         blend=blend * nn
         nn=nn-1
         If kn > 1
            blend=blend / IntegerToFloat(kn)
            kn=kn-1
         EndIf
         If nkn > 1
            blend=blend / IntegerToFloat(nkn)
           nkn=nkn-1
         EndIf
      endwhile
      bezret.x=bezret.x+path[k].x * blend
      bezret.y=bezret.y+path[k].y * blend
      bezret.z=bezret.z+path[k].z * blend
   Next

EndFunction

function IntegerToFloat(i as integer)

f#=i
    exitfunction f#

endfunction f#

Function pow(a as float,b as float)

//C Like :-)

exitfunction a^b

EndFunction c#

+ Code Snippet

rem
rem AGK Application 1.08B9

rem Bezier Curve Example
rem MR 06.04.2013

SetDisplayAspect(4/3)
SetVirtualResolution(800,600)

type TVector3
    x as float
    y as float
    z as float
endtype
global VectorMax=6
global dim path[VectorMax] as TVector3 //vector list
global bezret as TVector3 //return from Bezier until AGK can handle types correct

global TestSprite as Integer
TestSprite=createSprite(0)
setSpriteScale(TestSprite,1,1)

path[0].x=100
path[0].y=300

path[1].x=200
path[1].y=300+50

path[2].x=300
path[2].y=300-100

path[3].x=400
path[3].y=300+50

path[4].x=500
path[4].y=300+200

path[5].x=600
path[5].y=300-200

path[6].x=700
path[6].y=300-50

do
 Print("Hello Bezier Curve")

 setspritecolor(TestSprite,255,255,255,255)
 for i = 0 to VectorMax
  SetSpritePositionByOffset(TestSprite,path[i].x,path[i].y)
  drawsprite(TestSprite)
 next

 setspritecolor(TestSprite,0,255,0,128)
 for mu#=0.0 to 1.0 step 0.01
  Bezier(mu#)
  SetSpritePositionByOffset(TestSprite,bezret.x,bezret.y)
  drawsprite(TestSprite)
 next

 Sync()
loop
end

Function Bezier(mu as float)

 //MR 06.04.2013

 //General Bezier curve
 //mu 0.0 to 1.0

 k as integer ,kn as integer,nn as integer,nkn as integer
 blend as float,muk as float,munk as float

 px as float,py as float,pz as float

 n=VectorMax //< global

   bezret.x=0.0
   bezret.y=0.0
   bezret.z=0.0

   muk = 1.0
   munk = pow(1.0-mu,IntegerToFloat(n))

   For k=0 To n
      nn = n
      kn = k
      nkn = n - k
      blend = muk * munk
      muk =muk * mu
      munk = munk / (1.0-mu)
      While nn => 1
         blend=blend * nn
         nn=nn-1
         If kn > 1
            blend=blend / IntegerToFloat(kn)
            kn=kn-1
         EndIf
         If nkn > 1
            blend=blend / IntegerToFloat(nkn)
           nkn=nkn-1
         EndIf
      endwhile
      bezret.x=bezret.x+path[k].x * blend
      bezret.y=bezret.y+path[k].y * blend
      bezret.z=bezret.z+path[k].z * blend
   Next

EndFunction

function IntegerToFloat(i as integer)

    f#=i
    exitfunction f#

endfunction f#

Function pow(a as float,b as float)

 //C Like :-)

 exitfunction a^b

EndFunction c#

Back to top

Profile PM Email

Sorry your browser is not supported!

AppGameKit Classic Chat / lagrange interpolation

Attachments