Moving Sprite along predetermined path

[blueznl]

Keep going, people, this is interesting

[DarkDragon]

For 2 modifier points just cut the one modifier point into two... its simple like that.

Instead of interpolating in these lines:
p1 ------> mp
mp ------> p2

Interpolate this lines:
p1 ------> mp1
mp2 -------> p2

the interpolation between the 2 interpolation points i1 and i2 will be the same like before.

[gnasen]

I couldnt resist and played some more around. This is the result:



As you can see, the result seems to be very good for an odd degree of 3 or higher. However there seemed to be a bug, because it failed for very high degrees. After some time I noticed, that it seems to be a problem with precision or size of the variables. So I will try to locate and fix this problem. So far:

Code: Select all

EnableExplicit

InitSprite()

Structure s_point
  x.d
  y.d
EndStructure
Procedure solve(Array matrix.d(2), Array polynom.d(1))
  
  Protected x.i,y.i,z.i,factor.d
  Protected size.i = ArraySize(matrix(),2)
  
  For x=0 To size-1
    For y=x+1 To size
      If matrix(x,y) <> 0
        factor = matrix(x,y) / matrix(x,x)
        For z=0 To size+1
          matrix(z,y) = matrix(z,y) - matrix(z,x) * factor
        Next 
      EndIf
    Next
  Next
  
  For y=0 To size
    For z=0 To y-1
      matrix(size+1,size-y) = matrix(size+1,size-y) - matrix(size-z,size-y) * polynom(size-z)
    Next
    polynom(size-y) = matrix(size+1,size-y) / matrix(size-y,size-y)
  Next
  
EndProcedure
Procedure derivate(degree.i,x.i,d.i)
  
  Protected a.i, factor.d = 1
  
  For a=0 To d-1
    factor * (degree-a)
  Next
  factor * Pow(x,degree-d)
  
  ProcedureReturn factor
  
EndProcedure
Procedure spline(Array in.d(1), Array polynom.d(1),degree.i)
  
  Protected deg.i = degree+1
  Protected size.i = ArraySize(in())
  Protected Dim matrix.d(size*deg,size*deg-1)
  Protected Dim polynom.d(size*deg-1)
  Protected x.i,y.i,z.i
  Protected value.d
  Protected d.i,e.i
  
  ;/ create system of linear equations
  For z=0 To size-1
    For d=0 To deg-1
      matrix(z*deg+d, z*deg+0)  = Pow(z,d)
    Next
    matrix(size*deg,z*deg+0)    = in(z)
    
    For d=0 To deg-1
      matrix(z*deg+d, z*deg+1)  = Pow(z+1,d)
    Next
    matrix(size*deg,z*deg+1)    = in(z+1)

    If z <= size-2
      For d=1 To deg-2
        For e=0 To deg-1
          matrix(z*deg+e, z*deg+1+d)     = derivate(e,(z+1),d)
          matrix(z*deg+e+deg, z*deg+1+d) = matrix(z*deg+e, z*deg+1+d) * (-1)
        Next
      Next
    EndIf
  Next
  
  For x=1 To degree/2
    matrix(degree+x-2,size*deg-degree+x) = 1
  Next
  For y=1 To (degree-1)/2
    matrix(size*deg-y,size*deg-y) = 1
  Next

  
  ;/ solve system
  solve(matrix(),polynom())
  
EndProcedure
Procedure createPath(Array in.s_point(1),degree.i)
  
  Protected deg.i = degree+1
  Protected size.i = ArraySize(in())
  Protected Dim xpath.d(size)
  Protected Dim ypath.d(size)
  Protected Dim xpoly.d(size*deg-1)
  Protected Dim ypoly.d(size*deg-1)
  Protected z.i
  
  
  For z=0 To size
    xpath(z) = in(z)\x
    ypath(z) = in(z)\y
  Next

  spline(xpath(),xpoly(),degree)
  spline(ypath(),ypoly(),degree)
  
  ;/ draw
  Protected a.i,b.i,c.i
  Protected cur.d,valueX.d,valueY.d
  
  For a=0 To size-1
    For c=0 To 50
    
      cur = a+c/51
      
      valueX=0
      valueY=0
      For b=0 To degree
        valueX + xpoly(a*deg+b) * Pow(cur,b)
        valueY + ypoly(a*deg+b) * Pow(cur,b)
      Next
      
      If valueX >= 0 And valueX < 800
        If valueY >= 0 And valueY < 600
          Plot(valueX,valueY,$FFFFFF)
        EndIf
      EndIf
      
    Next
  Next

EndProcedure

;-------------------- TEST --------------------

Dim points.s_point(5)

points(0)\x = 25
points(0)\y = 240
points(1)\x = 50
points(1)\y = 70
points(2)\x = 25
points(2)\y = 90
points(3)\x = 100
points(3)\y = 110
points(4)\x = 125
points(4)\y = 45
points(5)\x = 150
points(5)\y = 70

OpenWindow(0,0,0,200,300,"blezier",#PB_Window_SystemMenu)
OpenWindowedScreen(WindowID(0),0,0,800,600,0,0,0)

Define eventID.i

Repeat
  Repeat
    eventID = WindowEvent()
    If eventID = #PB_Event_CloseWindow
      End
    EndIf
  Until eventID = 0
  ClearScreen(0)
  
  StartDrawing(ScreenOutput())
    createPath(points(),3)
    Define a.i
    For a=0 To 5
      Box(points(a)\x-1,points(a)\y-1,3,3,$0000FF)
    Next
  StopDrawing()
  
  FlipBuffers()
ForEver

[#NULL]

i tried a less mathematical aproach, that is to say, moving from point to point by speed and angle.
i guess one could also use this way to precalculate the hole path from some way points.
there's still a lot of tuning possible. for example the speed of rotation towards the next waypoint could be calculated from both the angle difference and the distance of the waypoint. currently its just approximation of the angle towards the needed angle by a certain factor per frame, so it doesn't take wider bends for waypoints that are further away. still you could 'emulate' that by using just more waypoints.
if you change the speed, you probaby have also to adjust the rotation speed or the tolerance to reach the waypoints. if you need your waypoints very close, you should also increase the rotation speed, otherwise points could be orbited without being reached.
use LMB/RMB to set/clear waypoints.

Code: Select all

InitSprite()
ww=400
wh=400
style | #PB_Window_ScreenCentered
style | #PB_Window_SystemMenu
style | #PB_Window_MinimizeGadget
hWin=OpenWindow(0, 50,100,ww,wh, "LMB: set points      RMB: clear points",style) :: AddKeyboardShortcut(0,#PB_Shortcut_Escape,10)
OpenWindowedScreen( hWin, 0,0,ww,wh, 0,0,0)

NewList p.POINT()               ; waypoints
x.f = ww/2                      ; object x
y.f = wh/2                      ; object y
angle.f                         ; object angle
speed_move.f = 0.4              ; movement speed
speed_rotate.f = speed_move*0.1 ; rotation speed
distance_tolerance.f = 3.0      ; pixel tolerance to reach waypoint
angle_needed.f                  ; angle from object to next waypoint
angle_diff.f                    ; rotation needed to point straight to next waypoint

CreateSprite(0,ww,wh)           ; only for saving passed way (the blue line)

Repeat
  event=WindowEvent()
  em=EventMenu()
  Select event
    Case #PB_Event_CloseWindow
      quit=1
    Case #PB_Event_Menu
      Select em
        Case 10
          quit=1
      EndSelect
    Case #WM_LBUTTONDOWN             ; add point
      LastElement(p())
      AddElement(p())
      p()\x = WindowMouseX(0)
      p()\y = WindowMouseY(0)
    Case #WM_RBUTTONDOWN             ; clear points
      ClearList(p())
      StartDrawing(SpriteOutput(0))
        Box(0,0,ww,wh,#Black)
      StopDrawing()
  EndSelect
  
  ; check arrival
  If ListSize(p())
    FirstElement(p())
    ; distance check only axis-based. you could use real distance calculation here if prefered
    If Abs(p()\x-x) < distance_tolerance And Abs(p()\y-y) < distance_tolerance
      DeleteElement(p())
    EndIf
  EndIf
  
  
  If ListSize(p())
    FirstElement(p())
    angle_needed = ATan2( p()\x-x, p()\y-y )
    
    ; (seems obsolete)
    ;If angle_needed < 0
    ;  angle_needed + 2*#PI ; 
    ;EndIf
    
    ; get angle difference
    If angle_needed > angle
      If (angle_needed-angle) < #PI
        angle_diff = (angle_needed - angle)
      Else
        angle_diff = -(2*#PI - (angle_needed - angle))
      EndIf
    Else
      If (angle-angle_needed) < #PI
        angle_diff = - (angle - angle_needed)
      Else
        angle_diff =  (2*#PI - (angle - angle_needed))
      EndIf
    EndIf
    
    ; rotate object
    angle + angle_diff*speed_rotate
    
    ; (seems obsolete)
    ;While angle > 2*#PI : angle - 2*#PI : Wend
    ;While angle < 0     : angle + 2*#PI : Wend
    
    x + speed_move*Cos(angle)
    y + speed_move*Sin(angle)
  EndIf
  
  DisplaySprite(0,0,0)                                              ; old path (blue)
  
  StartDrawing(ScreenOutput())
    ForEach p()
      Circle(p()\x,p()\y,2,#Green)                                  ; waypoints
    Next
    DrawingMode(#PB_2DDrawing_Outlined)
    Circle(x,y,4,#White)                                            ; position
    LineXY(x,y,x+20*Cos(angle_needed),y+20*Sin(angle_needed),#Red)  ; angle needed
    LineXY(x,y,x+10*Cos(angle),y+10*Sin(angle),#Green)              ; current angle
  StopDrawing()
  
  StartDrawing(SpriteOutput(0))
    Box(x,y,1,1,#Blue)                                              ; save current position
  StopDrawing()
  
  FlipBuffers()
  ;ClearScreen(#Black)
Until quit

[Fluid Byte]

I think I have enough material to work with and study now

Thanks guys for all the valuable infos and source code!