Normally there are all kinds of aspects to a simulation that are driven by mathematical functions, like gravity, momentum, population growth rates, economic trends, etc. However, mathematical functions can be difficult to tweak, and I’m finding it much easier to use lookup tables instead. This makes it much easier to make slight modifications: rather than adding additional terms to a function, I just have to modify the values in a table.
I wrapped up the logic for storing a table of points and providing interpolated values between those points into a Python class. Using Python’s __getitem__ method lets my object behave like an array, so I can just index into it when I need a value. Here’s the class:
class InterpolatedArray(object):
"""An array-like object that provides
interpolated values between set points."""
def __init__(self, points):
self.points = sorted(points)
def __getitem__(self, x):
if x < self.points[0][0] or x > self.points[-1][0]:
raise ValueError
lower_point, upper_point = self._GetBoundingPoints(x)
return self._Interpolate(x, lower_point, upper_point)
def _GetBoundingPoints(self, x):
"""Get the lower/upper points that bound x."""
lower_point = None
upper_point = self.points[0]
for point in self.points[1:]:
lower_point = upper_point
upper_point = point
if x <= upper_point[0]:
break
return lower_point, upper_point
def _Interpolate(self, x, lower_point, upper_point):
"""Interpolate a Y value for x given lower & upper
bounding points."""
slope = (float(upper_point[1] - lower_point[1]) /
(upper_point[0] - lower_point[0]))
return lower_point[1] + (slope * (x - lower_point[0]))
You use it like this:
points = ((1, 0), (5, 10), (10, 0))
table = InterpolatedArray(points)
print table[1]
print table[3.2]
print table[7]
Here are some examples of the kinds of curves you can easily make:
points = [(0, 0), (2, 9.5), (4, 8.5), (6, 4), (8, 1), (10, 0)]
points = [(0, 10), (2, 10), (4, 9), (6, 7), (8, 4), (10, 0)]
points = [(0, 0), (2, 0), (4, 1.5), (6, 8.5), (8, 10), (10, 10)]
Feel free to use this in your own projects.
This post is about being productive. It is also about drawing charts, Google App Engine, and monkeys. But mostly about being productive.
For a couple years now I’ve been running a project night. Once a week, myself and a few friends get together to work on whatever projects we’re currently involved with. The goal is to sit down and get stuff done, in the company of other productive people.
Last week, a friend and I decided to collaborate on a service for recording and charting measurements. The basic problem we’d be solving: “I want to measure some property X every N seconds and then draw a chart of the data.” The service would take care of aggregating the data and drawing charts. The user of the service would just have to write a client to periodically report measurements.
We set ourselves a challenge: try to finish a (very) rough end-to-end prototype in 2.5 hours. It would have a simple API for reporting new data points, a web page where you could view the charts, and one example client. Here’s what we managed to get done:
The whole things is done using Django on Google App Engine. There’s a simple REST API for posting new measurements, and a simple web interface for viewing the charts (which are drawn using Google Chart API).
Some observations from the project:
Picking a name is hard. Unless you’re in a hurry, in which case it becomes easy: you just pick the first name someone shouts out that isn’t taken. Stats Monkey was the first name that passed this test for us.
Having two people sitting next to each other made it much easier to stay in scope. When one of us was about to waste time over-doing something or going off on a tangent, the other one would step in. I don’t think we would have finished the project if we hadn’t been sitting next to each other announcing what we were about to do.
We both already had a lot of experience with all the tools we were using. This really helped, because there was basically no setup time. Google Code and App Engine both have really low startup costs for a project like this. I think maybe only 10-15 minutes were spent getting a subversion repository and hosting.
We hit a lot of SVN conflicts. We also had trouble with incomplete syncs/commits because we were both used to p4 semantics (where a commit includes files from the entire workspace, not just the current directory). It would be worth trying to mitigate this if we try something like this again.
The code is full of bugs and security holes, and doesn’t have any tests. Since we just barely made our deadline, I don’t think this was a mistake. We didn’t hit any major roadblocks, but this was probably just luck.
I’ve finished a first pass at building cities on an island. You can create a new island* and then start building on it. You can start cities, build roads, and irrigate bare land to create fields. There’s also a terraforming menu, so you can flatten mountains and fill in the ocean if you want. Terraforming won’t be there in the finished game, but makes it easier to play around with different island shapes at this stage. Some of the basic building logic is implemented (so you can’t build a road across mountains, you can’t build a city in the water, etc.)
The interface is…simple. It is the simplest interface that could just barely be construed as working. I’ll definitely be spending more time on this, but I want to get the core of the game working first.
As I hinted at in my last post, I’m writing this game in 2 distinct parts:
1) A library which implements a simple island economy game
2) A django app which puts a nice user interface on this library
By implementing my core game logic as pure (non-django-related) python, I have a bit more freedom writing tests and experimenting. I’m just writing normal tests using the unittest module. I’ve started on a basic economy, and so I have a couple command-line programs that let me poke around at different parameters trying to get something reasonably stable and convincing.
The live version is running at http://naru.countlessprojects.com. If you try it out, I’d appreciate any comments, questions, or feedback you might have.
* For now, I’m requiring sign-ins using google accounts. This was the fastest way for me to make sure no one else can edit your maps. I definitely want to allow instant, no-sign-in play later, but right now there are much bigger features to tackle.
I’m finding that BlobProperties are a very handy way to optimize for the App Engine Datastore. The first iteration of my island map had a Map model, and a Tile model. It used entity groups, so one Map entity was the parent of 100 Tile entities. Nice and clean, and of course dog slow. You don’t want to be loading 101 entities with every request if you can avoid it.
I added some quick-and-dirty benchmarking to time the datastore calls and then tried several different approaches. The one I settled on was BlobProperties and pickle. Basically, my Map model has a BlobProperty which stores all the tiles in pickled format. When I load the map out of the datastore, I use pickle.loads() and before I save the map back, I use pickle.dumps(). This means that I only have to load a single entity out of the datastore to display a map.
Nice side benefit: My core game logic is now pure python, so it is really easy to work on it outside of app engine (or even django). This is handy when writing benchmarking tools, testing, and prototyping new algorithms.
Possible drawback: I think I will hit compatibility problems if I try to load old pickled objects after renaming python modules. If this becomes a problem, I plan to start pickling an intermediate format like a dict instead of full objects.
Some of the folks at Google have released a sweet Google App Engine Helper for Django. It consists of a skeleton Django project with all the little tweaks necessary to run on top of App Engine, and it makes it really easy to get started.
I used the helper to start a simple Django app that shows tiled maps, using the images I previously created. Making a map generator is way, way down on the list of things that might possibly make this game fun, so I just quickly made three 10×10 islands manually. Here’s the code which generates the island in the screenshot:
island1 = _Expand("""O O L L O O L L L O
O L C_road_s L L L L F L O
O L L_road_en L_road_ew L_road_ew F_road_esw C_road_w F O O
O L L L L F_road_ns F L L O
O O O L L L_road_ns L L L O
O L L L M L_road_ns L L L L
L L L L L L_road_ns M L L L
L L L M M L_road_ns L L L O
O L L L L L_road_en C_road_w O L O
O O O L L L L O O L""")
The app picks one of the three islands randomly and spits out an HTML table containing the image tiles. A little bit of CSS makes it fit together without borders/gaps:
table {
border-collapse: collapse;
}
td, tr {
line-height: 0;
padding: 0;
}
.island {
border: solid 1px black;
float: left;
margin: 1em;
}
If you want to see it live, the latest version is running here.
Smooth coastline!
For the island game I’m creating using App Engine, I need a tiled map. I wasn’t expecting this to be difficult, but the sheer number of different tiles required is daunting. If I limit roads to only entering a tile from the north, south, east, or west, there are still 15 ways for roads to cross a tile. Since I don’t want blocky, square islands with abrupt land/ocean transitions, I need a set of 46 coastline tiles. Start multiplying by different types of base tile (forests, fields, mountains, tiny villages, big cities, etc.) and the situation quickly gets out of hand.
Blocky coastline
The only sane solution appears to be transparent overlays which are composited on demand. I don’t see a way to do server-side compositing with App Engine (plus I don’t think it would scale well), so that leaves client-side compositing. I did a simple mock-up with transparent PNG images, using absolute positioning to stack them on top of each other. It seems workable. Traditionally, transparent PNG images weren’t supported well by IE6, but since only 10% of the visitors to my site are using IE6, I might just forget about supporting it.
So that’s the long-term plan. In the spirit of getting a working prototype as quickly as possible, though, I’m going to start with a really simple tileset where I can pre-generate all the combinations and just serve static images. Here are the 6 tiles I’m starting with:
Ocean
Land
Mountains
City
Field
Road
I’m not going to allow roads over mountains for now, so there are 50 possible tiles (16 road combinations * (city, field, land) + ocean + mountains). Pre-generating all the combinations is a snap using PIL.
#!/usr/bin/env python2.5
import os
from PIL import Image
def composite(images):
"""Composite a stack of images, [0] on top, [-1] on bottom."""
top = images[0]
for lower in images[1:]:
top = Image.composite(top, lower, top)
return top
def combinations(list):
"""Generate all combinations of items in list."""
if list:
for c in combinations(list[:-1]):
yield c
yield c + [list[-1]]
else:
yield []
def load(name):
return Image.open(os.path.join('sources', '%s.png' % name))
def save(name, image):
image.save(os.path.join('img', '%s.png' % name))
def make_roads(name, above, below):
"""Save tiles with roads. Images in above will be composited above
the roads. Images in below will be composited below the roads."""
roads = dict(w=load('road_overlay'),
s=load('road_overlay').transpose(Image.ROTATE_90),
e=load('road_overlay').transpose(Image.ROTATE_180),
n=load('road_overlay').transpose(Image.ROTATE_270))
above = [load(filename) for filename in above]
below = [load(filename) for filename in below]
for directions in combinations(sorted(roads.keys())):
out = composite(above + [roads[x] for x in directions] + below)
if directions:
save('%s_road_%s' % (name, ''.join(directions)), out)
else:
save(name, out)
def main():
save('mountains', load('mountains'))
save('ocean', load('ocean'))
make_roads('land', [], ['land'])
make_roads('city', ['city_overlay'], ['land'])
make_roads('field', [], ['field_overlay', 'land'])
if __name__ == '__main__':
main()
PIL also comes in handy to paste together the first proof-of-concept map using the new tiles:
#!/usr/bin/env python2.5
import os
import sys
from PIL import Image
TILE_SIZE = 50 # Width/height of a tile in pixels.
in_file, out_file = sys.argv[1:3]
data = [line.split() for line in open(in_file).readlines()]
map = Image.new('RGB', (TILE_SIZE * len(data[0]), TILE_SIZE * len(data)))
for y, row in enumerate(data):
for x, name in enumerate(row):
image = Image.open(os.path.join('img', '%s.png' % name))
map.paste(image, (x * TILE_SIZE, y * TILE_SIZE))
map.save(out_file)
And here it is: The first example map!
Next on the agenda: Getting Django running on App Engine and serving this example map using HTML.
Neat! I’ve been kicking around the idea of making a simple online game for a while, and now Google App Engine pops up. I love great coincidences, and this is definitely one to take advantage of. App Engine is still really new, so it is hard to tell if it is a good vehicle for writing online games. There are certainly people trying, but instead of sitting on the sidelines watching them, I’m going to wade in and find out for myself: I’m going to build a game using App Engine.
Time for a rough design. I like to start with limitations, figuring out where the boundaries are. The most basic limitation is that I’m just one guy, so the game needs to be pretty simple for me to be able to finish it. The grand scale of a game like World of Warcraft is right out, obviously. I don’t know flash, and I’d prefer not to get bogged down in complicated Javascript, so that means HTML and simple AJAX. This suggests a board game, or some kind of 2D game on a fairly small map. App Engine brings another set of limitations. There’s no background processing (between requests), which makes a turn-based game attractive. There’s also not a lot of CPU available for each individual request, which suggests I should stay away from complicated AI, physics, etc.
Ok, so I’m going to make a small 2D turn-based game. As I was thinking through the limitations, I was building up a list of examples; a list of games that would fit within my constraints that I could use as a reference:
At this point, I’m thinking some kind of colonization/economy game, drawing inspiration from Sim City, Civilization, and Oasis (aside: Oasis is a great turn-based game. It is small and simple, yet fun; a really good example of how to cut a game down to the bare essentials). The core focus will be on expanding an economy by building cities and roads, and managing trade. I may also add a discovery element with exploration (i.e. the map is hidden at the start) and/or a technology tree. To keep things simple, I’ll probably just make the map into an island (keeps the player constrained).
A basic game might run something like this: The player starts with a single settler on the coast of the island. They explore the island a bit and build a tiny village. Once the population starts to grow, they can build other villages elsewhere on the island. At first, the villages will be self-sufficient, but as they get bigger and turn into towns, they will need to be able to trade with other nearby towns to get food, manufactured goods, etc. Building roads to connect towns will facilitate trade between them (towns on the coast might be able to trade using ships). As towns turn into cities, trade becomes even more important. The player can start building sea ports and airports to bring in foreign trade and tourism from outside the island.
I want the towns to have different characters. There might be a small fishing village, or a sleepy farming town, or a busy industrial port city, or a bustling metropolis. I also want the player to have to think a little bit about where they build a town, so some places on the island will be better for certain types of towns. For example, towns surrounded by fields will be great at producing food. A small village surround by mountains will barely produce any food (but it might produce a lot of raw materials like iron ore or gold). A sea port could only be built in a town on the coast.
Along the same lines, I’d like there to be several different, viable approaches to developing the entire island. For example, you could make lots of money from tourism, or by having a strong industry and relying on exports, but you probably can’t do both (that is, if you destroy the natural beauty of the island with factories, tourism will drop off).
One of the weak points of my design is that I don’t have a good idea what the end of the game will be. What are the player’s goals? It could be open-ended, like Sim City, or have a goal like Civilization, or have both a goal and a time limit, like Oasis. I like how Oasis explained both the goal and time limit as part of the narrative (”The barbarians will attack in 90 turns. Build up your defenses”) instead of just setting arbitrary limits. I’m not sure what the right answer is for my game, so clearly this will need more work.
Fortunately, my first constraint (I’m only one guy) makes it easy to design the multiplayer aspect: There won’t be one. Or rather, there won’t be anything substantial. I’d like to have a few embellishments, like some shared high-scores tables (highest population, highest GDP, top tourist destinations, etc.). I might also find a way to give in-game references to other players, similar to the tombstones in Oregon Trail (in Oregon Trail you would occasionally see tombstones with names of players who had died before at that spot).
Ok, that’s definitely enough of a design to get quite a ways into the game. This post is going to be the first in a series of posts chronicling my progress on the game. Likely next steps: getting the beginnings of a map up and starting in on the economy. Till next time…
A couple weekends ago I wanted to play around with some game ideas, to see if they were super-awesome or boring. I needed a simple framework to prototype them on, so I whipped one out using pygame. Then I sketched up some art. And made an installer.
And totally forgot to play around my original game ideas.
Damn. Maybe next time.
Anyway, here it is: a simple scrolling demo made with python and pygame. It has no real purpose (unless you want to do scrolling in pygame).
OSX
Windows
Source (Linux)
I hate it when a poorly-behaved SDL app (usually mine) grabs the mouse, crashes, and doesn’t give the mouse back. Great, now I’m stuck in X with no mouse. Here’s a handy python script to get it back:
#!/usr/bin/env python
# get the mouse back after an SDL app crashes
import pygame
pygame.init()
pygame.mouse.set_visible(False)
pygame.event.set_grab(True)
pygame.quit()
Attended my first Super Happy Dev House on Saturday night and had a great time. The house was packed with energetic people devoted to getting stuff done. Even though most of the people were strangers working on their own projects, it was really motivating to be surrounded by so much activity.
My project was getting boost.python working on my iBook. I wasn’t able to stay all night and didn’t reach my goal*, but I did learn about iPython from the people sitting next to me. Someone (not sure who) had designed a great poster for the event and they had printed up stickers & pins so there was even some schwag. I’m looking forward to the next one.
* My problem was I was trying to use the boost packages from fink. Turns out they delete a bunch of the files you need to use bjam. The answer? Download the source directly from boost.org (not sure why I didn’t think of that right away, actually). Mission accomplished.