I have a 2D tile based game with dynamic entities and am wondering how I should group the different types of entities I have. I want to use frustum culling to limit the number of draw calls, however I don’t want to check every single tile every frame. The same goes for my dynamic entities. I’ve decided that a quadtree is probably best for the enemies and such since they move around so much, however I’ve heard quadtrees are inefficient on modern day CPUs. Obviously, quadtrees would not be used to group together static tiles either. So my question is; what should I use to group the two types of entities I have?
You can create a grid for all the static tiles. You can use any other method for dynamic entities depending on their count.
What do you mean any other method? Like a quadtree?
For a tile based game you really only need to worry about the X and Y coordinate (or X and Z if it’s an isometric game) which simplifies the task a bit. I think a quad-tree would be over-kill for a tile-based game anyway.
The way I do it (and it might be over-simplifying things - but it is easy to refactor if it begins causing performance issues) is simply have a series of ‘sectors.’ Each sector would be about 20x20 (or 40x40) - really it can be any dimension - obviously you also have to consider that if you are on corners of a sector that is adjacent to three other sectors you are now looking at processing 4 times your sector dimensions - which isn’t that bad because you can perform the extra culling quite cheaply to determine which tiles are worth rendering of those sectors.
Each layer contains these sectors that are stored in a List. For convenience (and speed) there is another inner private class that is a very simple primitive 2D vector (nothing compared to your main game’s Math vector - i.e it doesn’t implement dot product or really anything - all it implements is the x\y public members (you really don’t even need getters\setters.) This vector class overrides the equals method so that you can use it as an index into your list of sectors. The idea is that it compares with these sectors to test if the coordinates of the vector fall within the sector - you can index through your list of sectors like this.
Finally, when objects\tiles are created or when they move, they note when they’ve switched tile ownership - the tile they own is their tile-coordinate (their world coordinates rounded to the nearest tile) - you might already have this implemented for tile picking\collision whatever if you do that on a per-tile level. When they’ve transferred ownership they inform the world and the world moves them to the appropriate sectors by looking up their coordinate in the arrays of sectors.
The idea is that your sectors are created on a demand basis. So you get an X\Y coordinate, you index through your list of sectors using that X\Y coordinate as an index, if you list doesn’t contain a sector for that coordinate you create one that contains the point and add that point to the sector.
Then when it comes time to render (and you know the tile bounds you need to render) you simply just pick up the appropriate sectors contained within that area and iterate through each entity contained in them (first doing standard culling to assure you aren’t wasting CPU time on a draw call)
In the book “Developing Games in Java”, David Brackeen, the author uses a tilemap for static tiles and uses brute-force for dynamic entities in that map. The game is a platform game said in Chapter 5 of the book.
If you had a lot of dynamic entities, you can use a grid or quadtree for them but keep using the tilemap for the static tiles.