Praetor: Not Dead!

It's been a few months since I posted here--a gap that started, appropriately, just after I declared Praetor past the hard bits. Heh.

The delay has been caused by a new project starting at the office, which has consumed all my free time. The office is shutting down (as in, fully powered off while they swap power transformers or something) for a whole week during the holidays, though, so I can't make any progress on my Official Work and have plenty of time to play with Praetor again.

A few months ago I hired an artist to provide the big map, a 4-megapixel image that the game will reveal progressively as you work your way through the campaign. He delivered that in October, and it's perfect. A lesson from this: invest a little and farm out the things you can't do well to someone who can. If I'd done that map it would've looked awful; instead, this key piece looks like something out of the Lord of the Rings and it adds credibility to the whole project. Here's a small piece from it to give you an idea:

In addition to incorporating this gem, over the last few days I've made a lot of little changes: polishing up the tutorial, fixing bugs, rounding off the UI (adding an options dialog, delete-game popup and so on) and even adding some new content.

I've also made the executive decision that this first release will provide the campaign game only: no two-person online play yet. That's an unpleasant step back but it's very freeing; there was a good month of work needed to allow two-player games, and I don't want to waste that time. Now I can focus on the campaign, which is really the essential one-player RPG part anyway.

The role playing campaign takes place over 100 battles that occur as you work your way through the world map. Last week I had one test battle available; now I've thrown that test code away and have 4 finished battles instead--each with its own enemy, sound effects, game strategy and incorporation into the campaign narrative. In other words, the game is now 4% complete. Experience says it takes about two hours to add each battle at this point, which means I'm about 192 working hours from finishing the app.

That sounds like a lot, but in truth it's pretty exciting. Just as I predicted last time, I'm now seeing Praetor marching forwards: every few hours I extend the campaign a little further, and I'm already seeing my character increase in strength and gain new playing pieces as he racks up victories. And best of all, the freaking game is fun--I'm really enjoying the test play, and am still learning new ways to use the pieces I have.

This thing's going to be a winner, and I'm all excited about it. :)

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

More Kaitron, More Chess

Wizards of Kaitron, now with more tiles! We've made three decks like this one, each with about 22 playing tiles.



The unusual tile in the center is just a helper: it's to remind the player which kind of element beats which other kind of element.

On the WP7 front, my Chess Club program is starting to look pretty sweet. I've finished the watch-others-play and watch-lectures sections, along with the solve-chess-puzzles for FICS (ICC support on the latter is forthcoming). That last part was tricky because I finally had to teach the thing to let users move the pieces, not just watch what's happening on the server. Still lots of UI work to do, but for sheer functionality the game is nearing completion.

WP7: Word Wrapping in XNA, Made Easy

In Silverlight, formatting text is about the easiest task of all. Boldface? Different colors? HTML markups? Word wrapping? Bah--all these are trivial.

In XNA, though, there are no primitives for any of these features. Instead there are exactly two tools at your disposal: SpriteFont.MeasureString() and SpriteBatch.DrawString(). Neither of these know anything about formatting at all--and they're certainly not going to accomplish any word-wrapping for you.

XNA isn't the only environment that lacks this basic text manipulation toolset. After running into this wall several times, I've eventually settled on an approach: a CompiledText class that turns a plain string into a formatted, word-wrapped, ready-to-draw array of individual text segments. Each segment lives on a single line and has the same formatting options--italicized, boldfaced, color blue, whatever.

One of the nice things about this approach is that you can do the hard work of constructing the CompiledText object infrequently--only when the text to be displayed changes--and in your calculation time rather than while you're doing the actual frame rendering. Once you've built the object, actually rendering the formatted text is accomplished by a very tight loop that just iteratively makes SpriteBatch.DrawString() calls--minimizing CPU cost while drawing a frame.

The CompiledText class I've uploaded needs a second file to run: AnimationUtils.cs, which exports a SqueezeText method. This thing figures out exactly how much text you can fit onto a line, by calling the primitive SpriteFont.MeasureString() and running a binary search across the string. (For better performance, you might want to refactor this thing to only test at word-break boundaries; it's currently doing the measuring first, then finding word-break boundaries afterwards.)

By the way, those who take a look in AnimationUtils.cs will discover an HslColor class that allows you to convert an XNA color to hue/saturation/luminosity values, then change them and convert back to RGB. Great for fades and color-shifts and such. Also in there is a C# version of probably the oldest method I've ever written: a method for moving sprites from one square of a chess board to another with a nice pretty motion that speeds up at the start and slows down at the end.

Resurrecting Chess Club

A long, long time ago I wrote a program called Icarus. It was a chess game, but it didn't know how to play. Instead, it was client software for interacting with the Internet Chess Club. You'd fire this thing up, and next thing you knew you'd be playing chess against someone else over the intertubez.

Fast-forward about ten years and Icarus had long since been sold to ICC for parts, and I didn't really care since the world had moved to mobile phones anyway. And there was this nice company called Danger that sold a Hiptop cell phone (T-mobile's Sidekick), and I could write programs for it. And naturally I wrote yet another client to talk with ICC--this time from your mobile phone. It was actually a pretty slick piece of technology and a well done little game. But Danger refused to sell it, for reasons they never really explained well.

(Every time you read in the news about how developers are all up in arms about Apple being too opaque or restrictive about their App Catalog, I laugh. Heartily. Danger was so insanely protective of their app catalog--which pre-existed the iPhone by years, mind you--that they made Apple look like a porn starlet eager for her first Big Flick.)

Anyway, fast forward a few more years, and Microsoft is just a few months from entering the smartphone market itself. And here I am, once again writing a chess client for a mobile phone. But (insert Monty Python swamp-routine accent here) this time, it will stay up.

For all that internet chess is an old story, I'm actually doing something kind of novel here. Microsoft, in its wisdom, has decided not to provide a sockets API with their phone--and that means there will be just about zero online games happening in the first release. Well, one: mine. Because I'm damned well connecting to the chess servers anyway, even without sockets. Woot. I'll post about how that's working after I've had a nap.

WP7: Primitive Cool

Imagine this: you've got a cool new mobile phone coming to market, and you want to compete on the world stage against the iPhones and Androids of the day. What do you need?

Slick multi-touch screen, check. Good MP3 experience, check. Um, telephone stuff I guess, check. Mmm... what about a gaming experience? Well, turns out it's Microsoft's turn to come out with a new phone, and since they've got this Xbox product line, they've got a bit of entertainment reputation to uphold. So, the new toy better have a heavy 3D processor or six built in. Check.

Picking up with WP7 (that's "windows phone 7" for those who aren't yet in the know) development kit, the first confrontation I got was from the language: everything's written in "C#". Which I do not know. This is kind of embarrassing, since I (a) used to work for Microsoft, the company that eventually came up with C#; and since I (b) am used to knowing all about any programming language I need. Whoops.

Fortunately, picking up C# was really just a day or two of effort (thanks in part to a C# pocket reference, which really summarized the language quite nicely). What proved harder was teaching the stupid phone to draw a line.

No shit. There literally is no graphics primitive for drawing a freaking line on the freaking screen. So when the first trick I wanted to do was take an image and kind of draw it slanted in a 3D-like-way, I had to do some serious experimentation to even get the ball rolling.

Which is the point of the post, dear reader. I submit to you now two blobs of C# source code:

• PrimitiveRect.cs - a class that lets you easily draw lines and filled rectangles on the WP7 device; and
  
• TexturedQuad.cs - a more complex class that lets you take an offscreen bitmap and stretch it onto any four-pixel-defined-rectangle on the screen.

Since I'm a mobile phone veteran, both of these classes are strong on the ability to precalculate early in order to keep the actual render cycle CPU-light. And since I'm a WP7 and C# newbie they probably look a little weird. But they're working great for me, so maybe they'll be useful to you too.

Wizards of Kaitron

First post at the new web site, and just to keep everyone guessing, I'm not even going to talk about computer gaming for once. Instead, it's time to show off the new OTB game that my son and I put together.

Wizards of Kaitron is a tile game that's at least vaguely like Magic-the-Gathering: you and your opponent both have a main character (a Wizard here), and your MCs each have some amount of HP, and your goal is to do damage to that guy until he dies. Poof, you win.

The novel part is, Kaitron uses the topology of playing tiles. To attack the enemy wizard you have to work your way over there, with your tiles and his fighting as you go. Each tile has its own health and special abilities, like being able to rotate in place or heal neighbor tiles and so on.

Each tile has different attributes, one for each side. There are four elemental attributes (earth, air, fire, water) and four ethereal attributes (light, dark, spirit, death). And there's a rock-paper-scissors-like system where this-beats-that to decide which tile wins in a given combat.

The mechanics of playing a game are a little more cumbersome than I'd like, but it's definitely turned out to be an enjoyable game, with a lot of strategy and a little luck involved.

My 13-year-old son and I plotted out the game a few days ago and play-tested using carboard tiles to see how it would work. That led to some rule tweaks, following which I ran out to Home Depot and a craft store. I picked up a set of 36 2"x2" kitchen tiles, some stick-on felt for backing, self-adhesive clear inkjet labels and a bunch of colored rhinestones. And poof, we've got some lovely playing tiles.

Before moving to this site, my blog was "Game Programming 101"--but I've renamed it to "Game Development 101" since the "programming" part has been getting too much attention. Developing a game is more than just writing lines of code, even if you're working on a well-understood game like checkers. The rename is to help me remember that. :)