My coding project, part VII

After a long break

My pygame project has advanced more than you could guess by the amount of posts about it. Mostly I've been fooling around with the background stuff, not much of what I've done will be directly visible to the user. Then again, if you look at the previous post, quite a bit has changed.

The last time we got to a part where the game world and its sectors were created and a map based on that was shown to the user. At this point there's absolutely nothing to play so I refuse to call it a "player". The map could be opened and closed and the game could be (un)paused. Basic stuff but nothing spectacular.

Next steps

In the first iteration of my project the game's view was fixed and the ship flew around freely. The first thing I had to do was to attach the viewport to the ship. So the ship would always be in the center and the viewport would scroll around the sector, following it. Because the sector would always be (much) bigger than the viewport, there was no sense in rendering objects that weren't inside the viewport's area. Therefore the sector would need a data structure for its gameobjects that would give all the necessary information to achieve this.

QuadTree

The idea of a QuadTree is that whenever a single cell's capacity is used up, it subdivides into four subcells where the objects will be redistributed. And so on and so on until the maximum depth of the tree is reached. No explanation I give can be better than the existing ones so you can read more from wikipedia, for example.
The necessary explanation is that I implemented my own version (or a part of it) of a QuadTree. At this point, when its mere existence is enough, all the sector's contents is inserted into the qtree. The aforementioned need of finding all the gameobjects inside the viewport was the first real use case. Because the sectors are squares, all my gameobjects are basically squares and all the quadtree cells are squares, everything can be solved with pygame's colliderect methods.

def get_contained_objects(self, rectangle):
  contained_objects = []
  if self.gameobjects:
    for gameobject in self.gameobjects:
      if rectangle.colliderect(gameobject.get_rect()):
        contained_objects.append(gameobject)
      if self.top_left:
        contained_objects.extend(self.top_left.get_contained_objects(rectangle))
        contained_objects.extend(self.top_right.get_contained_objects(rectangle))
        contained_objects.extend(self.bottom_right.get_contained_objects(rectangle))
        contained_objects.extend(self.bottom_left.get_contained_objects(rectangle))
  return contained_objects

What's most important in the code above is the rectangle parameter, which is the surface area of the viewport. That viewport is calculated around the centerpoint of player's ship. While working on that also the offset of the ship from the sector's 0,0 point is calculated. That offset is needed to render all the other gameobjects related to the ship.

Maybe (most likely, even) I explained it a bit funnily, but what can I do. Solving this small set of problems took a few evenings and sessions. I was pretty proud when I finally got it working properly. My biggest problem had been that I thought of it way too complicatedly - yet again.

Return of the GameObjects

Of course I needed something to be rendered on the screen, so that I could check the basic functionality of my QuadTree. In  the beginning I had those three subspace pirate ships I mentioned a related post or three ago. In addition to those I wanted to return the Asteroids back to the screen as well, but better than the last time. While I was on it, I'd test the insert and division methods of the tree with some randomly generated content.

My old asteroid code was almost directly transferrable. Mostly I added some more randomness to the init. Based on a 2d6 toss, a result between 9-12 spawns an ice asteroid, otherwise a rock asteroid. Anohter 2d6 decides the size with the old familiar small / medium / large / enormous options. The material affects both the color, the randomized mass and the rotation speed. Those asteroids that consist of rock are both heavier and slower than the icy ones.