A faster starfield

Hi everyone, I made a starfield for a game I'm currently working on. It works well enough (I may try to improve the visuals later) but it gets slow when there are more than several hundred stars onscreen at once. I was wondering if anyone could look through the code and see if they had any ideas of how to improve the speed. Thanks a lot!

Type TStarfield
	Global list:TList = CreateList()
	
	Field sx#,sy#
	Field layersX:Float[][3]
	Field layersY:Float[][3]
	Field layersTime:Int[][3]
	Field nstars
	Field rate
	
	Method New()
		list.addlast(Self)
	End Method
	
	Function Create:TStarfield(sx#,sy#,density#)
		Local s:TStarfield = New TStarfield
		s.nstars = sx*sy*density
		s.rate = 700
		
		For Local i = 0 To 2
			s.layersX[i] = New Float[s.nstars]
			s.layersY[i] = New Float[s.nstars]
			s.layersTime[i] = New Int[s.nstars]
			For Local t = 0 To s.nstars-1
				s.layersX[i][t]= Rnd(sx)'TStar.Create(Rnd(sx),Rnd(sy),255,255,255,3)
				s.layersY[i][t]= Rnd(sy)
			Next
		Next
		Return s
	End Function 
	
	Function DrawAll(x#,y#)
		For Local i:TStarfield = EachIn(list)
			i.draw(x#,y#)
		Next
	End Function
	
	Function UpdateAll(x#,y#)
		For Local i:TStarfield = EachIn(list)
			i.update(x#,y#)
		Next
	End Function
	
	Method Draw(x#,y#)
		Local time = MilliSecs()
		For Local t = 0 To 2
			Local tx = x*(t+1)/2
			Local ty = y*(t+1)/2
			For Local i = 0 To nstars-1
				If layersX[t][i]+tx>0 And layersX[t][i]+tx<GraphicsWidth() And layersY[t][i]+ty>0 And layersY[t][i]+ty<GraphicsWidth()
					If time-layersTime[t][i]<rate Then SetColor 128,128,128
					DrawOval layersX[t][i]+tx-(t+1)/2,layersY[t][i]+ty-(t+1)/2,t+1,t+1
					SetColor 255,255,255
				EndIf
			Next
		Next
	End Method
	
	Method Update(x#,y#)
		Local time = MilliSecs()
		For Local t = 0 To 2
			Local tx = x*(3-t)/2
			Local ty = y*(3-t)/2
			For Local i = 0 To nstars-1
				If layersX[t][i]+tx>0 And layersX[t][i]+tx<GraphicsWidth() And layersY[t][i]+ty>0 And layersY[t][i]+ty<GraphicsWidth()
					If time - layersTime[t][i]>rate And Rand(600) = 1 Then layersTime[t][i] = MilliSecs()
				EndIf
			Next
		Next
	End Method
End Type

At first glance I'd say you primary cause of slowdown is going to be the use of ovals. I think I would either load images or just create them in code, but drawing ovals every frame is probably not going to be terribly quick.

Are ovals nice to use here anyway?

Hi, would rectangles make things any better? I tried switching but the difference seemed negligible. I mean it's not a big deal as it runs fast enough but it still seems to be slowing things down more than it needs to. Thanks for the help!

Also you're setting the color every single star, which is an awful lot of state changes. I would minimize those as much as possible.

Can you show a bit more of the implementation? I am trying it but I am obviously doing something wrong because it is creating some very strange star fields.

Yea sure. You would use it as follows,

Graphics 800,600

TStarfield.Create(10000,10000,0.0001)
Local x#,y#
While Not KeyDown(KEY_ESCAPE)
	Cls
	If KeyDown(KEY_LEFT) Then x:+5
	If KeyDown(KEY_RIGHT) Then x:-5
	If KeyDown(KEY_UP) Then y:+5
	If KeyDown(KEY_DOWN) Then y:-5
	TStarfield.UpdateAll(x,y)
	TStarfield.DrawAll(x,y)
	Flip
Wend

Eventually i'll change the rectangles to something a bit more pretty.

@Gabriel the color suggestion definately did speed things up somewhat. Thanks!

I agree also you don't want to be calculating ovals every time especially if the size does not change. An image of an oval will be much faster.

So I am right in saying that would create 10000 stars per layer, with three layers, for a total of 30000 stars, but there are only ever a couple of hundred on screen?

Precalculate GraphicsWidth() and GraphicsHeight() - this can be very slow.

Do the same for things like layersX[t][i]+tx which are used often.
Array lookups can be expensive. Creating a local variable isn't.

@AngelDaniel: I switched to using images and it seemed to increase the performance by quite a bit.

@DJWoodgate: Yea, that's exactly what it's doing, but it only updates/draws the stars that are on screen. I agree that it would be ideal if I could find a way not to traverse the whole array. I thought about sorting it by distance from (0,0) but I just don't think the speed up would be that substantial.

@Brucey: I precalculated GraphicsWidth and Graphics Height. I'll do the array indices later.

Thanks for the help everyone. I would love to hear more suggestions if you have any.

Use quad tree to sort the stuff, this allows you quite easy "getting the set of starts to draw"

I would switch from using a linked list of stars and just use arrays.
Do you REALLY need the flexibility of being able to add and remove stars in and order?

honestly:

just use say, a few 128x128 sprites, with lots of stars on them, tiled.

It will be un-f-believably fast :)

@Brucey: why do you say graphicsheight() and graphicswidth() are slow?... sure it's a function call but that's minuscule compared to other things.

@Brucey: why do you say graphicsheight() and graphicswidth() are slow?... sure it's a function call but that's minuscule compared to other things.

@AngleDaniel: sure arrays are faster but lists are just so much nicer to work with....

just optimize the expensive things which almost always have to do with the graphics, switch to images, watch the state changes and don't spend all your time on optimizations... because often they don't give you the best bang for the buck (unless of course your purpose is the optimizations and not the app)

Depends on the platform you are running it on. On Linux at least (where I tried his code), taking out repeating calls to those sped things up a lot.

Anyhoo.. was just one of many things that made an immediate difference on my BlitzMax... But I realize there's probably only me using Linux as it is... :-)

I'd just keep a screens-worth of stars in memory and when one moves off the screen randomly place it the other side. Also I'd set up a Star type containing the X, Y, Speed and Colour variables and use an array of those. Calculate the colours during the update phase and store this with the actual stars, might be worth generating a dynamic list of stars with the same colour and drawing all stars with the same colour together.

DrawRect rather than DrawOval too.

Here's a Starfield that I've been working on for a Crazy Comets-alike game. I can happily get several thousand stars on screen with no slowdown.

Framework BRL.GLMax2D
Import BRL.Random
Import BRL.Math

SetGraphicsDriver GLMax2DDriver()
			
Type TStar
	Const SPREAD:Int = 800
	
	Field x:Float
	Field y:Float
	Field z:Float
	Field sx:Float
	Field sy:Float
	Field size:Int

	Function create:TStar()
		Local n:TStar = New TStar
		n.ResetPosition()
		z = Rand( 1, 255 )
		Return n
	EndFunction

	Method ResetPosition()
		x = Rand( -1000, 1000 )
		y = Rand( -1000, 1000 )
		z = 500
		size = Rand( 1, 3 )
	EndMethod

	Method Rotate( theta:Float )
		x = Cos( theta ) * x - Sin( theta ) * y
		y = Sin( theta ) * x + Cos( theta ) * y
	EndMethod

	Method Move( speed:Float )
 		If z < speed
			resetposition()
		Else
			z :- speed	
		EndIf
	EndMethod

	Method Translate()
  		sx = ( x * SPREAD ) / ( z ) + CentreX
  		sy = ( y * SPREAD ) / ( z ) + CentreY
  		If sx < 0 Or sx > Width Or sy < 0 Or sy > Height
			ResetPosition()
		EndIf
	EndMethod
	
	Method Draw()
		SetColor( Rand(32,255), Rand(32,255), Rand(32,255) )
		DrawRect( sx, sy, size, size )
	EndMethod
EndType

Type TStarfield
	Const NUM_OF_STARS:Int = 800
	Field stars:TStar[NUM_OF_STARS]
	Field rotating:Int = False
	Field rotateTarget:Int = 100
	Field rotateCurrent:Int = 0
	Field rotateSpeed:Int = 1
	Field changeDelay:Int = 0
	Field speed:Float = 8.0
	
	Function create:TStarfield()
		Local n:TStarfield = New TStarfield
		For Local i:Int = 0 To NUM_OF_STARS - 1
			n.stars[i] = TStar.Create()
		Next
		Return n
	EndFunction
	
	Method Update()
		If rotating = False
			If Rand(1,100) <= 10
				rotating = True
				rotateTarget = Rand( -250, 250 )
				changeDelay = Rand(0,150)
			EndIf
		Else
			If rotateTarget = rotateCurrent
				If rotateTarget <> 0
					rotateTarget = 0
				Else
					changeDelay :- 1
					If changeDelay = 0 Then rotating=False
				EndIf
			Else
				If rotateCurrent < rotateTarget
					rotateCurrent :+ rotateSpeed
				Else
					rotateCurrent :- rotateSpeed
				EndIf
			EndIf
		EndIf
		
		For Local i:TStar = EachIn stars
			i.Move( speed )
			i.Rotate( Float( rotateCurrent/100.0 ) )
			i.Translate()
		Next
	EndMethod
	
	Method Draw()
		SetAlpha( 0.8 )
		For Local i:Tstar = EachIn stars
			i.Draw()
		Next
		SetAlpha 1.0
		SetColor( 255,255,255 )
	EndMethod
EndType

Graphics 1024,768,0,60

SetBlend alphablend

Global Width:Int = GraphicsWidth()
Global Height:Int = GraphicsHeight()
Global CentreX:Int = Width/2
Global CentreY:Int = Height/2

Global starfield:Tstarfield = TStarfield.Create()

SeedRnd( MilliSecs() )

While Not KeyHit( KEY_ESCAPE )
	Cls
	starfield.Update()
	starfield.Draw()
	If KeyHit( KEY_F1 ) Then DebugStop
	Flip 1
Wend

HTH

Muttley

that's weird... are the functions different on different OSs? on windows they just return a variable.

yes thats what they do on any plattform but the way to get those values is faster or slower. You forget that on Linux, half of all people do not have hardware accelerated 3D desktop or block it in games by using Beryl and other eye candy stuff.

You should avoid function calls in tight loops... in this instance the overheads can stack up. Try pulling the content of you star update and draw functions directly into the respective updateall functions.

Another possibility is to make use of the deterministic nature of Random. Assign sectors of say 256*256 a unique number based on their position. Use this number as a random seed to determine all the star properties in this sector. You could buffer this information for faster access for screen refresh but essentially you do not need an array or list at all and there is no need to cycle through tens of thousands of stars. This gives you the advantage of a consistent and repeatable starfield if that is what you are after.

The other things is that you're creating and stepping through 30000 stars each update and draw loop even though there are never more than about 80 on screen at any one time.

You need to use some smoke and mirrors. It's highly unlikely that the player will notice that the stars are not the same when they change direction, so you can get away with randomly placing the stars on the other edge. Or if you want a little consistency have a starfield slightly larger than your screen display. For example if your resolution is 800 x 600, have a starfield size of 1600x1200 with only the middle being visible. That way at least half a screens worth will look the same when the player changes direction. They're unlikely to notice the rest, plus you'll be able to get away with only having about 200 stars, so much more processing time for the actual game...

Also don't forget about BMAX not batching any geometry for rendering, so every time you draw anything using MAX2D you're making separate calls to the hardware, thus stalling the bus. First try commenting out the rendering part, and check how fast your stuff is running, then with rendering. Then, try using OpenGL. Also, ovals/circles are probably not the best things to use for speed (more than 2 triangles per circle) Lastly implement a vertex cache class so you can push a ton of geometry with a single hardware call.

Here ya go, I fiddled with my other starfield to show what I meant (apart from the double width/height thing):

Framework BRL.GLMax2D
Import BRL.Random
Import BRL.Math

SetGraphicsDriver GLMax2DDriver()
			
Type TStar

	Field x:Float
	Field y:Float
	Field speed:Float
	Field size:Int
	Field colour:Int

	Function create:TStar()
		Local n:TStar = New TStar
		n.x = Rand( 0, Width )
		n.y = Rand( 0, Height )
		n.speed = Rnd( 0.001, 1.5 )
		n.size = Rand( 1, 3 )
		n.colour = Int(255 * n.speed)
		Return n
	EndFunction

	Method Move( _x:Int, _y:Int )
		x = x + _x
		y = y + _y
		If x < 0
			x = Width
			y = Rand( 0, Height )
		EndIf
		If x > Width
			x = 0
			y = Rand( 0, Height )
		EndIf
		If y < 0
			y = Height
			x = Rand( 0, Width )
		EndIf
		If y > Height
			y = 0
			x = Rand( 0, Width )
		EndIf
	EndMethod
	
	Method Draw()
		SetColor( colour, colour, colour )
		DrawRect( x, y, size, size )
	EndMethod
EndType

Type TStarfield
	Const NUM_OF_STARS:Int = 800
	Field stars:TStar[NUM_OF_STARS]
	Field speed:Float = 8.0
	
	Function create:TStarfield()
		Local n:TStarfield = New TStarfield
		For Local i:Int = 0 To NUM_OF_STARS - 1
			n.stars[i] = TStar.Create()
		Next
		Return n
	EndFunction
	
	Method Update( x:Int, y:Int )
		For Local i:TStar = EachIn stars
			i.Move( (x*speed)*i.speed, (y*speed)*i.speed )
		Next
	EndMethod
	
	Method Draw()
		SetAlpha( 0.8 )
		For Local i:Tstar = EachIn stars
			i.Draw()
		Next
		SetAlpha 1.0
		SetColor( 255,255,255 )
	EndMethod
EndType

Graphics 1280,1024,32,60

SetBlend alphablend

Global Width:Int = GraphicsWidth()
Global Height:Int = GraphicsHeight()
Global CentreX:Int = Width/2
Global CentreY:Int = Height/2

Global X:Int = 0
Global Y:Int = 0

Global starfield:Tstarfield = TStarfield.Create()

SeedRnd( MilliSecs() )

While Not KeyHit( KEY_ESCAPE )
	Cls
	If KeyDown( KEY_UP )
		Y = 1
	ElseIf KeyDown( KEY_DOWN )
		Y = -1
	Else
		Y = 0
	EndIf
	If KeyDown( KEY_LEFT )
		X = 1
	ElseIf KeyDown( KEY_RIGHT )
		X = -1
	Else
		X = 0
	EndIf
	
	starfield.Update( X, Y )
	starfield.Draw()
	If KeyHit( KEY_F1 ) Then DebugStop
	Flip 1
Wend

With this method I can get a rock-solid 60fps even with all your original 30000 stars onscreen at the same time. :)

HTH

Muttley

Wow, thanks for all the help everyone. I'm amazed by how little I notice whether or not the starfield is randomized as you move along. The speed ups are really good!

No problem. Glad to be able to help. :)

Muttley

You would need a third party random number module though, wouldn't you?

If anyone is interested the final code for the starfield is,

Type TStarfield
	Global list:TList = CreateList()
	
	Field sx#,sy#
	Field layersX:Float[][3]
	Field layersY:Float[][3]
	Field layersTime:Int[][3]
	Field nstars
	Field rate
	
	Method New()
		list.addlast(Self)
	End Method
	
	Function Create:TStarfield(density#)
		Local s:TStarfield = New TStarfield
		s.nstars = width*height*density
		s.rate = 700
		
		For Local i = 0 To 2
			s.layersX[i] = New Float[s.nstars]
			s.layersY[i] = New Float[s.nstars]
			s.layersTime[i] = New Int[s.nstars]
			For Local t = 0 To s.nstars-1
				s.layersX[i][t]= Rnd(width)'TStar.Create(Rnd(sx),Rnd(sy),255,255,255,3)
				s.layersY[i][t]= Rnd(height)
			Next
		Next
		Return s
	End Function 
	
	Function DrawAll()
		For Local i:TStarfield = EachIn(list)
			i.draw()
		Next
	End Function
	
	Method Randomize()
		For Local t = 0 To 2
			For Local i = 0 To nstars-1
				layersX[t][i]=Rnd(width)
				layersY[t][i]=Rnd(height)
			Next
		Next
	End Method
	
	Method Move(x#,y#)
		For Local t = 0 To 2
			For Local i = 0 To nstars-1
				layersX[t][i]:+x*(t+1)/4
				layersY[t][i]:+y*(t+1)/4
				If layersX[t][i]>width
					layersX[t][i] = 0
					layersY[t][i] = Rnd(height)
				ElseIf layersX[t][i]<0
					layersX[t][i] = width
					layersY[t][i] = Rnd(height)
				EndIf
				
				If layersY[t][i]>height
					layersY[t][i] = 0
					layersX[t][i] = Rnd(width)
				ElseIf layersY[t][i]<0
					layersY[t][i] = height
					layersX[t][i] = Rnd(width)
				EndIf
			Next
		Next
	End Method

	
	Method Draw()
		Local time = MilliSecs()
		For Local t = 0 To 2
			For Local i = 0 To nstars-1
				If layersX[t][i]>0 And layersX[t][i]<width And layersY[t][i]>0 And layersY[t][i]<height
					If time - layersTime[t][i]>rate And Rand(600) = 1 Then layersTime[t][i] = MilliSecs()
					If time-layersTime[t][i]<rate 
						SetColor 128,128,128
						DrawRect layersX[t][i]-(t+1)/2,layersY[t][i]-(t+1)/2,t+1,t+1
						SetColor 255,255,255
					Else
						DrawRect layersX[t][i]-(t+1)/2,layersY[t][i]-(t+1)/2,t+1,t+1
					EndIf
				EndIf
			Next
		Next
	End Method
End Type

Thanks once again everyone for your help.

Have you got the main code around that too? Just tried with a slightly modified version of what you posted before and it was very glitchy.

Well the main code is a lot more than a starfield, but to use the starfield you would do something like this,

Graphics 800,600

Local stars:TStarfield = TStarfield.Create(0.0005)
Local x#,y#
While Not KeyDown(KEY_ESCAPE)
	Cls
	If KeyDown(KEY_LEFT) Then stars.move(5,0)
	If KeyDown(KEY_RIGHT) Then stars.move(-5,0)
	If KeyDown(KEY_UP) Then stars.move(0,5)
	If KeyDown(KEY_DOWN) Then stars.move(0,-5)
	TStarfield.DrawAll()
	Flip
Wend

The only thing I'd suggest next is that the current method you use looks a little rigid and artificial, as there are only 3 different speeds and therefore 3 distinct layers.

I find this a little jarring to the eye, although in the past this was probably the best/only way of doing it. I have a Starfield that does just that which I wrote in assembly on the Commodore 64 (will have to dig that out sometime), but lack of processing power was the driver there of course.

Having a randomised speed for each star and scaling the colour value accordingly (like in my example) looks far nicer IMHO (YMMV, IANAL, etc.) of course ;).

Muttley

Thanks for the suggestion. Does this look any better in your oppinion?

Type TStarfield
	Global list:TList = CreateList()
	
	Field sx#,sy#
	Field layersX:Float[]
	Field layersY:Float[]
	Field layersR:Int[]
	Field layersG:Int[]
	Field layersB:Int[]
	Field layersSpeed:Float[]
	Field layersSize:Float[]
	Field layersTime:Int[]
	Field nstars
	Field rate
	
	Method New()
		list.addlast(Self)
	End Method
	
	Function Create:TStarfield(density#)
		Local s:TStarfield = New TStarfield
		s.nstars = width*height*density
		s.rate = 700
		
		s.layersX = New Float[s.nstars]
		s.layersY = New Float[s.nstars]
		s.layersR = New Int[s.nstars]
		s.layersG = New Int[s.nstars]
		s.layersB = New Int[s.nstars]
		s.layersSize = New Float[s.nstars]
		s.layersSpeed = New Float[s.nstars]
		s.layersTime = New Int[s.nstars]
		For Local t = 0 To s.nstars-1
			s.layersX[t]= Rnd(width)
			s.layersY[t]= Rnd(height)
			s.layersR[t]= Rand(100)+155
			s.layersG[t]= Rand(100)+155		
			s.layersB[t]= Rand(100)+155
			s.layersSpeed[t]= (Rnd(2)+1)/2
			s.layersSize[t]= Rnd(2)+1
		Next
		Return s
	End Function 
	
	Function DrawAll()
		For Local i:TStarfield = EachIn(list)
			i.draw()
		Next
	End Function
	
	Method Randomize()
		For Local i = 0 To nstars-1
			layersX[i]= Rnd(width)
			layersY[i]= Rnd(height)
			layersR[i]= Rand(100)+155
			layersG[i]= Rand(100)+155		
			layersB[i]= Rand(100)+155
			layersSpeed[i]= (Rnd(2)+1)/2
			layersSize[i]= Rnd(2)+1
		Next
	End Method
	
	Method Move(x#,y#)
		For Local i = 0 To nstars-1
			layersX[i]:+x*layersSpeed[i]
			layersY[i]:+y*layersSpeed[i]
			If layersX[i]>width
				layersX[i] = 0
				layersY[i] = Rnd(height)
				layersR[i]= Rand(100)+155
				layersG[i]= Rand(100)+155		
				layersB[i]= Rand(100)+155
				layersSpeed[i]= (Rnd(2)+1)/2
				layersSize[i]= Rnd(2)+1
			ElseIf layersX[i]<0
				layersX[i] = width
				layersY[i] = Rnd(height)
				layersR[i]= Rand(100)+155
				layersG[i]= Rand(100)+155		
				layersB[i]= Rand(100)+155
				layersSpeed[i]= (Rnd(2)+1)/2
				layersSize[i]= Rnd(2)+1
			EndIf
			
			If layersY[i]>height
				layersY[i] = 0
				layersX[i] = Rnd(width)
				layersR[i]= Rand(100)+155
				layersG[i]= Rand(100)+155		
				layersB[i]= Rand(100)+155
				layersSpeed[i]= (Rnd(2)+1)/2		
				layersSize[i]= Rnd(2)+1

			ElseIf layersY[i]<0
				layersY[i] = height
				layersX[i] = Rnd(width)
				layersR[i]= Rand(100)+155
				layersG[i]= Rand(100)+155		
				layersB[i]= Rand(100)+155
				layersSpeed[i]= (Rnd(2)+1)/2			
				layersSize[i]= Rnd(2)+1
			EndIf
		Next
	End Method

	
	Method Draw()
		Local time = MilliSecs()
		For Local i = 0 To nstars-1
			If layersX[i]>0 And layersX[i]<width And layersY[i]>0 And layersY[i]<height
				If time - layersTime[i]>rate And Rand(4000) = 1 Then layersTime[i] = MilliSecs()
				If time-layersTime[i]<rate 
					SetColor layersR[i]/2,layersG[i]/2,layersB[i]/2
					DrawRect layersX[i]-layersSize[i]/2,layersY[i]-layersSize[i]/2,layersSize[i],layersSize[i]
				Else
					SetColor layersR[i],layersG[i],layersB[i]
					DrawRect layersX[i]-layersSize[i]/2,layersY[i]-layersSize[i]/2,layersSize[i],layersSize[i]
				EndIf
			EndIf
		Next
		SetColor 255,255,255
	End Method
End Type

The usage is exactly the same.

Yeah, that looks much nicer. :)