NewsForumsCodeLogsGallerySpecsSearch

grid based physics optimization = weird results...

BlitzMax Forums/BlitzMax Programming/grid based physics optimization = weird results...

Nate the Great(Posted 2009) [#1]
I was working on my physics engine and I thought of something... why dont I update all of the collisions with my grid optimization backwards instead of forwards to see if it increases stability... now the order you do your collisions shouldnt make a whole lot of difference should it? no but for some reason the boxes start intersecting and jittering all over the screen. Does anyone know enough about grid optimizations in verlet physics to guide me in the right direction... here is what I did...

'grid loop
For y = 0 To GridHeight-1
	For x = 0 To GridWidth-1
		'grid stuff here
	Next
Next


was changed to this

'grid loop
For y = GridHeight-1 To 0 Step -1
	For x = 0 To GridWidth-1
		'grid stuff here
	Next
Next


now kotsoft said he noticed that my fluid simulations had 'grid artifacts' so I believe there must be a bug in my code that leads to 'grid artifacts' (aka the fluid forming a grid shape which looks really odd for a fluid) and it also must cause my code to not run properly backwards... :p but from the evidence given, Nate the Great and his magnifying glass could not find the bug...

edit: heck why dont I just give out the whole of grid.bmx

Private
Global GridArray:Grid[100]
Global Gridlength:Int
Global GridWidth:Int
Global GridColumnCount:Int = 0
Global GridRowCount:Int = 0
Public
Global GridActive:Int = False

Type Grid	'this preforms fixed grid optimizations
	Field x:Int	'x and y in array not in the physics world
	Field y:Int
	
	Field VIG:verlet[20]
	Field VIGcount:Int
	
	Function Active:Int()
		Return GridActive
	End Function
	
	Function GridSize:Int()
		Return GridLength
	End Function
	
	Function Activate:Int(siz:Int)
		maxverlsiz = siz
		gridlength = maxverlsiz
		gridwidth = gridlength
		GridColumncount = (physicsrightbound-physicsleftbound)/gridwidth + 1
		GridRowCount = (physicslowerbound-physicsupperbound)/gridlength + 1
		gridarray = gridarray[..((GridRowCount+1)*(GridColumnCount+1))]
		GridActive = True
		
		Local x:Int = 0
		Local y:Int = 0
		
		For x = 0 To (GridColumnCount*GridRowCount)-1
			Gridarray:grid[x] = New grid
		Next
		
		Local g:grid
		For x = 0 To GridColumncount-1
			For y = 0 To gridRowCount-1
				g:grid = Gridarray:grid[(x+y*GridColumnCount)]
				g.x = x
				g.y = y
			Next
		Next
		Return True 
	End Function
	
	Function Clear()	'clears the grid
		Local g:grid
		Local i:Int
		For i = 0 To (GridRowCount*GridColumnCount)-1
			g:grid = GridArray:grid[i]
			g.VIGcount = 0
		Next
	End Function
	
	Function Update()
		Grid.Clear		'clear the grid
		Grid.Sort		'sort each verlet into the grid
		Grid.Collisions	'calculate collisions for each grid piece
	End Function
	
	Function Collisions()
		Local g:grid
		Local gg:grid
		Local ggg:grid
		Local x:Int = 0
		Local y:Int = 0
		Local xflag:Int = 0
		Local yflag:Int = 0
		
		For y = 0 To GridRowCount-1
			For x = 0 To GridColumncount-1
				
				g:grid = gridarray:grid[(x + (y)*GridColumnCount)]
				If g.VIGcount Then
					xflag = 0
					yflag = 0
					grid.collidegrid(g:grid,g:grid)
					
					If g.y < gridrowcount-1 Then yflag = True
					If g.x < gridcolumncount-1 Then xflag = True
					
					If xflag Then
						
						ggg:grid = gridarray:grid[g.x+1+(g.y)*GridColumnCount]
						grid.collidegrid(g:grid,ggg:grid)
						
						If yflag Then
							gg:grid = gridarray:grid[g.x+(g.y+1)*GridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
							
							grid.collidegrid(gg:grid,ggg:grid)
							
							gg:grid = gridarray:grid[g.x+1+(g.y+1)*gridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
							
						EndIf
					Else
						If yflag Then
							gg:grid = gridarray:grid[g.x+(g.y+1)*GridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
						EndIf
					EndIf
					
					
				EndIf
			Next
		Next
	End Function
	
	Function CollideGrid(g:grid,gg:grid)
		If g.VIGCount And gg.VIGcount Then
			Local v:verlet
			Local vv:verlet
			For Local cnt1:Int = 0 To g.VIGcount-1
				For Local cnt2:Int = 0 To gg.VIGcount-1
					v:verlet = g.VIG:verlet[cnt1]
					If g = gg Then v.done = True
					vv:verlet = gg.VIG:verlet[cnt2]
					If (v <> vv) And ((g = gg And vv.done = False) Or g >< gg) Then DoVcollisions(v:verlet,vv:verlet)
				Next
			Next
		EndIf
	End Function
	
	Function Sort()
		Local vcnt:Int
		Local v:verlet
		Local x:Int
		Local y:Int
		Local g:grid
		For vcnt = 0 To verlcount-1	'loop through all verlets and place them in the correct grid cells
			v:verlet = verletarray:verlet[vcnt]	'extracts verlet out of verlet array
			
			x = (v.x-physicsleftbound)/GridWidth		'computes the x and y grid position the verlets should be stored in
			y = (v.y-physicsupperbound)/Gridwidth
			If x > -1 And y > -1 And x < gridcolumncount And y < gridrowcount Then
				g:grid = gridarray:grid[x+y*GridColumnCount]	'gets the grid instance out of the grid array
				g.add(v:verlet)		'adds verlet to the grid cell
			EndIf
			
		Next
	End Function
	
	Function IsActive:Int()	'allows user to know if the grid is active or not
		Return GridActive
	End Function
	
	Method add(v:verlet)
		VIG:verlet[VIGcount] =  v:verlet
		VIGcount :+ 1
		If VIGcount > VIG.length - 2 Then VIG = VIG[..VIG.length+20]
		v.GD:grid = Self
	End Method
	
End Type


IK its messy and uncommented but I am working on it... commenting every line until I find the bug.

edit 2: oo I love when this happens... I try to figure something out for ages then boom it hits me within a minute of posting :) problem solved

edit 3: nevermind, it doesnt work


Nate the Great(Posted 2009) [#2]
so does anyone know about verlet based physics around here?


_Skully(Posted 2009) [#3]
Not really... but could it be that calculating the grid from start to finish each time would grid artifact the calculations... what if... and this is a big WHAT IF, you started at a different point each loop and cycle once through it... or used some kind of randomization technique that would hit every point?


Nate the Great(Posted 2009) [#4]
or used some kind of randomization technique that would hit every point?


thats a good idea if I could find one fast enough.... I guess I could make a stack (array) or all the grids in order then switch 2 radom grids 50 times... that might do the trick, but I know I am doing something else wrong... there is something that is buggy about the code... it should in theory work perfectly backwards but it doesnt!?!


_Skully(Posted 2009) [#5]
Am i correct in saying that vertlets will not interact unless they are in the same grid? if so what happens when vertlets are on the right and left or top and bottom borders of adjacent grids?

{edit} On closer look at the code I am incorrect...wrongo... see below


_Skully(Posted 2009) [#6]
Could be here?
	Function CollideGrid(g:grid,gg:grid)
		If g.VIGCount And gg.VIGcount Then
			Local v:verlet
			Local vv:verlet
			For Local cnt1:Int = 0 To g.VIGcount-1
				For Local cnt2:Int = 0 To gg.VIGcount-1
					v:verlet = g.VIG:verlet[cnt1]
					If g = gg Then v.done = True
					vv:verlet = gg.VIG:verlet[cnt2]
					If (v <> vv) And ((g = gg And vv.done = False) Or g >< gg) Then DoVcollisions(v:verlet,vv:verlet)
				Next
			Next
		EndIf
	End Function


Don't know if this is correct but you might be able to optimize this...

	Function CollideGrid(g:grid,gg:grid)
		If g.VIGCount And gg.VIGcount Then
			Local v:verlet
			Local vv:verlet
			For Local cnt1:Int = 0 To g.VIGcount-1
				v = g.VIG[cnt1]
				For Local cnt2:Int = 0 To gg.VIGcount-1
					vv:verlet = gg.VIG[cnt2]
					If v=vv Continue
					If vv.done=False DoVcollisions(v,vv)
				Next
				v.done=True
			Next
		EndIf
	End Function


this part was confusing the sh&t out of me...

If g = gg Then v.done = True


so if you are processing the same grids this vertlet is done?

If (v <> vv) And ((g = gg And vv.done = False) Or g >< gg) Then DoVcollisions(v:verlet,vv:verlet)


so if the vertlets are different AND (the grids are the same and the second vertlet is not done... or the grids are different) do vertlet collisions

Eyes crossed :P


_Skully(Posted 2009) [#7]
When you reverse your grid processing you are looking at grids behind you rather than forward...

I think your grid reversal problem is here:

					If g.y < gridrowcount-1 Then yflag = True
					If g.x < gridcolumncount-1 Then xflag = True
					
					If xflag Then
						
						ggg:grid = gridarray:grid[g.x+1+(g.y)*GridColumnCount]
						grid.collidegrid(g:grid,ggg:grid)
						
						If yflag Then
							gg:grid = gridarray:grid[g.x+(g.y+1)*GridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
							
							grid.collidegrid(gg:grid,ggg:grid)
							
							gg:grid = gridarray:grid[g.x+1+(g.y+1)*gridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
							
						EndIf
					Else
						If yflag Then
							gg:grid = gridarray:grid[g.x+(g.y+1)*GridColumnCount]
							grid.collidegrid(g:grid,gg:grid)
						EndIf
					EndIf



Nate the Great(Posted 2009) [#8]
thanks for taking such an indepth look I will explain all of the quirks that you pointed out.



this part was confusing the sh&t out of me...




this part is a bit confusing but its basically saying if I am checking for collisions between two grids and they are the same grid then v.done = true so I wont redundantly check for collisions which can lead to weird results

we use vv.done later... in the next line

If (v <> vv) And ((g = gg And vv.done = False) Or g >< gg) Then DoVcollisions(v:verlet,vv:verlet)


this says if the verlets are not the same then
if the grid is the same and these verlets have not been checked togethor already or if the grids are different the it doesnt matter if they have been checked already then

wait theres a flaw in there somewhere... I sense it but I dont really see it.... you know the feeling.

I think your grid reversal problem is here:



I dont see a problem.. could you be a little more specific?


_Skully(Posted 2009) [#9]
You check the next grid to the right, down, and down-right...

When you reverse the flow wouldn't you need to check the left, upper, and upper-left? maybe


wait theres a flaw in there somewhere... I sense it but I dont really see it.... you know the feeling.



Ya, I was getting the sense something was wrong.. try the re-written version I did:

	Function CollideGrid(g:grid,gg:grid)
		If g.VIGCount And gg.VIGcount Then
			Local v:verlet
			Local vv:verlet
			For Local cnt1:Int = 0 To g.VIGcount-1
				v = g.VIG[cnt1]
				For Local cnt2:Int = 0 To gg.VIGcount-1
					vv:verlet = gg.VIG[cnt2]
					If v=vv Continue
					If vv.done=False DoVcollisions(v,vv)
				Next
				v.done=True
			Next
		EndIf
	End Function


Basically the above compares each vertlet in grid g to each vertlet in grid gg. If vertlets are the same (should only occur when the same grid is being compared) it passes over it... if the vertlet being compared has already been done it also ignores it. Otherwise it will DoVCollisions...

finally when the vertlet in grid g is complete it flags as done.


Nate the Great(Posted 2009) [#10]
Ok I will try it skully :)

and I havent tried it yet because I dont have verlet max with me atm but I am thinking about just rewriting the grid function if yours doesnt work.


_Skully(Posted 2009) [#11]
Funny thing is... if I adapt your vertlet code to my tile engine... everything's position consists of a tile pointer, x, & y... so they are automatically sorted by the map tile size for collision detection :)


Nate the Great(Posted 2009) [#12]
[Funny thing is... if I adapt your vertlet code to my tile engine... everything's position consists of a tile pointer, x, & y... so they are automatically sorted by the map tile size for collision detection :)


yeah I guess... I dont know how I would go about doing verlet to tile collisions though... Its harder than it sounds.


_Skully(Posted 2009) [#13]
Its easy.. I have a pixelcollides function for particles :)


Nate the Great(Posted 2009) [#14]
I hope its fast enough for fluids!!! lol


_Skully(Posted 2009) [#15]
Might be... it just reads the image pixelmap... might not be for the number of particles you're dealing with though!


Nate the Great(Posted 2009) [#16]
yeah it may be best to use polygons to outline the tiles but those dont have a grid optimization atm


_Skully(Posted 2009) [#17]
the pixelcollision is working at 100000 operations in 43 ms on my machine


Nate the Great(Posted 2009) [#18]
hmmm so I assume 1,000 fluid points in .43 ms?

and then lets say theres 100 tiles thats 100,000 43 ms again :p


_Skully(Posted 2009) [#19]
Well, we can process them differently..

Since each fluid point needs to be processed, we could loop through those, comparing them to other points within adjacent tiles rather than looping through every tile. In fact, you could adapt that to your code as well... since you store the grid that each point is contained in within the vertlet itself, you could loop through the vertlets and process the grids as you go... this way you would never touch a grid that does not contain a vertlet.

Food for thought...


_Skully(Posted 2009) [#20]
I'm making some assumptions here... like there is a TList of vertlets
For v:vertlet=eachin Vertlets
	If Not v.flag
		g:Grid=gridarray[v.x+(v.y)*GridColumnCount]
		CollideGrid(g,g)
		If v.y < gridrowcount-1 Then yflag = True
		If v.x < gridcolumncount-1 Then xflag = True
		If xflag Then
			ggg:grid = gridarray:grid[v.x+1+(v.y)*GridColumnCount]
			grid.collidegrid(g,ggg)			
			If yflag Then
				gg = gridarray:grid[v.x+(v.y+1)*GridColumnCount]
				grid.collidegrid(g,gg)
				grid.collidegrid(gg,ggg)
				
				gg = gridarray:grid[v.x+1+(v.y+1)*gridColumnCount]
				grid.collidegrid(g,gg)			
			EndIf
		Else
			If yflag Then
				gg = gridarray:grid[v.x+(v.y+1)*GridColumnCount]
				grid.collidegrid(g,gg)
			EndIf
		EndIf
	EndIf
Next



Nate the Great(Posted 2009) [#21]
I'm making some assumptions here... like there is a TList of vertlets



well I use arrays for speed but I am going to add one for user accesability... right now everything is low level physics... no advanced bodies or groups or anything...


_Skully(Posted 2009) [#22]
Ok then you can just replace the eachin vertlets with rifling through your array.


Nate the Great(Posted 2009) [#23]
yeah... I decdided to just rewrite my grid now though.