Planet terrain collision

When I started my lunar lander project several years ago the planet was a smooth disc. Detecting landings and collisions involved a simple radius check. Recently I dusted off the project and made a more complex, randomly generated terrain, invalidating that collision model. After putting the kids down for quiet time yesterday, I brewed a pot of coffee and set to work adapting collision code I'd written previously for Abyss, my Ultima Underworld hacking experiment. I have something that basically works, now, which is exciting as it is a big step toward this being a playable game.

Unfortunately there isn't much to see in still images. The rocket is prevented from going into the ground, that's all. I've included a couple of random screenshots just to have something to look at. Here's a shot of the final approach for a landing. The dim blue line is the ballistic trajectory and the brighter line is the powered trajectory. It's important not to let the powered trajectory dip below ground level!



This is zoomed out a lot more and shows the chaotic nature of the terrain that I've got at the moment:



The terrain generator is very simple, and generates inaccessible pockets of air inside the planet as well as floating islands in the sky. The floating islands are kind of cool; the inaccessible caves are just taunting; I need to remove them in a post-process.

For physics purposes, the terrain is represented by a binary space partition; the BSP divides up space into about 20,000 convex polygons (depending on the random terrain), some of which are solid and some of which are air. I use sentinel values in the child pointer slots of a BSP split node to signal solid and empty leaves, so there is no storage allocated for the leaves themselves. Each split node costs 20 bytes: the three line equation coefficients and pointers to its two children.

The rocket is currently represented by a disc. (Yes, eventually it will be more complex.) To detect intersections between the BSP and this disc, I traverse the BSP tree depth-first, building a stack of the currently active splitting lines. If the disc straddles a split line, the branch not taken is saved on a stack to be visited later. Otherwise I just go down the side containing the disc.

When the recursion hits a solid leaf, the stack of active splitting lines implicitly defines the polygonal region for that leaf. I have a function that returns the smallest separating axis between this region and the disc. If it turns out that the disc and the leaf region are overlapping, I generate a contact constraint in the direction of the separating axis.

This week I also switched all the code to 32-bit floating point arithmetic; large portions of it used 64-bit precision as a holdover from my orrery project. I also was able to reduce the integration from fourth-order Runge Kutta to a second-order method (Heun's). The main place this shows differences is when orbiting under high time acceleration.

One of the remaining top priorities is coming up with an adequate camera control algorithm. I'd really like to minimize the amount of manual control necessary, so I have to figure out what is important to show. Making a more complex rocket model, with shock absorbing landing gear, is another.

Lunar lander terrain progress

I've been working on the terrain and camera control for my “Lunar Lander on a round planet” project.

The planet generator now creates a BSP representation of the terrain in addition to the boundary representation, to be used for collision and contact.

I downloaded the latest version of the Box2D physics engine to use as a reference. The released version has only convex polygons and circles as its physics primitives; I would need to compose a bunch of convex polygons to make the terrain. Apparently there is an unreleased version with an edge-list primitive, which could also work for the terrain.

Box2D and Chipmunk use spatial hashing rather than BSPs. I'm not sure yet which would be best for my planet; I'm going forward with a BSP for now. I have an idea for computing contact with BSP leaf nodes using the split planes to implicitly define the convex polygon around the leaf. That ought to use memory fairly efficiently.

When I started the BSP implementation I tried to set it up such that the deepest splits would identify which of their leaves were inside and which were outside (based on the surface normal). The idea is to avoid having any storage for the leaves; only for the splits. I think that only works if your splits always lie on the surface somewhere, though. I ended up using two sentinel values to represent inside and outside leaves (instead of the one sentinel value you'd need for the other scheme) and it simplified things considerably.

Implementing ray intersection against the BSP terrain has allowed me to experiment with some camera framing algorithms. Framing the ballistic trajectory is good for some situations. One problem is that the impact point can change distance instantaneously which makes the camera jump around. I also tried shooting a bunch of rays in all directions to form some sort of idea of the locally visible terrain, but this also tends to change in jumpy ways. Currently I'm working on an algorithm that is based primarily on the specific mechanical energy, since that changes smoothly.

Generating terrain with lots of tunnels made me realize that I needed to enhance my gravitation formula to work inside the planet. The force of gravity falls off linearly as you work your way from the surface to the center.

Perlin simplex noise

I'm now working on my lunar lander program again. The core idea is to adapt Thrust gameplay for a circular planet, so that orbiting is a possibility. My goal is to release something in early December.

The top priority is to get an interesting planet to land on. I am working from these sources, albeit translating everything into two dimensions:

• Ysaneya's journal
• GPU Gems 3 Chapter 1
• Simplex Noise Demystified

The basic idea I'm trying out is to define a density function over the plane, and then evaluate it to find the boundary where density crosses from negative to positive. The density function can be built up out of a variety of pieces; at the moment I'm starting with a radial increase with an offset (d = r - 1):



Layered on top of that are several octaves of Perlin's simplex noise. The first two are shown below:





I convert the implicit function to a surface by subdividing a large triangle that encompasses the planet; you can see its outline (cropped by the window rectangle) in the pictures above.

Below are the results of layering the radius function with three octaves of noise:







There are lots of other things to try; this is as far as I got last night.

The next step is to build a BSP or spatial hash in order to make the terrain solid. That should not be hard. After that I will probably want to triangulate the interior and texture it; I'm still thinking about the best way to accomplish that.

The noise functions don't guarantee that everything will be interconnected. You can see free-floating bits, as well as isolated pockets of air inside the ground. It might be nice to filter out the isolated pockets, and maybe justify the floating junks of rock by rendering a background layer to suggest that it's the cross section of an arch.

Mr. Roboto

The Joel Test is a good starting point for gauging the level of professionalism where you work, or are thinking of working. One of the twelve items is “Do you use version control?” While this is incredibly important on its own, there are ways you can enhance your use of it.

The Perforce revision control software comes with a sample Python script for emailing out change notifications to everyone on the team. I improved the mail formatting a bit and we run it every fifteen minutes at work. I think it's a great motivator. After checking something in I find myself looking forward to receiving the email. When someone checks in a particularly important change people will hit “Reply” and congratulate them, providing even more positive feedback.

Change notifications are good to push to the team, as opposed to being fetched from a wiki or database, because they affect people in ways both expected and unexpected. It's good to know, even in a peripheral way, what's going on. Our art team receives all the same checkin emails, and often when something goes haywire it gives them a starting point for tracking down the problem. Similarly, sometimes a coder will see a checkin email and realize that the reviewer missed something: some of the checked-in code is a duplicate of something that already exists, say. It's easy to hit “Reply” and send the information to the person who made the checkin.

We've found other uses for automated emails at work. Once a week people get an automated email summarizing their open bugs, for instance. Another emailer that has acquired a personality of its own is Mr. Roboto (so named because it signs emails “Domo arigato, Mr. Roboto” after the Styx song).

Often an artist will create an entire suite of new files—model, sub-models, textures, and so forth—but forget to check in some of them. Since they have the complete set of files on their local machine they don't see that there is a problem for everyone else. It can be tedious to track down the responsible party by hand; thus the birth of Mr. Roboto.

Mr. Roboto does a dependency analysis every fifteen minutes and identifies files that reference missing files. Then he goes spelunking in the version control database to figure out who the likely culprit is. Currently he considers two scenarios: that the missing file was deleted, or that it was not added. If the missing file is in version control but has been deleted, Mr. Roboto complains to the person who deleted it. Otherwise, Mr. Roboto complains to the last person to change the file with the broken dependency.

This catches a lot of the most common problem cases. Obviously there are scenarios where this fails. For instance, I run scripts to do automated changes to large batches of art files periodically. Once I've done that I become the last changer on those files so complaints related to them come my way. It isn't too bad, though, and it encourages us to keep everything clean. Most of the time we aren't missing files, which has not been the case on previous projects I've worked on.

Since we now run Mr. Roboto every fifteen minutes to catch problems quickly, we ended up adding a throttling mechanism so he'd only complain about any given file once a day.

Makeover Concept

Been thinking about possible graphical overhaul of ThiefRL. Basic idea is to keep things very symbolic (since realism is expensive and possibly less readable) while still making them more attractive.



I'm a fan of David Macaulay's books and am attempting to ape his illustration style to some extent. The left-hand side is crappy but I was experimenting with different line weights; ideally you'd have one or two line weights in the final drawing. I also need to figure out how to lay in ground texture while keeping it distinctly in the background. There could be watercolor-style washes of pale color under the ink-work.

There is a paper texture (not a great one) and some vignetting to suggest an overhead light source. The ink lines have been filtered a bit to look like they have bled a bit into the paper. People might be represented by tokens or push-pins on top of the page. It might be interesting to have little drops of blood soak into the paper and gradually oxidize at the spots where people are injured.

Compare to original ASCII-based shot:



Not everything has been transferred to the mockup. The aspect ratio of the mockup tiles is 1:1 while the screenshot tiles are 1:2, as well. Buildings would be redesigned to not looked squished under the square aspect ratio.

I've been kicking around the idea of putting walls on the lines between squares (instead of running down square centers) while I'm at it but I'm unsure if it would be a good idea or not.

You definitely get more of a “night” feel from the original. Maybe the “blueprint” look is not the best way to go.

Screenshots

Due to various computer crashes and restorations I've ended up with several different versions of some of my main projects, with the rest scattered about. I've been sorting and consolidating them all into a single set, updating where possible to compile with Visual C++ Express 2008 and Direct3D 9.

I may need to break down and buy Developer Studio again; some of my projects use MFC or WTL and neither of those comes with the Express edition. I have one project (my 64 KB shooter) which needs to compile without the C runtime library; the new compiler is producing calls to a bunch more functions such as __IAtan2. The Express edition also does not include source for the C runtime library, so I haven't yet figured out what those functions are supposed to do.

“Penultima” started out as a turn-based game written as an exercise for a Mode X sprite system based on Michael Abrash's articles. Later, I was working on a COFF-based sprite animation system under DirectDraw, where the sprites are compiled into COFF-format object files (an almost entirely redundant phrase) and linked directly into the executable. I used this project as a testbed and turned it into a real-time game, although the gameplay isn't really all there. The main character is Link from his Minish Cap outing; not my own art.

Subdivision surfaces seem like they could be a handy tool to use for level construction. Here they're used to produce a cave-like space. I plan to revisit this soon; it ought to provide a good challenge for physics simulation.

These people are attempting to mill about without hitting each other; a project where I was exploring crowd movement. I think they're pretty cute; they also show up as bystanders in my 64 KB first-person shooter.

This is Marion Wolfe, love interest from Outcast, in her funeral bier. Outcast is a fantastic game and one that I spent quite a bit of time hacking on, deciphering the file formats.

When I was working on my 64 KB FPS I thought a lot about how to construct levels from tiny amounts of data. This house is made from a very simple input file describing the floor plan, and some descriptions of the door and window features. I'd love to pick this up again and expand on it; working from floor plans is a really quick way to build an environment.

After I finished Psi Ops I had some down time so I wrote an orrery. It uses massive tables of orbital elements from JPL to position the asteroids, planets, and comets. This shot illustrates the remarkable way in which Jupiter's gravity collects asteroids at points 60 degrees ahead of and behind it in its orbit.

This is the first level of Ultima Underworld: the Stygian Abyss. Another wonderful game that I've spent many hours hacking. Once I had the dungeon rendering it turned out to be a great place to work on first-person motion dynamics. Perhaps someday this will turn into a full-fledged remake, but there would be a lot of work to get to that point.

Knarly Hexes

Go try Knarly Hexes, the latest game from Everett Kaser.

It uses the same mental muscles as Minesweeper but, being a Kaser game, has more interesting logic deductions and a comprehensive hint system to teach them all.

I also played the Geneforge 5 demo this week. The game presentation has definitely improved from the last Geneforge game I played.

In terms of work, here are a set of common HDTV and notebook display resolutions, and the tile sizes that divide evenly into them. (The minimum size I did was 10; there are several smaller tile sizes that would also work.)

Resolution	Tile Size	Grid	# Tiles
1280 x 720	10	128 x 72	9216
	16	80 x 45	3600
	20	64 x 26	2304
1280 x 800	10	128 x 80	10240
	16	80 x 50	4000
	20	64 x 40	2560
1440 x 900	10	144 x 90	12960
	12	120 x 75	9000
	18	80 x 50	4000
	20	72 x 45	3240
	30	48 x 30	1440
1920 x 1080	10	192 x 108	20736
	12	160 x 90	14400
	20	96 x 54	5184
	24	80 x 45	3600
	30	64 x 36	2304