What’s on this page? I’m interested in producing complexity out of simple parts. This page contains bookmarks that I collected while working on games; I did not write most of the content linked from here. As a result the set of links here reflects the types of things I needed to know: only a few specific topics (not everything related to game programming), general ideas instead of platform-specific information (graphics, sound, compilers), and ideas and designs instead of source code (I find it easier to go from an idea to code than from code to an idea). Other sites, like Gamedev Tuts+, Gamedev, and Gamasutra, cover lots more topics than mine does.
Determining how to move around on a map is an interesting problem. There are many different approaches, ranging from simple (walk forward until you hit something) to the complex (path finding algorithms with heuristics). These are pages about pathfinding in general, with some bias towards A*:
- Overview of Motion Planning covers both movement and pathfinding algorithms
- Amit’s Notes about Path-Finding (including A*) [last updated Sep 2011]
- Overview of the main issues that come up when choosing a pathfinder
- Choosing a graph representation for pathfinding
- Vehicle Pathfinding (long)
- Game pathfinding and AI resources
- Technical papers about navigation and paths
- Finding the “best” path is hard
- Using Regions for Shortest Path
- Shortest Path vs. Maze Solving Algorithms
- Applet showing obstacle avoidance (also see more steering behaviors)
- Steering Behaviors
- Design flaws with steering behaviors
- Collision Avoidance Behavior of Pedestrians
- Terrain Analysis used in Age of Empires
- Motion using Potential Fields
- Pathfinding: the basics covers different types of graphs (grids, waypoints, navmeshes) used for graph search algorithms like A*
- Fringe Search [PDF] - possibly faster than A* for games (download the code here)
- Cooperative Pathfinding [PDF] - useful when you have many units moving in narrow spaces, and need the units to be aware of each other
- Introduction to Pathfinding Algorithms
- More Pathfinding algorithms (minimum spanning tree, Dijkstra’s algorithm, Johnson’s Algorithm, Bellman-Ford, Floyd-Warshall, …)
- Terrain recognition and obstacle avoidance
- Movement in space, with spaceship acceleration. Also see part 2 and part 3.
- Flanking algorithms using pathfinding
My current favorite algorithm is A*, because it can handle varying terrain costs well, and it seems to be faster than most graph searching algorithms. However, it’s only one piece of a pathfinding solution. Map design and map representation come before A*. Grids are easy to work with but not always the best approach. Formations, path following, movement, path recovery, and animation come after A*. Many games don’t need A* at all: it deals with discrete steps, not with continuous movement; it works on graphs and does not take full advantage of spatial coherence (i.e., a map location is very similar to its neighbors) or temporal coherence (e.g., if we already found a path a few seconds ago, it’s likely if we try again the path we find will be similar); and if the game world is changing quickly it’s not worth planning very far ahead. A* is a good tool but it’s not the only one to look at.
- Intro to A*
- Using Navigation Meshes for pathfinding
- Multi-resolution A*
- Lists vs. Binary Heaps for A*
- Choosing a heuristic for A* (and other performance notes)
- An analysis of heuristics for A* [PDF]
- Speeding up A* by dropping admissibility
- Path Finding [150+ message newsgroup discussion] [290k]
- A* references
Code and Demos
- A* for Beginners (with Basic code)
- A Java Applet demonstrating A* (mirror site) (be sure to use the Fudge method for best results)
- A* Explorer [Windows application] Lets you step through the A* algorithm.
- Flash pathfinding demo, includes source code.
- Python code for A* and other search algorithms — note that the
astar_searchfunction is only four lines long!
The link to my A* code is to the second version , with bug fixes, optimizations, and parameterization for different heuristics and cost functions. The first version of my code is available on Steve Woodcock’s pages, and it may be easier to read and understand.
Many times I play a game and wish that the computer opponents were written better. Sometimes the computer player is given different rules; other times it has the same rules but gets more money (or other resources) than you. The result is that the game doesn’t seem balanced: it’s just too obvious that the computer is not playing well, and that the game is brain vs. brawn rather than brain vs. brain. At the same time I don’t want AI that’s too good; if it were, then it’d always beat me and I’d be frustrated!
- Overview of Game AI
- An introduction to AI in Games
- Guide to AI architectures: ad-hoc, state machines, behavior trees, utility functions, planners, neural networks
- AI Wisdom [book]
- Geoff Howland’s Practical Guide to AI and part 2
- A different Overview of Game AI [PDF]
- Great Expectation-Formations — AI shouldn’t just react to the world, but it should form expectations about the world, and react to deviations from that.
- Terrain Reasoning for 3D Action Games [PDF]
- Planning in Games: an Overview - STRIPS, HTN, Behavior Trees, Utility systems
- Using Potential Fields in RTSes
- The AI of F.E.A.R [PDF] - Jeff Orkin’s planner AI
- Need-driven AI
- The Procedural AI in Killzone [PDF] Includes line of sight, firing range, pathfinding, and tactical evaluation at run-time
- Making AI more challenging, in particular, by making it less predictable
- Strategy and Tactics by DreamWeaver [62k]
- Behavior trees
- AI in Empire-Based Games
- Hierarchical AI
- Monster AI in Unangband
- Grenade handling AI [PDF]
- The Current State of Human-Level Artificial Intelligence in Computer Simulations and Wargames: A list of references for game AI
- Getting more Behavior out of Numbers - alternatives to using hard thresholds
- Secrets of Enemy AI in Uncharted 2
Computer AI is most commonly used to implement opponents for the player. However it can also be used to implement the world (for example, all the businesses in Railroad Tycoon), assistants to the player (for example, the automatic city management in Civilization), or computer players that are not necessarily opponents (for example, non-player characters in role-playing games).
- AI Beyond Computer Games
- Under the Hood of The Sims [slides] (also see these design docuemnts)
- S.T.A.L.K.E.R. uses the terrain to assign goals to the NPCs nearby
People talk about how cool it would be to use neural networks, genetic algorithms, or machine learning for games. Read this first before you go down that route. I’m not going to provide any references for them. Instead, I’ll point to some techniques that are not discussed nearly enough:
- Subsumption Architecture for AI (Rodney Brooks)
- AI in Black & White
- Introduction to Reinforcement Learning (if you find this topic interesting, be sure to see the book by Sutton and Barto)
In choosing a technique for AI in your games, keep it as simple as possible. If you know the answer, put the answer into the program. If you know how to compute the answer, put the algorithm for computing it into the program. Only if you don’t know the answer, and don’t even know how to compute the answer, should you resort to complex techniques that can learn how to find the answer (neural networks, simulated annealing, genetic algorithms, subsumption architecture, reinforcement learning, genetic programming). These complex techniques can come at a high price, in terms of programming time, game performance, difficulty of debugging, and lack of control.
A lot of what is hard about writing a game is getting the design right. What makes a game fun? Game design is an art, not a science. It’s not just the rules of the game but the way in which you interact with the game.
- How to Prototype a Game in Under 7 Days — some good advice for getting something put together quickly to see if it’ll make a good game
- Tight Systems of Cause and Effect
- Too Many Clicks! Design the UI around the things the player wants to do, not around the objects in the game.
- The Chemistry of Game Design
- Game Balance
- Ramblings about RPG Design includes topics such as balance, food, economy, time, death, weapons, storyline, and magic.
- Confessions of a horrible game player - why you shouldn’t punish game players for playing your game
- Resources, currencies, and meters
- The Design of Online Economies: Part 1 (Currency), Part 2 (NPC Merchants), Part 3 (Items), and Part 4 (Skills)
- The Essence of Computer Games
- Evolutionary Design - why you should get something up and running before designing everything about your game
- Medieval town size: how many peasants are needed to feed towns and armies
- Persistent Myths about Game Design
- Urban modeling - models used in SimCity
- Sims, BattleBots, Cellular Automata, God and Go - an interview with Will Wright
- Designing simulation games - they’re games, not necessarily realistic models
- Game Economies and self-balancing designs
- The 36 plots for games
- One Billion Buttons: how to gradually teach complex concepts
- Positive and Negative Feedback
- Believability in games (read the comments too)
- Progressive vs. Experience games
- Realism in games: how much is too much?
- An example of why you don’t want too much realism in a game
- The use of physics in games
- Loops and Arcs - structures for game design
- The Future of Game Design (2005)
- Addictive Games
- Designing controls for a game, including how to combine controls to build more complex ones
- Design notes for my game, SimBlob
- Design notes for my game, Solar Realms Elite
- Design documents for Ultima 7 part 2
- SimCity Essay
- Why you should share your game designs
- The Focus of Gameplay
- UI for games: displaying information vs. immersion
- Bad Twinkie, a database of game design mistakes
- Random numbers for damage rolls and other RPG stats
I love tile grid based games because tiles can produce a lot of complexity from some simple parts. There are several topics that come up with tile based games. The data structures are typically variants of 2 dimensional arrays. The display transforms an array of tile data into top-down (2D), isometric (2.5D) views, or full 3D views. There are also side views but I don’t cover that here. The algorithms on grids allow you to implement gameplay elements ranging from line of sight to evaluating where enemies are likely to be. Tiles also work well with procedural world building algorithms, such as the ones in Diablo, Civilization, and Dwarf Fortress.
The basic tile structures do not depend on whether your display is 2D, 2.5D, or 3D. These articles are about how to store your data.
- Tile-Based Games FAQ
- Amit’s Thoughts on Grids includes squares, hexagons, and triangles
- Data structures for tile based games
- A file format to handle linked lists of objects
- Placing multiple objects on each tile [newsgroup discussion]
- Streaming Data: how to choose tiles to load, if your entire map doesn’t fit into memory
- Tile-based games techniques
A 2D tile grid can be displayed in various ways. The most straightforward is top-down or side-view, but these days it’s more common to see isometric or 3D views. Note that most “isometric” views in games aren’t true isometric, but dimetric.
- Guide to projections in games
- Creating Isometric worlds
- Isometric, Dimetric, Axonometric projections
- Isometric Engines - are they for you?
- Overview of Isometric Engine Development
- Isometric math - converting back and forth(New!)
- Implementing isometric tile systems
- Isometric Coordinates using basis vectors
- Sorting objects in isometric view
- Why 2D is Better than 3D (not specifically about games)
- Offsetting background tiles, drawing tiles from corners instead of centers to improve terrain transitions
- Marching squares goes into details about implementing tile drawing from corners(New!)
- Creating tile seams for textures.
- Map representations for 2d platformers
- Line Of Sight Algorithms
- Computing Line of Sight for Large Areas
- Tutorial for making a Roguelike, including map representation, dungeon generation, field of view, fog of war
- Line tracing on a grid — determining all tiles that are touched by a line
- Collision, visibility, and grid representation in tile based games, including using edge information
- 2d visibility on a grid, using polygons for computation, and part 2, which improves the algorithm
- Visibility algorithm for top-down 2d polygon map which can also be used with tiles
- Precise angle shadowcasting in a 2d grid
- Determining the range that a unit can move to
- Using tiles for flows [video and paper] The idea is to put motion/flow information into the tiles instead of in the objects; it reminds me of the reversal of roles in The Sims objects
- Influence maps
- Occupancy grids, using influence maps to let NPCs track possible locations of players
- Also read about pathfinding algorithms, which are often used on grids.
Although procedural map generation can be applied to non-grid worlds, it’s most often used with grids. Viewed at a single point in time, generated game maps are rarely as nice as hand-crafted worlds. However, they have three advantages: (1) lower cost per world if there are many worlds to be made, (2) more replay value because the next time through the world is different, and (3) potential for the world evolving while the game progresses.
- Amit’s World Map Generator
- Procedural Content Generation: generating terrain, cities, buildings
- Dungeon generation in Unangband
- Generating game worlds with a lock-and-key structure so that certain rooms require objects from other rooms
- Algorithm for building rivers
- Adding rivers to randomly generated terrain
- The original Rogue algorithm for generating dungeons
- 11 Maze Generating Algorithms with demos and code
- Using noise functions to generate caverns such as those in Terraria and Minecraft
- Irregular shaped rooms, simple algorithm
- Tunneler algorithm for digging dungeons in DungeonMaker
- Guide to random Terrain Generation techniques
- Wiki guide to procedural content generation
- Simulating Large Virtual Worlds
Many war games use hexagonal grids instead of square grids. Squares share an edge with four neighbors but also touch another four neighbors at just one point. This often complicates movement along grids because diagonal movements are hard to weight properly with integer movement values. You either have four directions or eight directions with squares, but with hexagons, you have a compromise—six directions. Hexagons don’t touch any neighbor at only a point; they have a small perimeter-to-area ratio; and they just look neat. Unfortunately, in our square pixel world of computers, hexagons are harder to use, so I’ve collected some articles that may help you turn common square-grid algorithms into hex-grid algorithms.
- Amit’s guide to hexagonal grids
- Amit’s Thoughts on Grids includes squares, hexagons, and triangles
- Overview of hex grid coordinates
- Hexagonal coordinates explained, including hex/pixel coordinate conversion
- Numbering Systems; Distances; Angles
- Isometric Cube Coordinates
- The HexPart numbering system with algorithms for range, bearing, offset, and line of sight
- Comparison of Hexagonal coordinate systems, including pixel to hex coordinates, and hex distances
- Hexagonal Coordinates and Distance function
- Hexagonal Grid Math, including mouse position to hex coordinate, and source code in Java and Actionscript
- Pixel Location to Hex Coordinates
- Converting mouse location to hex coordinates
- Line of Sight and Distance, plus a Java applet demonstrating field of view (includes Java source)
- Identifying directions in a hex grid [PDF]
- Grids used in Cellular Automata
I have found object oriented programming to be useful for user interfaces, operating systems, and games. At the same time, it’s commonly believed that object-oriented programming is the best way to program (especially back in the 1990s, when I started this page), but there are lots of situations where other approaches work much better. Since most of my readers are familiar with object oriented programming, the links I collect here are mostly about alternatives to the usual approaches.
- Data-oriented instead of object-oriented, and part 2
- Why data layout matters for performance
- Understanding Component-Entity Systems
- Entity systems instead of Objects, especially for MMOs. I found parts 2, 3, and 5 most useful ; also see how to apply entities to Bomberman
- What is an entity framework? - step by step, how to move from traditional OOP to entities
- Components for game entities
- Entity systems in terms of nouns and verbs
- How to represent hierarchical data in a data-oriented way
- Multiple Inheritance and RPGs
Adventure games often have good puzzle and story structures. When I started this page in the 1990s, I was especially interested in MUDs and interactive fiction. TADS was the tool to use, or maybe Inform. Since then, there have been lots more tools, such as Curveship, Hugo, Inklewriter, Twine, Quest, and ADRIFT. I never did work on an interactive fiction project, so I don’t have a great set of links. Check out the Interactive Fiction Wiki for more.
- Interactive Fiction design patterns
- The structure of puzzles in Ocarina of Time (Zelda)
- Modeling Opinions in the NPC Social Graph
- NPC Conversation Techniques
- Narrative Flow Graphs [PDF] based on Petri Nets, for representing story elements
- Big List of Plots
- Laws of MUDs
- Non-linearity in games
- Object Oriented Adventure Games
- Text vs. Graphical MUD thread [newsgroup posts]
- Text vs. Graphical MUDs (Raph Koster’s view)
- Modeling Opinion Flow in Humans: use the Boids algorithm to model human opinions in social groups
- Prose in Games
- I Have No Words & I Must Design
I usually recommend putting general rules (“find a path from here to there”) in source code and specific rules (“if sensor 9 triggers in corridor 3, make guard 18 find a path to sensor 9”) in data files. However some things fall in between and are hard to express purely as data. That’s where scripting languages come in.
Scripting languages give you a way to write a lot of non-speed-critical code with comparatively little effort. You can design the language to specifically deal with your game, so the amount of work you have to do is less than for a general purpose language. Also, you can write the compiler to optimize for different things (like size instead of speed), allow more features (like dynamic patching at run-time), and even user customization (for enthusiastic users!).
- The Secret Life of Game Scripting
- Intro to writing an interpreter: in only 90 lines of code, he implements variables, execution, higher-order functions, recursion, branching, lists, trees, and procedure calls. (Not specific to games but a good introduction)
- Rule-Based Programming and a comparison to Object-Oriented programming for game scripting
- Properties Pattern, useful to know before you design your own language
- Bytecode Interpreter pattern and implementation(New!)
- Game scripting with Stackless Python
- Building a scripting engine parts 1, 2, 3, 4, 5, 6, 7, 8, 9
- NPC Scripting
- Discussion about what language to use, how to implement [newsgroup discussion]
- Scripting languages in MUDs [newsgroup discussion]
- Implementation strategies for scripting languages [newsgroup discussion]
- Writing modifiable games
- Scripting languages used in Interactive Fiction
- Using Stackless Python and microthreads for games
As much as I love scripting languages, my recommendation is to put as much as possible into plain data files (no code) that are processed by your game. If you really need a general purpose language, use Lua. Only make your own scripting language if it’s a small game specific language. For example, a game specific script for a play might look like this:
Amit [to Steve]: Hello, friend! Steve [nods to Bryan]: Welcome to CGDC. [Amit exits left.]
Note that it’s very high level: it doesn’t specify exactly how Amit speaks or how Steve nods or even the timing. For this to work, you need to have some assumptions about how people behave, and that makes the language specific to the system you are setting up. In this particular language, the use of brackets marks actions and the colon marks speech. In another language brackets might mark optional parameters and colons mark sections. The more general purpose your language, the fewer assumptions you can make, so it becomes more verbose. For example, the conversation might look like this:
Amit.turns_towards(Steve); Amit.walks_within(3); Amit.says_to(Steve, "Hello, friend!"); Amit.waits(1); Steve.turns_towards(Bryan); Steve.walks_within(5); Steve.nods_to(Bryan); Steve.waits(1); Steve.says_to(Bryan, "Welcome to CGDC."); Amit.waits(3); Amit.face_direction(DIR_LEFT); Amit.exits();
That’s a program, not a script. See the difference? The script is high level, and specifies what you want to be done, while the program is low level, and specifies exactly how to do it. It’s not a great deal harder to interpret the first syntax than the second. You already have a programming language (C, C++, Pascal, Basic, etc.). You don’t need another! (Unless your goal is simply to allow run-time flexibility, which can be done with dynamically loaded libraries, or by using an existing language like Lua.)
Try to think differently. If you’re going to go through all the effort of making a scripting language, don’t make it look just like C. Think about using an event-based structure. For example, have commands like “when X happens, do Y.” Think about having many things happen at once. Amit doesn’t have to stop just because Steve is saying something. Think about different styles of programming, like rule based, functional, imperative, logic, and object-oriented. Think about alternate rules of logic, like fuzzy logic (truth isn’t certain) or linear logic (one truth can turn into another, making the first false). Make the language take advantage of the structure of your game, and you may find it much easier to build parts of your game world. Otherwise you’re paying a high implementation and integration price without gaining the benefit of a second language.
Economics is the study of human choices when it comes to managing resources (money, time, happiness, raw materials, goods, and so on). In many strategy games, economics is an important aspect of the design. Balancing the resources of your world can be a fun part of the game. Economics is also important in multi-player game dynamics: you want to reward people for making money, yet you don’t want them to have so much power that new players cannot have fun. One thing I want to explore is how location influences economics. In high school economics, businesses compete by price. Whichever business sells for less will win. But if transportation cost is a factor, then both businesses can coexist, and the player has to make interesting decisions about where to place new facilities to balance all the variables (availability of labor, transportation cost of raw materials, transportation cost of product, tax rates, zoning laws, etc.).
- Is it a game or a world?
- Economies in a virtual world
- AI Economics Agents
- Medieval Demographics Made Easy
- Economies of Virtual Worlds (more about macroeconomics than microeconomics)
- Medieval Price List
- Transport system in Widelands
- Economic model of Pirates of The Burning Sea: labor, prices, markets, upkeep, taxes, and world events
It’s hard to come up with rules for economics in an online virtual world when the underlying costs are so different. In the physical world, “objects” take resources to build, but they typically do not use resources to keep (if you don’t use them), and you typically do not get those resources back when you throw the object away. Therefore our real world economy is based on buying things. In the virtual world, the “objects” take a small amount of memory and if you destroy the object, you get the memory back. At the same time, the very existence of a virtual object costs CPU time, which cannot be recovered. Therefore the virtual world economy might be based on renting things. If your world’s economy reflects the underlying costs, a diamond ring may “cost” as much as a bucket of sand. Although this reflects real costs of running your server, and therefore would discourage players from overloading it, it may not make sense for your game.
In addition to the economics of objects, you have to consider the economics of living in the world. In the physical world, mere existence of a person has a cost; in the virtual world, existence is cheap. Since a player may not be “logged on” all the time, it’s hard to come up with fair rules for the cost of existence without penalizing either players who play a lot (your core audience) or players who can’t log on much (who are likely to leave if penalized for not being there all the time). If you require someone to work for a living, the casual players may not be able to compete, and may leave.
This page and other pages I have written are Copyright © 2013 Amit J Patel.
If I have a link to one of your pages or to a saved copy of something you posted to a public newsgroup, and you would prefer that I remove the link, please send me email.
I say no to exchanging links, advertising, or web rings. Don’t even ask.