The Monkey Project

Python Game Development News

Archive for the ‘Techniques’ Category

Introduction to Spatial Hashes

with one comment

One of the things that bites the beginner games programmer earliest is that detecting intersections between objects can get slow very quickly.

For example, say there are 100 actors in a level – I use actor to mean an object that interacts or moves as separate from scenery objects or tile maps. Which ones are colliding with which other ones? A naive answer requires around 5,000 tests per frame. This gets dramatically worse as the number of actors increases – 20,000 tests for 200 objects, 45,000 for 300 objects, and so on (it is O(n²) for asymptotic complexity fans – but you already knew that).

Fortunately there are well-established techniques for making this process faster: indexes. If you are familiar with databases, the principle is exactly the same. As well as maintaining the positions of the objects, we maintain a datastructure that lets you quickly narrow down the set of objects you’re interested in.

It’s difficult to actually narrow down the set of objects to those that really are intersecting, but we can narrow it down to a much smaller set that potentially intersect. In collision detection, this is called the broad phase. Having rapidly retrieved that narrowed down collection, we can more quickly scan for objects that are really intersecting. Unsurprisingly, the latter operation is called the narrow phase.

A spatial hash is one way of indexing objects in space. As Python programmers, we should perhaps call them spatial dicts, but let’s go with the literature on this one. Like a dict, a spatial hash has O(1) properties.

The basic principle is to split space into an infinite number of cells – each cell can contain an arbitrary number of objects. A cell that is empty simply isn’t stored. In Python, this is just a dict, where the keys are the coordinates of the cell in space, and the values are collections of objects. Let’s briefly look at an implementation and how we populate it:

class SpatialHash(object):
    def __init__(self, cell_size=10.0):
        self.cell_size = float(cell_size)
        self.d = {}

    def _add(self, cell_coord, o):
        """Add the object o to the cell at cell_coord."""
        try:
            self.d.setdefault(cell_coord, set()).add(o)
        except KeyError:
            self.d[cell_coord] = set((o,))

    def _cells_for_rect(self, r):
        """Return a set of the cells into which r extends."""
        cells = set()
        cy = floor(r.y1 / self.cell_size)
        while (cy * self.cell_size) <= r.y2:
            cx = floor(r.x1 / self.cell_size)
            while (cx * self.cell_size) <= r.x2:
                cells.add((int(cx), int(cy)))
                cx += 1.0
            cy += 1.0
        return cells

    def add_rect(self, r, obj):
        """Add an object obj with bounds r."""
        cells = self._cells_for_rect(r)
        for c in cells:
            self._add(c, obj)

So this is easy – each object extends into one or more cells. To add the object to the spatial hash, we just add it to the dictionary with each cell coordinate as a key. A set to conatin the objects in each cell is created if it doesn’t exist.

Removing an object is just the reverse process:

    def _remove(self, cell_coord, o):
        """Remove the object o from the cell at cell_coord."""
        cell = self.d[cell_coord]
        cell.remove(o)

        # Delete the cell from the hash if it is empty.
        if not cell:
            del(self.d[cell_coord])

    def remove_rect(self, r, obj):
        """Remove an object obj which had bounds r."""
        cells = self._cells_for_rect(r)
        for c in cells:
            self._remove(c, obj)

Then testing for a potential set of objects with a single object is just this:

    def potential_collisions(self, r, obj):
        """Get a set of all objects that potentially intersect obj."""
        cells = self._cells_for_rect(r)
        potentials = set()
        for c in cells:
            potentials.update(self.d.get(c, set()))
        potentials.discard(obj) # obj cannot intersect itself
        return potentials

Testing for all potential collision pairs is also relatively easy – we’d loop through the keys of the spatial hash collecting all combinations of the objects in a cell wherever there are 2 or more objects in that cell.

Another use is in viewport culling – a spatial hash would let you easily retrieve a potentially visible set (PVS) of objects.

The asymptotic lookup complexity of O(1) for insertion, deletion, lookup, etc makes spatial hashes seem faster than they really is. In reality, a well-implemented quadtree – lookup complexity O(log n) – would typically perform faster until the space gets vast. This is because hashing is slow and trees are fast. But spatial hashes are easy to implement, especially in Python. A drawback is the need to tune the cell size. The performance of spatial hashing will suffer if moving objects cover too many cells or there are too many objects per cell. Cells should be a reasonable match for the sizes of objects in them.

The full code for this spatial hash is available, but this implementation is for reference and no doubt faster, more fully featured implementations are available.

Written by mauve

May 18, 2011 at 12:00 pm

Posted in Techniques

Strategy Pattern for AI

leave a comment »

Creating realistic computer opponents in many games approaches more of an art form than a science. In puzzle games we can sometimes analyse the game to determine how best to play, perhaps capping the depth the AI will search for solutions to reduce its difficulty as an opponent. But how do we create a sophisticated opponent in less mechanical games?

Strategies

A method I’ve used before involves the AI selecting between a number of competing strategies (in the design pattern sense less than in the “game plan” sense).

It is usually possible to describe a variety of different strategies for an AI player. Just some might be:

  • Patrol
  • Watch
  • Raise the alarm
  • Take Cover
  • Pursue
  • Snipe
  • Camp
  • Flank
  • Firing
  • Blind-firing

Even games like driving games might have AI strategies, to the extent that drivers can be said to be driving aggressively or defensively. Perhaps if the car is damaged, they might drive gingerly and seek out the pit lane.

Each strategy is intended to be simple, mechanistic, and easy to code. Strategies mustn’t require a big timeslice to constantly re-evaluate the situation, because we want many AIs can be run at the same time. The “strategy” an AI has adopted may control many aspects of its behaviour – invariably the actions it takes, but perhaps also what animations are shown and what phrases it says.

Note that activities like pathfinding and puzzle-solving aren’t strategies – though some strategies might invoke these methods.

Choosing which strategy to adopt

Some strategies – running to a point, for example – eventually finish, and the AI would then select a suitable successor strategy or reconsider.

However every so often the strategy in use is reconsidered anyway, based on new tactical information – for example, the player hides or takes cover or climbs a tree. This can be infrequent because players will interpret any latency in reacting to the tactical situation as a human quality of reaction time (immediate reaction in a computer opponent is jarringly unnatural). An enemy that is alert may react sooner than an enemy that is taken by surprise.

It is important that strategies do not change willy-nilly. There must either be no tactical information or new tactical information for a new state to be selected, otherwise an AI that has been running in for the kill might appear bizarrely to stop and camp.

Ideally strategies will be sophisticated in their own right – something I dislike in computer games is where an enemy “patrols” by walking to a point then stopping, looking around, walking back, stopping, looking around, repeat. In real life people ordered to patrol are much less deterministic than this. They might sit in a good spot most of the time and occasionally take a random wander. They might look around and behind themselves more often rather than vacantly. So these strategies might be more granular – a guard who is in general patrolling might actually have several patrolling strategies that he swaps between.

An enhancement might be for nearby AI characters to introspect the strategies of those near them, or call out the strategies they are adopting, and adapt their choice of strategy accordingly. This would allow groups of AIs to work together.

Example Code

This technique was used in my Pyweek 10 game, Bamboo Warrior – the code for this is in aicontroller.py if you’d like to see an example (Warning – this is Pyweek code and is not as clear as it could be).

Written by mauve

May 12, 2011 at 12:00 pm

Posted in Techniques

Screenshot Code

with 2 comments

If you want people to look at your game, screenshots are what most pique people’s attention.

It’s sometimes possible to take screenshots using a generic screen grab tool, but that’s not always the case, and it’s not always quick and easy. It’s best to set up a specific key you can press to take screenshots quickly and easily (I invariably use F12).

Fortunately doing this from Python code is pretty formulaic.

Pygame

Pygame can directly save a surface as an image. The code to do this just needs to be dropped into your event handling.


import datetime
import pygame

def screenshot_path():
    return datetime.datetime.now().strftime('screenshot_%Y-%m-%d_%H:%M:%S.%f.png')

...

# in your event loop
if event.type == KEYDOWN:
    if event.key == K_F12:
        pygame.image.save(screen_surface, screenshot_path())


Pyglet

In OpenGL, you have to read back the colour buffer to an image and save that. As you generally don’t want the colour buffer’s alpha channel to be saved if it has one, there are a couple of OpenGL calls to force every pixel to be read as opaque. Pyglet can handle reading and saving the colour buffer though.


import datetime
from pyglet import gl
from pyglet.window import key

def screenshot_path():
    return datetime.datetime.now().strftime('screenshot_%Y-%m-%d_%H:%M:%S.%f.png')

...

def on_key_press(symbol, modifiers):
    """This is your registered on_key_press handler.

    window is the pyglet.window.Window object to grab.
    """
    if symbol == key.F12:
        gl.glPixelTransferf(gl.GL_ALPHA_BIAS, 1.0)  # don't transfer alpha channel
        image = pyglet.image.ColorBufferImage(0, 0, window.width, window.height)
        image.save(screenshot_path())
        gl.glPixelTransferf(gl.GL_ALPHA_BIAS, 0.0)  # restore alpha channel transfer

Written by mauve

May 4, 2011 at 4:00 pm

Posted in Techniques