• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
dsm1891

Culling 'not on screen' Entites

8 posts in this topic

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! :)

0

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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 [i]too much[/i] of a problem.

Edited by Servant of the Lord
1

Share this post


Link to post
Share on other sites

 

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.

0

Share this post


Link to post
Share on other sites

 

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!!

0

Share this post


Link to post
Share on other sites

@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.

0

Share this post


Link to post
Share on other sites

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.
0

Share this post


Link to post
Share on other sites

 

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

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0