Thursday, July 10, 2008

Morocco

I just finished my most recent project, a version of Othello for the iPhone. No, it's not the flashiest game on the iPhone, and it doesn't take advantage of the accelerometer or other cool features on the device. But it's a solid strategy game that I hope will appeal to people wanting a game they can pick up and play on the subway, or waiting for an appointment, or, uh, you know, other places you might have several minutes to yourself...

I would have liked to have blogged more about the iPhone SDK like I did with the XNA articles but I wasn't sure how much I could say given the NDA that Apple imposed on Registered iPhone Developers. Frankly, I was thrilled to have even been accepted.

Writing for the iPhone was fairly easy. I'd never written a line of Objective C but had no trouble picking it up. It probably helped a bit that I'd done a little Smalltalk programming in college. But even without that it's not a difficult language if you are used to object-oriented concepts. And X-Code is a full-featured development environment that had all of the tools necessary to take the chores out of coding and debugging. The iPhone Simulator, in particular, is a very nice piece of software that lets you do an amazing amount of development and debugging without even touching the real hardware.

That said, overall I have a preference for developing for XNA. I missed some of the bells-and-whistles in Visual Studio, which is by far the best development environment I've ever used. And Apple's NDA forced a complete lack of community support that, frankly, I thought was a big mistake on their part. Although I haven't done any recent XNA development and I'm no longer posting regularly to the XNA forums, I still enjoy following the posts, blogs, and goings-on in the XNA community and find it to be one of the most vibrant and lively development communities around. Microsoft is to be commended for fostering that.

I'll try to post some snippets of iPhone code before too much longer for any of you that might be interested.

In the meantime, you can check out the Morocco page on Bayou Games, or download it directly from the iTunes App Store.

Sunday, September 23, 2007

Yet Another Reason I Love C#

Sorry for the lack of updates recently. I took over a project in July that had several challenges and consumed my time for the past couple of months. Not that I was spending every waking hour at work, but after putting in 10-12 hour days coding and dealing with the responsibilities of being a team lead (schedules, status meetings, interfacing with the customer, and all of that other fun stuff), the thought of doing more coding for fun wasn't high on my list of priorities.

Despite the workload, it was, for the most part, an interesting project — the kind that makes me enjoy programming for a living. It was challenging and stimulating work that built on my company's existing experience developing embedded sensor networking products. But there was one challenge in particular that I could have done without.

Without going into too much detail, this is our second generation of sensor networking products and this version is still fairly young. The first generation was written in Ada and was very much tied to a specific platform and architecture. Now that there are a number of readily available and inexpensive embedded platforms capable of running a variety of operating systems, including Windows CE and even embedded Linux, our goal with the second generation was to make the product more readily portable. We also needed to keep it very extendible, since we market it to a variety of customers — multiple branches and offices within the military, as well as state and local governments, and even commercial — all of whom have slightly different needs and uses for networking sensors.

So, because of those requirements, we decided to switch from Ada to C++ and to develop a basic framework which provided the core functionality needed by all of our customers. The framework was designed to have a "common" set of code that was completely OS and hardware-independent, along with a platform-specific middleware layer. Individual projects are also intended to be completely platform-independent and merely link in the version of the framework for the platform it runs on.

All of that reflects sound software engineering principles and looks great on paper as a way to get around the many problems with writing truly portable C++ code. However, late in the project we discovered the software crashed whenever one particular type of message was sent from our sensor networking device. I took a look at it and found that in the section of code that was crashing, variables on the stack were getting changed, seemingly at random.

I immediately assumed it was a threading problem, and that another thread had a rogue pointer or perhaps a stack overrun. I asked a couple of our senior engineers to look at those possibilities, but they were unable to track it down. Just a few weeks before delivery, I was concerned we may not be able to deliver a working product. So we had a brainstorming session to think of all of the possibilities. We had proven it wasn't a stack overrun, and it was too regular and repeatable to be a thread timing problem. Because the crash itself happened inside the WinCE STL string library, there was some discussion of it being a problem with that library. However, the fact that we used STL strings throughout our code without seeing this problem anywhere else, suggested that wasn't likely.

We narrowed in on the fact that the function that was crashing seemed to be laying out the message structure in memory differently than the functions that passed in the message, which were all in different compilation units. With that information, it took me only an hour more of stepping through the code with the debugger to find the problem. The crashing function was using a definition of time_t that was only 32-bits. All of the other compilation units correctly used a 64-bit version of time_t since we don't want our product to become obsolete in 2038.

How did this happen? The most immediate reason is that one particular header file in the supposedly portable section of the framework code included a Windows header file that defined time_t as being 32-bit. OS-specific header files were supposed to be relegated to the middleware layer. That said, because of its C legacy, C++ makes it far too easy for problems like this to occur. Conditional compilation and the vagaries of determining exactly what "standard" header is being used in a particular file make it far too easy for different compilation units to use different definitions of supposedly "standard" types.

C# and Java (and Ada), have their own problems, but this kind of pulling-out-your-hair problem simply can't happen in those languages. A significant amount of experienced resources were spent tracking down a problem that shouldn't have been able to happen in the first place.

Anyway, sorry to ramble on about a non-game-programming related problem. The good news is that we had a very successful sell-off demonstration of our product last Friday and the customer is very happy. Which means my working hours will return to normal and I can hopefully get back to finishing off Snowball Fight and participating in the XNA community again.

Thursday, August 9, 2007

XNA: Ready for Prime Time?

CoDe magazine has an in-depth article on XNA titled, Microsoft XNA: Ready for Prime Time? It looks at XNA's strengths and deficiencies, and how it is being used and viewed by professional game studios and programmers. Definitely worth a read.

Friday, August 3, 2007

Congrats to DBP Winners

The DBP results are in, and the only surprise for me is that so many of the entries had been made available to play. I had expected there would be more "surprise" entries that had not been shown publicly. I also expected more pro entries so it was good to see the list dominated by small teams of hobbyists, many of whom are regulars in the XNA forums.

For those who haven't played all of the finalists, here are quick links for the seven finalists with public installers. A few of the others finalists have installers available if you go to the #xna channel on EFnet. If I get permission from the authors, I'll post links to those here as well.

Blazing Birds (Xbox)
Chaos (Windows)
Hippocrate's Dilemma (Windows)
Little Gamers (Xbox)
Magic Crystals (Xbox) (Windows )
Proximity HD (Windows)
Shuggy (Xbox) (Windows )

The following are a few other personal favorites that didn't make the finalist cut. There are a lot of other good games in the full list but if you haven't played these, you should check them out.

Battle for the Seas (Windows)
Dream Sower (Xbox) (Windows)
Headbanger (Xbox) (Windows)
In Your Face Football (Xbox)
Vacuum Ball (Xbox)

Congrats to all of the finalists, but also to everyone who managed to complete a game to enter. This has been a lot of fun for me, both as a participant and to see the results!

Friday, July 13, 2007

Platforming Sample From Creator Of Shuggy

David Johnston (aka Deajay169), the creator of Shuggy (one of the absolute best of the Dream-Build-Play entries), has created a sample project that shows how to create a basic platformer. This is very good stuff and the code is well-written and easy to understand. A must-read for anyone who wants to understand how Mario Brothers (or Shuggy!) works.

Tuesday, July 10, 2007

Pathfinding Sample Using A*

Most game developers these days know of the A* (pronounced A-star) algorithm as the preferred method of finding a path around obstacles on a map. A* is actually a general-purpose graph-search algorithm based on theories presented by Hart, Nilsson, and Raphael in a 1968 paper for the IEEE Transactions on Systems Science and Cybernetics entitled, "A formal basis for the heuristic determination of minimum cost paths."

Whew! Fortunately, although it may seem intimidating at first, the A* algorithm is quite simple and you don't have to be an IEEE fellow to understand it. My first introduction to it was in one of my AI classes in college in Nilsson's book, "Principles of Artificial Intelligence." Interestingly enough, that book doesn't even mention the algorithms use for pathfinding on a map. The example he provides uses the algorithm to traverse a search tree to solve the 8 puzzle.

However, it should be obvious (when you think about it) that pathfinding on a map is merely a specialized case of a generic graph-search. And, as it turns out, one that the A* algorithm is particularly useful for solving, provided you can determine accurate "costs" for moving between adjacent nodes on the map.

Overview

The basic idea of the A* algorithm is to divide a map into adjacent nodes. Some nodes are free of obstacles and can be entered. Other nodes can not be entered. Between any adjacent nodes, there is a cost associated with moving from one node to another.

The algorithm starts by looking at all of the nodes adjacent to the starting point. For each one, it determines an estimated total cost of moving from that node to the destination, generally based on distance without regard to possible obstacles (which aren't known yet).

It then chooses the node with the least estimated total cost and looks at all of the nodes adjacent to it. This time it tracks the actual cost of moving from the original node to the current one and then, again, adds an estimated cost to the destination to come up with a revised estimated total cost.

From all of these nodes, it again selects the node with the least estimated total cost and repeats the process. As it does so, it is continually refining the actual cost of moving into each node along various paths, always doing so by searching the lowest estimated costs first. When paths are discovered with actual costs that are worse than actual costs to the same node by other paths, they are eliminated from further consideration. The end result can be proven to be the shortest path between the start and destination nodes (assuming the heuristic for estimating total cost meets certain conditions).

For a more complete, and very readable, description, I highly recommend the article, A* Pathfinding for Beginners, by Patrick Lester. I couldn't hope to explain it in more understandable terms than he does.

An A* Implementation

I have created a sample "game" that demonstrates the implementation of A* that I used in Snowball Fight!. I created this as a separate sample application in order to make it easier to understand how the algorithm works and how to use this specific implementation. I stripped out almost all of the unnecessary code to focus as much as possible on the Pathfinding class.

In the sample, a Bug (er, insect) traverses the shortest available path around obstacles on a map towards a Flower. The Flower can be moved by the player using the keyboard or an Xbox 360 controller. Whenever the Flower is moved, the Bug uses the Pathfinder class to find the shortest path to its new location.

The sample is divided into two namespaces. The SwampLib namespace contains general purpose classes that can be reused in many games. The PathfindingSample namespace contains classes that are specific to the sample "game".

SwampLib

The main classes of interest in the SwampLib namespace are:

IMap
Defines an interface between a map and the Pathfinder class. This allows many map implementations to be used with the Pathfinder. The only restriction is that the map must be capable of being divided into "tiles". Note that this does not mean the map must be a traditional tilemap. In fact, the Map implementation in this sample is not a traditional tilemap.

MapLocation
A struct that represents a tile on an IMap.

Pathfinder
Any object that wishes to find a path through a map must create an object of this class. The constructor to the Pathfinder object takes an IMap object as a parameter. The map associated with the Pathfinder can later be changed, if desired, with the one restriction that the map must be of the same size as the original map.

The FindPath method is used to find a path from any starting tile to any destination tile. The path found is stored as a stack of destination MapLocation waypoints.

Traversing the path is done by calling Pathfinder's Complete method to make sure that the destination has not already been reached. If Complete returns false, the GetNextWaypoint method can be called to get the MapLocation of the next waypoint.

PathNode
PathNode is only of interest in understanding the A* implementation. It is not publicly accessible outside of the SwampLib namespace and is used internally by the Pathfinder class to keep track of the status of each node (tile) on the map while finding a path.

Sprite
The Sprite class is not related to pathfinding, or the A* algorithm, but is provided as a reusable class for managing on-screen sprites. It provides collision detection and handling capabilities via the BoundingCircle and BoundingRectangle classes, although these are not used in this sample.

XnaGame
The XnaGame class is a subclass of Microsoft.Xna.Framework.Game class that is intended as a parent to other Game classes. It provides access to a number of commonly needed resources and methods.

PathfindingSample

The classes that make up the PathfindingSample itself are:

PathfindingGame
The game itself, which inherits from SwampLib.XnaGame. This class creates the GameComponents and Sprites, and loads all game content. It also manages updating and drawing the player's target Reticle.
InputComponent
This GameComponent manages the state of the keyboard and gamepad input controls. It is implemented as a singleton to make it easier for all of the other classes to access its properties.

The SetTarget property is true if the user has requested to change the target's position via the A button on the gamepad or the Spacebar on the keyboard.

The ToggleBlockedTiles property is true if the user has requested to toggle whether or not blocked tiles are highlighted on the map.
MapComponent
This DrawableGameComponent handles the majority of the game logic. It maintains a list of Sprites associated with the map (although in this case, that is only the Bug and Flower). It is responsible for updating all active Sprites and drawing the map and all visible Sprites.
Bug
The Sprite that uses the Pathfinder class to find the shortest route to the Flower's current position. Look at this class to understand how to use the Pathfinder class.
Flower
The Sprite that represents the target the Bug is seeking. Its location is set by the Reticle class when the user changes the target's position via the SetTarget property of the InputComponent class.
Reticle
The Sprite that represents the player's targetting reticle. It is under the control of the user via the left thumbstick on the gamepad or the arrow keys on the keyboard. When the user selects the SetTarget input, it raises the TargetMovedEvent which notifies the Flower and Bug of the Flower's new location.
Map
The game's implementation of the IMap interface. It is responsible for actually drawing the map background and fixed objects when directed by the MapComponent. It is also responsible for keeping track of which tiles are clear and which are blocked by fixed objects. Finally, it provides a number of helper methods that are used by the other classes that need to query the status of map tiles.

Conclusion

That's it! You can download the full source here:

Pathfinding Sample

I tried to make the code as readable and well-documented as possible. If you have any questions, feel free to leave a comment or email me at SwampThingTom at bayougames dot com.

Monday, July 2, 2007

Dream-Build-Play Entries

The following is a list of Dream-Build-Play entries, with links to web sites, videos, and installers (where available). I'll edit this post as I learn about more.

Aquattack
ZX360
2D Action
Windows / Xbox

Baby Gamer - Musical Rain
Baltico X
Screenshot

Bathtub Navy
Galactysis
3D Action
Website
Video
Screenshot
Windows
Xbox

Battle for the Seas
Joopsy
3D Turn-based Strategy
Video
Windows

Big Sky
Screenshot 1
Screenshot 2
Screenshot 3

Blazing Birds
Dagfari
2D Action
Website
Video
Xbox

Block Realm
Chromatic
3D MMORPG
Website

Botload
jstewart
Xbox

Bullet Hell Tactics
Kobingo
Website
Video
Windows

Burning Angels
Arthur_Frontfree
3D Shooter (3P)
Website
Video 1
Video 2

Butterfly Paradise
CatalinZima
3D puzzle
Screenshot 1
Screenshot 2
Screenshot 3
Xbox

Chaos
hellborg99
2D Action
Website
Windows

Cuber
Taber
3D Puzzle
Website
Xbox
Windows

Crystal Glyder
vRAGmAZTER
3D Flyer
Website
Xbox

Dark'nd
FritzLafferty
3D Sci-Fi/Action Multiplayer Arcade
Website
Xbox

The Dishwasher: Dead Samarai
Jamezila
2D Brawler
Website
Video

Dog Food
CheekyOaf
2D Platformer
Website
Windows

Doppelganger
PumpkinPaul
2D Shooter
Website
Windows

Dream Sower
Kyle0654, LoneRockstar, CatalinZima, atlStylin
3D Action
Website
Screenshot 1
Screenshot 2
Screenshot 3
Video
Xbox
Windows

EleMental
MadGamer7
FPS
Website
Windows

Evil Aliens
CoamIthra
Windows

Exisled
LOSTlogic
2.5D Shooter
Xbox
Windows
Video 1
Video 2
Video 3

The Farthest Land
xVxObliVioNxVx
2D Fighter
Video
Windows

Galactic War
DarthCheesiest
3D Action
Video

Ghost Ball
Da Coder
3D Sports
Screenshot 1
Screehshot 2

Give it a Rest
Camp ELM
2D Side Scroller
Windows

Gravitron Ultra
Screenshot 1
Screenshot 2
Screenshot 3

GunStyle
Alex
2D Multiplayer Shooter
Website

Hasta La Muerte
Screenshot 1
Screenshot 2
Screenshot 3

Head Banger
Ganksoft Entertainment
Website
Windows
Xbox

Hippocrates Dilemma
Handkor
2D Shooter
Website
Windows

HurricaneX
3D Action
kobunketsu
Video

In Your Face Football
barkers crest
2.5D Arcade Sports
Video
Xbox

Lazyville
hnathanh
Video

Little Gamers: Teh Game
Epsicode
2D Action
Website
Video
Xbox

Magic Crystals
qillerneu
2.5D Action Puzzler
Xbox
Windows

Mech Rider Z
DexterZ
3D Mech Shooter
Website

Memories
MarginalWotan
3D Action Adventure
Windows

Minpick
BitChain
2D Puzzle
Website

Mr. Pluck Adventures
rwp QUARK
3D Platformer
Video
Windows

Nanonomi
Duckocide
2.5D Action
Website
Video
Xbox

The Night of the Puppets
MutantPenguins
2.5D Action Adventure?
Website

Odyssey
Ringo
2D Shooter
Windows

Proximity HD
SageClock
2D Strategy / Board Game
Windows

PvP
Chryso
FPS?
Screenshot 1
Screenshot 2
Screenshot 3

Ragu
Screenshot 1
Screenshot 2
Screenshot 3

The Real Invaders
lalolete
3D Action
Video

Rocketball
gameD3V
2.5D Party
Website
Screenshot 1
Screenshot 2
Screenshot 3

Roto Motion
HadesSpaniel
2D Puzzle
Video
Windows

Samarai Soul Hunters
SamaraiForever
2.5D Brawler
Website
Video

Shuggy
deejay169
2D Platformer
Website
Video
Xbox
Windows

Sky Burner
moriarty72
3D Action Flying
Windows

Snapcount
AwkwardGamesLtd
2D Action
Windows
Screenshot 1
Screenshot 2

The Snoobies
chenpwnage
2D Action
Website
Xbox
Video
Screenshot 1
Screenshot 2
Screenshot 3

Snowball Fight!
SwampThingTom
2D Party
Website
Xbox
Windows

Solar Defense
chronos78
2D Shooter
Screenshot 1
Screenshot 2
Screenshot 3

Space Sudoku
Rexorep
Screenshot
Video

Sprockets of Strife
Website
Screenshot 1
Screenshot 2
Screenshot 3

Starcrushers
Zener
Website
Video
Windows

Tower Defense
KriscC
2D Action Arcade
Website
Windows

Truck Defender X
Christopher
3D Action / Strategy
Video

Viduce
Screenshot 1
Screenshot 2
Screenshot 3

Vocab Trainer
Jendrik
Educational
Website
Windows

Vacuum Ball
Greytone8
2.5D Action Puzzler
Website
Xbox

X-Road
DrCosinus
2.5D Shooter
Website
Windows
Xbox

X Space Cruiser
Anonymous
3D Space Racing
Website
Screenshot 1
Screenshot 2
Screenshot 3
Windows

xSpace
ClydeCoulter
3D Space Shooter
Website
Windows

Xtreme Table Soccer
Nivel21
Windows

Yo Ho Kablammo!
Screenshot 1
Screenshot 2
Screenshot 3