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.

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.

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

Dreamt-Built-Played

Uploaded the latest build of Snowball Fight! to the Dream-Build-Play website this morning. There's plenty more I plan to do with the game but it's nice to have this milestone passed. Thanks to everyone who provided feedback on the previous release. And, of course, thanks to Microsoft's XNA Team for providing an excellent product with amazing support (for free!) and to the XNA Community for providing so much help and information.

You can download the latest Windows release at bayougames.com and the latest Xbox 360 release at gameprojects.com.