Shortest Paths
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*:
These pages are about specific techniques for pathfinding and object movement:
A*
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, there are several reasons not to use A*. A* deals with discrete steps, not with continuous movement; A* 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). You can also build hybrids, where A* is used for large scale paths (between waypoints) and other techniques are used for finding paths between waypoints.
Code and Demos
The link to my A* code is to the second version [4-Feb-1998], 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.
Search for more pages on A*, pathfinding.
Tile Based Games
There are two topics that come up with tile based games: display and world representation. The two issues are orthogonal. You can have a 2-D game without tiles; you can have a tile based game with a full 3-D view.
- Tile-based games tend to have top-down (2-D) or isometric (2.5-D) views.
2-D graphics allows artists to use more detail—they can control individual pixels and form complex shapes, which is harder in a world of 3-D polygons and texture mapping.
- Tile-based worlds are made by combining small pieces into interesting patterns.
Compare Chinese Hanzi (sixty thousand complex characters forming two hundred thousand words) to Roman letters (between twenty and thirty simple characters forming two hundred thousand words). It’s much easier to create new words with Roman letters than with Chinese characters. Or compare Lego Bricks from decades ago (mostly ... bricks) to Lego Bricks today (mostly specialized pieces). It’s much easier to create new maps by combining a few simple reusable pieces than with a large set of customized components.
Search for more pages on influence maps, isometric maps, line of sight.
Hexagonal Grids
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.
Search for more pages on hexagons.
Artificial Intelligence
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
- AI Wisdom [book]
- Geoff Howland’s Practical Guide to AI and part 2
- The Current State of Human-Level AI in Computer Simulations - a list of papers, articles, and books
- 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.
- Moderator’s notes for AI Roundtable at CGDC 2003, CGDC 2002, CGDC 2001, CGDC 2000, CGDC 1999, CGDC 1998, CGDC 1997.
- Terrain Reasoning for 3D Action Games [PDF]
- Need-driven AI
- The Procedural AI in Killzone [PDF] Includes line of sight, firing range, pathfinding, and tactical evaluation at run-time
- Computer Attacks [20+ message newsgroup discussion]
- Making AI more challenging, in particular, by making it less predictable
- Strategy and Tactics by DreamWeaver [62k]
- AI in Empire-Based Games
- Extensible AI [163k - newsgroup discussion]
- Hierarchical AI
- Grenade handling AI [PDF]
- Evolutionary Approach to AI
- The Current State of Human-Level Artificial Intelligence in Computer Simulations and Wargames A list of references for game AI
- comp.AI.games FAQ
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).
Everyone talks about neural networks and genetic algorithms. I’m not going to provide any references for them. Instead, I’ll point to some techniques that are not discussed nearly enough:
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.
Search for more pages on artificial intelligence.
Object Oriented Programming
I have found that the best places to use object oriented programming are user interfaces, operating systems, and games. It’s commonly believed that objects are too slow for games, but if you use them appropriately and only where they’re a benefit to your design, they should not be a major problem for speed. It's also commonly believed that object-oriented programming is the best way to program, but there are lots of situations where objects are worse than other approaches.
Below are articles related to object oriented design but not specifically about games.
Search for more pages on objects.
Adventure Games
Although I’m not a big fan of adventure games, I’ve found that adventure game writers often have more time to work on story and game design than people working on action games. If you’re looking for story ideas or story design tips, or if you’re working on a MUD or massively multiplayer online game, take a look at these.
Search for more pages on interactive fiction, adventure games.
Game Design
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
- Too Many Clicks! Design the UI around the things the player wants to do, not around the objects in the game.
- 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
- The Design of Online Economies: Part 1 (Currency), Part 2 (NPC Merchants), Part 3 (Items), and Part 4 (Skills)
- The Essence of Computer Games
- The Art of Computer Game Design
- Evolutionary Design - why you should get something up and running before designing everything about your game
- Classification of game genres
- Persistent Myths about Game Design
- The Myth of Replayability
- The "death penalty" in games
- 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
- 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
- The Future of Game Design
- 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
- Self-Explanatory simulations in games
- The Focus of Gameplay
- UI for games: displaying information vs. immersion
Search for more pages on game design, design documents.
Scripting Languages
One of my favorite topics is scripting languages, but I don’t see much discussion of them as related to games programming. I think that 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!).
I think for the best results, the scripting language should be game specific. I want to be able to write scripts, not code. For example, a 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 Python.)
Try to think differently. Your scripting language doesn’t have to 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.
Search for more pages on scripting languages.
Economics
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.).
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.
Notices
This page and other pages I have written are Copyright © 2008 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.