Jump to content

  • Log In with Google      Sign In   
  • Create Account

Culling 'not on screen' Entites


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 dsm1891   Crossbones+   -  Reputation: 1309

Like
0Likes
Like

Posted 14 July 2013 - 02:48 PM

Hello all,

 

I am currently working on a 2D RTS game (tiled based and oblique projection). I wanted a way to only draw the entities that are currently on screen, my first instinct was to store the entities in an array, then check through that array, to see if any entities where inside the camera view, and if they where draw them.

 

However, this will become taxing to do if there is a large amount of units and/or players (enemy), as it would have to sort through the hundreds(ish) of times a second. My second, thought was to store them in a two dimensional array (according to their X and Y values), then use a calculation based of the camera position, to start/stop drawing the entities only in the camera view (this is pretty much the same process I use to draw the map's tiles).

 

This method has the advantage it would be a lot easier to draw, as I wouldn't need to sort them according to their Y Value (so units could over lap each other (again, oblique projection)). The only real downside is when entities start moving around the map, they would delete each other if they walked through each other(although could be prevented). Also, to me at least, it seems a bit long winded. 

 

Does anyone else have any suggestions/alterations?

 

Thanks a lot! :)



Sponsor:

#2 markr   Crossbones+   -  Reputation: 1653

Like
1Likes
Like

Posted 14 July 2013 - 03:39 PM

My initial thought is that you're doing this wrong - simply "culling" entities out of the view frustum does not stop them from consuming resources (altogether).

 

You should consider "freezing" or even deleting entities which go too far away from the player. Exactly what behaviour you use depends on your game mechanics.

 

Rather than stop rendering them, you can also stop doing anything else with them (e.g. stop calling their tick function, remove them from collision detection etc), or delete them completely (which also has the effect of freeing memory).

 

A simplistic implementation would break the world into "blocks" of some size (maybe 2-9 screens) and attach a list of "inactive" entities to these blocks. When the player gets close to a block, "activate" all ents in the block. When an active entity gets too far away from the player, you can deactivate it by moving it out of the active list into the inactive entities for its block.

 

It also depends how you initialise the areas of the map the player hasn't yet visited. If your game is relatively small, you could initialise all mobs at the beginning of the game and just activate them when the player gets near.

 

If your game is bigger, you could "lazily" populate the world with monsters, and only populate blocks when the player reaches them for the first time - although this leaves the opportunity for a fast moving player to use a lot of memory by causing many blocks to be initialised.

 

A variety of other tricks could be used along the same lines. Use your imagination.



#3 Servant of the Lord   Crossbones+   -  Reputation: 19662

Like
1Likes
Like

Posted 14 July 2013 - 04:00 PM

I am currently working on a 2D RTS game (tiled based and oblique projection). I wanted a way to only draw the entities that are currently on screen, my first instinct was to store the entities in an array, then check through that array, to see if any entities where inside the camera view, and if they where draw them.

Seems reasonable.
 

However, this will become taxing to do if...

Do I detect a hint of premature optimization? smile.png
 

...if there is a large amount of units and/or players (enemy), as it would have to sort through the hundreds(ish) of times...

Hundreds doesn't sound bad at all. It's a simple collision: Does sprite rect collide with camera rect? 3D games do way more advanced collision than that - it shouldn't be too slow.
 

...it would have to sort through the hundreds(ish) of times a second.

If it does become a slowdown (when testing in release mode and after profiling, ofcourse), you could make it not check every entity every frame. Batch them - do 1/3rd of the checks one frame, the second 1/3rd the next frame, do the final 1/3rd the third frame.

 

An every simpler solution would be to just draw the 100-ish sprites continually. Seriously, 100 sprites should render very quickly. A single 3D model can be 100,000 polygons or more. 100 or even 1000 sprites shouldn't pose too much of a problem.


Edited by Servant of the Lord, 14 July 2013 - 04:07 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#4 dsm1891   Crossbones+   -  Reputation: 1309

Like
0Likes
Like

Posted 14 July 2013 - 04:16 PM

 

Hi thanks for your reply, Ill take it on board. You are correct in some areas, and Ill defiantly think about what you said, however...

 

Most of the time the entities will be doing X,Y or Z off screen, for instance say an enemy is taking  1 damage every two seconds, I will still need to update him and or his AI. therefore simply deleting entities cant be done(?). Any entities that are not onscreen are simply (prob not the right term but) Mathematical, then when the camera rolls around they have a sprite ect. ect. 

 

I don't want to be drawing an entity that isn't visible (whats the point right?), but say there is 200 entities simply polling each one "are you in the camera view?" or "are you active?" every time I render the scene will be a major bottle neck in my game. I guess I was really asking for a better way of doing that.

 

Sorry for any misunderstanding.



#5 dsm1891   Crossbones+   -  Reputation: 1309

Like
0Likes
Like

Posted 14 July 2013 - 04:21 PM

 

Thanks for the reply, Very helpful.

 

I guess im one of those people who, doesn't want to bottle neck the system (AT ALL) :)

 

But seriously thank you about batching the process, once you said it, I remembered an article I read a while ago thinking, "oh Ill have to do that if [this problem] becomes an issue"

 

Cheers!!



#6 markr   Crossbones+   -  Reputation: 1653

Like
0Likes
Like

Posted 15 July 2013 - 02:51 AM

@dsm1891:

 

You don't need to poll the "inactive" entities in case they need to become active. You can just attach them to block-based lists and only activate the ones which are coming close to the player.

 

You do need to poll the active entities to find out whether they can become inactive, however, you'd need to do this anyway.

 

In the case of something "important" such as a "boss" enemy, you might want to consider them to be always active (until dead, anyway), they will chase the player "to the ends of the earth", right?

 

Other monsters can go inactive after a while because while the player is busy in the town checking out the market prices, your game doesn't want to keep updating 1000 skeletons in a dungeon somewhere which can't possibly reach the player anyway.



#7 PunCrathod   Members   -  Reputation: 278

Like
0Likes
Like

Posted 15 July 2013 - 06:18 AM

I don't want to be drawing an entity that isn't visible (whats the point right?), but say there is 200 entities simply polling each one "are you in the camera view?" or "are you active?" every time I render the scene will be a major bottle neck in my game. I guess I was really asking for a better way of doing that.

Depends on what kind of a system you are targeting. If you are targeting modern x64 pc with a processor clocked atleast 2ghz you really can't bottleneck the game with an if(unit_x<screenrightborder_x+unitsize&&unit_x>screenleftborder_x-unitsize&&unit_y<screentopborder_y+unitsize&&unit_y>screenbottomborder_y-unitsize) (note border orders may wary depenging on your cordinate system) when your unit count is less than thousands. Infact you can't really optimize it any better than that without falling into the premature optimization whirlpool because you need your untis to "mathematically" be there anyway.

Do you use immidieate mode(drawing each sprite separetely) or are you constructing a vertex buffer object/s to draw your scene? If your target system can support using VBOs then you propably should use them. For example you only would need to construct a VBO for the whole tilemap once at the start and again only if the tilemap changes. Then draw the whole tilemap with a single draw command and let the GPU do the culling.

I am somewhat puzzled over these other guys who keep talking about enemies and bosses and whatnot being close to the player. Last time I checked RTS was for realtime strategy and there were no players in the game. The player was a disembodied viewport in the sky giving orders to all sorts of units. But maeby the RTS genre has changed since five minutes ago.

Long story short. If the game is to be played with a desktop pc or a laptop with under a thousand units you don't need anything more fancier that just checking if the units are on the screen. It'll give you all the optimization you need.

#8 dsm1891   Crossbones+   -  Reputation: 1309

Like
0Likes
Like

Posted 15 July 2013 - 10:13 AM

 

I don't want to be drawing an entity that isn't visible (whats the point right?), but say there is 200 entities simply&nbsp;polling each one "are you in the camera view?" or "are you active?" every time I render the scene&nbsp;will be a major bottle neck in my game. I guess I was really asking for a better way of doing that.

Depends on what kind of a system you are targeting. If you are targeting modern x64 pc with a processor clocked atleast 2ghz you really can't bottleneck the game with an if(unit_x<screenrightborder_x+unitsize&&unit_x>screenleftborder_x-unitsize&&unit_y<screentopborder_y+unitsize&&unit_y>screenbottomborder_y-unitsize) (note border orders may wary depenging on your cordinate system) when your unit count is less than thousands. Infact you can't really optimize it any better than that without falling into the premature optimization whirlpool because you need your untis to "mathematically" be there anyway.

Do you use immidieate mode(drawing each sprite separetely) or are you constructing a vertex buffer object/s to draw your scene? If your target system can support using VBOs then you propably should use them. For example you only would need to construct a VBO for the whole tilemap once at the start and again only if the tilemap changes. Then draw the whole tilemap with a single draw command and let the GPU do the culling.

I am somewhat puzzled over these other guys who keep talking about enemies and bosses and whatnot being close to the player. Last time I checked RTS was for realtime strategy and there were no players in the game. The player was a disembodied viewport in the sky giving orders to all sorts of units. But maeby the RTS genre has changed since five minutes ago.

Long story short. If the game is to be played with a desktop pc or a laptop with under a thousand units you don't need anything more fancier that just checking if the units are on the screen. It'll give you all the optimization you need.

 

Hey,

 

Thanks, ill defenitly look into vertex buffers :)

 

And im not sure, but they could be referring to an RPG, even so, the techniques can be transferred in some instances

 

Thanks a lot



#9 kalle_h   Members   -  Reputation: 1394

Like
0Likes
Like

Posted 15 July 2013 - 11:35 AM

Frustum culling simple bounding boxes is really fast. I even use SIMD optimized sphere vs frustum culling for all my particles(thousands per frame) and this is for mobile game that is running 60fps. Read what DICE did with Battlefield 3. They ditched complex hierarchy based culling and started to use bruteforce algorithm instead and they gained a lot of performance. http://dice.se/wp-content/uploads/CullingTheBattlefield.pdf






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS