Amit's Game Programming Information

Determining how to walk 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). I've been writing some pages about path-finding algorithms and ideas; John Lonningdal has several pages about algorithms that are simpler to implement; and I've also saved some articles from newsgroups. These are pages about pathfinding in general, with some bias towards A*:

• Amit's Notes about Path-Finding (including A*)
• Smart Unit Navigation and Pathfinding Page (several alternatives to A*)
• Vehicle Pathfinding (long)
• Technical papers about navigation and paths [53k]

These pages are about specific techniques for pathfinding and object movement:

• Using Regions for Shortest Path
• Shortest Path vs. Maze Solving Algorithms
• Applet showing obstacle avoidance
• Motion using Potential Fields

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 unclear whether A* is the best choice when there aren't terrain costs to worry about; another algorithm may be optimized for fixed movement costs. Also, A* deals with discrete steps, not with continuous movement, so other algorithms are better when you want to find a continuous path (like a spline path). 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. From an implementation perspective, A* may be more difficult if you aren't familiar with some forms of mathematics (graph theory, at least).

• Using A* to find the shortest path
• An A* Tutorial (with C++ code)
• A Java Applet demonstrating A*
• Path Finding - long newsgroup discussion [290k]
• Choosing a heuristic for A* (and other performance notes)
• An explanation of A* by James Matthews as well as A* Explorer, an application (for Windows only, sorry) that lets you step through the A* algorithm.
• Speeding up A* by dropping admissibility
• A* Optimizations - newsgroup discussion [46k]
• A* references
• Patrick Feuser's A* code (C++ Source)
• My own A* code (C++ Source and header file ), and Petr Sulla's improvements.

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.

Although the latest games seem to use 3-D rendered worlds, tile-based (2-D or isometric) games appeal to me because they tend to have more work put into the game play and less in flashy graphics. Two recent games that use isometric displays instead of full 3-D worlds are Roller Coaster Tycoon and SimCity 3000. In these games, the artists can put in details that you may miss with 3-D polygons. You can get quite a lot of bang for the buck when using tiles -- building worlds from a few key tiles is somewhat like building hundreds of thousands of words from just a few letters. I'm fascinated whenever the whole is much greater than the sum of its parts, and tile based games are no exception.

• Tile based maps (an introduction)
• Isometric views (an introduction)
• Isometric Views (another introduction)
• Isometric Engines - are they for you?
• Tile-based games FAQ
• Tile-based games techniques
• Why 2D is Better than 3D (not specifically about games)
  
• Line Of Sight Algorithms
• Determining the range that a unit can move to
• Influence Maps Thread [65k]
• An Influence Map Applet
  
• Data structures for tile based games
• Isometric Maps and file formats
• A file format to handle linked lists of objects
• The Case for Random Maps
• More Tile Game Information

Search for more pages on influence maps, isometric maps, line of sight.

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 therefore used by bees); 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.

• Numbering Systems; Distances; Angles
• Isometric Cube Coordinates
• The HexPart numbering system with algorithms for range, bearing, offset, and line of sight
• Pixel Location to Hex Coordinates
• Line of Sight and Distance

Search for more pages on hexagons.

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!

I've collected some articles and pointers to information about artificial intelligence in games. The first link is to Steven Woodcock's AI page, which should be your first stop when looking for AI information as it relates to games. There's a lot of interesting reading here!

• Steven Woodcock's AI in Games Page
• Geoff Howland's Practical Guide to AI and part 2
• Subsumption Architecture for AI (Rodney Brooks)
• Moderator's notes for AI Roundtable at CGDC 2000
• Genetic Algorithms for Games [book list]
• Computer Attacks - newsgroup discussion [31k]
• Strategy and Tactics by DreamWeaver [62k]
• AI in Empire-Based Games
• Extensible AI - newsgroup discussion [163k]
• Simulation in Games
• Understanding Geography
• Hierarchal AI
• Evolutionary Approach to AI
• comp.AI.games FAQ

Search for more pages on artificial intelligence, genetic algorithms.

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. I've saved some articles discussing objects, games, and efficiency, and there's also a link to an object framework for tile-based games. The first listed article is especially good to read if you are concerned that object-oriented programming is slow; it analyzes the assembly code produced by C++ compilers to show how it compares to procedural code.

• Object-Oriented Programming for Game Programmers
• Object Oriented Adventure Games
• Efficiency of Objects
• OOP and Games
• OpenDoc for Games
• Multiple Inheritance and RPGs

Below are articles related to object oriented design but not specifically about games.

• Squares and Rectangles
• Quantum Mechanics and OOP
• A quantum mechanic's opinion of the above article

Search for more pages on objects.

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 (as I am), take a look at these.

• Rec.Arts.Interactive-Fiction Archive
• Interactive Fiction design patterns
• Intelligent NPC's
• NPC Conversation Techniques
• 36 Dramatic Situations
• Big List of Plots
• Medieval Demographics Made Easy
• Laws of MUDs
• Non-linearity in games
• Text vs Graphical MUDs (newsgroup posting)
• Text vs Graphical MUDs (Raph Koster's view)
• Prose in Games
• I Have No Words & I Must Design

Search for more pages on interactive fiction, adventure games.

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. I haven't seen any books I really like on this subject, but there's one that sounds promising: Game Architecture and Design. One of these days I hope to have time to read it.

• Ramblings about RPG Design includes topics such as balance, food, economy, time, death, weapons, storyline, and magic.
• The Essence of Computer Games
• The Art of Computer Game Design
• Game Designer Diaries
• Game Architecture Design
• Progressive vs. Experience games
• Designing `Realistic' Games
• Addictive Games
• Design notes for my game, Solar Realms Elite
• SimCity Essay
• Creating a Great Design Document
• Space Game Design Tips
• Self-Explanatory simulations in games
• The Focus of Gameplay
• Storytelling in an Action game

Search for more pages on game design, design documents.

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!).

• Clues for a Game Design Methodology , mostly about scripting languages for games
• Article on general language implementation part 1 , plus parts 2 3 4 5 6 7 8
• Scheme Underground (Scheme makes it easy to write other languages)
• Writing Modifiable Games including logic, data-driven, scripts, and virtual machines
• Scripting languages in MUDs (newsgroup posts)
• Data representation in scripting languages

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 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
• Dynamics of Multi-Agent Systems
• Medieval Price List
• What might be in a Medieval City?
• Campaign Economics

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.

Sometimes I have strong opinions about particular subjects, and I want to write them down. So here goes.. I've started a section on this page with rants I have made into web pages.

• C++ vs. C Programming

Possible topics for future rants:

1. Arrays vs. Lists
2. C++ vs. Java
3. Objects vs. Non-objects
4. Templates vs. Inheritance
5. Dynamic cast vs. Visitor
6. Casts vs. Conversions

Some things I just can't justify classifying, but hope that they will be of interest to game programmers:

• Why I don't write games for a living
• Advice on finding a "games programming" university
• Guide to Terrain Generation
• The Rise of "Worse is Better"
• Integrating your objects with your Shell
• How Amit uses Threads without locking
• A Critical Look at Programming Languages ; Amit can agree with the basic message but not the details, and maybe he'll rant on this subject someday

Search for more pages on terrain generation, or

This page and other pages I have written are Copyright © 2001, 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.

And finally, for those who don't know me: I am not a professional game programmer. I do not do "contract" games. I am not looking for a job. This is just a hobby of mine. Please don't write to me about exchanging links, advertising, or web rings. I'll just say no.