Progress? Yes, that would be lovely. Thanks.

I think Praetor has finally gotten past the Hard Part. Every project reaches a point where multiple subcomponents have become functional--maybe not finished, but at least functional--and it's time to integrate them. That's when the real hairball begins. Integrating the audio, the rendering engine, animation sequencing, the storage subsystem and so on turns the complexity knob up to eleven. If the subsystems aren't individually stable or if their interfaces were designed poorly then the whole thing usually cracks and the project ends. On the other hand, if it hangs together, the the rest of the project gets easier and easier. Being such a large project (okay, large for a one-man outfit anyway), Praetor has had an unusually long period of integration. Fortunately, though a number of minor problems have turned up from time to time, its separate subsystems have held up very well indeed and I believe the worst of the work is over. At this point one can start a new Campaign, read through some filler RPG elements, mess with the world map, challenge enemies and actually play a full battle against the enemy. If the player loses there's more RPG elements and the player gets to retry; after a victory the world map expands and new options appear. The computer AI--rewritten three times--plays a tough game and moves quickly. Changes in the game are saved persistently, and one can pop in and out of the game without any ill effects--perfect for handling inbound phone calls for example. In other words, it's acting like the real, final game should. But having passed the tough part doesn't mean it's anywhere near halfway done. This project is unusal for me in many ways, not the least of which is that it involves a lot of content. Most games I produce rely on either fixed or random initial conditions; they don't have narrative, they don't require a series of fifty different playing boards or anything. I pick projects that are simple like that because I don't have time (or adequate creativity) to fill in all those details. Praetor, though, needs a lot of content. The campaign alone involves a hundred different battles, each with its own playing field and custom opponent, and most of them use new types of cards. There are narrative elements throughout the campaign, and unique graphics and sounds for all this stuff. And I only have a small fraction of that finished: one territory's battlefield, seven or eight different cards and "TODO: show something meaningful now" text appearing for the campaign RPG elements. All that stuff is bulky, but none of it is particularly risky. So at the point the game looks like it will make it--it's just a matter of time.

^^^ Hey, look, new screenshots!

When AI is plenty A, but not so I

Normally one of the parts I like best about writing a strategy game is implementing the computer opponent. Trying to find a balance between heuristics and raw CPU horsepower is almost as much fun as playing an AI-enabled game and losing to it for the first time.

In Praetor, though, the AI is a pain in the ass. The problem is that each player has way too many options.

Consider chess: on the opening move you have 20 different moves from which to choose. A computer player could pick the best first move by simulating the board after each one of those 20 moves, and deciding which of the resulting boards looks the best. Not so bad, right? Just 20 moves to consider--can't take too long. That's called a "1-ply" search.

But regardless of the computer player does first, the second player then gets a turn--and he likewise has 20 moves to pick from. If the computer player wants to consider his opponent's responses, then for each simulated move it makes it needs to consider each possible response by the opponent. That would be a "2-ply" search, and it means the computer would be setting up and studying a total of 400 boards to decide which first move is probably best. As the game progresses the number of options each player has will increase a little because the board opens up, but then it also starts decreasing again as pieces come off the board. If we average those effects and assume that each player always has roughly 20 moves to choose from, then a 3-ply search would require the computer to consider 8,000 boards, and a 4-ply search would involve considering 160,000.

In Praetor, an average piece has about 18 squares to which it can move--maybe limited to 12 in a typical case because of terrain or other pieces being in the way. The player can play cards from his hand, and most cards either let you pick a target piece or square to manipulate. Some pieces have special abilities they can invoke, and others will happen to be within range to attack enemies. And here's the real pinch: most actions a player takes use up some energy, and a player's turn continues until he runs out of it. So instead of just picking which single piece to move or card to play, a player needs to pick what order to do those things in for each turn. Is it better to move then play this card, or play this card then move?

All those options mean that, just a few turns into the game, a player typically has millions of possible ways to play on each turn. Which means that even a simplistic 1-ply brute force search is out of the question (remember, the first release vehicle is a cell phone: not much CPU to spare). So what to do?

Heuristics to the rescue. A modern chess AI for your desktop will easily walk 8- or 9-ply deep--that would be 512 billion chess boards if it were walking that tree brute-force (e.g., considering every option). There's no way that's going to happen, which means chess AIs also rely on heuristics to prune that vast tree of options.

The goal of heuristics is always the same: to quickly identify probably-pointless moves and discard them, so you can reduce the number of choices that you have consider at each stage. With Praetor, since the game tree is so wide, I need to rely on heuristics that prune pretty heavily in order to get good moves in any kind of reasonable amount of time.

The first heuristic I've chosen is the most drastic: instead of considering in depth the result of moving every piece to every square, I'm going to have the computer quickly consider each square and pick exactly one to consider in depth. That immediately reduces the millions-of-options-per-turn to just hundreds-of-options-per-turn. I also plan to heuristically restrict where particular cards can be played: no point in sending a fireball there since it wouldn't hurt any opposing pieces, nor there since it would hurt mine. Sometimes sacrificing a piece would let the AI win the game six moves later on, but most of the time it's dumb so I won't even let it look.

Praetor in Pictures

They say a picture is worth a thousand words; I hope so, because I'm many thousands of words behind in posting to this blog and yet I have a lot of pictures to show.

(Click the picture--or right here--to see a lot more stuff.)

As my family will tell you, I'm still working full speed on Praetor as I try to get it ready for an early launch with the Windows Phone 7 devices that are coming out later this fall. This is such an ambitious project that I don't think a 2010 launch of the game is realistic, but I'd like to have it substantially complete by the end of the year anyway.

I've got a lot to post about move sequencing, network gameplay and computer AI--just too busy coding to explain what I'm doing. So hang in there, more posts are forthcoming as things slow down.

I stayed up late last night to finish writing a bit of multitouch code--actually the first time I've ever needed to do so (write multitouch support, that is, not stay up late). I was surprised at the amount of math involved to get the behavior that I wanted.

Still working on my new project Praetor, which among other things presents a fairly large world map at one point. I wanted that map to be able to pan and zoom with the same smooth behavior as Google Maps. If you've ever tried the Maps applet on the iPhone you know what I mean: it's surprisingly intuitive to drag the map around, pinch to zoom out and reverse-pinch to zoom in. And although I've observed the mechanics of the display matching itself to my motions frequently, I'd stopped at the reverse-engineer stage and hadn't really thought about implementing my own subset.

I started with a world map--just a big image (say, 2000 pixels on each side), far larger than the tiny screen of this phone (480x800) can show at once. To allow zooming in and out I had to allow for a scaling factor: the on-screen size of the image would be (worldmapsize / scale), so if scale==1 then I'd show a small portion of the map life-size and if scale==2 then I'd show a lot more of the map but shrunken down by 50%. And since I can't fit the whole map on the screen at once (except when scale is very large, zooming way away from the image), I have to account for panning too: what virtual pixel sits right underneath the center of the physical screen?

Anyway, I'll skip a lot of the trial and error in order to summarize the approach that finally worked out. When my app first notices there are two fingers on the display, it remembers how far apart they are and it averages their locations to identify the spot right in the middle--noticing primarily not the actual coordinates of the pixel on the screen, but more importantly which point in the virtual world map is currently being drawn there.

Thereafter when the fingers move--one or both, doesn't matter--I calculate a new distance-between value and a new center-point (this time worrying about both screen-space and world-map space). The change in distance-between-fingers represents a change in scale, and it turns out that the new scale should be equal to (old scale) * (old distance) / (new distance). From that simple formula it's clear that if you spread your fingers apart, the scale is going to decrease--moving from a high value towards 1, meaning that the pixels on screen are getting bigger. And the reverse for zooming out.

It's important to be precise about just how much the scale changes when you move your fingers, because ideally the behavior of the map is likewise very precise. Put two fingers on a map of the US--one finger in NYC and another in LA, and pinch. When you look again, your fingers should still be on those cities--which means you need to have calculated exactly the right scale and moved the map exactly with the fingers.

Right, so there was scale: just look at the distance between the fingers. To make the pan aspect work too, I concentrated on the center point, remembering that initial virtual pixel that was visible in the center when the fingers first touched down, and panning the display until that same virtual pixel is once again directly between the two fingers wherever they go. And poof: instant Google Maps behavior.

The last polishing touch was to allow the map to actually leave the legal bounds of the screen. This is something that Apple introduced in its iPhone and is really pleasing to the eye. In Windows, a scrollbar is a hard stop: if you try to page-up when you're at the top of the page, nothing happens. On an iPhone, if you're at the top of the page and try to drag downwards with your finger, the page will actually follow you (technically it does so at half speed from your finger, but that's a minor point). When you release your finger, the page will snap back to its legal setting--right at the top of the screen.

There are two reasons this works well from a UI standpoint. The first is that there's an immediate, direct visual response to any input you give: there's no concept of "that motion is illegal so I'll ignore you," which is otherwise very frustrating. The second is that the user gets used to being able to peek around the sides of an object to see if there's anything else--and that behavior makes the device's virtual space feel larger than it really is, which is freeing and pleasant. All good stuff.

Fortunately, it's also really easy to implement--you just have to relax your constraints a little bit, and recognize that it's just not that awful to draw this rectangular image such that it's halfway off the screen. Once the fingers stop dragging, on every frame you move the image 1/Nth of the way back to where it was (newPos = oldPos + (correctPos - oldPos) / N), and over the next few animation frames the display will "snap" back to where it belongs.

Working from Mock-Ups

The DVD for Prince of Egypt has a making-of track, which for one reason or another I ended up watching some years ago. And in there, one of the talking heads described that one of the first things they produced for the movie--even before any substantial animation was done--was the title track's music. (Remember that theme, the one that plays while we're watching the slaves being beaten?) The talking head said that having that song supplied a tone for the whole rest of the work.

For me, I've found that I can establish the tone of a work best by throwing together screen mockups in Paint Shop Pro. In the early days of a project I'll spend more time in PSP than I will writing code, as I try to get the look of the game right. Mechanically screen mockups are also useful--for example, to ensure that my hexagonal tiles will actually tile together properly to form a solid board with no gaps, or that my cloud layer isn't so thick that it obscures the game, and so on.

I was going to start Praetor by jumping right into the thick of the battle and putting that engine together, but every time I started down that track I found there were too many parts that had to be done first. So I backed up and started with--of course--the main menu.

The left-hand screenshot is the PSP mockup I put together, and the right-hand shot is live from the emulator. I've darkened the background a bit from the mockup to help the buttons stand out, but when I see how the game looks on the actual hardware I'll have to retune it.

If all goes well you'll be able to play Praetor three ways: playing the campaign (which consists of roughly 100 battles against the computer, with some RPG elements thrown in), playing an isolated battle against a local computer or networked human, and playing an isolated battle as a correspondence game over the net. It's that last aspect that led to the main menu design: in theory you could have a dozen games going, each with a shot clock measured in hours or days. So the main menu evolved into just a list of games that you're playing, and it will show the status of each game (it's my turn, or it's not, or my opponent resigned, or I'm still looking for an opponent, or whatever).

Chess Club, Finished

Microsoft finally (finally) dropped us a new SDK for writing Windows Phone 7 apps, and that let me throw together the last remaining bit for the Chess Club app: landscape support.

Landscape's important not because it's particularly essential in practice--in point of fact I like holding the phone vertically for this one, not sideways--but because it lets you capture videos better for YouTube. To celebrate, I put together the third and final demo video for Chess Club--this time with an audio track too, since watching four minutes of chess with no one saying anything is the kind of thing only I can enjoy. :)

http://www.youtube.com/watch?v=OBuq9Zaa3ng


Next up, revisiting Omega--this time with extra crunchy bits added. Yum.

Nearing Completion

My Windows Phone 7 app, cleverly named Chess Club in an attempt to obfuscate what it really does, is nearing completion. I've thrown a four-minute video up on YouTube to show off what it can do. :)

http://www.youtube.com/watch?v=AkeNHTXJ28g