Blobs in Games

From Red Blob Games's Blog

Selecting objects in a 3d world #

Once I can move around in my game world, the next step is to interact with objects. I need to determine what object, if any, the mouse points at. There are three general approaches I know of:

• OpenGL picking. In OpenGL, you can use “selection mode” to identify which object the mouse points at. This involves assigning a number to each object using glPushName/glPopName, then re-rendering the portion of the scene very close to the mouse pointer using gluPickMatrix and glRenderMode(GL_SELECT), then looking at the object numbers that were rendered by reading from the glSelectBuffer array. In theory, you can re-render using exactly the same rendering code. In practice, you want to skip expensive operations like setting up textures, drawing outlines, using shaders, etc. Once you determine what object was drawn at that location, you still don't know exactly where the mouse points. I used this approach in SimBlob 2 and was somewhat unhappy with it. It's easy but it's sort of ugly.
• Raycasting. The mouse pointer is a 2d location, and it translates into a ray in 3d space. In theory, the ray begins at the camera and goes back into the distance. In practice, the ray begins at the near plane of the viewing frustum and goes through the far plane. You can use gluUnProject to determine where the ray is; use z==0 for the near plane and z==1 for the far plane. Raycasting works well if you have kept the geometry of all of your objects; it's more of a pain if you generate it on the fly (as I did in SimBlob 2). You have to implement ray-object intersection for all of your object primitives (triangles, boxes, etc.), and it helps if you have a scene graph or spatial partitioning tree so that you don't have to intersect the ray with every object in the world. Once you perform the intersection, the closest hit tells you not only which object is involved but where on that object the mouse points. This approach requires the most work but it's the most reliable and has the best accuracy.
• Depth buffer. Just about everyone is using the depth buffer in a 3d program. Once you render your scene, OpenGL has the depth (z) value at every pixel. You can ask for the z value with glReadPixels. You can then compute the world space location of the mouse pointer using gluUnProject and the z value you just read. The final step is to determine what object is at that location. This approach is easy, but the depth buffer doesn't have much precision, the precision varies among graphics cards, and the depth buffer is altered when using polygon offsets, so it's not reliable. Another disadvantage is that translucent objects get in the way because they show up in the depth buffer.

I started out using the depth buffer approach, but I've switched to raycasting. The depth buffer has too little precision to give me the accuracy I wanted. I also wanted to distinguish between game objects (selectable) and translucent annotations (not selectable), and the depth buffer doesn't give me that level of control.

Labels: programming , project

Navigating a 3d world #

As I implemented navigation in my 3d world, I had a set of choices to make about how navigation should work. There's a camera with some position (x, y, z) pointing in some direction (θ, ρ) and some type of lens (field of view). That gives me 6 variables for the player to control, and that seems like too many.

• Scrolling (Panning). If you scroll “up”, what direction does the document go? In most GUI systems, the document goes down. Try it out in your web browser. As you drag the scroll bar up, the document moves down. However, some types of documents move the opposite way. Try visiting Google Maps and drag the map around. As you drag the mouse up, the document (map) moves up. The difference is in what you are dragging. In most applications (including web browsers), you are dragging the view. If you move the view up, you move towards the top of the document, which means the document moves down. If however you're dragging the document, it goes in the other direction. I have been playing Black and White 2 lately, and in it you drag the map. I initially chose to drag the document (map), but then changed it to dragging the view (camera).
• Scroll controls position or velocity. If you drag the mouse pointer, does it control the position of the scrolling or the speed? If you have Firefox or Opera, try the autoscroll feature and compare it to using the scrollbar. Autoscroll controls the speed; the scrollbar controls the position. The advantage of controlling the position is that it feels easy to control, especially when combined with dragging the document. The advantage of controlling the velocity is that you can move around the entire game world without repeatedly lifting the mouse, dragging across the screen, then lifting the mouse again. Some applications offer both. Google Earth and some OpenGL demos let you drag to control the position, but if you let go while still dragging, it sets the velocity. I find this very hard to control. I chose to make mouse dragging control only the velocity.
• Rotation. The camera direction has two degrees of freedom, whether you use angles or vectors, so you need two controls for full control of it. Some games restrict the camera, and thus may only need one or zero controls. I chose to fully allow rotation around the z axis and offer minimal control over rotation of the other axis (looking up and down). Given rotation, there is a choice of rotation point. Black and White 2 is unusual in that it rotates and zooms around the position you point to with the mouse. It gives more control but I found it disorienting. I instead chose to rotate around the center of the screen. The best rotation point is likely to be something closer to the camera than what I've chosen, but rotating around the center of the screen is easier to implement.
• Type of zoom. There are two approaches to zooming. You can change the lens. A “telephoto lens” has a small field of view and corresponds to “zoomed in”; a “wide-angle lens” has a large field of view and corresponds to “zoomed out”. (I'm being a bit imprecise; see this article and the comments if you want the details.) You can also change the position. Moving the camera close to the subject makes it “zoomed in”; moving it far from the subject makes it “zoomed out”. These two approaches are not equivalent. I chose to keep the lens fixed and move the camera around for zooming. Dragging the mouse up or down moves the camera up or down, which also rotates the view somewhat. When the camera is up high, it's rotated to point top-down; when it's near the ground, it's rotated to point forwards.

I started with 6 variables to control. Dragging the mouse occurs in 2 dimensions, allowing control of 2 variables per button or modifier. For a typical strategy game, god game, or city builder, the player can move around the entire map, so you probably want to control camera position (2 or 3 variables), camera direction (1 or 2 variables), and zoom (1 variable). For a first person shooter, the camera must remain at the player's location, so you'd probably want to control camera rotation (2 variables) and zoom (1 variable). For a third person RPG, you probably want camera rotation (1 variable) and zoom (1 variable).

My game is a simulation, so I want to move the camera in at least 2 dimensions, plus 1 variable for rotation and 1 for zooming. I don't allow changing the camera lens, so instead zooming involves changing both the camera height and rotation. That leaves me 4 variables to control with mouse drags. I'm reserving the left mouse button for interacting with game objects. I've chosen to assign the right button to scrolling (2 variables); and the middle button to rotation (1 variable) and zooming (1 variable). These mouse dragging rules make the mouse dragging always control the camera, not the map. They're simple and self consistent. They aren't perfect, but I'm happy with them so far.

Labels: programming , project

Rough sketch for a transportation game #

As I thought about the things I learned working on the SimBlob project, I realized that I hadn't explored a lot of the topics I originally wanted to explore. I spent my time playing with environmental simulation (water, weather, fires, dams, floods, vegetation, etc.) and never got to anything else. I decided to start over and focus on a few topics in a simple game. In my new project I'm going to explore economic simulation and transportation networks. I have a rough idea of where I'm going, but as I learn things, I expect that the design will change.

There are lots of transportation/economic/city games out there: Railroad Tycoon, Transport Tycoon, SimCity, Simutrans, Locomotion, Transport Giant, Traffic Giant, Industry Giant, LinCity, A-Train, Capitalism, The Settlers, Mobility, and probably many more. There are also many projects in development (some abandoned): Transport Empire, OpenCity, 3DTT, Widelands, Zugspiel, and of course, BlobCity.

My intent is not to clone one of those games, but instead to explore economic and transportation models by writing a game. Throughout history, transportation has affected the development of business and vice versa. The Phoenicians used ships to transport goods, and built a trading empire that lasted a thousand years. The Romans built roads and aqueducts. The Arab empire was based on trade between the east and the west, using caravans and ships. In the United States, railroads greatly altered the flow of goods and linked the west and east coasts. The Panama Canal and Suez Canal helped goods flow by ship. In the late 20th century, advances in transportation made possible the rise of FedEx and the flow of cheap goods from the Asia Pacific region. The use of standard shipping containers linked ship, rail, and truck transportation systems together. None of the games I've tried explore all of these ideas. Have you ever seen a crossdock or Less-than-Truckload shipping in a computer game? I've been fascinated with these topics and would like to explore them in a simulation game.

The basic idea of the game is that businesses trade with each other using an inefficient transportation network (such as people carrying boxes on foot), and the player can offer better forms of transportation. As transportation gets cheaper, the businesses make more money, so they expand. The number of businesses goes down, but the size of the businesses goes up. Increased volume and a change in business structure means the player has to adapt. The player has to choose among hand delivery, hand trucks, carriages, gasoline powered trucks, large trucks (semi-trailer trucks), rail, and ships. As volume goes up, the basic unit being transported gets larger as well, from individual products to boxes to pallets to containers. Upgrading too early is wasteful; upgrading too late is inefficient. Reliable transportation infrastructure can affect how businesses and cities develop. The player has to choose areas of the world to develop, structures to use for each type of good (central distribution, multiple hubs, point to point), sharing among multiple types of goods, temporary storage (warehouses), and modes of transport. As times change, the player has to monitor the efficiency, health, and profitability of the networks and choose which to upgrade, replace, or dismantle. I'm really not sure whether such a game would be fun for anyone but me. I tend to like logistics in games.

Given that game programming is just a hobby of mine (and I have plenty of other hobbies), I think the basic idea is too ambitious for me to attempt at first. Instead I'll design a simpler game and work on that. I've found in the past that if I take big steps, I'm more likely to fall, so I've learned to take small steps. I also don't want to spend forever on this game; I have plenty of other topics I want to explore. Once I've decided my next steps, I'll post them here.

Labels: design , project

Getting started, 3d world #

I'm starting a new game project, not because I think I'll write a cool game, but because I want to explore some ideas (economic simulation and transportation networks). I decided to use 3d graphics for two reasons:

• I want to learn more 3d programming. I've played with GL and OpenGL for a long time but I've never been completely comfortable in a 3d world. Each time I write an OpenGL program, I learn more about 3d graphics programming.
• Ease of programming. I believe it's easier to work in a 3d graphics system than in a 2d graphics system, until you get to the point where you want artwork. Since I don't expect to have nice artwork, I think 3d graphics will be easier. The graphics card handles things like isometric views, filling polygons, gradients, lighting, and textures. There are simple approaches for mapping screen coordinates to game coordinates and back, because the graphics card does the mapping. It's very simple to alter the appearance of objects for highlighting and mouse manipulation; you can just change the color or lighting. And the CPU is freed up for doing things like AI and world simulation.

I started out writing a simple GLUT program that set up a window and the camera, then drew a simple triangle. Once I got it running, I added stub code for the standard set of GLUT callbacks (mouse handler, keyboard handler, window resize handler). I changed the scene from a simple triangle to a square grid, added a mouse handler that highlighted the current square, and made the right mouse button drag the camera around. I then started refactoring the simple GLUT program into modules (mouse, camera, timer, vector algebra, etc.), added simple lighting, improved the camera dragging code, and added some cubes to the scene. I implemented collision detection between rays and boxes and then used that to highlight the object the mouse pointed to.

Working a little bit each night, I've spent a week on all of this. It's all graphics code and no real game code. Have I gotten stuck in a “tar pit”? No, although there are some things like lighting and gradients that are dangerous to spend too much time on, I think this initial time setting up the 3d world will be well worth it later on.

When I work with programming languages, I really appreciate having an interactive prompt. Lisp, Scheme, and Python are much more approachable because they have this. I can just start Python and inspect variables, create and change objects, explore, test, etc., all without having to go back to my code and insert new commands. You can also do this with interactive development environments (like Smalltalk's). I want something similar at the game level, where I can move around freely and click on an object to see all of its properties. I'd like to create, destroy, and modify objects as the game is running. I don't expect to build all of this at the very beginning, but having an infrastructure that exposes all the game objects in a uniform way will help me later on. How much do I really need at this point though?

Two of the approaches used to uniformly represent 3d objects are scene graphs and spatial partitioning (BSP trees, octtrees, bounding box trees, etc.). Scene graphs are useful for representing changes to lighting, scale, rotation, translation, color, material, textures, and objects with shared components. For example, instead of representing a complex soldier 3d model for each soldier object, you'd store it once and have it occur multiple times in the scene graph, each time with a different rotation and position. Spatial partitioning is useful for collision detection. For example, instead of testing every vehicle against every other vehicle to see if any of them collided, you would partition space into smaller areas and only test vehicles if they are in the same part of the game world. Both scene graphs and spatial partitioning can also be used to render only the objects that are visible in the scene; this can greatly speed up the rendering.

I've decided that the number of objects in my game is small at the moment and is likely to stay small for some time, so I will use the brute force approach. I'll test against every object for collision detection, I'll render every object and let the graphics card figure it out, and I'll replicate geometry (vertices, colors, normals, etc.) for each object. At some point I may need scene graphs and spatial partitioning, and I'll go back and add them in. Code that depends on whether I have a list or a scene graph should remain as isolated as possible, so that I can switch later.

Having written a minimal 3d world rendering system, I'm ready to go back to designing more of the game. While exploring new ideas, I tend to alternate between design and implementation. What I learn from implementation feeds back into the next round of design, and working on the design lets me step back from the implementation to see the big picture.

All the code for this game is open source, under the MIT license.

Labels: project

Getting started, again #

I'm starting a new game project. First, I made a list of my goals (which mainly involve trying out new things). Then I sketched out the idea for a game and thought a little about how it would play and what I would learn by programming it.

Before starting to program though, I started by setting up my programming environment:

1. Version control. I set up a Subversion repository on local disk. Later: set up a remote repository, either on a web server or using some code hosting service like Sourceforge.
2. Makefile. I set up a simple Makefile that should work on Linux, Mac OS X, and Windows/Cygwin, using conditional compilation to isolate the platform-specific rules. Later: figure out automake or makemake or one of those other cross-platform build configuration systems.
3. Notes file. I created a text file where I will keep all my notes. It needs to be something easy to edit and search through. Later: use a wiki?
4. Backups. I have a script that uses rsync over ssh to copy the Subversion repository to another machine. Later: get an off-site backup solution.
5. Install VMWare. VMWare offers their Player for free, and they also offer an Ubuntu Linux image for download. It was very easy to set this up. After Ubuntu started up (inside VMWare, running inside Windows XP), I had to install a few more packages (g++, OpenGL+GLUT development libraries, GNU make), but after that I was able to test my code on Linux. I don't have a similar setup to test on the Mac. Later: set up a script that will periodically sync with the Subversion repository, attempt to compile, and email any error messages to me.

After setting up the development environment, I wrote a simple 3D application. I find it much easier to extend existing code than design everything up front and write it all at once, so I start by writing a very simple program that I can then extend.

My next step on the design side will be to write down a more detailed description of the game world, what the player is supposed to do, and why the task is fun/challenging. My next step on the implementation side will be to figure out how I want to represent the game world.

Labels: project

Change of Direction #

As I worked on SimBlob 2 and learned more about 3D graphics, I started changing the game from hexagonal to triangular grids. I then got distracted and started writing an article about grids for my game programming site. While writing the article I realized that there are so many other topics I wanted to explore with SimBlob, and never got around to them. Why?

I spent most of my time in SimBlob 1 (1994-1998) exploring terrain generation, hexagonal maps, water flow, erosion, multithreaded programming, and GUI libraries. I spent most of my time in SimBlob 2 (2002-2005) exploring terrain generation, hexagonal maps, water flow, erosion, and 3D graphics libraries. There's a lot of overlap there. I ended up exploring a lot of the same ideas again. I love those topics, but they've become “tar pits” for me. I get stuck, tweaking and trying out new variants, trying to make it just right. In the end I've learned something and had a lot of fun but haven't gotten much done. Since I am writing games as a hobby, that's just fine, right?

The trouble is that when I get stuck doing one thing repeatedly, I am not spending my time trying out new things. I want to use games to explore environmental simulation, business simulation, city simulation, transportation systems, autonomous agents, machine learning and AI, control theory, and emergent behavior. Of these topics, I've spent most of my time focusing on environmental simulation. I think that was fine the first time, but after recognizing the tar pits in SimBlob 1, I created them again in SimBlob 2, and ended up getting stuck again on the very same topics.

I've decided to stop working on SimBlob 2 and start working on a new game. I'm avoiding the tar pits I've had in the past (terrain, water flow, erosion, hexagon/triangle grids) by having a completely flat grid with square tiles and no water. Sometimes doing something quite different is just what you need. I want to explore 3D graphics some more, but the main focus will be on economic simulation and transportation systems. I expect to find new tar pits to get stuck in. :-)

Labels: project

Polite games #

A few months ago I mentioned that Guild Wars is polite, and as a result, I play a lot more. I still play Guild Wars occasionally. It's so easy to start up, and I don't have to go find the CD.

The two games I've gotten since then are The Movies and Black and White 2 (both from Lionhead Studios). Both of them have long startup sequences. They show me splash screens and advertisements (for Intel and ATI) every time. Then only after the splash screens are shown does the game start loading. At the very least the game should load while the splash screens are up! In addition, the CD has to be in the drive for the game to start. That means it's a major pain to go back and forth between the games.

I find that I'm playing the polite game more than the impolite games. If I'm in the mood to play a game but I have to go find the CD, I'm less likely to play that game. And every time I have to sit there looking at the Lionhead Studios logo, I'm reminded of the company that makes me sit there instead of taking me straight to the game.

Another impolite practice used by many game companies is to use nasty copy protection techniques. I don't get games from the file sharing networks, but it makes me unhappy that pirates are getting a better game experience than I am! (Copy protection gives people more incentive to get a pirate copy instead of buying the game.) What I find totally weird is that StarForce copy protection is even used for game demos. What's the point of making a free demo uncopyable?? StarForce remains on my system even though I've uninstalled the King Kong demo. That's awful. I'm not going to buy any of those games now.

You can find instructions for removing StarForce on this StarForce Boycott site.

Make your software polite, and I'll use it more. Make your software rude, and I'll avoid it.

Update: [2006-03-12] After removing the StarForce drivers, I discovered that my CD-ROM drive was in "PIO" mode instead of "DMA" mode like it should be. This is a symptom of StarForce having been on my system. I uninstalled the IDE drivers in Windows XP and rebooted, and it reinstalled them in DMA mode. PIO mode on some newer drives causes damage over time; I don't know if my drive has suffered any damage.

Labels: review

SRE on the web #

Ten years ago, I lost the source code to Solar Realms Elite (SRE), a game I had worked on. Since then, many people have wanted to build a clone. I've tried to help them, both through email and by posting what I remember about the game's design. However, most of the projects had not gotten very far.

Yanick Bourbeau has built a web version of SRE called Imperium Galactica (which also happens to be the name of an older, unrelated game). It's fairly complete and offers a few things SRE did not (like simultaneous play by several players). I've been playing for a few days and it's fun! The game isn't quite balanced yet, but that will take a little bit of time to fine tune. Try it out!

SVG woes #

I've been working on some new illustrations for my game programming pages. In the past I had created bitmap diagrams using Gimp or by writing custom code. This time I'm using Inkscape, which produces SVG, in the hopes that I can directly embed SVG onto the web page.

Unfortunately browser support for SVG stinks.

First, not all browsers support SVG. So you need a fallback. That's fine; I can produce PNGs with Inkscape.

Second, there's the question of whether to use <embed> or <object> tags. The answer seems to be that <object> is the “right” answer, but it crashes Safari 1.0. So I should use <embed>, right? I would, except <embed> doesn't support fallbacks.

This means that I to support browsers without SVG (by using PNG fallbacks), I have to crash the Safari browser. Ugh.

Even if that problem is solved, the next problem is that different SVG implementations support different features. Adobe's SVG plugin, Mozilla/Firefox SVG, and Opera SVG are all different. Even the very simple SVG I wrote does not work the same on all three. Opera does not seem to support text at all.

Browser vendors: it's worse to have limited SVG support than no support. With no support, the fallback will be used, and the reader will see something useful. With limited support, the reader will get a broken diagram.

Even if browsers supported SVG, the web server I use does not use the correct MIME type. It sends text/xml instead of image/svg+xml. I'm not sure how much this matters in practice though. (Side note: I find it interesting the change from text to image. This is going to generally be a confusing point with XML, since it's text underneath, but the rendering of it may not be.)

I have decided not to embed SVG on my pages (although I might link to it). I will turn SVG into PNG and embed PNG on my pages.

Black and White 2 AI #

I played Black and White 2 for many hours yesterday. The computer player and I were in a stalemate. The computer kept sending armies against me and I kept defeating them. I had built my town with walls around it, and then put archers on top of the walls. I was building up my strength while defending myself, in preparation for a big attack. I felt pretty safe.

After around 40 attacks, I realized that they weren't all the same. The computer wasn't using the same attackers each time. It tried the creature, archers, swordsmen, and catapults. It tried combinations of them. Sometimes it would come through my main entrance, and sometimes it would come around the back entrance to the city. The computer player also destroyed major sections of the city using the “earthquake” power, but I recovered from these too. After a while the enemy creature figured out that he should kick my wall in. His archers and swordsmen stayed back, out of range, while the creature came up and destroyed my wall, including the archers on it. After it breached the wall, the army swarmed into my town and killed half my people.

I rebuilt my wall and started to recover, but the computer's newly discovered strategy worked well. It tried several variants but kept going back to the same approach: kick down the wall, then swarm the town. This forced me to try some new strategies. Although being on the wall has advantages, it leaves the archers vulnerable when the enemy creature attacks the wall. So I moved them behind the wall. I've also learned to open my gate, wait for the enemy army to get close, then close the gate and set their army on fire. I have no good strategy for the creature knocking down my wall though, and I'm constantly losing townspeople and then rebuilding.

After a long stalemate, the computer AI learned how to attack more effectively, and now I'm having trouble keeping my city safe. I'm very impressed by the AI. I'm not sure how it's programmed, but it tried out many different things and learned which ones work the best. From the game AI techniques I've learned (genetic algorithms, neural networks, fuzzy logic, state machines, etc.), the AI in Black and White 2 seems to match most closely with what I know about reinforcement learning. It's a technique that uses online learning (observing results as the game is played) instead of training (from examples constructed ahead of time), allows both exploration (trying new things in order to learn) and exploitation (taking advantage of what you've learned), and associates rewards (like whether the attack was successful) with actions (like kicking down the wall and keeping the army away from my archers). I recommend Sutton and Barto's book if you want to learn more. It's entirely possible though that the game uses something much simpler that just happens to look impressive, but my guess is that it's using reinforcement learning.

Labels: review