Blobs in Games: 2006-02

From Red Blob Games's Blog

Transportation game, basic objects #

I wanted to start with something simple for my transportation game. I want to explore the transportation of goods between businesses. I created a simple model:

• Business. Each business (labeled B in the diagram) can consume and produce items. For example, a steel mill consumes iron and produces steel. Some businesses only consume; some only produce. In my initial implementation, there is only one producer (a dock, where goods are imported from other areas) and one consumer (a retail store, where goods are bought).
• Cargo. The goods and materials are put into containers (crates, boxes, pallets, etc.) and the containers (labeled C in the diagram) are moved around the game world. Each container represents some amount of material or goods. In my initial implementation, there is only one type of cargo (“goods”) and only one size of container.
• Loading Areas. A business may not consume goods as soon as they arrive, and it may produce goods that are not immediately picked up. Loading areas (labeled A in the diagram) are a place for cargo to be stored.

I haven't yet chosen good terminology. Is it business or building? Is it cargo or container or goods? Consistent use of terminology will help in picking good names in the code. I want to choose names that are general enough to cover a wide variety of cases.

I think the model has some nice properties. It's very general, so it can apply to many different kinds of businesses. For example, a warehouse is a business that produces the same thing it consumes, and consists almost entirely of loading areas. The loading areas make it easy for the player to see when the transportation system is working too fast or too slow. However, there are a lot of unanswered questions at this point. Does each type of cargo require its own loading area? Does a business buy from just anyone or does it choose its suppliers? How are perishable goods represented? I will leave these questions for later and focus on the simple case: one producer, one supplier, one type of cargo.

Labels: project

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