Saturday, December 25, 2010
Saturday, September 4, 2010
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.
Monday, August 23, 2010
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.
Monday, August 16, 2010
Tuesday, July 27, 2010
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.
Tuesday, July 20, 2010
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).
Monday, July 12, 2010
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. :)
Next up, revisiting Omega--this time with extra crunchy bits added. Yum.
Friday, July 2, 2010
Saturday, June 26, 2010
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.
Thursday, June 24, 2010
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.
Monday, June 21, 2010
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.
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 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. :)