Introduction to Spatial Hashes

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.

Review: Ardentryst

There aren’t many Python games that achieve the production values present in Ardentryst by Jordan Trudgett and friends. The game is visually and acoustically lush.

Ardentryst is a platformer/RPG set in a magical fantasy world. Each level is a platform game where players fight monsters with weapons or spells. There is also a world map that lets you select levels, and shops where you can sell the loot you’ve collected and buy better stuff.

The gameplay, combat and the chests and loot you are rewarded with are pitched perfectly, but what makes the game so impressive is the volume of content. As well as fully animated characters and beautiful backgrounds and art, the game is accompanied throughout by enchanting music.

The technical effects are also impressive. I counted up to 4 layers of parallax backgrounds and foregrounds in some places. There are some accomplished particle effects including fireballs with a heat-haze and Nyx’s icy breath and the flurries of snow in the screenshot below.

It’s possible to upload your character scores and levels to the global high-score table. Astonishingly there are only 174 scores on the table at the time of writing. If you do play, be sure to upload a score!

The game is fully featured but sadly rather short. The last release was in July 2009; Jordan has since abandoned it to work on a completely new version. Ardentryst is 100% Python and Pygame and licensed under the GPL, so more content could be created if anyone was interest in doing so.

Interview: Christopher Night of Team Multiverse Factory

Christopher Night, aka Cosmologicon, was the director and producer on the Team Multiverse Factory entry for Pyweek 12, Fractured Soul, which placed second in the team competition. Christopher has also had two previous Pyweek winners in the individual competition, Mortimer the Lepidopterist in Pyweek 11, and Panspermia, in Pyweek 8.

What inspires you/drives you to make games using Python?

This is probably different for me than for most people. I don’t like using libraries or frameworks. I’ve made about 10 solo games in Python now, and I’ve never used anything beyond Pygame, PyOpenGL, and NumPy. What I like about Python is its highly expressive syntax and powerful standard library. Game development in, say, C++ is mature enough that everyone has a complicated framework they like, so there’s little attention paid to development without one. Whereas with Python, I feel like you can jump right in.

Pyweek also has a lot to do with it. I like Pyweek a lot. The scope and community are just about right for me. I originally learned Python in order to compete in Pyweek 6.

What games/genres influence you most, and how?

I don’t have any conscious influences that I can think of, as in, I enjoy this game so I want to make more games like it. Games are definitely good for reference, though. When it comes to designing controls and UI, it’s great to know a lot of games and understand the design choices and why they work, so that you can make the best choices for your own game. But when it comes to a core mechanic, I like to try to do something different. I actually don’t play that many games, but my favorites are single-player action, adventure, and strategy games with a strong story like Zelda.

I was particularly impressed by the idea of freezing yourself into statues in Fractured Soul. How did you come up with the concept?

Nothing special, I think it just came from the idea of playing through the level nine times. You can look at the entirety of the concept as it was when the game started on our wiki under IDEA1.

It wasn’t a unique idea, either, someone else posted basically the exact same idea we had.

Yes, actually superjoe’s winning individual entry also has the concept of piling up duplicates of your character. Did you spot any really original ideas in other Pyweek entries?

Not as many as in previous Pyweeks. Lots of people did as good a job as possible with the theme [“Nine Times”], but I didn’t think this theme really lent itself to much originality. The only examples of really original interpretations (IMHO) I can think of are Tee and adrwen.

How did you tune the difficulty of the game?

Poorly. This is a very important issue for puzzle design, and if things had been slightly different it could have gone badly for us. We were fortunate enough to have enough content that we could make all the stages after the tutorial optional. That way if one of the levels was too hard it wouldn’t break the game.

How close to your original concept was the final submission?

The mechanics were very similar. You could see the original concept in the link above. The idea of the “counterweight” platforms came pretty early on day 1. The storyline, sound, and graphical style were pretty much absent from the original concept. They all came late in the week.

Was there anything exciting that you left on the cutting-room floor?

There are usually features I want to add but don’t have time for. That wasn’t the case this time. There were several features that were somewhere between “jotted in the margin of my notes” and “implemented but disabled” that got cut, namely: double-jumping, wall-jumping, enemies, rolling boulders, water/lava whose level can change, keys, ladders, elevators, teleporters, mobile portals, switches in the ceiling, levels with bizarro mechanics, and using stones to keep objects from moving. (There’s no way we would have had time to implement all of them, of course.) The reason these were cut, though, is because the game was already pretty full. I don’t know about the rest of the team, but I prefer depth to breadth in gameplay. That is, really exploring a small set of mechanics rather than superficially using a larger set.

One exciting non-mechanic feature we cut was the ability to record yourself playing through a level, save it to a file, and play it back. This was working midway through the week, and we used it for some playtesting, but we had to break it on the last day.

Some of those features sound brilliant – I’d love to see what puzzles you could create with water and lava. Will they ever see the light of day or is the game done and dusted now?

Yeah, we’re thinking of continuing work on it, and that would include adding some mechanics. I haven’t gotten around to it yet myself, but I’d like to, especially if we can get someone to work on the art.

You’ve personally had winning entries in Pyweek twice. Can you speculate on the formula for a winning entry?

So, I’ve entered Pyweek solo five times, and placed 7th, 1st, 9th, 4th, and 1st. That’s enough to form some comparisons, and I can look at the other games and try to work out patterns.

My winning entries were based on ideas I came up with early on day 1 and stuck with. Starting halfway through doesn’t work, nor does forming your idea before the competition begins.

I think that a winning entry tends to feel complete, even if it’s not complete in your mind. One finished level leaves a better impression than three half-finished levels. If people don’t know the features were planned, they won’t miss them. Winning entries tend to be easy to medium difficulty. For solo entries, winning entries tend to do more with less. Simple, retro graphics and geometric shapes are fine.

But of course, I don’t really believe in a winning formula. Mostly it’s just making a good game. 🙂

One last question. What’s next for you personally, and for next PyWeek?

As much as I like Python, I’m becoming frustrated that my games are difficult to distribute. Browser-based games get so much more coverage these days than downloadable games. If someone can get pygame running in Google Native Client or something like that, that would be great! In the meantime, I’m trying to learn HTML5 or Flash.

But I’m always planning come back for Pyweek. Multiverse Factory was a very successful experiment in working on a team, from my point of view. But I don’t know if I’ll be entering solo or on a team next time.

Strategy Pattern for AI

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).

3D Engine roundup

The overwhelming majority of retail games have been in 3D for a decade or more, and we’ve long since passed the point when the majority of indie games are 3D. Yet it nearly all standalone Python games are in 2D. Why is this? A couple of suggestions spring to mind – 3D is harder and more time consuming than 2D, for example, or that Python is too slow for 3D. But are these really the barrier that people have suggested?

Both of these rationalisations would seem to be pointing to a lack of suitable tools and frameworks for delivering 3D graphics in standalone Python games. For tools, there is of course Blender, which certainly has a steep learning curve but is at least sophisticated enough to be able to produce cutting-edge 3D graphics.

There are a variety of frameworks available, each with pros and cons. Alas many of these would appear to be poorly maintained and/or poorly documented.

More information on these will be forthcoming, but let’s take a quick run-down of what’s available:

Bindings for 3D Engines

Examples: Panda 3D, Python Ogre, pyirrlicht

There are a variety of bindings for fully-features scenegraphs/engines. These generally substitute a need to know low-level OpenGL calls with a steep learning curve of the classes and datastructures of the engine. They can require a lot of setup and compiling of dependencies, or a heavy SDK/runtime to download and install before a game is playable, which make it significantly harder for many users to run games using these frameworks. Some may not even be cross-platform at all.

Of the examples listed above, Panda3D treats Python as a first-class development language and as such is maintained and has extensive documentation, pyirrlicht is maintained but apparently undocumented, while Python-Ogre is less well maintained and poorly documented.

Python/Pyrex/Cython Frameworks

Examples: Soya3D, PySoy

There are a few frameworks built from the ground-up for faster Python 3D. In theory, using Pyrex/Cython should mean that these frameworks are tolerably fast without being inconvenient for Python developers. In practice though, Soya3D is not infrequently maintained and has incomplete documentation, while PySoy is under active development, but unfinished and undocumented after 5 years of development (You are actively discouraged from using it yet – this is not esr’s “Release early, release often” methodology). Both of these tie in a swathe of dependencies that offer far more functionality than just a scenegraph, at a cost of potential extra work to get up and running with them (Soya3D is broken on current Ubuntu, for example).

Pure Python Engines

Examples: SPyRE, tdgl, Pyggel

Pure Python (based on PyOpenGL or Pyglet) have the lowest burden of dependencies, and is also the most legible and adaptable for Python programmers, but it is also likely to be slow – how slow, and whether that is a problem, is an open question. Each of these examples seems to be relatively poorly maintained, but nevertheless, they do indicate there is a body of useful Python code available to use. If you wanted to get a pure Python engine going, you do not have to start from scratch.

Have you used any 3D frameworks and how did you get on with them? Leave a note in the comments.

Hunt the Wumpus

Last Thursday night was the monthly meeting of the London Python Dojo. The Dojo is a club for Python developers to get together, learn new tools, techniques and libraries for Python or just share experiences. Tim Golden described what happened at a previous Dojo, which paints a picture of the general mixture of things that happens at one of these events.

Recently the Dojos have often had a mild game programming theme, and this is understandable: game programming is more light-hearted than the kind of tasks most of us do for a living, and stretches to cover many facets of Python. This Dojo there were a number of projects proposed and voted on, but a Hunt the Wumpus game seemed to have substantially better support than the other options.

Nicholas Tollervey explained the basic rules for the Hunt the Wumpus of this challenge:

• There is a labyrinth of rooms through which the player can move.
• There is a “wumpus” that also moves through these rooms.
• If the player is in a room adjacent to the “wumpus”, the player can hear it.
• The player wins if he and the wumpus are in the same room.

With a mere hour and a half’s coding time this was a relatively steep challenge, but the five teams each produced something of an interesting nature. One team demonstrated efficient maze storage using simply a python set of 2-tuples (the room coordinates). Another demonstrated a talking wumpus using Mac’s say command.

Our team was able to demonstrate a graphical (ASCII-art) implementation of these rules, including random maze generation and a roaming wumpus (and a knowledge of pig latin):

#####################
#     #   #         #
# # # ### # ### ### #
# # #   #   #   #   #
### ### # ### #######
#   #   # #   #     #
# ### ##### ### ### #
# #         #     # #
# ##### ##### ##### #
#     # #     #     #
# ### # # ###########
# # # # #   #       #
# # # ##### # ##### #
#   #     # #     # #
### ### ### ##### # #
# #   #     #   # # #
# ### ####### # ### #
# #   #       #     #
# # ### ########### #
#    W P#           #
#####################
ouyay ancay earhay a umpusway omingcay!!
terenay a irectionday:

I feel our team benefitted strongly from splitting efforts into two streams, one working on bottom-up datastructures for representing and modifying the maze, player and wumpus, and the other researching maze generation on Wikipedia and then implementing it (instructively slowed down so that the algorithm could be seen working), and crafting the game loop and I/O.

I think the most impressive creation was the entry that replaced high-brow notions of mazes and even game state with heavy use of Python’s random module, and simply delivered the requisite user experience:

You are in a maze of twisty passages, all alike. Where's the Wumpus..?
Which direction ['e', 'n', 's']? n
You hear the Wumpus....
You are in yet another dark mysterious room.
Which direction ['n', 'w']? w
You hear the Wumpus....
You are in yet another dark mysterious room.
Which direction ['e', 'n', 's']? e
You hear the Wumpus....
You are in yet another dark mysterious room.
Which direction ['e', 'n', 's', 'w']? n
You are in yet another dark mysterious room.
Which direction ['n', 's', 'w']? w
You hear the Wumpus....
You are in yet another dark mysterious room.
Which direction ['e', 'n', 's', 'w']? w
You are in yet another dark mysterious room.
Which direction ['n', 'w']? n
You found the Wumpus! Well done!

It even delivers the user experience of running successful nosetests.

Though most attendees found this a very humorous approach, I think there’s a really powerful lesson here. For Hunt the Wumpus, this incarnation genuinely delivers a better play experience than any of the others. Why? Simply because there is a hard upper and lower bound on how many moves a game will take, which means you are guaranteed a reward after 7 to 12 moves – and that’s a better balance of reward to chore than any of the other games.

As game programmers we only need to create the illusion that the world works a certain way, and we should be free to look for ways to do it more cheaply or for better control over the user experience.

Game Review: Flash Tactics

One of the things I want to do with this blog is showcase some of the best examples of Python game development. There are plenty of candidates on pygame.org’s extensive database. I’m a bit of an RTS fan – among most other genres – so I was curious to see whether there are any polished RTS games in the database.

One that I turned up that is extremely polished is Flash Tactics – a real-time tank fighting game.

The player controls three tanks of slightly different types, which can me moved forwards or backwards across the landscape and told to target specific enemies. Each tank fires automatically as long as it has a shot, and that depends a lot on the angle of the terrain on which it is sitting. Thus a lot of the game is about choosing good firing positions for your tanks. Your tanks respawn after 10 seconds so you always have three to play with, but if all are killed at once the game is over.

It is also possible to purchase modifications for your tanks, including the awesome armour mod that makes your tank twice as strong but twice the size; earning these involves building up a combo by killing the enemy tanks as fast as possible. Modification points are only awarded at the end of a level so they are quite difficult to obtain.

This game has a very polished appearance, with superb smoke effects and explosions, with the only flaws being that some of the effects are a little flickery, and the heavy use of nearest neighbour rotation leaves the sprites heavily pixellated. I particularly like the comic chat messages the tanks spout, such as “I didn’t sign up for this!” and “He had a friggin family!”

It’s also worth pointing out the excellent levels drawn with a delightful cartoonish style but with good attention to the foreground and background detail, each offering an interesting mix of combat terrain.

What other Python games have you enjoyed playing lately? Leave a note in the comments.

Screenshot Code

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

One-Hour Games

After Pyweek 12, a few contestants fuelled by the drug of Python game coding set about a new challenge, writing a game in one hour, solo.

superjoe and John opened the competition with hour-game and space_bombers:

hour-game, by superjoe

space_bombers, by John

Chard followed up with an addictive little avoid-the-laser game, futility

futility, by Chard

My attempt was a simple destroy-the-planet game.

hourgame, by mauve

camel, made by Cosmologicon in just 30 minutes, was created according to a randomly selected theme:

camel, by Cosmologicon

And that’s all I’ve seen, so far. If anyone would like to participate, simply set your timer for one hour, knock up a game from scratch, in Python, and pop a note with a link to a download in the comments.

Pyggy Awards, July 2011

Off the back of Pyweek 12, Greg Ewing has announced the 6th Pyggy awards, to be judged in July 2011.

This time the 2 month long contest is open to any open-source Python game, as Greg explains:

If you’ve had a Python game project on the back burner, you no longer have any excuse for not finishing it off! Get going!

Previously the Pyggy awards were only open to games building upon Pyweek entries or themes.