Constant speed through a Catmullrom Vector path - Help needed!

Author

Message

PiaPoi

13

Years of Service

User Offline

Joined: 4th Dec 2012

Location:

Posted: 6th Mar 2014 03:05

Link

I'm plotting the course of a ship (2D sprite), using the Catmullrom vector command to make a nice smooth course between waypoints.

How can I get it to move at a constant speed along the line drawn?

set display mode desktop width(), desktop height(), 32
set window layout 0, 0, 0
maximize window

sync on : sync rate 0
set text font "tahoma" : set text size 18 : set text to bold

Load Bitmap "Sprite.bmp", 1 `size 20x50
Get Image 1, 0, 0, Bitmap Width(1), Bitmap Height(1)
Delete Bitmap 1

Type Thing
    PosX As Float
    PosZ As Float
EndType

Dim ob(2) As Thing

NumOfWayPoints = 15  ` (Must be >=4 because we need two anchors, and two bend points; the +2 is the first and last bend points)
Dim WayPoints(NumOfWayPoints) As Thing

// hi = 00 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 55
// hi = 01 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 50
// hi = 02 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 40
// hi = 03 : WayPoints(hi).PosX = 58 : WayPoints(hi).PosZ = 30
// hi = 04 : WayPoints(hi).PosX = 65 : WayPoints(hi).PosZ = 22
// hi = 05 : WayPoints(hi).PosX = 75 : WayPoints(hi).PosZ = 22
// hi = 06 : WayPoints(hi).PosX = 100 : WayPoints(hi).PosZ = 30
// hi = 07 : WayPoints(hi).PosX = 120 : WayPoints(hi).PosZ = 50
// hi = 08 : WayPoints(hi).PosX = 130 : WayPoints(hi).PosZ = 70
// hi = 09 : WayPoints(hi).PosX = 170 : WayPoints(hi).PosZ = 180
// hi = 10 : WayPoints(hi).PosX = 200 : WayPoints(hi).PosZ = 200
// hi = 11 : WayPoints(hi).PosX = 240 : WayPoints(hi).PosZ = 210
// hi = 12 : WayPoints(hi).PosX = 248 : WayPoints(hi).PosZ = 220
// hi = 13 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 230
// hi = 14 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 250
// hi = 15 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 260

For hi = 0 to NumOfWayPoints
    WayPoints(hi).PosX = RND(Desktop Width()) : WayPoints(hi).PosZ = RND(Desktop Height())
Next

ignore = Make Vector2(1)
ignore = Make Vector2(2)
ignore = Make Vector2(3)
ignore = Make Vector2(4)
SplineCurve = 5 : ignore = Make Vector2(SplineCurve)

Do
    
    Ink RGB(0,255,0)
    set text to bold
    center text screen width()/2, 5, "SPACE TO MOVE"
    set text to normal

` Draw WayPoints
    For x = 1 to NumOfWayPoints-1
        Circle WayPoints(x).PosX, WayPoints(x).PosZ, 2
    Next x
    
    ` Detect if we're at the start of a new WayPoint, and plot the next section of curve
    If WP_Progress# = 0
        Set Vector2 1, WayPoints(WP_Reached).PosX, WayPoints(WP_Reached).PosZ
        Set Vector2 2, WayPoints(WP_Reached+1).PosX, WayPoints(WP_Reached+1).PosZ
        Set Vector2 3, WayPoints(WP_Reached+2).PosX, WayPoints(WP_Reached+2).PosZ
        Set Vector2 4, WayPoints(WP_Reached+3).PosX, WayPoints(WP_Reached+3).PosZ
    
        ` Calculate length of curve by splitting into smaller lines, doing Trig, and adding them together
        Length# = 0
        Dim SplineLength(10) As Thing
        SplineLength(0).PosX = WayPoints(WP_Reached+1).PosX
        SplineLength(0).PosZ = WayPoints(WP_Reached+1).PosZ
        
        For x = 1 to 10
            CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, 0.1*x
            SplineLength(x).PosX = X Vector2(SplineCurve)
            SplineLength(x).PosZ = Y Vector2(SplineCurve)
            
            a# = Abs(SplineLength(x).PosX-SplineLength(x-1).PosX)
            b# = Abs(SplineLength(x).PosZ-SplineLength(x-1).PosZ)
            Inc Length#, SqRt( (a# * a#) + (b# * b#) )
        Next
        
        ` Now get the factor by which to modify the speed.
                    ` The ship will travel between each point in the same amount of time. So for longer distances,
                    ` we must set the speed slower accordingly. 
        LengthAugment# = 100 / Length#
    EndIf
        
    ` Draw this journey stage   
    Ink RGB(255,255,255)
    For y = 1 to 50
        CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, 0.02*y
        Dot X Vector2(SplineCurve), Y Vector2(SplineCurve)
    Next

Text 40,40, Str$(Length#)
    Text 40,60, Str$(LengthAugment#)
     
    ` Draw and move ship
    If SpaceKey() then Inc WP_Progress#, 0.05 * LengthAugment#
    
    CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, WP_Progress#
    fPosX# = X Vector2(SplineCurve) : fPosZ# = Y Vector2(SplineCurve)
    CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, WP_Progress#+0.001
    fProjX# = X Vector2(SplineCurve) : fProjZ# = Y Vector2(SplineCurve)
    Angle# = aTanFull(fProjX#-fPosX#, -(fProjZ#-fPosZ#))
    
    Sprite 1, fPosX#, fPosZ#, 1
    Offset Sprite 1, Sprite Width(1)/2, Sprite Height(1)/2
    Rotate Sprite 1, Angle#
    
    If WP_Progress# > 1 then Inc WP_Reached, 1 : WP_Progress# = 0
    If WP_Reached > NumOfWayPoints - 3 then WP_Reached = 0
    
    Sync
Loop

+ Code Snippet

set display mode desktop width(), desktop height(), 32
set window layout 0, 0, 0
maximize window

sync on : sync rate 0
set text font "tahoma" : set text size 18 : set text to bold


Load Bitmap "Sprite.bmp", 1 `size 20x50
Get Image 1, 0, 0, Bitmap Width(1), Bitmap Height(1)
Delete Bitmap 1

Type Thing
    PosX As Float
    PosZ As Float
EndType

Dim ob(2) As Thing


NumOfWayPoints = 15  ` (Must be >=4 because we need two anchors, and two bend points; the +2 is the first and last bend points)
Dim WayPoints(NumOfWayPoints) As Thing

// hi = 00 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 55
// hi = 01 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 50
// hi = 02 : WayPoints(hi).PosX = 55 : WayPoints(hi).PosZ = 40
// hi = 03 : WayPoints(hi).PosX = 58 : WayPoints(hi).PosZ = 30
// hi = 04 : WayPoints(hi).PosX = 65 : WayPoints(hi).PosZ = 22
// hi = 05 : WayPoints(hi).PosX = 75 : WayPoints(hi).PosZ = 22
// hi = 06 : WayPoints(hi).PosX = 100 : WayPoints(hi).PosZ = 30
// hi = 07 : WayPoints(hi).PosX = 120 : WayPoints(hi).PosZ = 50
// hi = 08 : WayPoints(hi).PosX = 130 : WayPoints(hi).PosZ = 70
// hi = 09 : WayPoints(hi).PosX = 170 : WayPoints(hi).PosZ = 180
// hi = 10 : WayPoints(hi).PosX = 200 : WayPoints(hi).PosZ = 200
// hi = 11 : WayPoints(hi).PosX = 240 : WayPoints(hi).PosZ = 210
// hi = 12 : WayPoints(hi).PosX = 248 : WayPoints(hi).PosZ = 220
// hi = 13 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 230
// hi = 14 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 250
// hi = 15 : WayPoints(hi).PosX = 250 : WayPoints(hi).PosZ = 260

For hi = 0 to NumOfWayPoints
    WayPoints(hi).PosX = RND(Desktop Width()) : WayPoints(hi).PosZ = RND(Desktop Height())
Next 

ignore = Make Vector2(1)
ignore = Make Vector2(2)
ignore = Make Vector2(3)
ignore = Make Vector2(4)
SplineCurve = 5 : ignore = Make Vector2(SplineCurve)


Do
    
    Ink RGB(0,255,0)
    set text to bold
    center text screen width()/2, 5, "SPACE TO MOVE"
    set text to normal

    ` Draw WayPoints
    For x = 1 to NumOfWayPoints-1
        Circle WayPoints(x).PosX, WayPoints(x).PosZ, 2
    Next x
    
    ` Detect if we're at the start of a new WayPoint, and plot the next section of curve
    If WP_Progress# = 0
        Set Vector2 1, WayPoints(WP_Reached).PosX, WayPoints(WP_Reached).PosZ
        Set Vector2 2, WayPoints(WP_Reached+1).PosX, WayPoints(WP_Reached+1).PosZ
        Set Vector2 3, WayPoints(WP_Reached+2).PosX, WayPoints(WP_Reached+2).PosZ
        Set Vector2 4, WayPoints(WP_Reached+3).PosX, WayPoints(WP_Reached+3).PosZ
    
        ` Calculate length of curve by splitting into smaller lines, doing Trig, and adding them together
        Length# = 0
        Dim SplineLength(10) As Thing
        SplineLength(0).PosX = WayPoints(WP_Reached+1).PosX
        SplineLength(0).PosZ = WayPoints(WP_Reached+1).PosZ
        
        For x = 1 to 10
            CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, 0.1*x
            SplineLength(x).PosX = X Vector2(SplineCurve)
            SplineLength(x).PosZ = Y Vector2(SplineCurve)
            
            a# = Abs(SplineLength(x).PosX-SplineLength(x-1).PosX)
            b# = Abs(SplineLength(x).PosZ-SplineLength(x-1).PosZ)
            Inc Length#, SqRt( (a# * a#) + (b# * b#) )
        Next
        
        ` Now get the factor by which to modify the speed.
                    ` The ship will travel between each point in the same amount of time. So for longer distances,
                    ` we must set the speed slower accordingly. 
        LengthAugment# = 100 / Length#
    EndIf
        
    ` Draw this journey stage   
    Ink RGB(255,255,255)
    For y = 1 to 50
        CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, 0.02*y
        Dot X Vector2(SplineCurve), Y Vector2(SplineCurve)
    Next

    Text 40,40, Str$(Length#)
    Text 40,60, Str$(LengthAugment#)
     
    ` Draw and move ship
    If SpaceKey() then Inc WP_Progress#, 0.05 * LengthAugment#
    
    CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, WP_Progress#
    fPosX# = X Vector2(SplineCurve) : fPosZ# = Y Vector2(SplineCurve)
    CatMullRom Vector2 SplineCurve, 1, 2, 3, 4, WP_Progress#+0.001
    fProjX# = X Vector2(SplineCurve) : fProjZ# = Y Vector2(SplineCurve)
    Angle# = aTanFull(fProjX#-fPosX#, -(fProjZ#-fPosZ#))
    
    Sprite 1, fPosX#, fPosZ#, 1
    Offset Sprite 1, Sprite Width(1)/2, Sprite Height(1)/2
    Rotate Sprite 1, Angle#
    
    If WP_Progress# > 1 then Inc WP_Reached, 1 : WP_Progress# = 0
    If WP_Reached > NumOfWayPoints - 3 then WP_Reached = 0
    
    Sync
Loop

(sorry you just have to add something as "Sprite.bmp" 20x50 pixels).

My problem is getting the speed of the ship constant. Two complications:
(1) Because it moves proportionally between each point (0-1), it moves faster the closer together the points are. I try to resolve this by slowing it down by the same degree but it doesn't seem to work.

This is my main question!
(2) The Catmullrom spline distributes the points such that they bunch together around waypoints, and particularly tight corners, so even if my (1) solution worked, the speed would still fluctuate.

I'd be really grateful for anyone's help. Thank you

Back to top

Profile PM

Le Verdier

14

Years of Service

User Offline

Joined: 10th Jan 2012

Location: In the mosh-pit

Posted: 7th Mar 2014 21:27 Edited at: 8th Mar 2014 11:36

Link

here are my thoughts, this is partial thoughts I wrote quickly
so I hope that it won't be too much confusing...
the problem is : "we know the coords of a point on the curve, we want to find the next point at a given distance".(I'll call this "sampling distance")
There is no analytical solution for arbitrary curves. I would opt for a dichotomy search.

firstly, break the curve into segments. pre divide a part between two waypoints into 4 segments(maybe more). this to avoid some cases where the distance between end and start point are smaller than the sampling distance.

Type SplineSegment
WayPointIndex
DichLower#
DichUpper#
Depth
EndType

then we init search stack:

+ Code Snippet

depthmax =7
	PointMax = PointCount - 1
Dim SegStack( 4*PointMax + depthmax) as SplineSegment


	StackPtrI = 4*PointMax
    	WayPointIndex = 0
	For i = 1 To PointMax
		Dec StackPtrI
		SegStack(StackPtrI).WayPointIndex = WayPointIndex
		SegStack(StackPtrI).Depth = 0
		SegStack(StackPtrI).DichLower# = 0.0
		SegStack(StackPtrI).DichUpper# = 0.25
		Dec StackPtrI
		SegStack(StackPtrI).WayPointIndex = WayPointIndex
		SegStack(StackPtrI).Depth = 0
		SegStack(StackPtrI).DichLower# = 0.25
		SegStack(StackPtrI).DichUpper# = 0.5
		Dec StackPtrI
		SegStack(StackPtrI).WayPointIndex = WayPointIndex
		SegStack(StackPtrI).Depth = 0
		SegStack(StackPtrI).DichLower# = 0.5
		SegStack(StackPtrI).DichUpper# = 0.75
		Dec StackPtrI
		SegStack(StackPtrI).WayPointIndex = WayPointIndex
		SegStack(StackPtrI).Depth = 0
		SegStack(StackPtrI).DichLower# = 0.75
		SegStack(StackPtrI).DichUpper# = 1.0
		Inc WayPointIndex
	Next i
	StackPtrI = 4*PointMax

the algorithm would look like this:

currentwaypoint = SegStack(StackPtrI).WayPointIndex
init CMR vectors with waypoints

while segment not accepted
dec StackPtrI
if currentwaypoint ≠ SegStack(StackPtrI).WayPointIndex
init CMR vectors with waypoints
currentwaypoint = SegStack(StackPtrI).WayPointIndex
endif
calculate coords of curve at SegStack(StackPtrI).DichUpper#
distance between thispoint and startpoint
if thisdistance > samplingdistance

if thisdistance ≤ samplingdistancemax or depthmax reached
AcceptSegment = true
else
divide segment
endif
endif

endwhile

For the next frame:
startpoint = thispoint

...
finding the very exact distance is not always possible.. instead we accept
a value bounded between samplingdistance & samplingdistancemax

we define samplingdistancemax as: samplingdistance + a small value.
e.g samplingdistance + samplingdistance /(2^ depthmax)

we can compare squared distances. this avoids a unnecessary sqrt

No need large depth search. The dichotomy fills a bit in the the floating number at each iteration and these are limited to 23...

the divide segment code:

+ Code Snippet

DichUpper# = SegStack(StackPtrI).DichUpper#
DichLower#= SegStack(StackPtrI).Dichlower#
DichMid# =( DichUpper# + Dichlower#) *0.5
depth= SegStack(StackPtrI).Depth
waypoint= SegStack(StackPtrI). WayPointIndex
SegStack(StackPtrI).DichUpper#= DichUpper#
SegStack(StackPtrI).Dichlower#= DichMid#
SegStack(StackPtrI).WayPointIndex= waypoint
SegStack(StackPtrI).Depth= depth+1
inc StackPtrI
SegStack(StackPtrI).DichUpper#= DichMid#
SegStack(StackPtrI).Dichlower#= Dichlower#
SegStack(StackPtrI).WayPointIndex= waypoint
SegStack(StackPtrI).Depth= depth+1
inc StackPtrI

Voila!
It is not ready to run, but hope that helps..

Back to top

Profile PM

PiaPoi

13

Years of Service

User Offline

Joined: 4th Dec 2012

Location:

Posted: 8th Mar 2014 03:46

Link

Wow thanks, LV!

My programming knowledge is not sufficient to know immediately what you have in mind, but I'll do my best to work my way through your instructions and see what I can learn!

Is the idea that you sample loads of points along the spline, work out the actual distances between each, then altar the "speed" accordingly, such that it would go faster through the more densely packed points, and slower through the sparser points, giving the overall effect of a constant speed?

If not, I'll try to understand more by working through it!

Thank you again.

Back to top

Profile PM

Le Verdier

14

Years of Service

User Offline

Joined: 10th Jan 2012

Location: In the mosh-pit

Posted: 8th Mar 2014 11:34 Edited at: 8th Mar 2014 11:35

Link

Not really. We want to avoid computing a load of points. Only the less possible for required accuracy..
But before discussing I noticed there is something missing in your code

sync on : sync rate 0
...
Do
...
Sync
Loop

This implies to use a TBM
This topic has been recently discussed here
http://forum.thegamecreators.com/?m=forum_view&t=210153&b=6

When updating a position we use Pos=Pos+Velocity*ElapsedTime
or Pos=Pos+Speed*ElapsedTime in scalar form, Speed*ElapsedTime is the distance linearily travelled. linearily because this is not the length of the part of the curve..
We know the speed, the elapsed time, so the distance can be figured out for each frame..

Back to top

Profile PM

Phaelax

DBPro Master

23

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 10th Mar 2014 03:24

Link

I tried finding a solution to this same issue with beziers a long time ago, never really did find what I wanted. My method, though not very efficient, was to calculate the length of each line segment making up the curves. Sounds similar to what Verdier is suggesting, I'll have to look at his example.

http://zimnox.com

Back to top

Profile PM Email Website

Sorry your browser is not supported!

DarkBASIC Professional Discussion / Constant speed through a Catmullrom Vector path - Help needed!