Of the projects we have tackled at the Reading Python Dojo one of my favourites was programming AIs for the game Battleships, which came up in January 2013.

The dojo is not usually a competition, but in this case we waived that principle and split into two teams to create an AI that could play off against the other. I set down the basic battleships rules that we would compete under:

• The grid is 10x10.

• Each team has the following ships:

  Ship	Length
  Aircraft carrier	5
  Battleship	4
  Submarine	3
  Destroyer	3
  Patrol boat	2

The teams were not tasked with drawing a board or placing the ships. We simply drew the grids up on the whiteboard, manually placed the ships, and then had the computers call the moves. The computers were given feedback on whether each shot had hit, missed, or hit and sunk a ship.

Team A's AI was extremely deterministic, sweeping the grid in a checkerboard pattern from the bottom-right corner to the top left, until it scored a hit, in which case it would try and strafe each possible orientation of the ship in turn until it was sunk. It would then resume the sweep from where it had left off.

Team Alpha's AI was more stochastic, choosing grid squares at random until it scored a hit, then working outward like a flood-fill to completely carpet-bomb the ship. If at any point a square was completely surrounded by misses, then it could not contain a ship, and the AI would not pick this square.

On the night, Team A finally won after some astonishly unlucky misses from Team Alpha. Team Alpha benefitted from Team A's worst case performance by luckily placing a ship in the top-left corner of the grid where it would take the maximum 50 moves for Team A's sweep to find. The randomness of Team Alpha's AI injected a tension that at any point it could stumble across Team A's last ship and win, even as Team A's AI swept inexorably towards that final ship.

After the Dojo I began to wonder just how often Team A's AI would beat Team Alpha's. Team Alpha could get lucky and find all of Team A's battleships more rapidly than Team A could sweep the grid. To answer the question I wrote BattleRunner, which runs the unmodified AI scripts as subprocesses over thousands of games, albeit with a simple random ship placement strategy. It was actually my first Twisted program! While I normally use gevent for async I/O, I hit a snag very early on with Python's output buffering and wondered if switching to Twisted would solve it. It didn't; the solution was to call python with -u (or modify the AI scripts, which I was keen not to do).

The answer is that Team A beats Team Alpha about 64% of the time; Team Alpha wins 36% of the time.

BattleRunner also let me test improvements to the AIs; I was able to add a optimisation to improve how Team A's AI detects a ship's orientation. The Team A+ AI beats the original AI 54% of the time (and loses 46% of the time) - a small but significant improvement.

Perhaps you can do better than Team A's AI! There are lots of optimisations left to be had. Why not clone the repo and give it a try?

Last week's London Python Dojo at OneFineStay - Season 5 Episode 3 in case anyone is counting - was on the theme of poetry generators.

The theme was proposed as poetry generators using Markov chains, but as always at the Dojo many of the teams strive to take more "unique" approaches to tackling the problem. Markov chains have been seen many times at Dojos, and produce output that fools only a cursory glance:

Others seem to do not thy

Horse with his prescriptions are

String sweet self almost thence

Glazed with my way for crime

Lay but those so slow they

Sea and is all things turns

Enjoys it was thy hours but

Followed it is in chase thee

Receiving nought but health from

Bent to hear and see again

Boughs which this growing comes

Lets so long but weep to

Slumbers should that word doth

Enjoy'd no defence save in a

(From Team 3's generator)

My team spent a while at the start of the programming time designing a different approach. I was keen to try to generate rhyming verse and I had an idea for how one might go about it.

I had investigated the possibility of detecting rhymes a few years ago when I had the idea for a gamified chat forum. In this forum users would have RPG-style 'classes' and each class would confer special capabilities when users level up. The 'Bard' class would be rewarded for using rhymes and alliteration. I never got as far as creating the forum, but I did research how I might go about detecting rhymes.

Words rhyme if they share their last vowel sound and trailing consonants. "Both" rhymes with "oath" because they share the ending 'oh-th' sound. The spelling is useless to detect rhymes, as words are not spelled phonetically in English: "both" does not rhyme with "moth". It may be a bit more complicated than this to find really satisfying rhymes, but this approach is good enough to start with.

I eventually discovered the CMU Pronouncing Dictionary, which contains US English pronunciations for 133,000 English words.

If we look up the pronunciation of a word in the CMU data and take the last few phonemes (from the last vowel sound onwards), we get a key that corresponds to a unique rhyme. This key allows us to partition words or phrases into groups that all rhyme. "Both" and "oath" might be part of one group, while "moth" and "sloth" would be in another.

Another idea that came up in discussion, suggested by Hans Bolang, was to use lines of existing poetry and remix them rather than generating rhyming gibberish. Nicholas Tollervey immediately suggested we source these lines from Palgrave's Golden Treasury which is available on Project Gutenberg. The Golden Treasury contains thousand of poems that are a perfect input to the algorithm.

Our poem generator, then, simply classifies all the lines in the Golden Treasury by the rhyme key of their last word, and then picks groups of lines to fit a given rhyme scheme.

For example, a poem to fit the AABBA rhyme scheme of limericks:

That fillest England with thy triumphs' fame

I long for a repose that ever is the same.

Bosom'd high in tufted trees,

For so to interpose a little ease,

Tell how by love she purchased blame.

Or rhyming couplets (AA BB CC DD):

My Son, if thou be humbled, poor,

The short and simple annals of the poor.

With uncouth rhymes and shapeless sculpture deck'd,

And now I fear that you expect?

But now my oat proceeds,

Lilies that fester smell far worse than weeds?

And strength by limping sway disabled,

When the soundless earth is muffled!

The last example demonstrates a known bug: we rhyme a word with itself. This could easily be fixed.

All in all I'm pleased with our result. The lines of the Treasury all sound profound and sometimes forlorn and so come together rather well. The lines may have been written by great poets but here they're brought together in new combinations that almost sometimes seem to tell a story.

Our code is available on Github. Photos of the event are up on Flickr.

The second Devopsdays of 2013 in London wrapped up this afternoon after a packed schedule of talks, openspaces and socialising. As at the last event in March, there was plenty of food for thought, although as my current contract is primarily dev-centric the practical takeaways for me are the social aspects of process improvement and dev+ops collaboration rather than any specific technologies.

Drawing just a few threads from the notes that I took:

• Mark Burgess kicked off the talks by suggesting that rather than reacting to faults, it is better to proactively build fault tolerance into your infrastructure and applications. During the ignite talks someone's slide included a relevant quote: "Failure is the inability to handle failure."
• There were very varied ideas on how to become more collaborative between silos, including an openspace on how to roll out devops and a talk by Jeffrey Fredrick about the psychology and pitfalls of becoming more collaborative. One new idea I took away was the suggestion of making a business case to begin cross-function collaboration by demonstrating problems that stem from a lack of collaboration alongside business goals that can only be tackled through greater collaboration. Indeed, collaboration doesn't just need to be between dev and ops. We should collaborate with HR and IT departments too.
• I noted several discussions about the future of configuration management. Mark Burgess' talk mentioned the idea of managing infrastructure systems as a whole rather than acting at the level of individual nodes. The view was expressed that solid orchestration should be the backbone of the next generation of configuration managment tools rather than a value-added bonus. However others commented that the orchestration-based tools (Ansible) are not yet on a par with the more node-centric (Puppet and Chef).
• Some of the openspaces focused on wellbeing. It's easy to forget that technology should be about humans, not just about the cool things we might build. Someone brushed on the idea of a role of "People Leader" looking out for the welfare of team members.

To sum up it was a great conference, and while I'm not currently in a position to contribute new experiences to the technical openspaces, or apply those of others, I always find it very stimulating to be in a group of people who are deeply interested in finding ways to improve their working practices with both technological approaches and by improving "soft skills".

I look forward to the next devopsdays!

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.

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.

Andrew Kelley graduated with a degree in Computer Science from Arizona State University last Thursday. He loves programming, game development, and composing electronic music. In two months, he's starting work for Amazon in Seattle. Oh, and his entry, Lemming, was voted the winning solo entry in the latest Pyweek competition.

Congratulations on your PyWeek win - and with your first PyWeek entry too! Did it come as a surprise or were you feeling fairly confident?

Thank you!

I knew I would rank at least up in the top few games, simply because I was in that beautiful stage of freelancing where you have just finished a job, have plenty of money in the bank, and don't have to work for a while. With only 2 classes and no girlfriend I was able to spend upwards of 90 hours on the game. I think that's probably a bit more time than most other contestants had.

Have you written many Python games before?

This was my first Python (and Pyglet) game. I have a few really old Flash games online though. First game ever was in VB6, and the platform I've written the most games for is probably TI-83 (I had a long bus ride home back in high school).

Writing a game in Python was interesting. It's perfect for a rapid development competition like this - Python is fantastic with the arbitrary data structures you often need to solve one-off quick problems in game programming. On the other hand, I did experience some loss in CPU efficiency in my physics loop that writing it in C or C++ probably would have improved.

What would you say are most important lessons you learned through developing Lemming?

Do not write a level editor during PyWeek. I did this the first day, and then scrapped pretty much all my day 1 code on day 2 in favor of Tiled and DR0ID's tiledtmxloader. I'm very happy that I made that decision.

Reserve a non-trivial chunk of time for playtesting on friends and family - people who aren't a part of the development effort. You'll get a sneak peak of what everyone is going to complain about when they judge your game, and hence a chance to prevent that. Or even better, you'll get a preview of how judges will praise your game, and you can use that knowledge to expand upon that aspect.

Start 'em off really easy. The way your gameplay works to you is obvious, since you conceptualized and coded it. Not so for someone who hasn't seen your game yet. You don't want judges to get stuck on level 2 and give up, never to see all the cool stuff in levels 3 and above. There's a time and a place for really hard, difficult gameplay, and that is after the player has proven that they are ready for it. I think Loopback executed this perfectly with their difficulty modes. After playing on easy and getting the hang of it, you can move on to challenging for the really interesting gameplay.

Find good tools and practice before PyWeek. It shouldn't be a pain in the butt to create art, animations, and levels for your game. If it is, keep looking. You need good tools that stay out of your way so you can have more time developing and less time fighting with tools.

Was your original idea anything like the final submission or did it change a lot in the making?

According to my theme brainstorming document, my original idea was for the Fry Cook on Venus possible theme, "You're a french fry leading a stampede of lemming french fries. When you die control transfers to the next one behind you. Your death affects the environment."

When it came time to think of ideas for Nine Times, I thought, "The french fry game but with only 9 of you. And let's use lemmings instead of french fries."

So I pretty much implemented my original idea exactly, but the idea was purposefully vague enough to expand into the different possibilities that came out of it.

What in the world is that main character supposed to be, anyway?

I have no idea. Guesses people have made include "CigarMan", "Dog Poo on Fire ...Man", "The Sausage King from one of the other PyWeek theme proposals" and "The Peperami Guy". I'm no artist. To me he's just a really happy brown rectangle with a death wish.

How did you design the gameplay elements?

The process for inventing gameplay went something like this:

• Roughly sketch a level idea on paper, with gameplay concepts that I haven't programmed yet.
• Simultaneously create the art and code for the gameplay elements I had sketched out - make them work.
• Use Tiled to actually build the level I had sketched, utilizing the new art and code.
• Repeat. I only ended up going through 2 iterations.

In the reviews, your level design was praised - and cursed! ;-) - in equal measure. Was the level design something you put a lot of effort into?

Level design is really important to me. I think it can make or break a game. This is why doing most of the level design in crunch time was my biggest mistake. With half of the last day left, I only had 1 really hard grassy-hill themed level, and 1 really hard factory themed level.

I actually split the original level 1 into what is now levels 1, 2, and 3, in order to make them easier. Level 1 is fine, but everybody still gets stuck on levels 2 and 3. What this means is that my concept of difficulty was way off. I should have had more people playtest the game so that they could tell me it was too hard and so that I could make the difficulty ramp up more slowly, while still introducing cool gameplay concepts.

One of the pieces of feedback on the levels that really struck home for me was this: "The later levels of your walkthrough remind me of a Rube Goldberg device with the player getting flung hither and thither with no idea of what to expect next. That's not something it's really feasible to master." This comment is spot-on. I fell into a trap - I wanted to show off how capable and bug-free my physics engine was by making levels as complicated as possible. There is a time and a place for that, but in the case of Lemming the commenter is right, it happened far too much.

I think that as is, the current 9 levels only expose about 10% of the cool gameplay and puzzle levels you could achieve, with already existing code. Since time is a zero-sum game during PyWeek, this means I should have spent less time developing gameplay elements and more time level designing. Fractured Soul pulled off this balance beautifully. They have a pretty simple gameplay - there's not much more to it than jumping and placing 9 statues in each level. Yet they have a ton of wonderfully crafted puzzles that keep the game fresh.

What would you have added or changed if you'd had another week to work on Lemming?

Well, I have had another few weeks to work on Lemming, and I've done absolutely nothing, so I guess that's the honest answer. But hypothetically, the next few things I would add would be more levels, a better victory sound, more level themes and gameplay elements, more ways to die. I'd improve the level design, tweak various physics variables, like turning friction down, and fix some bugs!

Do you have any other projects you're working on?

Yes! Notably, mineflayer, a bot framework for MineCraft. Mineflayer makes it dead simple to create MineCraft bots in JavaScript.

I'm in the middle of refactoring it into a library so that we can kind of merge projects with Charged Miners, an OpenGL MineCraft viewer. Together this will provide an alternate client for people to play MineCraft with.

We hang out in #mcdevs on freenode. It's a pretty fun channel.

What aspects attract you about MineCraft?

I think the idea of starting out weak and vulnerable, but by slowly working your way up, you can become strong and powerful, is a big part of it. It's interesting how none of that is by "leveling up" but actually by moving, placing, and/or physically acquiring certain objects is what makes you strong and powerful. It's nothing inherent.

The Zero Punctuation video pretty much sums it all up.

Nowadays, I think the #mcdevs aspect of it is more fun than the actual game - that is, the community of people who are making MineCraft-related projects. Another example is bravo, an alternate server written in Python. One of our favorite pastimes is to gather in the IRC channel after a big MineCraft update and complain loudly together about how bad a programmer Notch is. ;-)

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.

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

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.

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.