Monday 29 December 2008

Speaking at linux.conf.au on 'The Linux Gooey'

If you're in Hobart on January 20th, 2009, you'll be able to drop by and hear me speak at the 2009 linux.conf.au Gaming Miniconf. I'll be talking about the Linux Gooey - why Linux needs a Game Maker and the evolving language of games.

You can see the full days schedule here; you will need to get tickets to attend the miniconf.

Friday 26 December 2008

PCG Wiki Membership Drive

I'm probably not doing enough to promote it, but the Procedural Content Generation wiki has been growing in leaps and bounds. It has over 600 pages relating to procedural generation created by a hard working team of individuals dedicated to the vision of procedural content generation. It's also the number two spot for the search term 'procedural generation' in Google - with only the entry on procedural generation in Wikipedia ahead of it - with over 1600 visitors and over 6000 page views in the last 30 days. That's excluding any peaks caused by getting mentioned on aggregator sites like Metafilter, Digg, Slashdot or Boing Boing

And I want you to be part of the team.

Well, actually part of the community. One thing that hasn't taken off is the PCG forums - they're a little barren at the moment, and I really need to jump start this part of the site. So I was wondering if you could help out by doing the following:

1. Creating a wikidot account.
2. Joining the site.
3. Introducing yourself on the introduction thread in the forums.

Much appreciate in advance.

Tuesday 23 December 2008

Ascii Dreams Non-Roguelike Game of the Year

It appears traditional to offer an end of year analysis of the best games of the year in preparation of the famine of the early months of the New Year. Prolific journalists and enthusiastic amateurs will provide well considered advice on which games they played provided the highs and lows, while developers and studios prepare the resolutions for 2009.

You too are being offered the choice of the best at my table – voting for the plenitude that is the 75 roguelikes which saw a release in 2008. Many of you reading this site on a regular basis will note that I also play games in other genres, perhaps skipping over the articles where I have boldy proposed designs and redesigns of what I have played in 2008. Based on these experiences, I would like to like to suggest a game of the year which falls outside the roguelike genre. But I have a confession to make. (With apologies to southern hemisphere readers).

In this grasshopper season rich with autumn’s bounties, I’ve played the ant.

I sit in my lounge, glancing briefly over the PS2 and Game Cube gathering dust under the widescreen LCD - calling it a television, when I’ve watched perhaps five hours of broadcast television all year would be a disservice – and over to the stacks of jewel cases of my gaming collection, stacked high with second hand gems of yesteryear like Half Life: GOTY edition, S.T.A.L.K.E.R., Company of Heroes and recent acquisitions, like Spore and...

Well, only Spore.

I noticed, and still contemplate, a distressing trend in my purchases, which has completely changed my buying behaviour this year. I would get a game, open and install the CD once, and play a while. Then I’d have to re-image my laptop – for a variety of reasons, discussed previously – and never touch the game again. The sheer inertia of having to wait for the install, perhaps swapping CD or DVD , disc after disc, then finding and installing all the patches, only to have to repeat the process a few months later, would exhaust me far before the euphoria of actually playing would hit. Not to mention the inconvenience of having to pack for the road, a frequent experience recently.

And so the game would sit discarded in its case – while I played Left4Dead, or Team Fortress 2, or World of Goo, because it was far easier to back the Steam cache up to hard drive, and faster to restore it than install a game from optical media.

To rub salt on the raw wound, a few weeks later, the now forgotten game would arrive on Steam, where I'd be left with the unpleasant choice of repurchasing it, or relying on the sundered shell of its former fragile, imperfect physicality.

So to confess my New Years resolution last year: I swore to only buy games this as they were digitally released.

I cracked, but once. Buying Spore was a calculated risk that Electronic Arts would be unable or unwilling to distribute their tent pole games on a third party platform – one which has just been proved wrong, spectacularly so when you consider the Steam version doesn’t require SecureROM.

Which is why my game of the year is a platform, Steam, not a game.

Because Steam is really the only game in town.

Stolen from elsewhere

In Google Reader, input:

up,up,down,down,left,right,left,right,b,a.

Monday 22 December 2008

Dedication

I believe we should be supporting this man on principle.

Welsh rarebit

When I was fourteen, I learned to touch type - on a type writer. You may not be familiar with these: imagine a keyboard, but when you type, your key press directly moves a mechanical arm which strikes a sheet of paper through an ink covered ribbon, leaving an ink covered impression on the paper. The paper is moved through the feed, like a printer, but only one character at a time, and when you press the enter key, the sheet of paper moves up a line. And get this: there is no screen.

(Kids these days. Also adults, these days, feeling like they have to explain stuff to kids these days.)

The important thing to remember is that typing was an optional skill. Only secretaries needed to type - senior management would dictate information to them either directly, or by recording it on tape and having the secretary play it back and transcribe from this. This was back when the work force was still divided into higher paying and lower paying positions, mostly on whether you were male or female, and my school, despite being a liberal bastion which a few years later elected to have male and female co-principals, still divided the classes up into electives for typing, home economics, woodwork and technical drawing.

What was different to many other schools, is each of these optional electives was not optional. Every fourteen year old who attended my college studied all four 'electives' throughout their second year. This drove my father wild.

He could understand how woodwork and technical drawing could be useful - and he'd had to suffer enough through me making Welsh rarebit to realise that home economics aka cooking would be useful to me later in life and him immediately. But typing. In no conceivable future of his could he see how typing could be a useful skill - this coming from a man whose bookshelves are bowed with Asimov, Clarke and Heinlein. He complained vocally to the school, tried to withdraw me from typing class for more mathematics, and generally made a nuisance of himself to my teachers. Nonetheless, I enjoyed it, even excelled at it, and it was only two hours a week for three months of my academic career.

I've always wondered at the utility of game competitions - where you are given an inspiration, genre or platform to develop within a limited timeframe. My problem is not coming up with the ideas or making the time to code - it is limiting the output of my ideas to manageable chunks. I find programming easiest when I'm working under a tight set of restrictions: say, catching the train to work where I'll be seated for about 30 minutes, developing Unangband in Eclipse. And it's this realisation that helps me understand what is important about the competitions: it's not the starting that is important, it's the limiting yourself - knowing when to finish.

The delightfully detailled specifications that Dan Cook provides over at the Lost Garden are the pinnacle of this theory of game competition design: his Fishing Girl prototype provides concrete descriptions of every game mechanic, as well as the art assets so that all you have to do is develop the implementation from this design, and then tune how the game plays.

The devil is in the detail - how the implementation work, how it feels, how it plays.

Dan is an impartial critic. You get a gold medal if you can convince him to play your game for 15 minutes. And he's never handed one out. Until now.

What makes this especially significant for me is one detail that is often overlooked when designing games: the quality of the art that Dan provides. It was a little known fact that I started working as a graphic designer before changing jobs to the IT industry. I didn't have a skill that is surprisingly easy to avoid as a graphic designer starting out: I can't draw.

Because of this I knew I could do an adequate job, but I could never be good, let alone great, without this essential skill. I could have invested the time learning, but I did have a set of skills that I could use immediately, and information technology was the place that I could progress far more quickly.

Art, or more importantly, the representation of information visually, is a critical component in game play. It is something roguelikes do so well - a topic I'll explore more another time - despite not having any art assets per se. But allowing the player to understand complex information visually at a glance is key to developing a great game, and why Dan Cook's game competitions are so useful to help you understand game design.

Not many programmers are artists, which is why you see David Gervais' tile sets used over and over in roguelikes, and why free, re-usable art assets are so critically important to the development of an open source game community. I don't ever see the ability to draw, to divide space in pleasing, aesthetic, information rich segments separated, enclosed, captured by lines becoming redundant.

A few years ago, my father confessed to me that typing was perhaps the best thing that I ever did in school. And that's why I'll be encouraging my children to draw - a skill I never made the time for.

Sunday 21 December 2008

Asserting a Coding Style: An Answer

Stu in the comments thread pointed me in the direction of Design By Contract in C, which points out the disadvantages of assert() or require() style of coding and offers an alternative. Have a read of the article, and then download the latest version, if you're interested.

Now, before I adopt this, I just have to persuade any other Angband variant that I'm likely to steal code from to adopt this standard as well...

Saturday 20 December 2008

Asserting a Coding Style

There are two schools of thought regards how your code should fail: either it should try to keep going as best it can, or it should hard stop.

After many years in IT, I'm firmly in the hard stop school. It makes it far easier to debug, if your program fails at the point at which an exception occurs, even if it is a less pleasant experience for your users. (And trust me, trying to talk someone on Windows through setting up a debugger is not easy - I mean, I can't even do it for myself at the moment).

The 'try to keep going as best it can' is often a euphemism for silently corrupt something, violate the assumptions we've got in the code and then fail inexplicably further down the track.

Luckily for people playing the game, Unangband, like Windows, is written to the silently corrupt and experience weird errors standard. Which is why I have in the back of my mind, the intention to adopt a coding standard that promogulates hard failure when it detects an exception.

The easiest way to do this is have an ASSERT() macro which if false, does something that'll cause general program fault, like dividing by zero. ASSERT is used in a couple of places in the Unangband source, where my more disciplined co-developer has attempted to impose some kind of rigor in the codebase.

What has piqued my interest and led me to discuss this, is a new dungeon generation algorithm posted on rec.games.roguelike.angband. This algorithm has been kindly put into the public domain by it's developer Kusigrosz, and you'll be seeing it at some point in Unangband as a new room type, nest and as a new dungeon theme. (Screen shot of the output either at the link or the start of this article).

The C source for this algorithm uses another macro REQUIRE() which if false, immediately exits the program and dumps the source code line at which the fault occurs. REQUIRE() is like ASSERT() in that it lends itself naturally to specifying the pre-requisites and post-requisites for a function. You can for instance add a line REQUIRE(x>0); which intuitively indicates that at this point in the code we expect x>0.*

What I ideally would like, is REQUIRE() but with the ability to set a failure level at compile time or run time. That way I could have a number of differing levels of failure, allowing the user or distribution to select how hard they want the program to fall over. The levels would be:

0. REQUIRE() compiles out completely, used on systems with limited memory or performance.
1. Silently return from the function.
2. Write a warning to a log file, and silently return from the function.
3. Write an error to standard out, including the line number of the source code and exit.
4. Dump the stack to a file, including the line number of a source code and exit, useful for a debug build for users who don't have the technical skill to set up a debugger.
5. ASSERT().

I'm quite happy to be able to bloat the source doing this in the long term, but I want to make sure I'm doing so with a robust mechanism.

So my questions are:

1. Is there any other mechanism out there that better supports this hard, flexible fail over?
2. What is the best C constructions to ensure levels 0 and 1 work in a platform independent manner? Remember, I don't know necessarily whether the function is intended to return anything at all.
3. Is there any macros or public domain code that supports dumping the stack at runtime? This would also need to be relatively platform independent. Note that Windows is the only platform where this is currently a major problem.

Thoughts and feedback welcome.

* The Unangband form of this, adopted from Angband, is as follows:

/* Paranoia */
if (x < 0) return;

which is very much of the form 'silently fail and keep going'. [Edit: And you'll see here, prone to failure. Of course, I meant if (x <= 0). But then out by one errors are always fun]. [Edit 2: And it also looks like I reversed the conditionality of the assert() statement, in which case assert() and require() are equivalent. Article amended. And I should read assert.h].

Similarly, the TRY {} CATCH construction is mostly focused on trying to recover from exceptions.

Friday 19 December 2008

Refactoring Hell

If there is some kind of coding hell, then refactoring is in the centre of the ninth circle of it.

I'm in the process of redesigning the Angband projection function, I dunno, for the fourth time in order to avoid unnecessary code duplication when it comes to applying magical effects to regions. I'm going to end up with a wrapper called project() which calls project_shape() to define a list of grids to affect, and then project_effect() which takes a list of grids and an effect, and applies that effect to the grids. This will allow me to take another list of grids - say a region - and use project_effect() directly to affect them.*

The problem I have with refactoring, is that you inevitably take a lot of hard won lessons and throw them away as a part of the refactor, and expose a lot of assumptions about how the code works to fundamentally different processes. And it's boring in the sense that at the end of it, the player doesn't notice any changes in the game, except more bugs.

So I'm tempted just to duplicate the code instead and move on. Especially as, having completed the refactor, I can get Unangband to reliably crash on my Windows box, which I can't get the mingw32 debugging environment working on for some reason - which means I'll have to debug on the Macbook instead. And do a sneakernet sync of the code repository to avoid polluting SVN with the offending code.

Ugh.

* The reason I have to take this approach, and can't do a single 'apply magic effect to a single grid' routine instead is quite subtle. One of the things magical effects can do is move you around e.g. teleport, waves, wind, gravity etc. But these effects can also potentially do damage. And I have to be careful that I don't move the player into another affected grid, and consequently double-hit them with a single magical attack (because of how important hit points are in a permadeath game, it'd be unfair to the player). So I've adopted the Sangband solution, which is to apply all the movement effects last, after all the other spell effects have occurred.

The Angband projection function already has this layering approach, applying effects to all the terrain first, then monsters, then the player. Sangband adds teleportation effects. And Unangband adds item breaking effects at the end, as items can explode to recursively create further projections, and I take advantage of tail recursion to ensure this happens in a safe manner. This means there is quite a bit of code to duplicate, which is why refactoring is a tempting trap to fall into.

The Symposium

There is only one symposium worth reading at the moment - games journalists on games journalism gathered into a herd by Shawn Elliot. I'm an interested outsider: as a potential review target at some future point, the only game reviews which I seem to learn stuff about the game from seem to be gaming diaries. Case in point is Tom Chick, who specialises in this kind of writing: he's just started writing about Fall From Heaven II, a Civilisation IV modification, in this mod. I expect to come away from this with a much greater understanding of the game, than any review I could care to name.

Thursday 18 December 2008

A method for implementing player-crewed sailing vessels in ASCII roguelikes

Another feature of the region code I’m developing is that it will allow me to implement moving platforms in Unangband. A platform overwrites the existing terrain with a new terrain type (say ‘wooden deck’) and records the old terrain type within the region code (a single scalar value can be stored for each grid in a region – this will record the terrain type originally underneath).

Then, when the platform moves, we rewrite the old terrain, translate the platform region one grid, and then overwrite the terrain in the destination location with the platform terrain type; recording the original terrain in the region data structure. It is important for this discussion to realise that we can’t stack multiple terrain types: each grid can have only one type of terrain.
Impassable terrain, monsters and objects complicate the algorithm. Impassable terrain is defined as any terrain through which the platform cannot pass. I’m still deciding how to define this flexibly: I suspect I’ll have a number of different platform types, capable of moving over floors, chasms, water, lava and so on – each of which is currently represented by a flag in the terrain data type.

To determine if the platform is going to move into impassable terrain, we’ll simply make a copy of it, translate it, and then fail to move the platform if the translated copy intersects any terrain it is not permitted to exist on.

For monsters (and the player), if they are standing on the platform, they’ll be translated along with the platform. If they are in the path of the platform, and capable of standing on the platform terrain, they’ll stay in their existing location (effectively stepping onto the platform as it moves over them); otherwise they’ll be pushed into an adjacent grid which is neither in the current platform location, or any grid of the translated copy.

Objects on the platform always move with it, if they are in the path of the platform they are always pushed: if no grid exists which the object can be pushed to, it is destroyed.

How do we get platforms to move in the first place? The fallback for many games is to have the platforms moving independently on a fixed path, and allow the player to jump on and off the platform at will. But this will massively complicate the level design – it may still be useful, but I have a smarter idea.

A key component of roguelike design is the ‘bump’ – that is allowing the player to interact with the game world by the process of attempting to move into it.

I’ll extend the concept of the bump to that of pushing. An terrain feature is push can be pushed by the player by having the player attempt to walk into a normally impassable piece of terrain, and the terrain feature is moved to an adjacent grid, allowing the player to pass. This process of moving requires that we make certain assumptions about what the underlying terrain is: for normally pushable terrain, we assume that the underlying terrain is an empty floor grid. In this instance, we can push terrain around as follows:

  1. Choose an empty floor grid adjacent to the pushed terrain – first in the same direction as the player attempted to move, and then check another adjacent grid, alternating clockwise and counter-clockwise from the first grid considered.
  2. If an empty floor grid is found, overwrite this grid with the terrain type.
  3. Overwrite the pushed grid with empty floor terrain.
  4. Move monsters, objects as described for moving platforms.
  5. Allow the player to move into the now empty grid.
To handle recovering pushable terrain from impassable dead ends, we could potentially let the player stand on the terrain and push ‘downwards’, choosing a random direction as a result, or have a separate ‘pull’ command, which allows the player to specify a direction for any adjacent ‘pushable’ object to move.

By combining platforms, and this concept of pushing, I can allow the player to push platforms around by defining a second region which contains ‘pushable hotspots’ (shown on the irregularly shaped platform to the left as '*' symbols) that, instead of just pushing a single grid, moves the entire platform in the direction the player specifies.

In this instance, I have to specifically link multiple regions together. But I have to do that anyway, to handle the instance where I might have multiple intersecting platforms. Consider the case where a platform of ice is created over a wooden platform. The wooden platform stores the underlying terrain types in it’s data structure; the ice platform stores only those regions which don’t intersect the wooden platform, for the rest it stores the fact that there is a wooden platform terrain type under it.

If the wooden platform moves, I’ll suddenly overwrite parts of the ice platform. So I have to come up with an algorithm to allow both platforms to correctly move over each other. If I have to worry about this special case anyway, I can readily enough include the code to move both platforms at the same time if they are linked together.

I can even get trickier, and demand that my pushable hotspot(s) have more strict requirements for what terrain they sit on than the rest of the platform. Consider a wooden platform that is held up by a chain over a chasm. I want to allow the platform part to exist anywhere in the chasm, but the part that is connected to a chain to only move on terrain that has the chain in it.

So I make this part the pushable hotspot, and apply the more stringent requirement to the pushable region.

This is where things start to get interesting: up until now I’ve assumed that a platform is built of a single terrain type – plus a second for the pushable regions. But I could equally build a platform from an ASCII template and have a mix of terrain types, pushable regions and grids which expose the underlying terrain. And this lets me implement vehicles: like sailing ships, but drawing the ASCII template onto the map at the vessel location. Bear with me as we look at some ASCII art:

This sturdy rowboat has two pushable regions: the oars. I mark these regions ‘reversed’ so that by pushing at the oars (‘*’), you go in the opposite direction to that you pushed. By sitting between the oars you can steer the boat left and right, sitting in the prow you can propel the boat forwards.

This large galley is filled with the undead spirits of sailors. By beating on the drums (‘*’) you cause the undead on that side of the galley to row – again in the reverse direction to your beat. The large deck will lead to much combat and looting of treasure.









This sailboat has a single sail (‘<’) that you can push to slowly propel the boat along - ideally you need a gust of wind, perhaps from a spell, to move quicker. By pushing at the boom (‘'’) you can reflect the way the template is laid out, causing the sail to swing to the other side of the boat.

The complication with the templates, is that I need to be able to rotate the templates as well as translate them. I need a robust design to handle this – but using the Angband project_path function should allow me to rotate the vertical strips of the template to any angle of a fixed length. Although a flight of fancy at this stage, there is the real possibility that in a future version of Unangband, you’ll be able to take to the sea and avast the land lubbers in other roguelikes.

Wednesday 17 December 2008

Request for votes: Ascii Dreams Roguelike of the Year 2008

Voting is open for 'Ascii Dreams Roguelike of the Year 2008'.

How did the roguelikes qualify?

The list was taken from the roguelike releases announced on the Rogue Basin news section between January 1st and December 17th 2008 and from the list of Actively Developing Roguelikes maintained by Jeff Lait. There are a record 75 entries this year.

What about 'x'?

Make sure you announced your roguelike on Rogue Basin for next year. In particular, NetHack didn't make it in, again.

What about the 7 day roguelikes?

I decided to exclude any 7 day roguelikes that weren't announced separately.

What's the prize?

Pride. And a sexy logo. You can see the winning 2007 logo on the Dwarf Fortress links page. Logo designs for this year are welcome.

Having a competition is a dumb idea/offensive/stupid when you can't police the results.

Yep. Doesn't stop it being fun. You can vote for multiple different roguelikes. The idea here is that you will be encouraged to go out and download a roguelike that other people consider interesting, not that there is any kind of real competition element involved.

Results for 'Which Unangband School do you prefer?'

Thanks to the 29 of you who voted. I'm surprised about the lack of popularity for the Druid... The results were:

Wizard
9 (31%)
Druid
3 (10%)
Master
5 (17%)
Sorcerer
9 (31%)
Thaumaturgist
6 (20%)

You'll have another opportunity to vote shortly - it's that time of year again.

Monday 15 December 2008

Design Re-Engineering

Valve is on the hunt again for upgrade advice - in this instance, for the Scout.

Unfortunately, I have little advice to offer here. I’m not a great scout player.*

But luckily, they’ve also recently released a patch that greatly improves playing the Engineer – by allowing the engineer to upgrade their dispensers and teleporters to level 3, with a consequent improvement in dispensing and teleporting speed. Here I am qualified to offer suggestions; the engineer is my first and foremost love and anything that allows the engi to fuss around their buildings and move around the battlefield more is an improvement in my book. So here are my engineering upgrade ideas:

The Quik-R-Ratchet: The Quik-R-Ratchet immediately (on one hit) builds any building to level 1. It allows buildings to be upgraded to level 2 at the normal pace, but cannot be used to upgrade a building to level 3.

Because running up and deploying buildings quickly is what engineers should do. It also helps two engineers work together much more efficiently, one with the Ratchet and one with the w’regular Wrench. Engineers should be encouraged to drop an annoying level 1 turret on the front line, or to move their turrets following an attack to confound the opposition.

The I-Spy-Shooter: The I-Spy-Shooter is a shotgun which immediately decloaks any spy, preventing them from cloaking for 5 seconds, and otherwise does half the damage of a normal shotgun.

There is nothing as frustrating as knowing there is a cloaked spy around, and not being able to do anything about it. You have to squat on your kit, back to the wall and pray. At least with the I-Spy, you’ve got a fighting chance. Of course, a disguise isn’t going to be stopped by this.

The Big Red Button: The BRB replaces the pistol, and allows the Engineer to teleport back to his teleport exit, provided both the exit and entrance are built and fully charged. Doing so discharges the exit, but requires the engineer stand still (in taunt mode) for several seconds to activate. ‘I said B...R...B...’

And this should allow Engineers to wander the battlefield, helping out others with their shotgun, while letting them get back to their equipment in a jiffy (provided a Spy hasn’t sapped it, of course). This may encourage engineers to build entrances in useless positions: if that is the case, it should be tweaked to teleport back to the entrance, or exit, depending on a left or right mouse click.

*I lied. At least about the advice thing. I might be able to come up with some scout solutions:

The Short Order Book: The Short Order Book replaces the pistol and can be used on any player on your team. Once you get an order from the player, by hitting them with the order book (at close range - a short taunt animation shows the scout writing up the order), the scout must collect a health and an ammunition pick up (or refill from a supply closet) to fill the order. Once the order is filled, the instant you touch a player of the same class as the order you took, you dispense them 25% of their ammunition, 25 health, 40 metal for an engineer and for a medic or spy, a 25% uber or cloaking charge. You can also part fill orders, with just either health or ammunition, but the class specific benefits will not apply.

This gives Scouts stuck behind the front line something to do, and helps speed up the game play for those teams stuck attacking or defending near their spawn point. And for once, a scout will be giving you health and ammunition instead of taking it. Understanding the game play for this is complicated, so the order book should take the form of a big checklist that gets filled in as the Scout completes the required actions:
[] Get health
[] Get ammunition
[] Give to _________

Once the scout has filled the first two steps, they automatically shout out as they move around the map e.g. 'I got an order for an engineer!'.

The Brooklyn Bridge: The Brooklyn Bridge, a fence board with a nail in it, as opposed to a regulation baseball bat, fixes any turret it hits in position until the Scout is killed, preventing the turret from turning, but still allowing it to fire in the direction it is pointing. It takes twice as long to attack with the Brooklyn as the regular bat.

Ah... the mythical anti-turret scout weapon. What rage and anger fills the Valve forums, discussing the pros and cons of various ways of the scout countering his ‘hard counter’ and the means by which he should do it. By whacking it, of course... the gun effect is far less useful than a Spy's sapper, and it is far harder to for the scout to get in position to use it, but against an undefended gun, the Bridge should provide a way past.

The Soar’n’Off Shotgun: The ‘shortie’ as it is affectionately known, does critical damage while the scout is in the air. It otherwise is incapable of criticals.

Because running around a target is more boring than running over it.

Pathfinding Redux

There is an ongoing discussion in the comments of the recent pathfinding post I did that you may want to read. Or contribute to for that matter.

The point I was making was that there can be so many complications to try to get pathfinding right, that you are probably better off coming up with a simple solution that works most of the time (such as making monsters always advance) than trying to capture all of the complexity aiming for a perfect algorithm. Your time can be more valuably spent elsewhere.

Violation of Contract

I'm about to violate a core tenant of Angband's user interface contract, and I'd like your advice.

Up until now, Unangband has followed Angband with regards to what can be in a single grid. In Angband, a single grid can hold:

1. a monster
2. either a trap or one or more objects or 'interesting' feature
3. if not an interesting feature or trap, then the grid must be a floor which is safe to walk on

This is a very important contract between the game and the player. That is, if there is an object in the grid, it is safe to walk on. You can actually use this to determine where traps are, by throwing objects around a room and see where they don't drop. More importantly, it allows you to interact with stacks of objects, by moving around the room, picking them up.

I'm in the process of implementing ranged traps. Ranged traps will have a region that they target, which triggers the trap when you move into it. This violates the above constraint, because you will end up with a grid that holds an object, and then a ranged trap where the region it targets includes the grids with the object.

I want to include the trap regions in the map display, to help the player avoid them. This leads to a second violation of the above contract: it's now possible to end up with a grid which is in the region of multiple traps. So I'm stuck with a user interface dilemma.

How do I display multiple trap regions, so that the player can most usefully determine which region is safe or unsafe, and the area effects of multiple regions? In Unangband, you can display up to 256 colours (more like 28 legible differences) and one ASCII character in each grid. There is no reverse video or stacking of multiple characters in a grid.

I want to be able to distinguish between the traps themselves, which you can disarm, and the trapped regions, which you can't disarm. The trap character is ^, and for historical reasons, I'd like to display the regions using x to indicate the trapped area - using the same colour as the particular trap type. I may have to use another character though, as x is already used for bridges of various kinds.

Suggestions welcome.

Sunday 14 December 2008

The Trap of Perfect Pathfinding

I'm firmly of the belief that there is no such thing as a perfect pathfinding algorithm. I've mentioned this during the article series on Unangband AI, but I'm working on improving traps in Unangband at the moment (a corrollory to getting druidic ongoing spell effects working), and it's very clear that in order to handle the complexity I want traps to have will overly complicate any attempt to build a 'correct' pathfinding algorithm.

I've just added the ability to avoid traps, as well as disarm them. Avoiding traps will become a more important requirement when I added ranged traps to the game (using a different implementation to NPPAngband ranged traps), but for the moment, think of it as particular trap types will not trigger if the player is in a particular state. If you are flying, you won't trigger pits or trap doors. If you are invisible, you won't trigger silent watchers. If you are in darkness, you won't trigger shafts of light. And so on.

My favourite is surreal paintings: you won't trigger these traps if you can see the painting. Which is just the kind of mess with your head weirdness that a magical scene that comes to life when you aren't looking should convey.

An important part of this concept is ensuring that the player can learn the various ways of avoiding traps. To do this, I try to make many of the trap types result in the game condition that then allows you to avoid the trap. This allows you to learn the associated way of avoiding the trap. For instance, one effect shafts of light can do is darken the room - which brings on the condition of darkness that prevents them from working. Similarly, magical symbols don't affect you if you have run out (or nearly run out) of mana. And an early magical symbol effect will be to drain you of mana.

Here's where the complication comes in: I want to make monsters avoid traps under the same scenarios as the player - to help the player learn these associations further. But this means that correct pathfinding will not only require knowing about the monster's permanent abilities, but their temporary ones. Which complicates pathfinding, because I need to model future effects. In particular, magical symbols will mean I'll need to model the monster's regeneration of mana, to determine whether they can safely cross an area filled with magical symbols (or more importantly, a single magical symbol with an area effect).

I've always had this problem, of course, because of dynamic terrain. Consider the following scenario and tell me how to design a pathfinding algorithm to handle it:

A monster runs into the room to attack the player standing in the doorway. Half way across, the player pulls a lever that floods the floor of the room with oil, then pulls out a match. Should the monster: a) keep advancing, b) retreat or c) stand still waiting for the player's next move? What other factors need to be considered?

Tuesday 9 December 2008

Angband portable update

It looks like First Age Angband on the Nintendo DS is coming along strong: you'll probably want to look at the thread on the angband.oook.cz forums, which includes some good screenshots (and some terrible ones: Nick, what were you thinking?) and then head off to the download page, provided of course you have the right hardware to allow you to play homebrew games.

This comes hot on the heels of the original Rogue being ported to the iPhone. To port Angband to the iPhone will require moving or recreating the Mac port from the Carbon to Cocoa API as pointed out in this thread. Luckily, there is one Cocoa port already available.

The real challenges as Nick McConnell points out are handling the reduced screen size and alternate interface. He's handled most of the issues in FAAngband, which along with the Windows CE port is the best place to get your Angband portable gaming fix at the moment.

Sunday 7 December 2008

Game On

I just had the pleasure of attending Game On, an exhibition at the State Library of Queensland on gaming - containing if I'm not mistaken virtually every piece of hardware ever used to play computer games on, including the likes of the Magnavox and a DEC PDP-11 running Space War. While I was not able to lose myself playing as long as I wanted due to family commitments, I'm looking forward to returning in early January for a fuller exploration of the exhibits: that is unlimited cabinet and console gaming from a wide selection of arcade and home console systems.

If you're a gamer in Australia or New Zealand, you should make the trek. It's on until the 15th of February.

(I massively enjoyed the few minutes of Warning Forever, a freeware shooter featuring procedurally evolving bosses that I played - well worth a download).

Monday 1 December 2008

Black Mesa Trailer

It's a day to get excited about a remake.

Designing a Magic System - Part Fifteen (On Hacks)

(You'll probably want to read parts one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen and fourteen first).

The school spell lists as I designed them in part fourteen are intended to be a mix of banding tradition as well as an attempt to find new ways of making magic in Unangband interesting. I've been inspired here, as much elsewhere, by the design work in Sangband and elsewhere by Leon Marrick and although aided by many, this particular series of articles is dedicated to him and the insight and inspiration he has given me and many others.

Angband is a game of resources: and each magic school has a different way of handling the resources of light, food, escape, healing, mana (spell points) and item identification which help define them. Wizards have no reliable source of food at all, and no high level healing, but can readily concentrate mana to recover it and have the most flexible range of escape spells, and both the ability to light rooms as well as to use light as an attack, and to replace their fuel based light source with a magical spell which can be indefinitely powered provided that sufficient mana is available (and that the wizard is not plunged into darkness by letting this spell run out - spells require light to be read from their respective spellbooks). The Unangband Wizard has the ability to take advantage of magical items such as wands and staffs: both with a spell (gauge magic) which readily identifies the number of charges that the item has, and a recharge magic spell to replenish these charges as they are used.

I attempted to balance the flexibility and power of the wizard escape spells by limiting them significantly for the other magical schools. Druids can only teleport to and from water or natural areas (defined as being adjacent to plants), masters only to and from darkness, thaumaturgists require a nearby source of fire, and sorcerors can only teleport temporarily, returning to the location that they teleported from after a moderate amount of time passes. This was done to allow other escape spells, such as temporary hasting, and spells which shape and change nearby terrain, such as wizard lock and warp wood, to be preferred by these classes in various ways. However, the escape spells are much less flexible, perhaps too inflexible, to be reliably used, and since escape is of critical importance to magic using classes it may mean that the wizard ends up being the preferred class choice for Unangband players.

Druids are encouraged to manipulate their surroundings and many druid spells have been made synergistic with each other: while they can only teleport near nature, they can create trees to bring nature to them in the first place, and then these trees can be used to tangleroot opponents or recover health using the tree of life spell; similarly the mana pool spell draws mana from nearby sources of water. Once opponents are entangled, it becomes much easier to affect them with slow building natural attack spells which are their forte (a yet to be implemented forte at the moment unfortunately), and the ground can be further prepared by shaping the rock by turning it to mud. Food for a druid is trivially satiated with a single spell, light is randomly scattered around them as opposed to lighting up whole rooms (which encourages more preparation to 'fill the gaps'), and item identification through a useful but obscure system of runes which hint at a particular items function.

Masters summon monsters, and while the friendly monster AI is powerful and flexible enough for monstrous combat between the master's allies and enemies, I need to give the master more granular control for when they summon multiple differing types of monsters. To encourage the master to have more investment in their minions, I've added a Find Familiar spell, which summons a unique creature that the Master can tailor over the course of their career - but if this creature dies, it is lost forever.

One thing I've enjoyed doing with various master spells is monster design: in particular the Animate Dead spell requires I come up with undead versions of various body parts and creature types. I'll say more about hacks shortly, but I've implemented this as a blend of hacks of various kinds, instead of a 'purer' convert a monster to undead function. The sorceror's Animate Object has been similarly entertaining.

Masters relish darkness instead of light, attacking with it in various ways, teleporting to and from it, and consequently have a temporary infravision spell which allows them to detect warm blooded monsters in the darkness - I should also add a Night Sight spell which provides further visual acuity at a higher level. High level healing is acquired by draining the life from living enemies (or allies), which simultaneously feeds the Master, and mana can be acquired by sacrificing hit points in return - since Masters need mana to pay off summoning debt, it could be overpowered letting this be more readily recovered. Item identification provides a general hint as to whether an item is beneficial, and what approximate effect it has.

Sorcerors are a mix of traps, charm spells, mental attacks and shape-changing: charms being more effective than the master's abilities in summoning, and shape-changing very much a work in progress. I've probably gone overboard in terms of making shape shifting unfriendly for the player to use as it forces them to discard equipment in various inventory slots. I suspect I'll move back to the Oangband/Sangband style solution of making shape-shifting just affect player attributes. Sorcerors are almost as flexible as wizards in the ways they can escape, perhaps more so, but lack a pure 'get away and stay away' single turn spell. They are superior to other classes in their item identification magics, and instead a source of sustenance, they can readily slow their metabolism to prolong the effects of food they have consumed. Sorcerors lack any ready source of light, healing or mana however, so will be forced to scrounge for other methods of illuminating the dungeon and recovering from wounds and spellcasting.

Finally thaumaturgists are attack, attack, attack, with a mainline in randomly assigned elemental types (to be implemented) and a sideline in acid and fire magics. They can usefully renew their torch flame to allow unlimited light and step into flames to teleport and escape but otherwise lack any utility spells.

After spending fifteen parts discussing various design decisions to try to come up with a consistent and systematic method, I've yet to find a solution. In particular, my answers are variations on two themes. The first is a refutation of the argument I made in part one, that 'As a game designer, [...] flavour is all important, but ultimately distracting'. Designing classes is almost all about flavour and style: do these abilities fit a consistent theme, do they complement each other, and so on? We can take on principles of good design, and the importance of the language and grammar of design will be increasingly a requirement as our games continue to increase in complexity. But ultimately, we want to present the player with interesting choices, a set of hills or valleys in the possibility space of the game, and to avoid overwhelming the player with too much choice, we have to highlight certain highs and lows, while ignoring others.

The second theme is the importance of exceptions. As a programmer, your intuition is ultimately to try to re-use your code where ever possible. But as a game designer, of the magic systems, you want to ensure that each ability uses at least some unique code path. That is, each ability in your game must in some way be a hack. It can be a small hack (fire burns, cold freezes) or a large hack (the recent implementation of a Find Familiar spell required a complete monster progression system to be interesting), but it should ensure that each ability is different, and therefore affects the game play in some unique way. Extend the ability idea as far as you can (cold freezes water, allowing you to cross rivers and block swimming monsters from attacking you) and then push yourself a little to see where it takes you. Don't obsess with trying to make the code clean and regular: it's the abilities that the player has that keep them empowered and playing, and suspension of disbelief should trump any reduction in code complexity.

Normally I finish these design articles with a set of principles, but here I only have practise. It has taken me close to 7 months to list these practises and there are many more devils in the detail that only a close inspection of the code and asking me questions will do justice to (and please, ask me on the blog rather than via email so that the questions and answers are shared for all). I'm not throwing my hands up in the air: but this type of design requires iteration and playing, and decisions, and your decisions will not be the same as mine.

(You'll want to continue reading the follow article series Designing a Magic System Redux, where I address issues, such as status effects, magic items and summoning which I haven't discussed so far).

One Fist, Two Fist, Red Fist, Blue Fist

Yah! Dystopia, my favourite Half-Life 2 mod will be coming to Steam.

NaNoWriMo

Ah - once again, I've failed to even come close to the NaNoWriMo required total. I've still found it a useful exercise, as always, and I've written far more fiction than I would have written otherwise. My problem is I still found plenty of time to blog, program and celebrate my birthday, and various other functions.

Or at least, I shouldn't think of that as a problem. I mean, that's living, write. I'll argue that we just need a southern hemisphere timed writing event, perhaps in May.

For those of you who've been following this blog, I strongly encourage you to do one of the following two things:

  1. Jeff Lait has published his 2005 NaNoWriMo. You may remember him as another roguelike developer and obviously a talented author as well. So please: buy his book.
  2. Alternately, you can help donate to the NaNoWriMo to keep this event running. They've failed to cover costs again. Details on donations are here.
Take care. I'll be trying again next year.