Jump to content
  • Advertisement
Sign in to follow this  

Frustum culling/space partitioning in a RTS game

This topic is 3663 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm working on a simple real time strategy game. I've come to the point where it's not viable to draw the whole scene to the buffer anymore, I really need to start not-rendering the parts that cannot be seen. I've implemented octrees and quadtrees before in simple situations, but I'm not sure this is the best way to go for a strategy game. Since in a typical RTS the view direction is pretty limited (isometric perspective, but not at a fixed rotation in this case), I think I can settle for something a little less overkill. As far as I can see, at least quadtrees will be more suitable than octrees. Since height differences in RTS games are usually relatively small, I think I can ignore this component and do 2.5D partitioning, meaning I just give each 'quad' a constant height (max height - min height of the world). But even quadtrees don't seem to be 'simple' enough. Basically the map consists of a heightmap, and a number of objects on it (foliage, rocks, etc.). All the buildings (except for maybe a few that are already added to the scenario) are placed by the players and their location can therefore not be known in advance. Units will be moving around and will probably need a seperate mechanism for culling anyway. So the property of quadtrees, that the leaf nodes are (partially) determined by the amount of polygons they hold, does not seem to help here a lot. So the best I can think of is to just divide the terrain into a number of (2.5D) regions with fixed size, and only draw those regions that are (partially) in view. Each region should probably have references to the regions around it (max. 8). These references can be used to easily look up the neighbouring regions, and also to place dynamic objects like units in the right region when they move over the borders of the one they are currently in. This then only leaves me with the cases where a unit is actually on the border of a region, where the old region isn't currently in view but the new one is (and the border is as well), in which case the unit might not be drawn although it is partially in view. These cases will not happen often though since the camera needs to be positioned in a way that on a border of the screen there is also a region border, and exactly at that place a unit would be crossing over. It might be more of a problem when a building is placed on an edge though, since it will remain there. I guess one thing that can be done is just put the object in both regions, and give it an 'already rendered this frame' flag. Is there a better way to do this for a strategy game? Am I missing something? And what is the logical place for the structure that divides up the game world? For now I've only been talking about terrain since it logically determines the bounds of the game world in this type of game, but the space partitioning structure should probably live outside the terrain class. The way I see it now, the best thing to do is something like this. Each object in my game that can be drawn is derived from a DrawableObject class, to ensure it has the needed properties when it's passed to the renderer. I think the best thing to do is set a terrain size, so I know the bounds, pass these bounds to the space partitioning structure and let it create a number of regions, then pass these regions back somehow to the terrain and use that info to create one DrawableObject (containing a vertex/index buffer of terrain) for each region. I have one question regarding vertex/index buffers on this point: Can I just make 1 big vertex buffer containing all the vertices of the whole terrain, and create seperate index buffers for each region, or do I have to create seperate vertex buffers for each region as well? Because the latter introduces some big problems for me... Now that I have a set of regions and landscape in each region, I can just place buildings and units in the correct region when they spawn. Units could do a check after movement to see if they crossed region borders, and be reinserted in a neighbouring region. When drawing the scene, I just give the renderer the regions, the camera frustum, and calculate what can be seen. All DrawableObjects from the regions that are visible can then be passed to the renderer to be drawn. Please let me know if there's a better way to do this, or if you foresee any problems with the described approach. Thanks a lot for any feedback.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!