A faster starfield
BlitzMax Forums/BlitzMax Programming/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) |
| ||
| why do you say graphicsheight() and graphicswidth() are slow? 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. HTH Muttley |
| ||
| 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. 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): 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 |
| ||
| 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 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. :) |
   |