MaxVerlet Test

BlitzMax Forums/BlitzMax Beginners Area/MaxVerlet Test

Chroma

(Posted 2011) [#1]

Time for a proper test. Collision is working. It's not the best but it's doing the trick. If anyone would like to contribute to this please feel free. Any comments or source code suggestions to improve this would be great.

Here's what you need.

Vec2.bmx

' Vec2

Strict

Import BRL.Math

Type TVec2

	Field x#, y#

	Function Create:TVec2(x#=0, y#=0)
		Local v:TVec2 = New TVec2
		v.x = x
		v.y = y
		Return v
	End Function

	' Sets x and y
	Method Set(x_#=0, y_#=0)
		Self.x = x_
		Self.y = y_
	End Method
	
	'Sets x and y to 0
	Method Zero()
		Self.x = 0
		Self.y = 0
	End Method

	' Copys a to Self
	Method Copy(a:TVec2)
		Self.x = a.x
		Self.y = a.y
	End Method

	' Returns a New copy of Self
	Method Clone:TVec2()
		Return TVec2.Create(Self.x, Self.y)
	End Method

	'---MATH---

	' Adds x and y to Self
	Method PlusVar(a#, b#)
		Self.x :+ a
		Self.y :+ b
	End Method

	' Adds a to Self
	Method PlusVec(a:TVec2)
		Self.x :+ a.x
		Self.y :+ a.y
	End Method

	Method PlusVecPlusVec(a:TVec2, b:TVec2)
		Self.x :+ a.x + b.x
		Self.y :+ a.y + b.y
	End Method

	' Adds a and b together and sets Self to the sum
	Method EqVecPlusVec(a:TVec2, b:TVec2)
		Self.x = a.x + b.x
		Self.y = a.y + b.y
	End Method

	' Subtracts a and b from Self
	Method MinusVar(a#, b#)
		Self.x :- a
		Self.y :- b
	End Method

	' Subtracts a from Self
	Method MinusVec(a:TVec2)
		Self.x :- a.x
		Self.y :- a.y
	End Method

	Method MinusVecMinusVec(a:TVec2, b:TVec2)
		Self.x :- a.x + b.x
		Self.y :- a.y + b.y
	End Method

	' Subtracts b from a and sets Self to difference
	Method EqVecMinusVec:TVec2(a:TVec2, b:TVec2)
		Self.x = a.x - b.x
		Self.y = a.y - b.y
	End Method

	' Multiplies Self times scalar
	Method MulScalar(s#)
		Self.x :* s
		Self.y :* s
	End Method

	' Divides Self by scalar (avoids div by zero)
	Method DivScalar(s#)
		If s = 0 Return
		Self.x :/ s
		Self.y :/ s
	End Method

	'---OTHER---

	' Dot product
	Method Dot#(v:TVec2)
		Return Self.x * v.x + Self.y * v.y
	End Method

	' Cross product
	Method Cross#(v:TVec2)
		Return Self.x * v.y - Self.y * v.x
	End Method

	' Returns magnitude of Self
	Method Magnitude#()
		Return Sqr(Self.x * Self.x + Self.y * Self.y)
	End Method

	' Normalize Self
	Method Normalize()
		Local mag# = Self.Magnitude()
		Self.x :/ mag
		Self.y :/ mag
	End Method

	' Return a New Vec2 of normalized Self 
	Method NormalizeNew:TVec2()
		Local mag# = Self.Magnitude()
		Return TVec2.Create(Self.x / mag, Self.y / mag)
	End Method

	' Returns distance between Self and v
	Method Distance#(v:TVec2)
		Local dx# = Self.x - v.x
		Local dy# = Self.y - v.y
		Return Sqr(dx * dx + dy * dy)
	EndMethod

	' Returns angle between Self and v
	Method Angle#(v:TVec2)
		Local dx# = Self.x - v.x
		Local dy# = Self.y - v.y
		Return ATan2(dx, -dy)
	End Method

End Type

' Creates and Returns New Vec2 with x and y properties
Function Vec2:TVec2(x#=0, y#=0)
	Return TVec2.Create(x, y)
End Function

MaxVE.bmx:

' MaxVerlet Engine v0.00.01

' This code is Public Domain

Strict

Import "Vec2.bmx"

Type MaxVE
	Global _shapes:TList
	Global _gravity:TVec2
	Global _scrn_collision

	Function Init()
		_shapes = New TList
		_gravity = New TVec2
	End Function

	Function Simulate(timestep#=.1, iterations=1)
		Local s:VShape
		
		' Collision Test
		Local t:VShape
		For t = EachIn _shapes
		If Not t.isStatic
			For s = EachIn _shapes
				
				If t <> s
				
					' Point in Shape Collision
					Local i
					For i = 0 To t.point.length-1
						If PointInShape(t.point[i], s)
							Local px# = t.point[i].prev.x
							Local py# = t.point[i].prev.y
							t.point[i].curr.Set(px, py)
						EndIf
					Next
			
				EndIf
		
			Next
		EndIf
		Next
		
		For s = EachIn _shapes
			If s.active Then s.Update(iterations)
		Next

	End Function

	Function SetGravity(x#, y#)
		_gravity.Set(x, y)
	End Function

	Function AddShape(s:VShape)
		_shapes.AddLast(s)
	End Function
End Type


Type VShape
	Field point:VPoint[]
	Field con_edge:VConstraint[]
	Field con_supp:VConstraint[]

	Field active
	Field isStatic

	Method AddPoint(x#, y#, mass#=1)
		Self.point :+ [VPoint.Create(x, y, mass)]
	End Method

	Method AutoConstraintEdge(stiffness#=.5)
		Local i, j, plen = Self.point.length-1
		For i = 0 To plen
			If i < plen Then j = i + 1 Else j = 0
			Self.con_edge :+ [VConstraint.Create(Self.point[i], Self.point[j], stiffness)]
		Next
	End Method

	Method AddConstraint(p1:VPoint, p2:VPoint, mode=0, stiffness#=.5)
		Local c:VConstraint = VConstraint.Create(p1, p2, stiffness)
		Select mode
			Case 1
				Self.con_supp :+ [c]
			Default
				Self.con_edge :+ [c]
		End Select
	End Method

	Method Update(iterations)
		Local i

		' dirty collision
		For i = 0 To point.length-1
			point[i].col = False
			If point[i].curr.x < 0 Then point[i].curr.x = 0 ; point[i].col = True
			If point[i].curr.x > 1023 Then point[i].curr.x = 1023 ; point[i].col = True
			If point[i].curr.y > 767 Then point[i].curr.y = 767 ; point[i].col = True
		Next

		'Refresh all VPoints first (making sure not to refresh a point twice)
		Local conlen = con_edge.length-1
		For i = 0 To conlen Step 2
			con_edge[i].p1.Refresh()
			If i < conlen con_edge[i].p2.Refresh()
		Next

		SetColor 200,200,200
		' Resolve edge constraints
	
	Local iter
	For iter = 1 To iterations
		
		For i = 0 To conlen
			con_edge[i].Resolve()
			con_edge[i].Draw()
		Next

		' Resolve inner support constraints
		For i = 0 To con_supp.length-1
			con_supp[i].Resolve()
			con_supp[i].Draw()
		Next
	Next
	
		SetColor 0,200,0
		For i = 0 To point.length-1
			point[i].Draw()
		Next
		
	End Method
	
	Method SetStatic(b)
		isStatic = b
	End Method
	
	Method ApplyForce(angle#, force#)
		Local i
		For i = 0 To point.length-1
			point[i].force.PlusVar(Sin(angle) * force, -Cos(angle) * force)
		Next
	End Method
	
	Method SetLocked(b)
		Local i
		For i = 0 To point.length-1
			point[i].isLocked = True
		Next
	End Method
	
	Method ShowOutline(b)
		Local i
		For i = 0 To Self.con_edge.length-1
			Self.con_edge[i].isVisible = True
		Next
	End Method
End Type



Type VPoint
	Field curr:TVec2
	Field prev:TVec2
	Field temp:TVec2

	Field mass#
	Field force:TVec2

	Field col
	Field isLocked
	Field isVisible

	Function Create:VPoint(x#, y#, mass#=1, vis=True)
		Local p:VPoint = New VPoint
		p.curr = TVec2.Create(x, y)
		p.prev = TVec2.Create(x, y)
		p.temp = TVec2.Create()
		p.mass = mass
		p.force = TVec2.Create()
		p.isVisible = vis
		Return p
	End Function

	Method Refresh()
		Local DAMP# = 1
		If Self.col Then DAMP = .9
		If Self.isLocked Return
		Self.temp.Copy(Self.curr)
		Self.curr.x :+ DAMP * (Self.curr.x - Self.prev.x) + Self.force.x + MaxVE._gravity.x 
		Self.curr.y :+ DAMP * (Self.curr.y - Self.prev.y) + Self.force.y + MaxVE._gravity.y		
		Self.prev.Copy(Self.temp)
		Self.force.Zero()
	End Method

	Method SetLocked(b)
		Self.isLocked = b
		Self.prev.Copy(Self.curr)
	End Method

	Method Draw()
		If Self.isVisible DrawOval Self.curr.x - 2, Self.curr.y - 2, 5, 5
	End Method
End Type

Type VConstraint
	Field p1:VPoint
	Field p2:VPoint
	Field restLength#
	Field stiffness#

	Field isVisible

	Function Create:VConstraint(p1:VPoint, p2:VPoint, stiffness#=.5)
		Local c:VConstraint = New VConstraint
		c.p1 = p1
		c.p2 = p2
		c.restLength = p1.curr.Distance(p2.curr)
		c.stiffness = stiffness
		c.isVisible = True
		Return c
	End Function

	Method Resolve()
		Local delta:TVec2 = Vec2( p1.curr.x - p2.curr.x, p1.curr.y - p2.curr.y)
		Local deltaLength# = p1.curr.Distance(p2.curr)

		Local diff# = (deltaLength - restLength) / deltaLength
		Local ds# = diff * stiffness
		Local dmd:TVec2 = delta.Clone()
		dmd.MulScalar(ds)
		
		p1.curr.MinusVec(dmd)
		p2.curr.PlusVec(dmd)
	End Method

	Method Draw()
		If Self.isVisible DrawLine Self.p1.curr.x, Self.p1.curr.y, Self.p2.curr.x, Self.p2.curr.y
	End Method
End Type



Function CreateVerletBox:VShape(x, y, w, h, mass#=1, stiffness#=.5)
	Local b:VShape = New VShape
	
	' create 4 corner points
	b.AddPoint(x - w / 2, y - h / 2, mass)
	b.AddPoint(x + w / 2, y - h / 2, mass)
	b.AddPoint(x + w / 2, y + h / 2, mass)
	b.AddPoint(x - w / 2, y + h / 2, mass)
	
	' auto connect the points as edge constraints
	b.AutoConstraintEdge(stiffness)
	
	' add cross support constraints
	b.AddConstraint(b.point[0], b.point[2], 1, stiffness)
	b.AddConstraint(b.point[1], b.point[3], 1, stiffness)
	
	b.active = True
	
	Return b
End Function

Function CreateVerletCircle:VShape(x, y, x_diameter, y_diameter, segments=8, mass#=1, stiffness#=.5)
	Local i, j

	Local c:VShape = New VShape
	Local deg = 360/segments
	For i = 0 To segments-1
		c.AddPoint(x + Sin(i*deg) * x_diameter/2, y + -Cos(i*deg) * y_diameter / 2, mass)	
	Next

	' outer edge	
	c.AutoConstraintEdge()

	'inner supports
	For i = 0 To segments/2-1
		c.AddConstraint(c.point[i], c.point[i+segments/2], 1, stiffness)
	Next
	c.active = True
	Return c
End Function

Function CreateVerletTriangle:VShape(x, y, size)
	Local i
	Local t:VShape = New VShape
	For i = 0 To 359 Step 120
		t.AddPoint(x + Sin(i) * size, y + -Cos(i) * size)
	Next
	
	t.AutoConstraintEdge()
	t.active = True
	
	Return t
End Function

' Collision
Function PointInShape(p:VPoint, s:VShape)
	Local in = 0
	Local i, x#, y#, x1#, y1#, x2#, y2#

	x = p.curr.x
	y = p.curr.y

	For i = 0 To s.con_edge.length-1
		x1 = s.con_edge[i].p1.curr.x
		y1 = s.con_edge[i].p1.curr.y
		x2 = s.con_edge[i].p2.curr.x
		y2 = s.con_edge[i].p2.curr.y
		
		If ((((y1 <= y) And (y < y2)) Or ((y2 <= y) And (y < y1))) And (x < (((x2 - x1) * (y - y1)) / (y2 - y1)) + x1))
			in = 1 - in
		EndIf
	Next
	Return in
End Function


Function IsOdd(n)
	Return n And 1'n&1
End Function


Function IsEven(n)
	Return Not n And 1
End Function

And here's the test program:


Strict

Import "MaxVE.bmx"

Graphics 1024, 768

MaxVE.Init()
MaxVE.SetGravity(0,.3)

' make some stairs
Local i, p
For i = 0 To 5
	Local b:VShape = CreateVerletBox(50 + 100 * i, 400 + 50 * i, 100, 50)
	b.isStatic = True
	MaxVE.AddShape(b)
	For p = 0 To b.point.length-1
		b.point[p].isLocked = True
	Next
Next

' make some weird bowl thing
Local bowl:VShape = New VShape
bowl.AddPoint(900,20)
bowl.AddPoint(970,600)
bowl.AddPoint(600,480)
bowl.AddPoint(500,480)
bowl.AddPoint(600,420)
bowl.AddPoint(700,300)
bowl.AutoConstraintEdge()
bowl.SetStatic(True)
bowl.SetLocked(True)
bowl.active = True
MaxVE.AddShape(bowl)

While Not KeyHit(KEY_ESCAPE)
Cls

	If MouseHit(1)
		Local circle:VShape = CreateVerletCircle(MouseX(),MouseY(),50,50,12,1,.5)
		MaxVE.AddShape(circle)
	EndIf
		
	MaxVE.Simulate(,3)

Flip 1
Wend
End

Qcat	(Posted 2011) [#2]

Hi!

i have been having a mess around with the code and it seems to be working quite well. There seems to be in issue with the collision Code I have attached a screen shot below.

I will have a good look and see if I can finger it out a fix in the next few days!

Other than that it all seems to be going very well!

Adam

Chroma

(Posted 2011) [#3]

Yeah it's got to do with the collision reaction only working one way at the moment. The shape that gets hit doesn't react yet. I'm still trying to figure that one out but I know it has to do with get a line normal etc blah blah lol.

If you set the CreateVerletCircle segments to about 12 or 16 it's really fun to play with. :)

Btw, thanks for taking an interest in this. It really helps when someone else is posting feedback and helping out.

Last edited 2011

GfK	(Posted 2011) [#4]

For the record - this isn't a beginner's subject.

Chroma

(Posted 2011) [#5]

For the record - this isn't a beginner's subject

You're right. I never should have started this thread.

Anyways, some things that aren't working correctly/To Do List:

1. Constraint "stiffness". I envision a value from .01 to 1. With 1 being stiff as a board. It seems any value over .5 makes the resolve part blow up.

2. Collision needs mass taken into account and also reflection.

3. Angular constraints. Still looking into this one.

4. Getting a shapes rotation value. Basically all you need to have is two points that are vertically aligned and then return the angle between them. But if you have really weird shapes....mmhmm.

5. All the collision really needs is to put in a collision reaction for the object that is getting penetrated by a point. Then maybe some bounding box checking to help speed it all up. For the object colliding with something it's easy. You just back the point that collided back up to the previous position and the object reacts naturally. But the object that gets hit....

6. A way to Parent a shape to another shape just by location alone. Useful for attaching wheels to cars etc.

7. Shape rotation. I've seen the code somewhere. Just have to find it.

8. Proper restitution/friction. And a way to assign a shape a friction value so things can be slippery (ice) or have lots of traction (pavement).

Last edited 2011

Chroma

(Posted 2011) [#6]

Here's a LoadShape function that will load your own custom verlet shapes that are saved with .mvs extension (mvs = MaxVerletShape).

' MaxVerlet :: LoadShape
Function LoadShape:VShape(mvsFile$, scale#=1.0, x#, y#)
	If Not FileSize(mvsFile) Return Null

	Local s:VShape = New VShape

	' Parse MVS file
	Local io:TStream = ReadFile(mvsFile)

	Repeat

	Local dat$[] = ReadLine(io).Split("=")
	Local key$ = dat[0]
	dat = dat[1].Split(",")
	Local i, val#[]
	For i = 0 To dat.length-1
		val :+ [Float(dat[i])]
	Next

	Select key

		Case "point"
			s.AddPoint(x + val[0] * scale,y + val[1] * scale, val[2])

		Case "autoconstraintedge"
			If Int(val[0]) s.AutoConstraintEdge()

		Case "constraint"
			s.AddConstraint(s.point[Int(val[0])], s.point[Int(val[1])], Int(val[2]))
			

		Default

	End Select

	Until Eof(io)
	CloseFile(io)

	s.active = True

	Return s
End Function

Here's what a simple box.mvs file looks like.

point=0,0,1
point=1,0,1
point=1,1,1
point=0,1,1
autoconstraintedge=1
constraint=0,2,1
constraint=1,3,1

Last edited 2011

Chroma

(Posted 2011) [#7]

The LoadShape function works great.

I think it's time to actually start trying to build a mini-game Qcat. Maybe something like "Crush the Castle". The only thing we need to do before that can happen is to add line to line collision and bounding box checking. And add joints and hinges so we can build a catapult.

ima747

(Posted 2011) [#8]

This is looking awesome. Can't wait to find time to play with it!
A) Fingers crossed you roll a MOD out of this when you're happy with the results
B) Having no experience with vertlets, wondering how hard it might be to convert them for 3D (since they looks like a pretty easy to understand implementation of physics from my glances through this...)

Qcat	(Posted 2011) [#9]

Wow!

Things are going really well with this I will happily help out how ever I can. I have not had chance to try the load object code out has yet. (Hectic day we have a new database rollout at work tomorrow!)

It might be handy to add a way to attach sprites to an object. Perhaps it might be worth adding some kind of tether point. And then using good old cos and tan to work out than angle!

A little angry bird�s castle destroying sounds like a fun little project to me!

Last edited 2011

Chroma

(Posted 2011) [#10]

I started working on a simple shape editor. Just a small windowed app that lets you plot points in succession and throw in edge and support constraints. Then export to .mvs file so they can be loaded directly in. Will post it soon.

Btw, for the .mvs file, here's what each number is.

point=x,y,mass
autoconstraintedge=1   'this automatically outlines the shape with edge constraints
constraint=point1,point2,mode   'where mode is 0 for edge or 1 for support constraint

Edge constraints (mode 0) are used for collision. Be sure to use support constraints (mode 1) when adding inner support constraints.
Also, try to plot points around 0,0 with 0,0 being center. This is will automatically be taken care of in the editor.

Last edited 2011

Qcat	(Posted 2011) [#11]

a shape editor is a must! i am hoping to have a few days off work next week so am planing to have a play around with the code you have posted so far.

how are things going at the moment?

Chroma

(Posted 2011) [#12]

It's going pretty decent I suppose. Haven't had much anything new to show in the last few days. I really want to get the collision stuff done. I was thinking about how to complete it. Tell me what you think of this. The PointInShape function returns True when a point enters a shape. But, it doesn't do anything except move the offending point back to it's previous position, which is fine for dealing with collision for the offending shape. But what about the shape that was collided into? At the exact moment of collision. If you draw a line from the current point position to the previous point collision, it will intersect with a line on the shape that was collided in to. So to find out what line was hit, you do a lines intersect test. This will allow for a reaction for the collision to the shape that was hit! I just have to get the code in place and start tweaking. I believe this might allow for vertical stacking of one block on top of another. Maybe... But the theory is sound. I think it will work.

Hopefully I'll have time to test this out later this morning.

Qcat	(Posted 2011) [#13]

The logic of that method sounds fine to me! But the only way to really find out is to give it a try.

Speed is probably a slight issue and I was thinking about how you would factor delta time in.

Chroma

(Posted 2011) [#14]

Yep that's true. I've researched how to put the mass into the algorithms too so that will show up in the code prolly next time around. But, working 12 shifts at working right now sooo...time will be short until Sunday. :(