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