What's dragging me down?

BlitzMax Forums/BlitzMax Programming/What's dragging me down?

Pineapple

(Posted 2010) [#1]

I wrote a falling sand game a good while back, and I recently got an idea to make one that's really fast. So I wrote this code, and it it's completely painfully slow. I'm not using anything but integer maths, and even then the great majority of the operations are logic-based. Yet it's horridly slow. Why? I thought it might just be the rendering, but it's not.

Mouse wheel scrolls through the elements, left click places them

Here's the code

SuperStrict

Framework brl.Graphics
Import brl.d3d7max2d
Import brl.linkedlist
Import brl.random
Import brl.polledinput
Import "parse.bmx"


' elements
Global emax@@=256
Global rmax@@=256
Global ename$[emax]
Global ergb@[emax,3]
Global eattrib@[emax,5] 
'Does it move, does it react, does it affect the movement of other elements, does it experience slip while in midair, 
'if it reacts once per frame or if it reacts with all the surrounding elements
Global egrav%[emax]
Global eslip%[emax]
Global edens%[emax]
Global ereacts:TList[emax]


' reactions
Type reaction
	Field probability@@
	Field instigator@@
	Field secondary%
	Field result1%
	Field result2%
	Field minimum@
	Field maximum@
	Field reaction_type@
End Type

' sandbox
Global fw@@=640
Global fh@@=480
Global subw@=fw/8
Global subh@=fh/8
Global box@@[fw,fh]

Global check:TList=CreateList() 'places that need to be updated
Type vector
	Field x%,y%
End Type


Function vect:vector(x%,y%)
	Local v:vector=New vector
	v.x=x;v.y=y
	Return v
End Function





Function updatefield()
	Local dated@[fw+1,fh+1]
	Local nextcheck:TList=CreateList()
	Local done%=0
	For Local v:vector=EachIn check
		
		If ib(v.x,v.y) Then
		If dated[v.x+1,v.y+1]=0
		
		If done<2048
		
			dated[v.x+1,v.y+1]=1
			Local here%=box[v.x,v.y]
			
			
			If eattrib[here,0] 'do physics
				Local fell%=0
				Local newx%=v.x,newy%=v.y
				If (egrav[here]>0) & (v.y<fh-1)
					If (edens[here]=>edens[box[v.x,v.y+1]]) & Not(eattrib[box[v.x,v.y+1],0]) | (Not eattrib[box[v.x,v.y+1],2]) 
						If Rand(egrav[here])
							newy=newy+1
							nextcheck.addlast vect(newx,newy+1)
						EndIf
						fell=1
						nextcheck.addlast vect(v.x,v.y)
					EndIf
				ElseIf (egrav[here]<0) & (v.y And 1)
					If (edens[here]<=edens[box[v.x,v.y-1]]) & Not(eattrib[box[v.x,v.y-1],0]) | (Not eattrib[box[v.x,v.y-1],2]) 
						If Rand(-egrav[here])
							newy=newy-1
							nextcheck.addlast vect(newx,newy-1)
						EndIf
						fell=1
						nextcheck.addlast vect(v.x,v.y)
					EndIf
				EndIf
				If (eattrib[here,3] | (Not fell)) Then
					nextcheck.addlast vect(newx-1,newy);nextcheck.addlast vect(newx+1,newy);nextcheck.addlast vect(newx,newy)
					Local l%=0,r%=0
					If v.x
						If (edens[box[newx-1,newy]]<edens[here]) & (eattrib[box[newx-1,newy],0] | (Not eattrib[box[newx-1,newy],2])) Then l=1 
					EndIf
					If v.x<fw-1
						If (edens[box[newx+1,newy]]<edens[here]) & (eattrib[box[newx+1,newy],0] | (Not eattrib[box[newx+1,newy],2])) Then r=1
					EndIf
					If Rand(eslip[here])
						If l & r
							newx=newx+1
							If Rnd()>.5 newx=newx-2
						ElseIf r
							newx=newx+1
						ElseIf l
							newx=newx-1
						EndIf
					EndIf
				EndIf
				
				If Not ((v.x=newx) & (v.y=newy)) Then
					nextcheck.addlast v
					Local n:vector=New vector;n.x=newx;n.y=newy
					nextcheck.addlast n
					Swap(v.x,v.y,newx,newy)
					For Local thru:vector=EachIn check
						If thru.x=newx And thru.y=newy Then check.remove thru;Exit
					Next
				EndIf
				
				dated[newx+1,newy+1]=1
				
				done:+4
			EndIf
			
			
			
			
			here%=box[v.x,v.y]
			
			Local num%=0
			If eattrib[here,1] 'do reactions
				Local work:TList=CreateList();num%=0
				For Local ox%=v.x-1 To v.x+1
				For Local oy%=v.y-1 To v.y+1
					If ib(ox,oy) & (Not(ox=v.y & oy=v.y)) Then
						For Local r:reaction=EachIn ereacts[here]
							Local n:vector=New vector;n.x=ox;n.y=oy
							If r.secondary=box[ox,oy] Then work.addlast n;num=num+1
						Next
					EndIf
				Next
				Next
				If num
					Local choice%=Int(Rnd()*num+(.5/Float(num)))
					For Local get:vector=EachIn work
						Local do:reaction=Null
						For Local r:reaction=EachIn ereacts[here]
							If (r.secondary=box[get.x,get.y] | r.secondary=-1) And Rand(r.probability) do=r;Exit 
						Next
						If (((Not choice) | (eattrib[here,4])) & (do<>Null))
							DoReaction(v.x,v.y,get.x,get.y,do)
							nextcheck.addlast v
							nextcheck.addlast get
						EndIf
						choice=choice-1
					Next
				EndIf
				
				done:+1
			EndIf
		
		Else
			
			nextcheck.addlast v
				
		EndIf
		
		EndIf
		EndIf
		
	Next
	
	check=nextcheck
	
End Function



Function checkall()
	ClearList check
	For Local x%=0 To fw-1
	For Local y%=0 To fh-1
		check.addlast vect(x,y)
	Next
	Next
End Function



Function Swap(x1%,y1%,x2%,y2%)

	If KeyHit(key_1) renderfield 0,0
	If Not KeyDown(key_space)
		SetColor ergb[box[x1,y1],0],ergb[box[x1,y1],1],ergb[box[x1,y1],2]
		Plot x2,y2
		SetColor ergb[box[x2,y2],0],ergb[box[x2,y2],1],ergb[box[x2,y2],2]
		Plot x1,y1
	EndIf
	
	Local temp%=box[x1,y1]
	box[x1,y1]=box[x2,y2]
	box[x2,y2]=temp
	
End Function






Function DoReaction(ox%,oy%,tx%,ty%,r:reaction)
	Select r.reaction_type
		Case 0 'normal reaction
			box[ox,oy]=r.result1
			box[tx,ty]=r.result2
		Case 1 'make a circle
			
		Case 2 'make a line
			
	End Select
End Function





Global sel%=1
Function interaction()
	Local m:vector=New vector
	m.x%=MouseX();m.y%=MouseY()
	If m.x<0 m.x=0
	If m.x>fw-1 m.x=fw-1
	If m.y<0 m.y=0
	If m.y>fh-1 m.y=fh-1
	sel=MouseZ()
	If MouseDown(1) Then
		box[m.x,m.y]=sel
		check.addlast m
		SetColor ergb[sel,0],ergb[sel,1],ergb[sel,2]
		Plot m.x,m.y
	EndIf
End Function








Function renderfield(x%,y%)
	For Local xx%=0 To fw-1
	For Local yy%=0 To fh-1
		SetColor ergb[box[xx,yy],0],ergb[box[xx,yy],1],ergb[box[xx,yy],2]
		Plot x+xx,y+yy
	Next
	Next
End Function

Function Rand%(target%)
	Return (Rnd()*(2^16)<target)
End Function


Function ib%(x%,y%) 'in bounds
	Return (x And 1) & (x<(fw-1)) & (y And 1) & (y<(fh-1))
End Function






Function LoadPhysics(file$)
	Local fil:TStream=ReadFile(file)
	
	Local on%=0
	Local slip_in_air%=0
	Local react_all%=0
	Repeat
		Local lin$=Trim(ReadLine(fil))
		
		Local cmd$=parse(lin)
		
		If cmd="element" Then
			ename[on]=param[0]
			Print "Reading element #"+on+" : "+ename[on]
			ergb[on,0]=Byte(param[1])
			ergb[on,1]=Byte(param[2])
			ergb[on,2]=Byte(param[3])
			egrav[on]=Int(Double(param[4])*(2^16/100.0))
			eslip[on]=Int(Double(param[5])*(2^16/100.0))
			edens[on]=Int(param[6])
			ereacts[on]=CreateList()
			If egrav[on]<>0 Or eslip[on]>0 eattrib[on,0]=1;eattrib[on,2]=1
			If edens[on]=0 eattrib[on,0]=0
			eattrib[on,3]=slip_in_air
			eattrib[on,4]=react_all
			on=on+1
		EndIf
		If cmd="_setattrib"
			eattrib[on,Int(param[0])]=Int(param[1])
		EndIf
		If cmd="_setslip"
			slip_in_air=Int(param[0])
		EndIf
		If cmd="_setreact"
			react_all=Int(param[0])
		EndIf
		
	Until Eof(fil)
	
End Function



'Does it move, does it react, does it affect the movement of other elements, does it experience slip while in midair, 
'if it reacts once per frame or if it reacts with all the surrounding elements











loadphysics "fsgtest.txt"

Graphics 640,480
	For Local x%=6 To 80
		box[x+90,70]=1
		Local v:vector=New vector
		v.x=x+90;v.y=80
		check.addlast v
	Next
renderfield 0,0

Print "Ready."

Repeat
	interaction
	updatefield
	Flip
Forever

Parse.bmx

	SuperStrict
	
	Import brl.retro
	Import brl.system
	
	
	Private
	
	Global paramchars$="~~~q` /\.!@#$%^&*()[]{}|:'_-+1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM"
	Global paramquantity@=10

	Function ResetParams()
		numparams=0
		For Local reset%=0 To paramquantity-1
			param[reset]=""
		Next
	End Function
	Function CleanParams()
		For Local clean%=0 To numparams-1
			param[clean]=Replace(param[clean],Chr(9)," ") 'tab
			param[clean]=Replace(param[clean],Chr(34)," ")'return
			param[clean]=Trim(param[clean])
		Next
	End Function
	

	Public
	
	Global param$[paramquantity],numparams@
	Global comment$="//"
	
	Function Parse$(line$,disp$="")
		line=Trim(Replace(line,Chr(9)," "))
		Local name$=""
		If Left(Trim(line),Len(comment))=comment Then CleanParams;Return ""
		ResetParams()
		Local pos@@=0,onparam%=-1
		Repeat
			pos:+1
			Local char$=Mid(line,pos,1)
			If char=" " And onparam=-1 Then onparam=0;numparams=1;char=""
			If char="," Then onparam:+1;numparams:+1;char=""
			If onparam>paramquantity-1 Then Exit
			If Instr(line,comment)=pos Then Exit
			If Instr(paramchars,char) Then
				If onparam=-1
					If Not(char=" " Or char="~q") Then name:+char
				Else
					If char="~q" Then 'if it's in quotes, then anything goes in a param.
						Repeat
							pos:+1
							char=Mid(line,pos,1)
							If char="~q" Then Exit
							param[onparam]:+char
						Until pos>Len(line)
						If pos>Len(line) Then CleanParams;Notify "Improperly teminated string "+disp+" ( "+param[onparam]+" )",1;Return name
					Else
						param[onparam]:+char
					EndIf
				EndIf
			EndIf
		Until pos>Len(line)
		CleanParams
		If numparams=1
			If param[numparams-1]="" numparams:-1
		EndIf
		Return Trim(name)
	End Function

And fsgtest.txt

// element name , red , green , blue , gravity , slip , density

element Empty, 0,64,0, 0,0,0
_setattrib 0,0
_setattrib 2,0

element Wall, 128,128,128, 0,0,880
_setattrib 0,0
_setattrib 2,1

element Sand, 255,250,12, 100,9,10
//_setslip 1

Note that any code pertaining to reactions is far from complete.

Czar Flavius

(Posted 2010) [#2]

Do you know how to benchmark your code? Time different sections to find the one that's being so slow, and then you know where to optimise.

plash

(Posted 2010) [#3]

First glance, I see a lot of global variables (slow) and non-Int datatypes (slow, depending on use, as the compiler automagically converts non-Int numeric values to Int).

Pineapple

(Posted 2010) [#4]

Do you know how to benchmark your code? Time different sections to find the one that's being so slow, and then you know where to optimise.

This is the first time I've run the code.

Derron

(Posted 2010) [#5]

replaced
Flip
with
SetColor 0,155,55
DrawText(check.count(),0,0)
SetColor 255,255,255
Flip

Play a bit and you wil recognize how the global var check will get have more and more items in it. Processing 5000 objects in a list is no fun for your cpu... plotting each of them in 640x480 should be possible but avoid it if you are capable of.

Another thing noteable: your code isn't working out of the box, needed to disable the framework-command as else max2d is missing and some other null objects will be around.

bye MB

Pineapple

(Posted 2010) [#6]

The problem isn't the number of checks - it creates a ton of them to make sure nothing is missed, but a couple if statements in the next game loop ensure that the same coordinate is never checked twice even if it appears multiple times in the list, and that particles that have no reason to update won't. I'm wondering why it gets so crazy slow at only about 200 actual particle updates/frame.