Monday, December 14, 2009

Another small lander prototype update

Updates will likely continue to be slight in the time leading up to Christmas.

There is a new version of the lander prototype.

Changes:
  • Increased rocket thrust: main nozzle by 75%, steering jets by 150%.
  • Added inset rocket view in upper-right corner of screen; useful when zoomed out. This will likely be replaced or augmented by indicators displayed over the rocket's location in the main display, so you don't have to look elsewhere.
  • Altered camera framing algorithm to emphasize the interesting band of radii on the planet. It can be made smoother than it is; just haven't finished yet.
  • Limited full-scene antialiasing to 4X, rather than 8X. I got really bad performance on one of the machines I tested on so this is an attempt to improve that.

Thursday, December 10, 2009

Slight update to lunar lander prototype

I've uploaded a new version to the website with a couple of small changes:
  • Tuned the steering jet controller so it doesn't overshoot
  • Changed X/Z zoom controls to operate continuously
  • Fixed camera smoothing so it doesn't lag behind the rocket

Monday, December 7, 2009

Lunar Lander: prototype version 1 released



Here is the first released version of my Lunar Lander program. It runs under Windows and requires Direct3D 9 to be installed. I had hoped to have more of a game by my deadline but didn't have time to implement much, so I've tried to tie things off so it is relatively bug-free and playable. Once some of the holiday madness subsides I will make another release.

You can fly the orange, spherical rocket around the planet and attempt to make soft landings. There are a couple of control schemes of varying difficulty. Controls in a nutshell:
  • Steer with the mouse
  • Accelerate with the left mouse button
  • Zoom view in/out with X/Z or 1-5
  • Restart if you get stuck with R
  • Esc pauses and displays additional help.
Known issues:
  • Occasionally the aiming rockets will rotate the vehicle the long way around.
  • It is possible to get positive feedback by pressing Tab to accelerate time while simultaneously increasing the orbit size; this will blow up the simulation and require a restart.

Once again, thanks to Scott Lembke for his Chipmunk physics engine, a heavily-modified version of which lurks within. Thanks also to my testers: Tom Elmer, Seth McNeill and David McNeill. Enjoy!

I've released a couple of other little games in the past:
  • ThiefRL, an attempt to amalgamate Thief with Rogue
  • SpaceRL, a very small Roguelike exploring zero-gravity movement

Merging and sizing rocket prototypes

I continue to work on my Lunar-Lander-on-a-globe. The prototype with the Chipmunk-based rigid body dynamics has been merged into the prototype with the round planet. However, the dimensions of the two were completely different: the planet has sea-level radius of one; the rocket from the other prototype had a radius of 15. I'm still attempting to get all of the physical and control parameters adjusted to make things playable.

It finally became imperative to produce a workable camera. I've left zoom control manual for now but am otherwise quite happy with what I've got. It's yet another use of a critically-damped spring, to drive the camera parameters toward their goal positions. The goal positions are chosen to interpolate based on zoom level between a small circle surrounding the rocket and a bounding circle around the planet and rocket.

Next steps are to finish tuning the physics and control parameters; implement death and reset, and add some goal landing spots. Then I think I will do a release of what I have and shift focus to holiday-related chores. Some time around Christmas/New Year I should be able to devote energy to making it into a more interesting game.

Monday, November 30, 2009

Child of Fire, Red Cliff reviews

The weekend, while long, was busy. We hosted two events: Thanksgiving and my daughter's fourth birthday party. I wasted what little free time was left reading Child of Fire: A Twenty Palaces Novel and watching John Woo's historical epic Red Cliff.

Child of Fire came to my attention via John Scalzi's Big Idea series, where authors get to plug their new books. First-time author Harry Connolly wrote an entry about his book that intrigued me despite the book's atrocious name. I finally got around to picking up a copy of the book and reading it. It's very well written and I'm looking forward to his future work. Recommended if you like Dashiell Hammett or Chandler.

Red Cliff is based on a 3rd-century battle retold in the 14th century Chinese novel Romance of the Three Kingdoms. When I worked at Midway we watched a bunch of Woo's films in preparation for working on a videogame with him. A lot of his trademark Wooisms can be found in this massive historical epic (cut down to 2.5 hours for US release). For instance, in Hard Boiled Chow Yun Fat's character blasts his way out of a hospital with a shotgun in one hand and a baby in the other. The opening of Red Cliff features a very similar incident, which I'm guessing was not in the original novel. Other Woo-bits include doves (of course) and Mexican standoffs, albeit with swords rather than guns. And random slo-mo of the duplicated-frame sort.

The characters felt really stale to me. I am interested in reading the original novel now to see if they are this one-dimensional there. The two characters that I felt stood out were Kong Rong (played by Wang Qingxiang), who was the tactical genius on the rebel side; and Xiao Qiao (played by Lin Chi-ling) who holds a Helen-of-Troy position in the story but with a strong Judith moment near the end.

I'd played one or two of the Dynasty Warriors games previously so a lot of the supporting hero characters (like Guan Yu) felt familiar. It is a little odd to have my scant historical knowledge derived from there, but that's how it is!

Monday, November 23, 2009

PID controllers

My brother is an electrical engineer; he's working on unmanned aircraft autopilots, among other things. He recommended using a PID controller. “PID” is an acronym for proportional, integral, derivative, the three terms that make up the control equation. The controller measures the error between current and desired position. It also maintains an integral of the error, and estimates the current derivative of the error. Then it linearly combines these three values to drive something intended to correct for the error.

I tried out a PD controller (leaving out the integral term). The error is the difference between the target heading and the current heading. The derivative of the error is then the current angular velocity. These are combined to drive the nozzle angle, which is clamped to stay within its movement range. It's an extremely simple controller but the results are much smoother than what I had before:



In the video I'm aiming the green arrow and manually firing the rocket. The rocket rotates freely in between firings. The steering algorithm is applied to the nozzle even when I'm not firing so you'll see it rotating in preparation to align the rocket with the arrow.

In terms of control I'm pretty happy with this. I may add some additional rotation jets to the rocket to allow rotation without adding large linear velocities; they would probably be controlled with the same algorithm.

Oh yeah: this PD controller is pretty much the same thing as a damped spring. The nozzle angle doesn't translate linearly into rotational acceleration but otherwise it is the same thing.

Monday, November 16, 2009

Rocket steering methods

My primary lunar lander prototype (not the one shown below) does not have true rigid body dynamics yet. The rocket's heading is driven directly by mouse movement. This makes it really easy to steer the nozzle but I have been unsure about how to alter it once the rocket can actually collide with the terrain in a way that applies torque. If you are able to directly rotate the rocket that could introduce unwanted interpenetration or arbitrary launch velocities.

I have a separate prototype at the moment where I am testing out the rigid body dynamics. The rocket, at the moment, has a single steerable nozzle. It will probably be necessary to add steering jets to make it easier to fly. Right now when you apply a torque to the rocket you are also applying a hefty linear acceleration as well.



The first control method is very simple to implement. The mouse rotates the rocket nozzle; the mouse button fires it. This is demonstrated in the first clip above.

In the second control method (shown in the latter half of the movie) the mouse sets a desired thrust direction. While the rocket is firing, an autopilot steers the rocket nozzle to align thrust in the specified direction. At the moment it's snapping the nozzle to one of three positions: extreme left, extreme right, and center. This is not terribly realistic; I'm still figuring out how to make it more natural.

Friday, November 13, 2009

Landing gear



(The Khrest from Perry Rhodan. Artwork by Ingolf Thaler. From Perry Rhodan Nr 278, 16 December 1967. From Winchell Chung's Atomic Rocket.)

There's a plague going around at work; I eventually succumbed. Being sick for a few days has given me the opportunity to spend a bit more time working on my lunar lander program. I have been studying a couple of 2D physics engines (Chipmunk and Box2D) because I want to add rigid-body dynamics to it.

I'd already done a previous lunar rover test with Chipmunk (it comes with a rover sample) so I added a round rocket to that to try and figure out how to design the landing gear:



In this landing gear, the upper strut is a shock absorber, while the lower strut is just a swing arm. The foot's orientation is locked to the swing arm. This is OK, but the feet are forced to slide outward as the rocket comes to rest. If they hit an immovable obstacle there is an abrupt shock to the rocket. Ideally the feet would not have any lateral force but I haven't been able to come up with a geometry for that, short of just having some pistons sticking straight down out of the rocket. Adding some shock absorption capability to the lower struts would help.

I have decided to try and use Box2D (possibly modified to use my own vector class) instead of Chipmunk. That will take some time to install. Neither engine deals with BSPs so I will probably initially represent the planet with a collection of convex polygons (which will likely take a fair amount of memory), and add support for BSPs later.

Monday, November 2, 2009

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.

Monday, October 26, 2009

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.

Monday, October 12, 2009

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:
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.

Monday, October 5, 2009

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.

Thursday, August 6, 2009

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.

Monday, July 27, 2009

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.

Monday, July 13, 2009

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

ResolutionTile SizeGrid# Tiles
1280 x 72010128 x 729216
1680 x 453600
2064 x 262304
1280 x 80010128 x 8010240
1680 x 504000
2064 x 402560
1440 x 90010144 x 9012960
12120 x 759000
1880 x 504000
2072 x 453240
3048 x 301440
1920 x 108010192 x 10820736
12160 x 9014400
2096 x 545184
2480 x 453600
3064 x 362304

Monday, June 22, 2009

Charlemagne, Disraeli, and Jefferson combined could not have done better! (in Haskell)

...but hopefully you can. I added the “in Haskell” part because I'm not sure exactly what summons the Haskelling hordes.



I finished up a first pass at translating the ancient game Hamurabi from BASIC to Haskell; I recently bought Real World Haskell and wanted to have another of my periodic goes at using the language.

The original BASIC program weighs in at 4,230 bytes and 121 lines. My port is somewhat more portly, at 10,280 bytes and 287 lines. The executable compiled by GHC is a mere 1.414 MB, which is a couple of orders of magnitude larger than the original probably would have been. Here is the source as it stands now:

-- Converted from the original FOCAL program and modified for Edusystem 70 by David Ahl, Digital
-- Modified for 8K Microsoft BASIC by Peter Turnbull
-- Ported to Haskell by James McNeill

import Char
import Random
import IO
import Text.Printf

-- Data structures

data GameState = GameState {
year :: Int,
people :: Int,
food :: Int, -- bushels
land :: Int, -- acres
landPrice :: Int, -- bushels per acre
totalDeaths :: Int,
cumDeathRate :: Double,
rng :: StdGen
} deriving (Show)

data Orders = Quit | Orders {
acresToBuyOrSell :: Int, -- negative number means sell
acresToPlant :: Int,
bushelsForFood :: Int
} deriving (Show)

data Results = Results {
peopleStarved :: Int,
peopleDiedOfPlague :: Int,
peopleBorn :: Int,
bushelsEatenByRats :: Int,
bushelsPerAcre :: Int
} deriving (Show)

data ValidateResult a = Abort String | Retry String | Accept a

-- Code

main = do
rng <- getStdGen
putStrLn "Try your hand at governing ancient Sumeria successfully for a 10-year term of\noffice."
let s = initialState rng
showResults s initialResults
doYears s
putStrLn "So long for now."

showResults :: GameState -> Results -> IO ()
showResults state results = do
printf "\nHamurabi: I beg to report to you,\n"
printf "In year %d, %d people starved, %d came to the city.\n" (year state) (peopleStarved results) (peopleBorn results)
printf "%s" (if (peopleDiedOfPlague results) > 0 then "A horrible plague struck! Half the people died.\n" else "")
printf "Population is now %d.\n" (people state)
printf "The city now owns %d acres.\n" (land state)
printf "You harvested %d bushels per acre.\n" (bushelsPerAcre results)
printf "Rats ate %d bushels.\n" (bushelsEatenByRats results)
printf "You now have %d bushels in store.\n" (food state)

doYears :: GameState -> IO ()
doYears sIn = do
let s = chooseNewLandPrice sIn
orders <- readOrders s
case orders of
Quit -> return ()
otherwise -> do
let (sOut, resultsOut) = applyOrders orders s
showResults sOut resultsOut
let fractionStarved = (fromIntegral (peopleStarved resultsOut)) / (fromIntegral (people s))
if fractionStarved > 0.45
then do
printf "You starved %d people in one year!\n" (peopleStarved resultsOut)
putStr finkMessage
else
if (year sOut) >= 10
then putStr $ finalReport sOut
else doYears sOut

readOrders :: GameState -> IO Orders
readOrders s = do
printf "Land is trading at %d bushels per acre.\n" (landPrice s)
buyLand s

applyOrders :: Orders -> GameState -> (GameState, Results)
applyOrders orders state = (stateOut, resultsOut)
where
stateOut = GameState {
year = (year state) + 1,
people = peopleFinal,
food = bushelsFinal,
land = landFinal,
landPrice = (landPrice state),
totalDeaths = (totalDeaths state) + peopleDiedOfPlague + peopleStarved,
cumDeathRate = (cumDeathRate state) + (fromIntegral peopleStarved) / (fromIntegral peopleInit),
rng = rngOut
}
resultsOut = Results {
peopleStarved = peopleStarved,
peopleDiedOfPlague = peopleDiedOfPlague,
peopleBorn = peopleBorn,
bushelsEatenByRats = bushelsEatenByRats,
bushelsPerAcre = harvestYield
}

landFinal = (land state) + (acresToBuyOrSell orders)

peopleFinal = peopleBeforePlague - peopleDiedOfPlague
peopleBeforePlague = peopleFed + peopleBorn
peopleDiedOfPlague
| plagueRandom < 0.15 = peopleBeforePlague `div` 2
| otherwise = 0
peopleFed = min peopleInit (bushelsEatenByPeople `div` 20)
peopleStarved = peopleInit - peopleFed
peopleBorn = 1 + ((birthRandom * (20 * landFinal + bushelsFinal)) `div` (peopleInit * 100))
peopleInit = people state

bushelsFinal = (bushelsBeforeRats - bushelsEatenByRats) + bushelsHarvested
bushelsEatenByRats
| ((ratD6 `mod` 2) == 1) = 0
| otherwise = bushelsBeforeRats `div` ratD6
bushelsBeforeRats =
(food state) -
bushelsEatenByPeople -
((acresToBuyOrSell orders) * (landPrice state)) -
((acresToPlant orders) `div` 2)
bushelsEatenByPeople = bushelsForFood orders
bushelsHarvested = harvestYield * (acresToPlant orders)

(birthRandom, rng1) = randomR (1, 6) (rng state)
(harvestYield, rng2) = randomR (1, 6) rng1
(plagueRandom, rng3) = random (rng2) :: (Double, StdGen)
(ratD6, rngOut) = randomR (1, 6) rng3

buyLand :: GameState -> IO Orders
buyLand s
| maxN <= 0 = sellLand s 0
| otherwise = do
choice <- readValidatedNum prompt validate defaultN
case choice of
Nothing -> return Quit
Just n -> sellLand s { land = (land s) + n, food = (food s) - ((landPrice s) * n) } n
where
prompt = "How many acres do you wish to buy (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
maxN = (food s) `div` (landPrice s)
defaultN = 0
validate n
| n < 0 = Abort abortMessage
| n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain. Now then," (food s)
| otherwise = Accept n

sellLand :: GameState -> Int -> IO Orders
sellLand s acresToBuy
| acresToBuy > 0 || maxN <= 0 = feedPeople s acresToBuy
| otherwise = do
choice <- readValidatedNum prompt validate defaultN
case choice of
Nothing -> return Quit
Just n -> feedPeople s { land = (land s) - n, food = (food s) + ((landPrice s) * n) } (-n)
where
prompt = "How many acres do you wish to sell (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
defaultN = 0
maxN = land s
validate n
| n < 0 = Abort abortMessage
| n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d acres. Now then," maxN
| otherwise = Accept n

feedPeople :: GameState -> Int -> IO Orders
feedPeople s acresToBuy
| maxN <= 0 = plantFields s acresToBuy 0
| otherwise = do
choice <- readValidatedNum prompt validate defaultN
case choice of
Nothing -> return Quit
Just n -> plantFields s { food = (food s) - n } acresToBuy n
where
prompt = "How many bushels do you wish to feed your people (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
defaultN = min maxN (20 * (people s))
maxN = food s
validate n
| n < 0 = Abort abortMessage
| n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain. Now then," maxN
| otherwise = Accept n

plantFields :: GameState -> Int -> Int -> IO Orders
plantFields s acresToBuy bushelsToFeed
| maxN <= 0 = return (Orders acresToBuy 0 bushelsToFeed)
| otherwise = do
choice <- readValidatedNum prompt validate defaultN
case choice of
Nothing -> return Quit
Just n -> return (Orders acresToBuy n bushelsToFeed)
where
prompt = "How many acres do you wish to plant with seed (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
defaultN = maxN
maxN = min landAvailable (min (2 * foodAvailable) (10 * (people s)))
landAvailable = land s
foodAvailable = food s
validate n
| n < 0 = Abort abortMessage
| n > landAvailable = Retry $ printf "Hammurabi: Think again. You own only %d acres. Now then," landAvailable
| n > 2 * foodAvailable = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain. Now then," foodAvailable
| n > 10 * (people s) = Retry $ printf "But you have only %d people to tend the fields. Now then," (people s)
| otherwise = Accept n

finalReport :: GameState -> String
finalReport s =
"In your " ++ show numYears ++ "-year term of office, " ++
show (round (100.0 * avgDeathRate)) ++ " percent of the\n" ++
"population starved per year on average, i.e., " ++
"a total of " ++ show numDeaths ++ " people died!!\n" ++
"You started with 10 acres per person and ended with " ++
show (round acresPerPerson) ++ " acres per person.\n" ++
comments

where
numYears = year s
numPeople = people s
numAcres = land s
numDeaths = totalDeaths s
avgDeathRate = (cumDeathRate s) / (fromIntegral numYears)
acresPerPerson = (fromIntegral numAcres) / (fromIntegral numPeople)
comments
| avgDeathRate > 0.33 || acresPerPerson < 7 = finkMessage
| avgDeathRate > 0.1 || acresPerPerson < 9 =
"Your heavy-handed performance smacks of Nero and Ivan IV.\n" ++
"The people (remaining) find you an unpleasant ruler, and,\n" ++
"frankly, hate your guts!\n"
| avgDeathRate > 0.03 || acresPerPerson < 10 =
"Your performance could have been somewhat better, but\n" ++
"really wasn't too bad at all. " ++
show numHaters ++ " people would\n" ++
"dearly like to see you assassinated but we all have our\n" ++
"trivial problems.\n"
| otherwise =
"A fantastic performance!!! Charlemagne, Disraeli, and\n" ++
"Jefferson combined could not have done better!\n"
(numHaters, _) = randomR (0, (numPeople * 4) `div` 5) (rng s)

readValidatedNum :: String -> (Int -> ValidateResult Int) -> Int -> IO (Maybe Int)
readValidatedNum prompt validate defaultValue = do
putStr prompt
hFlush stdout
line <- getLine
case maybeRead line of
Nothing -> return (Just defaultValue)
Just n ->
case validate n of
Accept n -> return (Just n)
Abort s -> do
putStrLn s
return Nothing
Retry s -> do
putStrLn s
readValidatedNum prompt validate defaultValue

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
[(x, str)] | all isSpace str -> Just x
_ -> Nothing

chooseNewLandPrice :: GameState -> GameState
chooseNewLandPrice s = s { landPrice = newLandPrice, rng = newRng }
where (newLandPrice, newRng) = randomR (17, 26) (rng s)

initialState :: StdGen -> GameState
initialState rng = GameState {
year = 0,
people = 100,
food = 2800,
land = 1000,
landPrice = 0,
totalDeaths = 0,
cumDeathRate = 0,
rng = rng }

initialResults :: Results
initialResults = Results 0 0 5 200 3

abortMessage :: String
abortMessage = "Hammurabi: I cannot do what you wish!\nGet yourself another steward!!!!!"

finkMessage :: String
finkMessage =
"Due to this extreme mismanagement you have not only\n" ++
"been impeached and thrown out of office but you have\n" ++
"also been declared 'National Fink' !!\n"


I've tried to mimic the original functionality as closely as possible. One small addition I made was for the program to print the range of valid input numbers after a question, as well as a default number which will be used if the player just presses Enter. This makes play a bit quicker.

It really bothers me that this program is so much longer than the original. I expect newer languages to have more power for making programs easy to write and read. If you have any concrete suggestions about how to improve/shorten this code (preferably with code snippets) I would love to hear them in the comments. I know this is pretty bad code.

I've separated getting instructions from the player from updating the game state. This allows the state update to be a pure function, but also means that some of the game state update has to be simulated during the process of getting instructions, so as to predict (for example) how much grain will be available for planting after feeding people. This causes some duplication of code.

The getting-instructions part is messy; you can see four very-similarly-shaped functions named buyLand, sellLand, feedPeople, and plantFields. These correspond to the four questions asked of the player. I'd like to find a way to extract more common structure from these since they are so similar.

The question-asking functions are chained so that each calls the next, if it is necessary to go on; the last one returns the completed Orders data structure. I don't like this structure; I'd prefer one where the questions were posed more independently. Unfortunately it is possible for the game to end immediately if the player ends a negative number which complicates control flow.

I will do a Python version of this some time. I expect it will turn out a bit longer than the BASIC due to using reasonable names for things but it will likely not be anywhere near this much longer.






This week I have also become infatuated with Mike Singleton's 1984 ZX Spectrum game The Lords of Midnight. I've been playing Davor Cubranic's Java port of it. Icemark.com is a website with lots of good info about how to play the game or its sequel.

Lords of Midnight is kind of a precursor to games like Heroes of Might and Magic, where the player commands armies led by heroes across a map. The big innovation in Lords of Midnight is that everything's done from a first-person perspective. This is of mixed benefit: it's more immediate, but you will find yourself playing primarily from a map (which you would have drawn on graph paper, in the old days) anyway. Everybody loves the 3D, with the people and the sunsets and the arrows flying right at my eye! but so often it just isn't the best perspective.

The other novel thing, again with middling success, is that it attempts to give situational reports in prose, as you can see in the screenshot. This is something that I think could be greatly improved and could actually prove useful. In this style of game you have to cycle through all your living heroes at least once per day to move them. It can be difficult to remember just who has done what, and where they're headed. A summary paragraph could be really nice.

Monday, June 15, 2009

I beg to report to you

I continued to work on my Haskell port of Hamurabi. (Here's a PHP version of Hamurabi that you can play in your browser.) It is nearly feature-complete; the yearly cycle works but it does not have impeachment or the final report after ten years. However it is still rather ugly. I should have something to share by next week.

I want to finish this up and move back onto ThiefRL. I've decided to bite the bullet and try a different turn order. I want to see what it's like when guards can prevent the player from getting past them, but to do that I need them to be able to see which way the player wants to move so they can intercept. So the turn order will be something like:
  • Display
  • Get player input
  • Get guard input (with guards looking at player input)
  • Resolve player's and guards' movements

The current turn order is mostly an “I go, you go” type of thing. The main exception is that guards' awareness is updated at the display point, rather than at the moment of their turn, thus ensuring that they see the world as it was displayed to the player.

Monday, June 8, 2009

Messing with Haskell

This week I spent some time attempting to port the old BASIC game Hamurabi to Haskell. I'd picked up a print copy of Real World Haskell so I was looking for something to try out.

It's been a challenge, and I haven't gotten as far as I would have expected. I wish the Haskell documentation, whether online or provided with the installation, was put together better. I'd like to have ready access to a language reference, not just the auto-generated library documentation; I'd like to have lots of sample code snippets; and I'd like for it to be fully searchable.

For instance: in BASIC you can write INPUT A to read an integer from the keyboard. The closest equivalent in Haskell is read but it aborts the program with an exception if the user does not type in something that can be parsed correctly. Since I was attempting to match BASIC's behavior I needed it to be able to deal more gracefully with bad input. With Google I eventually found a thread somewhere addressing this problem.

So far my program is not ending up any smaller than the original BASIC version, which surprises me a bit. I'm having difficulty deciding the best way to structure the program. I've discovered a method that emulates BASIC's goto style pretty closely, but it doesn't seem like that's necessarily a step toward readability, because the flow of control is embedded throughout the program:


main = buyLand

buyLand =
[choose how much land to buy with stored food]
if bought land:
feedPeople
else:
sellLand

sellLand =
[choose how much land to sell for food]
feedPeople

feedPeople =
[choose how much to feed your people]
plantFields

plantFields =
[choose how many acres to sow with seed]
displayYearResults

displayYearResults =
[show what happened as a result of player's choices]
if game not over:
buyLand


I've omitted several additional control branches: If the user inputs nonsensical numbers the original program sometimes prints a huffy message and quits.

There is a basic game state that I pass through all the functions; it contains information that needs to persist from one year of game time to the next. There are additional bits of information that flow between some stages as well. For instance the choice of how many acres to sow with seed is needed in displayYearResults but not needed after that, so I've left it out of the main game state.

Simple as Hamurabi is, I found myself needing to step back and do an even simpler game first. Here's one where the computer picks a number and the player tries to guess it:


-- Computer chooses a number; player guesses what it is
-- Example of basic I/O

import Char
import Random
import IO

minNum = 1
maxNum = 1000

main = do
targetNum <- randomRIO (minNum, maxNum)
putStrLn ("I'm thinking of a number between " ++ (show minNum) ++
" and " ++ (show maxNum) ++ ". Can you guess it?")
guess 1 targetNum

guess :: Int -> Int -> IO ()
guess totalGuesses targetNum = do
putStr ("Guess " ++ (show totalGuesses) ++ ": ")
hFlush stdout
line <- getLine
case (maybeRead line) of
Nothing -> putStrLn ("Give up? The number was " ++ (show targetNum) ++ ".")
Just guessedNum ->
if targetNum == guessedNum then
putStrLn ("You guessed it in " ++ (show totalGuesses) ++ " tries!")
else do
putStrLn hint
guess (totalGuesses + 1) targetNum
where
hint = "My number is " ++ lessOrGreater ++ " than " ++ (show guessedNum) ++ "."
lessOrGreater = if targetNum < guessedNum then "less" else "greater"

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
[(x, str)] | all isSpace str -> Just x
_ -> Nothing


This should give an idea of the level of verbosity that I'm contending with right now. Hopefully I can improve on this and come up with a clean way to structure the more complex program.

Monday, June 1, 2009

Back to work on ThiefRL

I spent Sunday morning trying to get my head back into my ThiefRL project. It seems to have promise. The question is how far to push with it. I have a bunch of potential features and I'm trying to organize and prioritize them.

I decided to axe a couple of potential features in order to keep the scope feasible. I'd been thinking about having sidekicks whose movements could be planned out ahead of a heist to some extent. The benefit would have been that it would create nice inter-character relationship fodder. However it would also involve an additional game mode (the planning stage) and it's not clear to me what, exactly, they would do. I worry that if they are capable of doing the same things as the player they would just steal the fun.

The other feature I've decided to drop is the idea of open-city gameplay. I'd been considering having big open cities with compounds embedded in them for more focused gameplay. However I worry that it would be difficult to get the density of risk and reward encounters up to acceptable levels across an entire city. It could certainly be done, but I am going to focus on running the player through a series of smaller areas instead.

These things could always be added in a sequel. Thief 3 added a city hub, for instance, which connected together all of the mission levels. I remember the city portion as being moderately successful.

I got a friend of mine who is a veteran gameplay designer/programmer to try it out recently. He said it was too difficult so I have been considering solutions. Part of the problem, I think, is training the player to move diagonally around corners to gain distance from pursuers. If I had the player follow an NPC in an early mission that might help with that.

I also need more ways to get away. I've got various ideas for that, and just need to start trying them out.

Sunday, May 3, 2009

Weaver Modulation

...about sins of omission there is one particularly painful lack of beauty,

Namely, it isn't as though it had been a riotous red letter day or night every time you neglected to do your duty;

You didn't get a wicked forbidden thrill

Every time you let a policy lapse or forgot to pay a bill;

You didn't slap the lads in the tavern on the back and loudly cry Whee,

Let's all fail to write just one more letter before we go home, and this round of unwritten letters is on me.
(From Portrait of the Artist as a Prematurely Old Man by Ogden Nash)

The frenzied finish to inFamous has subsided and I've just finished up a week of vacation. A large part of the week was spent atoning for sins of omission: visiting the dentist, renewing my driver's license, returning clothes to stores, mopping floors, and so forth. I have been reading and thinking, too, though, and finally put fingers to keyboard in the last couple of days.

The earpiece is one of videogames' hoariest clich├ęs. Generally there's a sexy-voiced female operative on the other end dispensing instruction, exposition, and exhortation. Infamous has it; Sly Cooper has it in nerdy-turtle form. In Psi Ops we mixed things up by using telepathy (can't tell you how many times I had to listen to what's-her-name say “I'm speaking to you in your mind, via telepathy”), but generally it's assumed to be some sort of magic radio that never fails unless the story requires it. Anyone who has used a cell phone knows this is a major simplification.

One of my childhood memories is of listening to amateur radio in the HF band. Radios in this band use single-sideband amplitude modulation because of its efficient use of both power and bandwidth. As you tune across a signal with an SSB radio you get some really interesting effects on the voice. Here's an example of a sexy-voiced female spy transmitting her report as a series of spoken numbers:



(Borrowed from this site. You may need to use Firefox or Chrome to see the embedded players; I had a lot of trouble even getting them to appear in Firefox. If they don't, you can always click on the links to the MP3 files and play them yourself.)

A lot of what you hear in this recording is noise, but the reason for the odd effects on the voices is that AM radio consists fundamentally of frequency shifting. A signal in the audible range of frequencies (20-2000 Hz, say) is shifted up by a whole lot (e.g. to 2 MHz) and then broadcast using radio waves. After receiving the signal, it is shifted back down to audible range to drive a speaker. If it isn't upshifted and downshifted by the same amount all the harmonics in the signal become misaligned with respect to each other. Human voices and our understanding of them are all about harmonics (which is why linear predictive coding works so well) so they sound pretty strange when they are out of alignment.

I'm interested in simulating what this round-trip transmission/reception does to an audio signal in the presence of noise and/or mistuning. The core part is the frequency shifting. I found an article that describes beautifully how to do digital frequency shifting using Weaver modulation. Since it is nicely illustrated and I'm still learning this stuff I refer you to it.

My three-year-old daughter supplies the audio clip for today's demonstration. (I've awakened a monster; ever since, it's been a never-ending litany of “Can we sit in front of Mommy's computer and say ‘Weaver modulation’ again?” Stage Dad, here I come!) First the original, and then a series of shifts upward and downward from there.

Original:



Here are the results of shifting this audio by a variety of frequency offsets:

Shifted down 10000 Hz:



Shifted down 5000 Hz:



Shifted down 1000 Hz:



Shifted down 500 Hz:



Shifted down 100 Hz:



Shifted down 50 Hz:



Unshifted:



Shifted up 50 Hz:



Shifted up 100 Hz:



Shifted up 500 Hz:



Shifted up 1000 Hz:



Shifted up 5000 Hz:



Shifted up 10000 Hz:



Shifted up 22050 Hz:



The recording was made using the Zoom H2 Handy Recorder, which lives up the “handy recorder” part of its name. It was a birthday gift from my wife, who researched the various options and found the one that delivers the best bang for the buck. It is also popular with music teachers in eastern Washington (my mother tells me) and my brother said he wished he'd bought one instead of whatever he did buy for field-recording classroom instruction. Highly recommended!

Monday, March 16, 2009

SpaceRL released

I knew ahead of time that it would be next to impossible for me to enter this year's Seven-Day Roguelike Challenge due to my work schedule. When the call for dates went out at the beginning of the year I decided to start immediately on something small in the hopes of having it ready to release to coincide with the Challenge deadline, since deadlines are good to have. The core idea was to try and approximate zero-gravity movement in a turn-based, square-based game, as I outlined in my previous post.

Starting with the engine for ThiefRL, my unreleased stealth-based Roguelike (eh; might as well release it now), I stripped out the sound propagation, guard speech, and various other things. I kept the line-of-sight code, the pathfinding, the map structure, and the basics of the monster type. I added in a random map generator from another experiment I'd done in villa creation, and I created the basic inertia-based movement scheme.

And that is pretty much where it is now.

I spent a huge amount of time thinking about how to do predictable rigid-body dynamics so that you could push collections of objects around (or be pushed by them). In the end I had to abandon all of that in order to get something done. Currently, only you and the monsters move, and the monsters don't obey the zero-gravity movement rules.

I also spent a huge amount of time on the dungeon (a.k.a. starship wreck) generator. I'm happy with the overall shape of the spaceships. Here are some examples (click to enlarge):



The generator starts with a target number of rooms and a horizontal or vertical symmetry axis. It accretes rooms next to existing rooms. Each placed room adds its four neighbor positions (if they're not already in use) to a set of candidate positions. The next position to use is drawn randomly from that set. Thus empty positions become more likely to be used as they acquire more used neighbor positions.



Once the core room layout is created, the walls are randomly offset by up to half a room in either direction. A fixup process ensures that rooms don't overlap by picking horizontal or vertical at each intersection and forcing the walls to align in that dimension at that intersection.



Next is the crazy part. Originally I allowed doors only between rooms that were adjacent in the original grid. However, the wall-shifting can create new adjacencies. At considerable pain I created a system to identify all adjacencies and form a graph of possible room connections (doors). Then I create a simply-connected graph by randomly adding edges between unconnected components until the entire spacecraft is connected. This ensures that you can always get everywhere. After that I add a random fraction of the remaining unused edges, as well as some doors to the outside.



I got partway through cleaning up the door placement. You may notice in the maps above that some doors are placed symmetrically and others aren't. I'd like to have the underlying door structure be symmetric, and then block or destroy doors to satisfy the level connectivity requirements, which would be determined by a system that would take into account locked doors and key placement; that sort of thing. You want to make the player work a bit to get through the level.

I also got partway into implementing air ducts: an alternate movement layer which only the monsters can use. The idea is that they can't open or close the doors, so if you close the doors they will backtrack to the nearest duct and get through to you that way. I think it shows promise but I just didn't get it done in time.

I've got loads of additional feature ideas which I'd like to put in when I get more time.




The ThiefRL game I linked to above is an entirely different experience. It features a single hand-authored map at the moment, which I have been using to test out gameplay features. You can't kill anything in that game, although you do play a threat to society. I'd estimate that it's got 30 minutes to a couple of hours of gameplay in it right now, and is quite a bit more fun (I think) than SpaceRL.

Sunday, March 1, 2009

Square-based, turn-based rigid-body dynamics

The day job's been very busy lately. I'm finishing up a game (Infamous) which I've been working on for something like three and a half years. I've always wanted to be on a game project from start to finish, and I'm almost there. It's sobering to think of my life in chunks of this length, though. I have two daughters I didn't at the start. How many more of these do I have left in my career? etc. It's night and I'm maudlin.

At home I've been thinking, fairly fruitlessly, about how to put simple rigid-body dynamics into a Roguelike framework. This was the inspiration:



In this scene from Tobias Buckell's Caribbean-flavored space opera, the heroes propel themselves across the zero-gravity core of a space colony by pumping lead into their pursuers with a giant Gatling gun.



The other inspiration would be Space Hulk, I suppose, although I've never played it.

First, I repurposed an earlier attempt to randomly generate villas to create derelict starcraft:



I did some work on opening and closing doors using bumping alone and finally came up with something I like. Bumping a door head-on opens it; the problem was always to come up with a reasonable interface for closing the door again. What I have now is that if the door is open and you stand in front of it and diagonally bump the door frame on either side it will close again.

My other current Roguelike-in-progress uses a Ctrl-dir key chord to close doors. In this game I'm devoting the Ctrl-dir key chords to shooting; the idea is that when you're shooting you keep moving in whatever direction you were moving the turn before (floating in zero gravity). Also, you cannot change your movement direction unless you're adjacent to a wall or other mass.

I mocked up movement for the player character and it went pretty well. I threw in some really basic monsters, and as soon as I gave them enough hit points that they took several turns to kill it got interesting. You'd want to lead them to a straight corridor, kick off, and glide backward while shooting.

The “physics” seems like it has potential for some interesting gameplay. For instance there might be a monster that can't be killed, only stunned. Permanently neutralizing it would involve pushing it to the nearest hatch and committing it to the void. Or you could have crate-stacking, but IN SPACE...

I thought it ought not to be too hard to adapt a rigid-body physics system to a turn-based, square-based regime but so far it has stymied me.

The important thing, I think, is for it to be predictable to the player. Positions are constrained to squares, obviously, and I want to prohibit multiple objects in the same square. I've decided to constrain velocities to be integral in each component as well. Furthermore I'm trying to constrain velocities to be -1, 0, or 1 in each dimension. Velocities of 2 or more might be okay for some things, but experimentation is necessary.

I've tried out solving collisions and contacts using a fairly standard impulse-based solver, in floating-point, and then rounding velocities back to integers. It doesn't yield good predictability though and falls down on some fairly simple cases, like a line of crates hitting another line of crates. With the right numbers of crates you can get it so that the momentum hasn't been totally propagated throughout the stack and some crates round to zero velocity and others not, which means they move on top of each other.

Contact is a tricky concept in the grid-based environment too. Objects that are diagonally adjacent are contacting if they're moving toward each other, but not if they are moving past each other. A conventional “relative velocity dotted with contact normal” approach can't distinguish these.

You can also have objects that will move into the same square on the next turn if left alone but which aren't actually adjacent at the start of the time interval. What ought to happen in these situations?





I'm now working out some problems on paper in terms of generating sets of contact constraints and solving them as a system of linear equations. I think it might be possible to do that with rational arithmetic so that everything comes out perfectly. There are some cases I'm not sure about though.

If you have any good ideas about doing “physics” in a turn-based, square-based game, I'd love to hear them. I feel like I'm spinning my wheels on this right now.

(An academic paper on this might be titled Rigid-body dynamics with large-scale time and space discretization.)