Scripted Movement

Monkey Forums/Monkey Programming/Scripted Movement

Jesse

(Posted 2012) [#1]

I have been trying to create a type of scripted movement for objects such as ships characters etc.. this is my second time attempting this although I don't know if this is feasible or is there a better way as I am not too happy with it. has anybody here worked on something like this? I am hoping somebody has a better algorithm that might want to share.

this is what I have:
[monkeycode]
Strict
Import mojo

Class PVect2D
Field x:Float
Field y:Float
End Class

Function Main:Int()
New Game
Return True
End Function

Class Game Extends App
Field script:Script

Field txt:String = "S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200"

Method OnCreate:Int()
script = New Script
script.Init(txt)
SetUpdateRate 30
Return True
End Method

Method OnUpdate:Int()
Local n:Int = script.Update()
Return True
End Method

Method OnRender:Int()
Cls()
script.Render()
Return True
End Method

End Class

Class Movement
Field pos:PVect2D
Field v:PVect2D
Field d:PVect2D
Field len:Float
Field distance:Float
Field angle:Float
Field direction:Int
Field radius:Float
Field speed:Float
Field stp:Float
Field state:Int
Field remaind:Float

Field index:Int

Const READSCRIPT:Int = 1
Const ARC:Int = 2
Const LINE:Int = 3

Const LEFT:Int = 1
Const RIGHT:Int = 2

Method Update:Int() Abstract

End Class

Class Script Extends Movement
Field pivot:PVect2D
Field pattern:String[][][]

Method New()
pos = New PVect2D
v = New PVect2D
d = New PVect2D
pivot = New PVect2D
End Method

'**************************************************************************************
' the scripted movement uses a set of instruction passed to the
' the module in a string and are as follow:
'
' postion:
' P=x:float,y:float
' example: "P=300,300"
' sets the position
'
' angle:
' A=angle:float
' exampe: "A=45"
' sets the direction of travel
'
' speed:
' S=Speed:float
' example: "S=2.5"
' sets the speed of travel
'
' Arc:
' C=radius:float,NumberOfDigrees:float,DIRECTION:int(left/right)
' example: "C=20,45,L"
' moves in an arc pattern from its current diretion using specified radius and number of
' Degrees To travel in the direction specified using L(For left) Or R(For right)
'
' Line:
' N=distanceToTravel:Float
' exampe: "N=100"
' moves in a straight line in the current direction a specifield number of pixels.
'
' the instructions can be conbined in a single string and separated by ";"(semicolon).
' example: "P=300,300;A=0;S=3"
'
'**************************************************************************************

Method Init:Void(scr:String)
Local pat:String[] = scr.Replace(" ","").Split(";")
pattern = New String[pat.Length()][][]
For Local i:Int = 0 Until pat.Length()
Local parts:String[]= pat[i].Split("=")
pattern[i] = New String[parts.Length()][]
Local comp:String[] = parts[1].Split(",")
pattern[i][1] = New String[comp.Length()+1]
pattern[i][0] = New String[1]
pattern[i][0][0] = parts[0]
For Local k:Int = 0 Until comp.Length()
pattern[i][1][k] = comp[k]
Next
Next
state = READSCRIPT
index = 0
End Method

Method InitArc:Void(dir:Float,rad:Float,distance:Float)
direction = dir
d.x = Cos(angle)
d.y = Sin(angle)
If dir = LEFT
pivot.x = pos.x + (d.y * rad)
pivot.y = pos.y - (d.x * rad)
Elseif dir = RIGHT
pivot.x = pos.x - (d.y * rad)
pivot.y = pos.y + (d.x * rad)
Else
Error "Invalid Arc direction parameter"
Endif
stp = 1.0/(PI/180.0 * rad)
radius = rad
Self.distance = distance
len = 0
state = ARC
End Method

Method InitLine:Void(distance:Float)
Self.distance = distance
len = 0
d.x = Cos(angle)
d.y = Sin(angle)
state = LINE
End Method

Method SetPosition:Void(x:Float,y:Float)
pos.x = x
pos.y = y
End Method

Method SetAngle:Void(ang:Float)
angle = ang
End Method

Method Update:Int()

If state = READSCRIPT
If index < pattern.Length()
Repeat
Select pattern[index][0][0]
Case "P" 'position
pos.x = Float(pattern[index][1][0])
pos.y = Float(pattern[index][1][1])
Case "A" 'angle
angle = Float(pattern[index][1][0])
Case "S" 'speed
speed = Float(pattern[index][1][0])
Case "C" 'arc
If pattern[index][1][2] = "L"
InitArc(LEFT, Float(pattern[index][1][0]),Float(pattern[index][1][1])) ' dir, radius, distance
Elseif pattern[index][1][2] = "R"
InitArc(RIGHT,Float(pattern[index][1][0]),Float(pattern[index][1][1])) ' dir, radius, distance
Else
Error "Invalid Arc parameters pattern #"+index
Endif
index += 1
Exit
Case "N" 'line
InitLine(Float(pattern[index][1][0]))
index += 1
Exit
Default
Error "Invalid movement type instruction #"+index

End Select
index += 1
Until index = pattern.Length()
Else
Return False
Endif
Endif
If state = ARC
Local ang:Float
If len < distance
ang = stp*speed
len += ang
If len > distance
remaind = len - distance
ang -= remaind
state = READSCRIPT
distance = len
Endif
Else
remaind = 0
state = READSCRIPT
Endif

Local tx:Float = pos.x - pivot.x
Local ty:Float = pos.y - pivot.y
If direction = LEFT
pos.x = pivot.x + tx*Cos(-ang) - ty*Sin(-ang)
pos.y = pivot.y + ty*Cos(-ang) + tx*Sin(-ang)
angle -= ang
Else
pos.x = pivot.x + tx*Cos(ang) - ty*Sin(ang)
pos.y = pivot.y + ty*Cos(ang) + tx*Sin(ang)
angle += ang
Endif
Elseif state = LINE
len += speed
If len > distance
remaind = len - distance
len = distance
pos.x += d.x * (speed-remaind)
pos.y += d.y * (speed-remaind)
state = READSCRIPT
Else
pos.x += d.x *speed
pos.y += d.y *speed
Endif
Endif
Return True
End Method

Method Render:Int()
DrawOval pos.x-1,pos.y-1,2,2
Return True
End Method

End Class
[/monkeycode]

Gerry Quinn

(Posted 2012) [#2]

I don't see anything wrong with it in general, except for the temptation to make it more elaborate than your game needs.

I presume Render() is just for debugging, and normally a script would be attached to an object which would consult it when it wants to move.

Jesse

(Posted 2012) [#3]

Thanks Gerry, I was just hoping somebody had a better more optimized algorithm, Because the way I have it, I use strings and they are really slow to process. when I first did the tests, I was splitting the string on the fly and flash was lagging pretty badly with a 30 FPS updater rate. I had to do all of the pre splitting of string in the initialization to improve it slightly. While this is fine for a single object, for multiple objects it would probably be really slow specially while introducing new objects during game play. Also, based on what I read from muddy shoes, multiple dimension array are slow. so, I will end up figuring an alternative to the data.

And yes, the Render is just for demonstration purpose. I was going to include an image that included the rotation for demonstration but I changed my mind and just included the DrawOval.

muddy_shoes

(Posted 2012) [#4]

Also, based on what I read from muddy shoes, multiple dimension array are slow

Can be, but the real point was that moving to single dimensional arrays is not something that will provide a noticeable performance boost outside of fairly specific circumstances. I'm not sure this is one as it seems highly unlikely that the array accesses are even a blip compared to the string operations.

I ran your code with a few thousand instances of your test script objects and speed didn't seem to be an issue on HTML5 or Flash. Enough objects or large enough scripts will make it an issue, of course, but I don't know how ambitious you intend to be.

As you said, you've front-loaded the string parsing. If that initial cost becomes a problem then you can spread the cost by only splitting it into the commands and parsing those as required, e.g.


Strict
Import mojo

Class PVect2D
        Field x:Float
        Field y:Float
End Class


Function Main:Int()
        New Game        
        Return True
End Function
Const NUM_TEST_OBJECTS:Int = 5000
Class Game Extends App
        Field script:Script[]

        Field txt:String = "S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200;S=2.5;P=200,400;A=0;C=50,90,L;N=100;C=100,45,R;N=50;C=20,135,R;N=200"

        Method OnCreate:Int()
                script = New Script[NUM_TEST_OBJECTS]
                Init()
                SetUpdateRate 30
                Return True
        End Method
        
        Method Init:Void()
            For Local i:Int = 0 Until NUM_TEST_OBJECTS
                    script[i] = New Script
                    script[i].Init(txt)
            End
        End
        
        Method OnUpdate:Int()
                If MouseHit()
                    Init()
                    Return 1
                End
                Local done:Bool = True
                For Local i:Int = 0 Until NUM_TEST_OBJECTS
                    If script[i].Update()
                        done = False
                    End
                End
                If done
                    Init()
                End
                Return True
        End Method
        
        Method OnRender:Int()
                Cls()
                script[0].Render()
                Return True
        End Method
        
End Class


Class Movement
        Field pos:PVect2D
        Field v:PVect2D
        Field d:PVect2D
        Field len:Float
        Field distance:Float
        Field angle:Float
        Field direction:Int
        Field radius:Float
        Field speed:Float
        Field stp:Float
        Field state:Int
        Field remaind:Float
        
        Field index:Int
        
        Const READSCRIPT:Int = 1
        Const ARC:Int = 2
        Const LINE:Int = 3
        
        Const LEFT:Int = 1
        Const RIGHT:Int = 2 

        Method Update:Int() Abstract
        
End Class


Class Script Extends Movement
        Field pivot:PVect2D
        Field pattern:String[]
        
        Method New()
                pos = New PVect2D
                v = New PVect2D
                d = New PVect2D
                pivot = New PVect2D
        End Method

'**************************************************************************************
'       the scripted movement uses a set of instruction passed to the 
'       the module in a string and are as follow:
'
'       postion:
'       P=x:float,y:float
'       example: "P=300,300"
'       sets the position
'
'       angle:
'   A=angle:float
'       exampe: "A=45"
'       sets the direction of travel
'
'       speed:
'       S=Speed:float
'       example: "S=2.5"
'   sets the speed of travel
'
'       Arc:
'       C=radius:float,NumberOfDigrees:float,DIRECTION:int(left/right)
'       example: "C=20,45,L"
'       moves in an arc pattern from its current diretion using specified radius and number of
'       Degrees To travel in the direction specified using L(For left) Or R(For right)
'       
'       Line:
'       N=distanceToTravel:Float
'       exampe: "N=100"
'       moves in a straight line in the current direction a specifield number of pixels.
'
'       the instructions can be conbined in a single string and separated by ";"(semicolon).
'       example: "P=300,300;A=0;S=3"
'
'**************************************************************************************

        Method Init:Void(scr:String)
            pattern = scr.Split(";")
            state = READSCRIPT
            index = 0
        End Method
        
        Method InitArc:Void(dir:Float,rad:Float,distance:Float)
                direction = dir
                d.x = Cos(angle)
                d.y = Sin(angle)
                If dir = LEFT
                        pivot.x = pos.x + (d.y * rad)
                        pivot.y = pos.y - (d.x * rad)
                Elseif dir = RIGHT
                        pivot.x = pos.x - (d.y * rad)
                        pivot.y = pos.y + (d.x * rad)
                Else
                        Error "Invalid Arc direction parameter"
                Endif
                stp = 1.0/(PI/180.0 * rad)
                radius = rad
                Self.distance = distance
                len = 0
                state = ARC
        End Method
        
        Method InitLine:Void(distance:Float)
                Self.distance = distance
                len = 0
                d.x = Cos(angle)
                d.y = Sin(angle)
                state = LINE
        End Method
        
        Method SetPosition:Void(x:Float,y:Float)
                pos.x = x
                pos.y = y
        End Method
        
        Method SetAngle:Void(ang:Float)
                angle = ang
        End Method
        
        Method ReadScript:Int()
            If index < pattern.Length()
                    Repeat
                        Local parts:String[]= pattern[index].Split("=")
                        Local comp:String[] = parts[1].Replace(" ","").Split(",")
                        Local command:String = parts[0].Trim()
                        
                            Select command
                                    Case "P" 'position
                                                    pos.x = Float(comp[0])
                                                    pos.y = Float(comp[1])
                                    Case "A" 'angle
                                            angle = Float(comp[0])
                                    Case "S" 'speed
                                            speed = Float(comp[0])
                                    Case "C" 'arc
                                            If comp[2] = "L" 
                                                    InitArc(LEFT, Float(comp[0]),Float(comp[1])) ' dir, radius, distance
                                            Elseif comp[2] = "R"
                                                    InitArc(RIGHT,Float(comp[0]),Float(comp[1])) ' dir, radius, distance
                                            Else
                                                    Error "Invalid Arc parameters pattern #"+index
                                            Endif
                                            index += 1
                                            Exit
                                    Case "N" 'line
                                            InitLine(Float(comp[0]))
                                            index += 1
                                            Exit
                                    Default
                                            Error "Invalid movement type instruction #"+index
                                            
                            End Select
                            index += 1
                    Until index = pattern.Length()
                    
                    Return True
            Else
                    Return False
            Endif
        End
        
        Method Update:Int()
        
                If state = READSCRIPT
                    If Not ReadScript()
                        Return False
                    End
                Endif
                If state = ARC
                        Local ang:Float
                        If len < distance
                                ang = stp*speed
                                len += ang
                                If len > distance
                                        remaind = len - distance
                                        ang -= remaind
                                        state = READSCRIPT
                                        distance = len
                                Endif
                        Else
                                remaind = 0
                                state = READSCRIPT
                        Endif
                        
                        Local tx:Float = pos.x - pivot.x
                        Local ty:Float = pos.y - pivot.y
                        If direction = LEFT
                                pos.x = pivot.x + tx*Cos(-ang) - ty*Sin(-ang) 
                                pos.y = pivot.y + ty*Cos(-ang) + tx*Sin(-ang) 
                                angle -= ang
                        Else
                                pos.x = pivot.x + tx*Cos(ang) - ty*Sin(ang) 
                                pos.y = pivot.y + ty*Cos(ang) + tx*Sin(ang)
                                angle += ang
                        Endif
                Elseif state = LINE
                        len += speed
                        If len > distance
                                remaind = len - distance
                                len = distance
                                pos.x += d.x * (speed-remaind)
                                pos.y += d.y * (speed-remaind)
                                state = READSCRIPT
                        Else
                                pos.x += d.x *speed
                                pos.y += d.y *speed
                        Endif
                Endif
                Return True
        End Method
        
        Method Render:Int()
                DrawOval pos.x-1,pos.y-1,2,2
                Return True
        End Method

End Class

You still need to test to see if it's actually better for your purposes on your intended platform though.

AdamRedwoods

(Posted 2012) [#5]

interesting ideas.

another thought would be to parse the animation string into an object array. this can be done OnInit() for all objects that have an animation string. you would have to keep an object list which is added to during a New().

Gerry Quinn

(Posted 2012) [#6]

I find it hard to believe that the problem is really in your algorithm, unless you have an extraordinarily large number of objects. Have you tried carrying out just typical algorithmic operations a few (or many) thousand times in a loop and checking the time taken using Millisecs()?

You could certainly make a few optimisations here and there, for example calculating Cos( ang ) just once. Some compilers will probably do that for you, but I suspect that won't apply to all the targets.

Your arrays are just look-up tables, so I doubt they are a speed issue. Where you might get a speed issue for multidimensional arrays is pathfinding, dungeon generation, board-games and such, where you are very much focused on cells and adjacent cells. And even there it's not all that terrible. I found for example that the Dijkstra algorithm was a little more than half as fast on 2D as 1D.

Jesse

(Posted 2012) [#7]

thanks muddy, I have yet to do some real tests as I haven't had much time to do work on it and won't today either going out fishing with a couple of friends but will soonish.

Garry, my initials test proved to me that the update method was slow. obviously, I don't have the original code to prove it because of the modifications I made with this new code. Maybe I jumped the gun as I haven't done any proper testing. My only reason for concluding that is because when I removed the parsing from the main loop the frame rate got normal before that it was slow and it showed clearly because it was skipping OnRender processing. So my conclusion is that every time I do parsing it will consume quite a bit of milliseconds. so if I have multiple objects in the screen each with its own script it will cause some serious lagging. All of these tests were done with flash so don't know about the other targets. If you wan't to believe that, its fine with me, and if you don't then that's also fine. I am just glad you took the time to comment and thank you for that.

Adam, I like your idea. I might end up doing that.