Column: @Play: The Python Strikes! You Are Being Squeezed!
July 27, 2009 4:00 PM |
['@ Play' is a monthly column by John Harris which discusses the history, present and future of the Roguelike dungeon exploring genre. This time - a discussion of using Python to make Roguelike games.]
So let's talk a bit about Roguelike development languages.
Traditionally, the One True Roguelike Language has been C. All of the current "major roguelikes," Nethack, Angband, ADOM and Dungeon Crawl, are either written in it or in C++. (Nethack makes use of bison and lex, and Angband used to use Lua for scripting.)
The genre's origins on Unix systems, its ties with the curses console library, its reliance on a console in general, and the fact that when the genre got started C was basically it as far as serious programming languages go, all these things combined to identify the genre somewhat strongly with C.
This is not as much the case now. As this year's 7DRL competition demonstrated, new roguelikes are now written in all kinds of languages, ranging from Java to MOS6510 assembly. A few were even written in Python, a language that has historically been regarded as more of a scripting language. I mean, scoff scoff, what business does a "real game" have being written in something like Python?
[NOTE: Our column this time is concerned with matters of development and computer languages. If you're just interested in playing them, you might find this one to be somewhat dry at best, and confusing at worst. I apologize for this; try back next time and we should have a more interesting column for you.]
Well... Python has progressed a point of nearly-unmatched flexibility. (Perl may be more flexible, but it's harder to learn. Ruby is similar in many ways.) It is a semi-compiled language; upon running, it is automatically compiled into a bytecode that is then run in an interpreted fashion. However, it also has an "immediate mode," allowing someone to test out code efficiently. These attributes combine to give it more than a little similarity to the BASICs that used to come with 8-bit computers, on which a legion of programmers, including myself, learned to smash bits together. Writing in Python is fun in a sense that is not often attached to the idea of software development.
And yet, Python is serious news. It's available for a plethora of systems, and it's got more than one interface to SDL for high-level hardware utilization. If the Python virtual machine isn't to your liking, there are versions that have been rewritten to use the Java and .NET machines. If that's not enough, using the Psyco module you can even cause your Python program to be transparently compiled to machine code, providing amazing speed increases in most cases.
Some time back I spent a couple of months tinkering with a roguelike engine in Python. The contents of this column are my own observations concerning Python as a roguelike language. It offers a unique set of benefits, but also a couple of surprisingly drawbacks, for use in implementing these games. I am by no means a Python expert, but I have played around with it for a while. Please give whatever weight to my impressions you deem appropriate. But it's enough for me to strongly suggest, if you're looking to get your feet wet in roguelike development, to give Python a try.
Note: although intended for people unfamiliar with Python in general, this column is not intended to be a primer or tutorial for the language of Python. It's pretty much just an overview of interesting features and potential pitfalls. We don't even get into some of Python's more interesting general aspects, such as its enforced indentation scheme. We're focused pretty sharply on using Python for making roguelikes. There are plenty of good Python resources on the web for the Googling, though, and not a few books devoted to the subject.
Lists
One of the primary advantages of using a language like Python (or one of several other scripting languages) is the ubiquity of lists as a data type. If you're used to arrays from other languages, which tend to enforce all elements being of the same data type (even if those are frequently pointers) and being tricky to resize at runtime, this can seem amazing. These attributes make arrays ill-suited to being used to manage stuff like inventory and monster lists, since they typically impose a hard limit on size.
Because of these limitations, roguelike development in C tends to be loaded to the gills with linked lists to handle space contents, inventory, monster populations, and, heaven help us, monster inventory. Linked lists are not a native type to C; the programmer has to either create and manage them himself (and I can say, from personal experience at the very least, that beginners designing such code are prone to making maddeningly elusive errors) or use an external library to handle the mechanics for you.
If you avoid using a library, you'll end up writing a lot of utility code to maintain these lists, and expending energy to write that code, energy that comes at the cost of your enthusiasm for the project. The great majority of software projects never see completion, and part of that, I submit, is the need to write abundant utility code. C's strengths lie in its relative closeness to the metal, but that means it does little for the developer. Even common things like string handling are notoriously convoluted in C.
Python, as a "very high-level language," handles strings like a dream, uses an efficient garbage collector, and its lists are practically a godsend. There are some difficulties with learning to use them; we'll talk about those once we get into Python's drawbacks. But most of it is a substance remarkably like gravy. What is especially cool about lists is that, unlike C's arrays, you can put any data type you want into a list's cells; they don't all have to be the same size. If you wanted, you could store a string in the first spot, an integer in the second, another entire list in the third, and so on, using them as makeshift structs. Mind, however, that Python contains robust support for classes, so there's little reason to do this.... All this is possible because, behind the scenes, Python is actually doing all the pointer juggling itself. This is not perfectly efficient, of course, but for a roguelike game the difference in speed can usually be measured in milliseconds.
Further, lists can do lots of things easily that arrays cannot. They can easily be increased or decreased in size, arbitrary elements inserted and removed, used as stacks, operations performed on every item, copied, and reversed, and a surprising number of other things. The random
module contains a method for easily shuffling the contents of a list in place. Of special interest is sorting: once your brain comes to properly grok list sorting, it'll start coming up with all kinds of nifty, unexpected uses.
Now, granted, the tradeoff is that lists are more computationally-expensive than arrays. Python's internal algorithms are well-optimized, but it simply has more to do beneath the surface than a C array lookup would, which is basically simple pointer arithmetic. It is worth noting that fast-action games have been written in Python (for instance, popular indie game Rom Check Fail is actually written in Python using a PyCap, an interface to PopCap's game development libraries), but it is still lacking for some purposes. Roguelikes, however, are mostly turn-based, and a lot of processing behind the scenes may not produce anything more than a tenth-of-a-second pause. This makes Python, and other very-high-level languages too, potent tools for a roguelike developer.
Dictionaries
Nearly as cool as lists is the dictionary data type, which is analogous to Perl and Ruby's hashes. If you're not familiar with the concept, try to imagine the following. Start with an array. Then, abandon the idea that the elements in the array are in some sort of definite order; you can iterate through all the elements in the dictionary with a for loop, but there are no guarantees what order they'll be in. To compensate for this, instead of indexing the dictionary by a boring ol' integer value, you can use any immutable type in Python. That is to say, you can have an "array" that you access, not with a number, but with a string, or a float, or--of particular use to us--a pair of coordinates. Since Python refers to everything using objects, and variables just contain references to them, you can have one list of all the monsters in the level, and alongside it a dictionary that refers to the same monster objects according to their coordinates. This would make getting all the monsters in a room, or in the range of an area-effect spell, a matter of checking all coordinates in a smal range, instead of the potentially much-more-expensive route of checking every monster on the level for proximity. More importantly, the code is more elegant; elegant code is easier to read and maintain, because your brain doesn't have to context shift to whatever devious technique you made up in prior weeks to get a feature working.
The idea of pointing these uses for hashes out is not to say you must do it this way, but to show that Python provides a strange and wonderful toolset for use. As you come to understand the things that Python makes both easy, and surprisingly fast, all kinds of clever ways to do things may present themselves to your mind.
For beginning programmers, however, I don't think any feature of Python is more useful than its interactive shell. It's what elevates Python to the realm of old 8-bit computer programming languages, and I mean that in a good way; with a quick command, you can test out almost any code Python will compile and make sure it does what you expect, just like the old days of sloped keyboard boxes and Microsoft BASIC. This above all helps make Python fun to work with by allowing for near-instantaneous testing of prospective code.
List Copy Troubles
I think Python is, overall, fairly well suited to the task of serving as a roguelike development language, but there are a few gotchas one must look out for when beginning to use it as such. I mention it here because I myself was bitten by this, and it took me quite some time to overcome the issue. One of the most intractable such problems comes from one of its greatest advantages, how it treats everything as an object, with all variables, behind the scenes, serving as merely references to the data.
This may not sound like much of a problem. Isn't that the entire point of a variable after all? But there is a secret gotcha here that will bite if you are unprepared for it! The trouble lies with Python's two classes of datatype, mutable and immutable. Simply, the data in a mutable type can be changed without changing the reference. Lists are mutable because you may change any of its contents but the identity of the list does not change: it's the same list, just modified. Imutable objects, conversely, cannot be changed without creating a new copy of the item. Python often takes care of that for you, so in many cases you don't notice there's a difference at all. In most cases, it just means that behind the scenes Python creates new copies of changed values and discards any old value that had been there. This is good because pretty much all numbers are immutable, and you never have difficulty using the += operator because Python just creates a new value to go in that spot. The most commonly encountered problems with immutable objects usually have to do with strings, which are immutable types in Python.
But mutable objects can pose difficulties, too. The problem comes in when you make a copy of a piece of data, producing two references to the same thing. If the data is immutable then that's not much of a problem, for when one of the values is changed it'll create a new value anyway. But if you assign the same list, a mutable type, to two different variables and then change one of the elements in that list, you'll find that both lists have changed. It is possible to be profoundly screwed over by this behaviour if you're not looking for it; it looks much like the kind of stray pointer bugs that C code sometimes spawns, with values changing unexpectedly, but it's not a bug. But if you're not careful, such reference copies can spread far throughout your program. It's difficult to cause Python to make an explicit copy of a mutable object, so difficult that Python has an entire module, copy
, devoted to it to making it easy.
Yet even with this module, the problem is not always easily solved. Consider the case where you have a list of lists, a structure that roguelike authors, for reasons we'll shortly examine, often end up trying in Python. A list is just a sequence of references, referred to by number instead of, as with simple variables, name. So, a list of lists is really a list of references to lists of references! If you make an ordinary copy of such a list, you'll only end up with a shallow copy; The top-level list will be copied, but the interior list contents will all refer to the originals, and these "quantum entanglement" change bugs will persist. Heaven help you if you make a list of lists of lists, which my own code used. The copy
module contains a special function for these structures, deepcopy, that ensures that every data item copied is new. The drawback is that deepcopy is relatively slow, since it does paranoid reference checking, and making lots of use of it can drag down your game.
Lack of Built-in Multi-Dimensional List
I mention that copy problems become bad if you make a list of lists. Why would one do such a thing? It sounds slightly obscene, doesn't it, an unholy rite of development that could conjure demon bugs. Yet Python has special need of such a data structure because... here it comes... the basic language does not contain an analogue for multi-dimensional arrays. Lists are a one-dimensional structures only. Need I remind you, roguelike dungeon levels are usually stored as two-dimensioned arrays of spaces. To simulate a grid, if you want to keep the syntax similar to C, you must use a list of lists. In code, this ends up looking like:
dungeon = [[wall, wall, wall, wall, wall],
[wall, stairsup, space, player, wall],
[wall, space, monster, space, wall],
[wall, space, treasure, stairsdown, wall],
[wall, wall, wall, wall, wall]]
Do you see what this list does? A single list is defined by square brackets; thus, square-brackets inside of square brackets define sublists. To read the contents of a space, for game logic purposes or to render the display, one can refer to it with:
dungeon[y][x]
But this scheme is vulnerable to all the copy problems mentioned above. I know of two ways to remedy this sanely: using a wrapper class around a list, and using a dictionary. The dictionary method I've described above; you just use a tuple (an immutable analogue for an array, using parentheses instead of square ones) for the coordinates. Like this:
dictarray = {}
# Assignment
dictarray[(3, 3)] = "floor"
# Recall
print dictarray[(3, 3)]
It's kind of a weird solution though; although it only uses up memory for the spaces you actually fill, it's a bit less efficient than an array, and if you try to access a spot that contains nothing it'll raise an exception. There are ways around this: you could access dictionaries using its get
method, like so:
dictarray.get((0, 0), "wall")
That supplies a default value for unassigned spaces. You could also use a wrapping class like we're about to do with lists to handle default cases, and there's also a way to change Python's handling of dictionaries to avoid this problem. Those are beyond the scope of this column, but are definitely doable.
Possibly the best tradeoff between efficiency and sane syntax is to make a new class to represent your multidimensional array. The first thing we should realize is that a multi-dimensional array is simply a one-dimensional one remapped. A 5 x 5 array is really, to the runtime, a 25-cell array with a little syntactic sugar to make it seem like something else. If we know the size of the x dimension of the array, we can easily do this math ourselves.
listarray = ["topleft", "topmiddle", "topright",
"middleleft", "center", "middleright", "bottomleft",
"bottommiddle", "bottomright"]
xsize = 3
#
# Retrieve cell 1, 2
x = 1
y = 2
print listarray[x + y * xsize]
This code returns "bottommiddle" as its result. C actually makes this relationship a bit more explicit, and we can do some pointer math in a way that makes sense if a raw buffer were to be used exactly like an array. But usually the compiler does this math behind the scenes. We can do it back there too, by using a wrapper class:
import copy
from defines import *
# 2D array-faking helper functions
import copy
class TwoDArray(object):
"""
Implemented as a list simulating an array, with extra attributes for the
size.
"""
def __init__(self, xextent, yextent, initialstate = 0):
"""
To initialize, we simply store the extents and create a list of the appropriate size.
Most of the code here should be self-explanatory.
"""
self.xsize = xextent
self.ysize = yextent
arraybuild = []
for index in range(xextent * yextent):
arraybuild.append(copy.deepcopy(initialstate))
self.array = arraybuild
def checkbounds(self, x, y):
if (x >= self.xsize) or (x < 0) or (y >= self.ysize) or (y < 0):
return False
else:
return True
def get(self, x, y):
if self.checkbounds(x, y):
try:
return self.array[x + (y * self.xsize)]
except IndexError:
raise
else:
raise ValueError, "Index out of bounds:" + str(x) + "," + str(y)
def put(self, x, y, assign):
if self.checkbounds(x, y):
self.array[x + (y * self.xsize)] = assign
else:
raise ValueError, "Index out of bounds" + str(x) + "," + str(y)
An example of use:
dungeon = TwoDArray(5, 5, "wall")
for x in range(1, 4):
for y in range(1, 4):
TwoDArray.set(x, y, "floor")
To recall the contents of a cell, we'd use the get
method instead, providing only the coordinates as arguments. If we wanted to, we could even subclass lists and make a new access method "official," with its own syntax, but that's beyond the scope of this column and my abilities at the moment. Heh.
There, that wasn't so bad, was it? Python is capable of performing miracles if used correctly. Notice, by the way, that many of the things I've mentioned here can also be done, in a similar way, with Ruby. It doesn't have as many built-in helper functions as Python, and those can come in handy at times, but to our perspective the languages aren't much different at all. The biggest change to this basic exposition lies in the fact that Ruby doesn't seem to have an explicit copy method, which sometimes leads to having to use strange solutions such as serializing the data with Marshal and unserializing it to make an unconnected copy.
In other news....
The developers of Dungeon Crawl Stone Soup have announced a tournament for the month of August under the most recent version of their game. The tournament will take place on the two semi-official Crawl public servers at and crawl.develz.org. Visit the Stone Soup home page for more information.
There is an up-and-coming commercial iPhone roguelike called 100 Rogues. We're going to try to have an interview with project lead Keith Burgun up in a few days, but in the meantime you might have a look at their Facebook page, which offers a little more information as well as an info video of an intriguing character class....
Categories: Column: At Play
29 Comments
Wow the timeliness on this article for me is uncanny. I was just starting development on my dream roguelike in python. I think that this will help me get it going slightly sooner. =)
Scott E. | July 27, 2009 9:04 PM
I don't know if it has happened yet, but there was a movement to remove Lua scripting from Angband not long after it was introduced. The argument primarily was that it was an unnecessary complication.
As for Python scripting, my main complaint has been broken compatibility between versions.
Billy Bissette | July 27, 2009 10:45 PM
I also agree how uncanny the timing of the article is for me, personally.
For anyone who is a hobby/novice programmer like me, I recommend the libtcod library for python:
http://roguebasin.roguelikedevelopment.org/index.php?title=Doryen_library
It, when combined with python and good understanding of object oriented design, is the easiest means to write a roguelike from scratch.
http://kooneiform.wordpress.com/2009/03/29/241/
is a great starting point and gets much better in the later tutorials.
Also, a good article idea is the Roguelikes that can be played on a server over ssh. There is a unique experience to be had when playing Crawl on the akrasiac.org server while also in the corresponding irc room having peers comment on the moves you make and generally help you.
Dana Kaplan | July 28, 2009 2:43 AM
I started developing CyberRogue in Python - I think I got "pretty far" (compared to current versions in C++ and Python with LibTCOD - see above) despite being a newbie to the language. At one point I decided to use LibTCOD rather than Console, so that I had more control over the way it looked.
Long story short; I converted to C++ because I felt Python was too slow with the turn processing (I guess I was doing "too much", but that's a relative term).
It's not going to stop me using Python in the future, nor is it going to stop me using it for this project - using Boost's Python integration means that, rather than making the whole game in slightly stiff C++, it can be made in C++ with parts made in Python. Now I just need to figure out which bits work well broken out into Python (I'm thinking AI and possibly items)
BTW: I'll give another thumbs up for LibTCOD, as it's wonderful - full 32 bit colour "console" (emulated using SDL) means you can do some interesting things.
Scautura | July 28, 2009 5:30 AM
Ruby's equivalent method is clone:
irb(main):001:0> a = [1, 2, 3]
=> [1, 2, 3]
irb(main):002:0> a[1] = 4
=> 4
irb(main):003:0> a
=> [1, 4, 3]
irb(main):004:0> b = a
=> [1, 4, 3]
irb(main):005:0> b[1] = 5
=> 5
irb(main):006:0> a
=> [1, 5, 3]
irb(main):007:0> b = a.clone
=> [1, 5, 3]
irb(main):008:0> b[1] = 6
=> 6
irb(main):009:0> a
=> [1, 5, 3]
Mark Josef | July 28, 2009 7:05 AM
Wow, interesting article!
I must admit that I've never delved that far into game development with Python (and don't use the language itself that much anymore), but I think that it's one of the most delightful coding experiences that an enthusiast can lay their hands on and has been very useful to me on more than one occasion.
Very true what you say about the N-dimensional array problem, though I'm surprised you didn't mention NumPy (http://numpy.scipy.org/) as one of the solutions to this little dilemma. I always assumed that it was a rather popular way to get additional functionality out of the language, and if I recall correctly there's not a horrendous loss of efficiency.
Rodain Joubert | July 28, 2009 7:10 AM
I'd recommend taking a look at Clojure, it has immutable lists, arrays and maps(dictionaries).
But be warned, once you've been spoiled by having immutable data structures it is very painful to go back to the mutable way of doing things.
http://clojure.org/
dale | July 28, 2009 5:44 PM
Interesting, if currently unintelligible in large part to me, article. Quite a few niifty bookmarks to delve into in the future as well.
Python is defiinitely one of the languages I'll need some competence in for a number of projects, so this was a pleasant surprise indeed.
Keep up the good work J. Harris!
getter77 | July 28, 2009 7:28 PM
I was anxious about writing this one, and only really pressed forward due to Josh Millard's request. I'm glad I didn't make too great a fool of myself, heh.
Aaah, I seem to remember clone from Ruby now... I rejected it for some reason though. Doesn't it only make a shallow copy?
On NumPy (which provides a more useful array class than Python's default): I knew I forgot -something-. However, doesn't it still only provide with C-style arrays?
Something I wish I had mentioned in more detail was Psyco, which I think satisfies some of your performance gripes Scautura. It really is a miracle worker so long as you keep yourself within a fairly broad subset of Python.
In fact, I have not used libtcod, but considering the problems I've had making cross-platform console apps using Python (surprisingly difficult since Python for Windows has no curses), I'll be sure to file it away for later investigation.
I knew about Angband's abandonment of Lua. Such is the way of things.
John H. | July 29, 2009 2:45 AM
Psyco does go a long way to "fixing" Python's perceived slowness, and I did try it out in my own project; however, you can't rely on it being installed on your target's machine, as it is not a standard module.
Another gripe is that there are different versions, so if you develop on 2.5 (for example) and someone has 2.6 and runs you software, there may be minor problems; version 3.0, and you're definitely asking for trouble (in fact, I believe LibTCOD doesn't run on 3.0 at the moment) and 2.4 is definitely out of the question once you use certain functions. To a degree, you're relying on your "customer" having the same environment as you have, which while it is not a problem for most N*X users, does cause a problem for the average Windows user.
There is, however, a way to compile Python into executables, which I hoped to use for the Python version of CyberRogue, so that goes a little way towards solving problems for the average Windows user. Not sure how well it plays with Psyco, however (I think it may have issues, but I didn't benchmark the "compiled" version with and without Psyco compiled in)
Scautura | July 29, 2009 3:14 AM
@Scautura, I've always meant to ask you, where exactly did the Python version of CR take its performance hit? Was it strictly in rendering or did it have issues in the game logic too?
georgek | July 29, 2009 7:41 PM
The original version that used Console (From Effbot) for Windows took its performance hit mostly in rendering, but also to a degree because it was my first version of game logic - I was processing every object in the world during every turn (monsters, lights, etc.), not just those that would affect what the player could see or those that had been "activated". That's just me being a newbie to roguelike development.
Version 2 (using LibTCOD) had the same slowdown but didn't have any of the game logic - all I was processing was the player at the point where it felt slow. I tried Psyco and it did make a difference, but I felt (this is personal opinion) I could do better working in C++ (note that, at the time I decided this, I probably knew how to do "Hello World" in C++, but I have experience with various other languages so I didn't think it would be a problem).
I do think the Python wrapper for LibTCOD does have a performance disadvantage over the C/C++ native version, but that's to be expected. The biggest hit in every version so far has been rendering, but I've worked on improving some of that in newer versions by not rendering the whole screen every time the player moved (now it just renders every time something changes) so it's possible that the Python version won't be affected so badly. I've kept the code so I can have a look.
With a very subjective point of view, if I'm benchmarking them against each other, original CyberRogue and LibTCOD (Python) CyberRogue feel about the same (but note again, I never did compare them directly), Psyco'd LibTCOD CR is about 5-10 times faster, and C++ CR is about 50 times faster (note that function-wise, LibTCOD PyCR and LibTCOD C++CR are about the same point)
It's entirely possible I'm perceiving something that doesn't exist (hence my comment about perceived slowness). I'll see if I can get some real benchmarks for different versions of CR and post them for people to see.
I am not willing to entirely give up Python, as I do find it an elegant language and some things make a lot more sense to do in Python than C++ - if I can use it for pluggable modules, or things that are likely to change often (items and AI spring to mind right now, but I'm sure there are more possibilities), then that will hopefully make things easier.
Scautura | July 30, 2009 5:50 AM
As far as psyco goes, I think the psyco manual suggests this little it of code:
try:
import psyco
psyco.full()
except:
pass
Will use it if it's available, but will skip it if it's not.
Brendan S | July 30, 2009 12:36 PM
On Python's slowness:
A lot of Python's speed issues may come from using it unPythonically.
For example, Python comes with high-speed sorting routines implemented in C. You're unlikely to be able to come up with a faster version yourself, so you can take advantage of that by using sorts creatively in your code. This goes all the way down the line; using Python lists and nested lists instead of linked lists, using hashes creatively, using lists as stacks, using Pickle for saving data... there are few aspects of roguelike development, I'd say, that are not touched by Python's many amenities.
Of course, your mileage may vary, and if you're implementing multiple ports of your game you might want to keep the Python constructs as close to C/C++ as possible in order to facilitate identical behavior between versions and ease of porting. But a good browse through some Python sites might come up with some interesting ideas for how to use its wealth of features.
John H. | July 30, 2009 3:00 PM
I tried to write a game in Python once, using Pygame for the graphics. After I started writing it, I saw that it was too slow for what I wanted to do. The game was a space exploration game, and Python couldn't even handle displaying 200 moving stars or more than a few enemy spaceships. I'm now rewriting that game in C, and it's much faster.
Python can be over 100 times slower than C. The official documentation says that cPickle (which is like the Pickle module, but written in C) is 1000 times faster than Pickle.
Nathan Stoddard | August 1, 2009 9:43 AM
In crashRun, haven't yet run into performance problems that I can blame solely on Python. When investigating slow parts of code, it's almost always been me doing stuff foolishly or naively. (Of course, were I using C, a foolish or naive method might have sufficed, saving me some time) And this is without trying out psyco.
Two other Python perks that stand out:
1) Its huge standard library is fantastic. With Pickle/cPickle, saving the game and levels is just a handful of code.
So much other stuff built right in.
2) List and String slicing save a lot of code as well.
Dana Larose | August 2, 2009 8:06 AM
Oddly enough, aside from myself being the biggest longshot of the bunch, there's a decent number of people ruminating on fashioning out a proper Roguelike of sorts using the engine for the upcoming PC game Elemental: War of Magic that Stardock's cooking up---which is aiming to base itself in large part on Python 3.x and eventually evolve to hardly any C++ heritage so as to allow for a robust content development, import, modding environment and just try to be forward looking in general since it'll be a new engine from scratch.
getter77 | August 2, 2009 5:19 PM
re: arrays:
There is a standard array type (try 'import array').
It's only 1d, but that [Y*width +x] calculation per lookup is still far more efficient than using lists. Unlike NumPy, it supports only atomic types, not complex types. This should be a non-issue for storing maps etc, though.
NumPy seems to be the future, though.. Py3k includes augmentations to the buffer interface specifically designed to make N-d array access easier + faster. And NumPy has such niceties as extended slicing (allowing you to, for example, get a specific 5x5 area by simply 'subarea = area[y:y+5,x:x+5]' (no copying is involved))
David Gowers | August 2, 2009 9:49 PM
My own project that used Pygame handled updates by buffering them all and doing them at once. It sounds like it went a lot faster than your system, even though it had to do complex updates like line-of-sight code. Psyco also helped a bit.
David Gowers: Standard arrays using atomic types is okay for some things, but it prevents you from storing classes, like dungeon space contents (including potentially a monster, a trap or a feature, and an undefined number of items), within the array. If an array could be used as effectively pointers/links to other objects that problem would go away, I note. One could also use an array for terrain types and a custom hash class, as described in the column, for other contents.
I have to admit I wasn't familiar with NumPy's array slicing syntax. Nifty! Hopefully Python 3 will be ready for general production soon. I'd be developing in it now except for that general performance penalty....
John H. | August 3, 2009 1:59 PM
There are some solutions for curses on windows. someone made a curses emulation library for pygame (sdl wrapper and more):
http://www.pyweek.org/e/Cursed/
and there's also wcurses for windows:
http://adamv.com/dev/python/curses/
deovn | August 14, 2009 10:22 AM
Ah, wcurses... I tried to get that to work before but failed.
John H. | August 29, 2009 1:42 AM
PDCurses has a windows port, which might be useful: http://sourceforge.net/projects/pdcurses/
P.S. The <code> tag under the listarray example wasn't closed, and it affects the rest of the page display.
Y.K. | August 29, 2009 11:14 AM
If I can offer one little pointer, I wrote a roguelike engine in Python several years ago. Realising how easy it was to design objects using multiple inheritance, I went a bit overboard*. I wanted to be able to create a framework into which individual modules could be plugged (e.g. a pulp fiction 30's indiana jones module, a science fiction module, a fantasy module), and that players would be able to carry things out of these modules and into other ones - even if the originals had been uninstalled. It uses a lot of horrible little tricks like using arrays of class function hooks called "shadows" to do things like damage mitigation and carrying a lot of chunks of compiled code around inside the player object.
At the end of writing the "engine", I was worn out. I didn't want to write the game anymore!
If anyone would like to pick it up and play with it, they are welcome to do so. The source is in the public domain and is available from http://progsoc.org/~curious/doku.php?id=ooband If I recall correctly, it uses SDL for display.
* Having a "Flammable" parent class that made things vulnerable to fire damage in their external containers seemed legit, but when I realised I had written a bolt action rifle class that required you to work the bolt to eject spent rounds I started to wonder if I hadn't taken this all a little too far.
curious | September 6, 2009 8:07 AM
My own Python roguelike project had a similar feature planned, curious. It might be cool to take a look at how you did it, thanks.
John H. | September 8, 2009 10:36 PM
John,
I'm sure the answer to "how [I] did it" will be "horribly", but I hope it is of some interest. Email me if you have trouble getting it up and running or if you want me to try and explain part of how it works.
curious | September 9, 2009 2:26 AM
you could also write a 2d list copy function instead to shallow copy the inner lists.
def 2d_copy(2dlist):
new_list = [row[:] for row in 2dlist]
return new_list
I don't use list comprehensions often but that should be equivalent (but slightly faster) to:
def 2d_copy(2dlist):
new_list = []
for row in 2dlist:
new_list.append(copy.copy(row))
return new_list
devon | September 9, 2009 11:33 AM
The solution to your lack of multi-dimensional arrays is the Numeric module, which also accomplishes lots of other cool things.
However, the speed problems of Python are definitely an issue for game developers. I ran into this myself, writing an OpenGL game in Python and finding that, no matter how thoroughly I optimized it, the framerate was unacceptable and the equivalent C code was an order of magnitude faster.
For non-graphically-intensive games like many Roguelikes, though, the development advantages of Python might be worth it. This is especially true considering Moore's law; the longer you wait, the less the performance difference will matter.
And for the compatibility issues: use py2exe, which will bundle up a Windows executable with your chosen interpreter version, code, and all used libraries.
DSimon | October 15, 2009 9:51 AM
Hey people.
I'm only just catching up on these old columns - they are really great, thanks John!
I'd like to add an opinion and a data point
Python performance will should never be an issue for a roguelike.
For example, I've written Python game code which draws hundreds of moving and rotating 3D objects in OpenGL, all at 60fps on very old and modest hardware (2005 end-of-line sale Thinkpad T60 laptop.) It's not as fast as C would be, but it's plenty fast enough for a smoothly animated real-time action game. This is before using Pyrex or Cython or any of those performance boosting technologies.
If I did use Cython on it (the successor to Pyrex) then it would be as fast as C.
The funny thing about performance, you see, which is very counter-intuitive at first, is that the algorithms you choose end up being *far* more important for performance than the mere ~100x difference between a translation from Python to C.
As with all programming performance issues, no matter what the language, our intuition is poor at guessing which parts of our code are slow. The key is to measure your program while it's running: Either print out the time take to call your function many times, or better still, use a profiler. Then fix the bits that are slow. This has to be done in any language, not just Python.
I spent eight years being a straight C and C++ jockey, and then years doing C# after that. The performance problems in Python are no worse, nor more frequent, than any of those languages.
Best regards.
Jonathan Hartley | November 29, 2010 5:37 AM
Hey, me again.
I've been reflecting overnight, and I wanted to come back and say that I don't think it's a good idea to use Numpy just for the sake of multi-dimensional array semantics. You might want to use Numpy if you want to use its array and matrix *operations* - taking dot products and matrix multiplication and transforming 3D geometry and its cunning multi-dimensional matrix slicing - although even then your needs might be fulfilled with less complications by using a pure Python library such as PyEuclid.
Alternatively, use Numpy for speed if you have a big chunk of data - matrices that are 100x100 elements, that you want to do a *lot* of math on (ie. multiplying or adding such matrices together.) You might conceivable find such a use for numpy in a Roguelike - however, this sounds to me like a minority use case. Most people will never need to. You should write it in pure Python first (because that will be easier) and then, like all performance fixes, switch to Numpy later when you've proven that you need it.
If you are simply looking to use a[x, y] syntax to address a two-dimensional array, then I'd recommend simply using a dictionary with tuples as keys, as John describes. However, you don't have to put the surrounding parenthesis when using a tuple to index into a dict:
>>> d = {} # empty dict
>>> coords = (2, 3)
>>>
>>> # put something into dict
>>> d[coords] = 45
>>>
>>> # or using hard-coded co-ords:
>>> d[4, 5] = 56
>>>
# now get something out
>>> d[2, 3]
45
>>>
>>> # and access a location that is unpopulated
>>> d[8, 9]
KeyError: (8, 9)
When you say a dict is 'less efficient' than a list or list of lists, this isn't something you should worry about. It depends on what you're doing. For many operations, dicts are actually faster. So it'll depend on what you're doing. Regardless, nothing you end up doing will be too slow, unless you're accidentally doing something outrageously inefficient - in which case it can be fixed, and there are many helpful people on Python mailing lists to help you out with that.
Best regards folks.
Jonathan Hartley | November 30, 2010 1:04 AM