Hey guys,

Been a long time since I've posted here, as life had gotten in the way. But I decided to throw some things aside and resume creating a game I was working on a while ago. I know this question has been asked many time, but I can't quite seem to find an answer that fits my question.

So I been wondering how to break up my game field, I'm currently using a grid which works quite well. But it doesn't help so much in intense areas of combat. I have my grid setup in a way that each section is 500x500 pixels large and 200x200 sections. So this means I end up with a map that is 100,000x100,000 pixels big. And it oddly works pretty well. But once an area of 500x500 ends up with a lot of objects in it, due to how combat is designed, it can get a little sluggish. Which is making me wonder if I should use a quadtree instead, but here is the problem:

Majority of the actors/units/structures/projectiles are say 5x5 to 50x50 pixels big. But then I have larger moving items that go up to 1000x1000~ pixels big. So in my Grid based collision for the the larger objects, I calculate the top left, right, bottom left, right, center and the top, bottom, left and right middle. So I can fit them into multiple grid sections so they don't skip out on collision. Now that works fine, except when I have say 500 objects in a single grid, (I sort the items so I do less collision, etc target vs player bullets only) it'll start to drag the framerate down. So this is what made me think a quad tree may be a better implementation as I'll be able to have much smaller sectors to do collision in.

Now the problem with a quadtree which I see is, how do I place the much larger objects into these smaller sections/leafs of a quad tree, so they don't get skipped out?

And the other issue is with my grid, is: a lot of the time majority of the grids end up being empty, due to the combat taking place in only 16~ grid sections at once. So it leaves me with a lot of empty grid sections, or a fair few (100~ish) with only 2 - 10 objects etc. Also there are no stationary objects, the whole world is always moving. (What I have currently does work and does what I want, I just want it even faster so I can add more items to the world while lowering collision).

So I would greatly appreciate anyone's thought on what sort of structure I could use instead, or point me to an example that does what I want, in a fairly optimized way.

Cheers,

Scott :)

First of all, make sure that it is the collision that is dragging down the framerate and not the rendering. Do all of the 500 objects each trigger a separate draw call?

As for the quad tree, one implementation I have seen treats all nodes as leaf nodes. To insert an object into a node you first get the object's bounding box.

def insertIntoNode(node, object):
  foundChild = False
  for child in node.children:
    if child.boundingBox.contains(object.boundingBox):
      insertIntoNode(child, object)
      foundChild = True
      break

  if not foundChild:
    node.objects.add(object)
    object.currentIndexNode = node

Then to update an object

def updateObject(node, object):

  if not node.boundingBox.contains(object.boundingBox) && node.parent:
    updateObject(node.parent, object)
  else:
    foundChild = False

    for child in node.children:
      if (child.boundingBox.contains(object.boundingBox)):
        updateObject(child, object)
        foundChild = True
        break
    
    if not foundChild:
      if object.currentIndexNode != node:
        node.objects.add(object)
        object.currentIndexNode.objects.remove(object)
        object.currentIndexNode  = node

The tradeoff is you don't have to insert one object into many nodes but it does increase the number of objects to check around node boundaries. The worst case is all the objects are in the center of the spacial index since all the objects would be in the same spacial node.

Also note the psuedo code I gave above doesn't handle splitting nodes when they get to full or combining them if the children empty out.

Thanks for the reply Happycoder.

Do you think it might be wise to build the above into a grid sector, but only the ones that have over 100 objects each update etc. So that way I can break down a grid sector into smaller leafs/sections. Or would something like this be unwise, due to running the grid like normal with multiple quad trees technically happening? Or should I possibly just add a smaller grid into each grid sector, for the more populated ones? If any of that makes sense.

Thanks

(Also I know it has nothing to do with my drawing calls)

For the time being, I just cut down the size of the gamearea, and increased the grid sectors. Which has fixed the issue for now, but in time when I want to increase the map size I might have to take a different approach. Or just load in the grid I'm in, plus the ones in a radius around me etc. If anyone has any thoughts or comments on the design though, I would love to hear them :)

Hi. Why is the size of the grid slowing you down. Are you doing searches on the grid from grid cell 0, 0 to max cell all the time or something. Normally you use indexes on grid cells. How do you get the render object from grid. Did you know you can break the screen into 2 triangles and use a 2d triangle raster to get cells that are in the screen area. This way you don't need to search all cells for visible objects. I say this because the grid is the faster way due to the use of calculated indexes.

Hi. Why is the size of the grid slowing you down. Are you doing searches on the grid from grid cell 0, 0 to max cell all the time or something. Normally you use indexes on grid cells. How do you get the render object from grid. Did you know you can break the screen into 2 triangles and use a 2d triangle raster to get cells that are in the screen area. This way you don't need to search all cells for visible objects. I say this because the grid is the faster way due to the use of calculated indexes.

My grid works fine, it's indexed and only uses/displays the cells that are on the screen. The issue was more about having 500 objects in a cell (stress testing), and getting a framerate drop. So I just decided to decrease the size of a cell, which in turn removed the collision lag. It is why I was wondering if I should of used a quadtree inside of each cell etc.