More updates to my A* pages #

I had a 5 day weekend (including Christmas). While not playing with magnets, I made some more updates to my A* pages, this time to the space usage, map representation, and AI sections. I didn't use PyGame for any of these sections, but I expect to for the upcoming Movement section, which will describe how to take a path and convert it into a smoothly moving object.


Fonts in OpenGL #

GLTT looks like a fairly easy to use library for rendering TrueType fonts into an OpenGL world.

Labels: ,

Updates to my A* pages #

Over the long (Thanksgiving) weekend, I made major updates to my A* pages for the first time in years. So far I've rewritten and added lots of diagrams to the A-Star Introduction and A-Star Heuristics pages.

To make the 16 diagrams, I wrote an interactive A* explorer. It uses PyGame and Peter Norvig's A* code. It was surprisingly easy to write. I really love Python.


Economics in games #

The economic model in Railroad Tycoon 3 looks pretty interesting. (I'd link to it but I can't find a site that I can view. It all seems to be Flash. Ick.) Each product has a price at each spot of the map. You can view the map, click on a product, and see green for high prices, yellow for medium prices, and red for low prices. Without any players, the price differentials lead local transporters (by river and over land) to transport goods from one place to another. The players can come in and do this more efficiently, by investing in rail lines. Your job is to find products that you can buy at low prices (typically, but not always, where they're being produced) and sell at high prices. A few years ago I had wanted to write a game like this but never got around to it.

In addition to transporting goods, you can create your own goods. You have to build a factory (or other building) that takes raw materials and produces another good. By building factories, you can create supply and demand. From what I've read on message boards, you have to do this to master the game.

There's a free demo available of Railroad Tycoon 3. I've been playing with it a bit.

Game development books #

This weekend was rather hot (100 degrees F) so I decided to keep the computer off and read instead. I'm continuing to read Andrew Rollings and Earnest Adams on Game Design, but not every weekend. Some unorganized observations:

I really like this book! No, it doesn't show you how to implement a BSP tree or interface to force-feedback joysticks. It's about the bigger picture, like how the game elements are put together, what makes a game challenging and fun, how interactive stories work, and so on. It's not about one particular genre of games; it covers all sorts of computer games. If your game design isn't fully fleshed out, this book will give you ideas. If your game is fully designed, it's still worth looking through this book, to get an idea of all the things you forgot to consider.

You have to like a book that uses "there is no spoon".

I liked the descriptive parts of the book (these are common story patterns ...; these are motivations for writing a game ...; these are the kinds of challenges that are commonly found in games...) more than the analysis/reviews ("[Dance Dance Revolution has] an interesting gameplay innovation, but one that is hardly likely to amount to anything other than an amusing diversion"; "the last third of [Half-Life] is a real letdown in gameplay terms"). The analysis of existing games is useful because it gives you something to connect to, but I haven't played many of the games they looked at so it didn't mean anything to me. The last third of Half-Life might not have good gameplay, but since I haven't played it, there's nothing I can do with their statement. My guess would be that professional game designers will have seen more of the games than I have (or at least the ones in the genre of games they're designing), and thus it's useful for them. The descriptive parts of the book were more universal, and I found them more useful.

Game development books #

I've been reading Andrew Rollings and Earnest Adams on Game Design. So far I've gone through 100 out of ~550 pages. It starts out covering what goes into a game from a high level -- challenge, victory, gameplay, interaction, and so on -- as well as the kinds of games out there. The book is organized well and I've enjoyed reading it so far. One of the things I like most is sections that contain a list of questions you should ask yourself about your game. The lists are short, the questions clear and concise, and they definitely make you think through the issues. As I go through the rest of the book, I'll post my thoughts on this blog.

Disclaimer: New Riders has sent me a whole bunch of books. So far, AR&EA on Game Design is my favorite. Other game-related books I've received: Chris Crawford on Game Design (Crawford), Get in the Game! Careers in the Game Industry (Mencher), Developing Online Games: An Insider's Guide (Mulligan,Patrovsky), and something about 3ds Max. Non-game-related books I've received: Python Web Programming (Holden), Linux Firewalls, Advanced Linux Programming (Mitchell,Samuel,Oldham), and a few others.

Counter-Disclaimer: I've been a big fan of New Riders programming-related books ever since I took a look at their MySQL and Python books; they were much better for me than the O'Reilly books on the same subjects. Many years ago, when I was universally condemning all game programming books, Andrew Rollings's Game Architecture and Design was the first book that seemed worthy.

Concentration takes time #

I haven't been working on SimBlob 2 for a while. It's really hard to concentrate on a game when I have a full-time job.

Grids #

I had started SimBlob with a hexagonal grid. In a 3d world, does it make more sense to have a triangular grid? I'm working through the coordinate system and its implications on the simulation.


Reading vs. programming #

I haven't been working on my game lately; I haven't had the energy. I've been reading some books that might help me understand what I want to do with SimBlob. Nexus is about networks, covering a broad range of examples: Sean Connery, fireflies, Tanzanian People's Defense Force, trickle-down economics, yeasts, Japanese whaling, Plato, Will Smith, Monica Lewinsky, IMDB, Carl Jung, monkey brains, Ross Perot, Islam, e.coli, airport hubs, grunge bands, mass extinctions, Ted Danson, free markets, Don Juan de Marco, Bing Crosby, the bell curve, and locusts. Emergence is about combining small, simple objects to get complex behavior. I'd certainly like to do that with the blobs in SimBlob.

Economic models #

I'm trying to build a very simple economic model for the blobs. There are two types of items: food and money. A blob can do four things: rest, plant crops, harvest crops, or eat. What makes this complicated is that the blob has to make a tradeoff between present and future and between comfort and wealth.

How can I make it interesting? I don't want one option to be always better than the other.

One way to make blob behavior interesting is a non-linear utility function. Intuitively, the unpleasantness (negative utility) of each hour of work increases the more work you've done. Hour ten is tougher than hour three. Also, the pleasantness of goods (positive utility) decreases for each additional unit. This is called diminishing marginal utility in economics. With this principle we can have blobs that do not always choose the same thing, because choosing the same thing over and over leads to reduced returns each time.

The blob decision algorithm is: compute the total utility function of each of the alternative actions and then choose the highest one.

What I still haven't worked out is how to value the future. Planting crops has a present negative utility and a future positive utility. But how do I value the future utility? Having two farms that can be harvested in six months isn't equal to having one farm that can be harvested in three months and another that can be harvested in nine months. How do I take into account the amount of time involved? How do I take into account the possibly varying price of food? Also, how do I take into account the ability to choose something different (by having free time) in the future?

Autonomous blobs #

I'm currently working on the blobs (villagers). I'd like them to be self-sufficient: they should be able to feed and shelter themselves by building farms and houses automatically to meet their needs. I've started by implementing simple blobs (currently represented by inverted pyramids, which are easy/fast to render) that can move around. Currently, blob positions are (x,y) instead of (m,n) -- world space, not grid space. We'll see how well this works.

To place a blob in 3-space, I need to compute z. To do this, I need to find out which triangle the blob is in; the vertices of the triangle are centers of hexagons, for which z values are known. I then convert the blob's location to barycentric coordinates within the triangle. The barycentric coordinates (b1,b2,b3) where b1+b2+b3=1 give me weights, and the blob's z value is b1*z1 + b2*z2 + b3*z3.

The actual implementation of the z-finding function reinterprets the hexagon grid as a rhombus grid. The nice things about rhombuses is that they are just a shear transformation away from a rectangular grid. That makes it very easy to figure out which triangle you're in.

Another thing I needed was to compute the gradient at any point. The gradient tells you which direction is the steepest. If you can picture a triangle in your head, take the normal to the triangle and project it down onto the z=0 plane. That tells you what direction is the steepest downhill. I use this to implement gravity: the force applied to the blobs is proportional to the gradient vector.

You can generalize the gradient to work on any function of (x,y). If you take the gradient of moisture(x,y), then you have the direction in which the moisture decreases most rapidly. Blobs that carry water to dry areas could use that gradient as a guide. If you take the gradient of food_price(x,y), then you have the direction in which the food prices decrease most rapidly. Blobs trying to buy food should move in that direction. Blobs trying to sell food should move in the opposite direction.

SimBlob 2 #

Status of SimBlob 2: I have the map working (hexagonal grid, mountains, valleys, water), 2.5d navigation (you move around in 2d and can rotate and zoom, but can't change altitude), and some environmental simulation (springs, water flow, erosion, soil moisture, ground vegetation (grass)). The code is OpenGL+GLUT and should compile for Linux/Mac/Windows, although I've been developing in Linux and haven't tested the other two platforms.

[Update: I'm no longer working on SimBlob 2.]