Object Management

[a327ex]

In this post I will detail the way I currently handle object management for my games. The main idea for how I handle this is loosely based on the concept of spaces detailed in this video:

The main concept is a Group, which is equivalent to a Space. This Group object will simply have a list of objects and then update and draw them when those functions are called:

Group = Object:extend()

function Group:new()
  self.objects = {}
end

function Group:update(dt)
  for _, object in ipairs(self.objects) do
    object:update(dt)
  end
end

function Group:draw()
  for _, object in ipairs(self.objects) do
    object:draw()
  end
end

This assumes each object has update and draw functions defined. Additionally, there needs to be a way of automatically removing objects that are dead. The way I do this is by checking for a .dead attribute:

function Group:update(dt)
  for _, object in ipairs(self.objects) do
    object:update(dt)
  end

  for i = #self.objects, 1, -1 do
    if self.objects[i].dead then
      table.remove(self.objects, i)
    end
  end
end

Finally, we also need a way to add objects to the group:

function Group:add(object)
  object.group = self
  table.insert(self.objects, object)
end

We also set the object's .group attribute to point to the current group because a lot of the times it's useful to be able to refer from the object's code to the group it belongs to (i.e. when you need to grab nearby objects, for instance).

This simple setup can get you very very far. At a level higher than this Group object we need somewhere to instantiate it. The way I do it by instantiating it in my State objects (similar conceptually to FlxState), which are just normal objects used to hold groups and other objects and to coordinate between them. MainMenu or OptionsMenu or Arena would be examples of these kinds of states. In the picture below is an example with the constructor for a MainMenu class:

Here a group is created for UI objects and they're added to it. Then the update and draw functions (not shown) call the group's update and draw functions as well. I will leave the details of these State-like objects for another article, I just wanted to give you some context of how these groups are used.

For now I'll focus on explaining some more useful functionalities to add to our Group class. The first thing is being able to get objects by their unique identifier. First, objects need to be stored somewhere by their .id attribute, and we'll do this in objects.by_id, where the keys will be ids and the values will be references to objects:

function Group:new()
  self.objects = {}
  self.objects.by_id = {}
end

function Group:add(object)
  object.group = self
  self.objects.by_id[object.id] = object
  table.insert(self.objects, object)
end

This assumes each object has an unique .id attribute. Now if we have an object's id we can easily get it by just accessing the objects.by_id table:

function Group:get_object_by_id(id)
  return self.object.by_id[id]
end

Finally, we also need to take care that when we remove an object due to its .dead attribute, we also remove it from the .by_id table, since if we have multiple references of the same object but we forget to remove some of them, the object will never get garbage collected, which will lead to memory leaks in your game.

function Group:update(dt)
  for _, object in ipairs(self.objects) do
    object:update(dt)
  end

  for i = #self.objects, 1, -1 do
    if self.objects[i].dead then
      self.objects.by_id[self.objects[i].id] = nil
      table.remove(self.objects, i)
    end
  end
end

Another improvement we can make to Groups is being able to get objects by their class. This might not be as easily achievable in languages other than Lua, but this is how I do it. Similarly to how we did for identifiers, we also create an additional .by_class table, add objects to it, remove objects from it, and create a get_objects_by_class function:

function Group:new()
  self.objects = {}
  self.objects.by_id = {}
  self.objects.by_class = {}
end

function Group:add(object)
  object.group = self
  self.objects.by_id[object.id] = object
  if not self.objects.by_class[object.class] then self.objects.by_class[object.class] = {} end
  table.insert(self.objects.by_class[object.class], object)
  table.insert(self.objects, object)
end

function Group:update(dt)
  for _, object in ipairs(self.objects) do
    object:update(dt)
  end

  for i = #self.objects, 1, -1 do
    if self.objects[i].dead then
      self.objects.by_id[self.objects[i].id] = nil
      for j, object in ipairs(self.objects.by_class[self.objects[i].class]) do
        if object.id == self.objects[i].id then
          table.remove(self.objects.by_class[self.objects[i].class], j)
          break
        end
      end
      table.remove(self.objects, i)
    end
  end
end

function Group:get_objects_by_class(class)
  return self.objects.by_class[class] or {}
end

Each object has a .class attribute which holds a reference to its class, and then we use that as keys in new tables which will hold instances of that class. Like with the .by_id table, this is just another way of holding objects for easy retrieval because often times you want to get all objects of a certain class to do some operation.

Finally, the last thing I'll focus on in this post is retrieving objects by location. Often times we want to retrieve objects in a certain area, and one very useful setup is dividing objects by buckets and then querying those buckets. This speeds up queries because instead of going through all objects and doing intersection calculations on all of them, we go through all buckets instead and only add the objects that are within buckets that collide with our area. This is a very simple exchange of memory for speed, which is also what we're doing with the .by_id and .by_class attributes.

First, we'll create the table that represents these buckets:

function Group:new()
  self.objects = {}
  self.objects.by_id = {}
  self.objects.by_class = {}
  self.cells = {}
  self.cell_size = 128
  return self
end

Here .cells will hold buckets, and .cell_size represents the size (width and height) of each bucket. So this means that the entire world will get divided into chunks of 128x128 units and all objects will be inside their own respective buckets. This recalculation will happen every frame, which seems wasteful but it's less wasteful than the alternative of looping through all objects for all objects that need to query for nearby objects every frame.

function Group:update(dt)
  for _, object in ipairs(self.objects) do object:update(dt) end

  self.cells = {}
  for _, object in ipairs(self.objects) do
    local cx, cy = math.floor(object.x/self.cell_size), math.floor(object.y/self.cell_size)
    if not self.cells[cx] = then self.cells[cx] = {} end
    if not self.cells[cx][cy] then self.cells[cx][cy] = {} end
    table.insert(self.cells[cx][cy], object)
  end
end

So here we're creating a new .cells table every frame then going through every object and adding it to its respective bucket by dividing its position by .cell_size. As an example of one function that might query this .cells table:

function Group:get_objects_in_rectangle(x, y, w, h)
  local out = {}
  local cx1, cy1 = math.floor((x-w)/self.cell_size), math.floor((y-h)/self.cell_size)
  local cx2, cy2 = math.floor((x+w)/self.cell_size), math.floor((y+h)/self.cell_size)
  for i = cx1, cx2 do
    for j = cy1, cy2 do
      local cx, cy = i, j
      if self.cells[cx] then
        local cell_objects = self.cells[cx][cy]
        if cell_objects then
          for _, object in ipairs(cell_objects) do
            if math.is_rectangle_in_rectangle(object.x, object.y, object.w, object.h, x, y, w, h) then
              table.insert(out, object)
            end
          end
        end
      end
    end
  end
  return out
end

This function gets all objects inside the specified rectangle. Instead of going through all objects we go through nearby bucket indexes (defined by cx1, cy1 top-left and cx2, cy2 bottom-right boundaries) instead, and then through the objects inside each bucket, checking to see if the object is colliding with the area we're querying. Also worth noting that this assumes all objects have .w and .h attributes.

This provides a pretty good base for managing objects in our games in a way that's fairly reusable but also simple. I intend on writing more articles exploring more aspects of game programming and in them I will expand on this Group class as necessary, but for now this covers the basics!