Monsters with class

Firstly, thanks Mikolaj for picking up and fixing lots of errors with my most recent changes to add monster classes. Monster classes, you might ask. Well what are those?

They're roughly equivalent to ego-monsters in T.o.M.E. Because Unangband puts much greater restrictions on what monsters can be generated at what level, I need lots more monsters for sufficient variety, particularly deeper in the dungeon. You've probably seen the Young/Mature/Old/Ancient Large/Huge/Giant Fast/Furious/Deadly Experienced/Veteran etc. prefixes that a lot of monsters get at the moment. These modify the monster maximum hp, armour class and speed for monsters which have LEVEL_AGE, LEVEL_SIZE, LEVEL_SPEED and LEVEL_POWER flags. There are basically 3 breakpoints for each flag, at 5 levels deeper, 10 levels deeper and 15 levels deeper. You'll also have seen one monster in each large group is bigger/stronger/faster/older than the others - he is the next category more powerful than would be expected for a monster of this depth.

Well, monster classes is another flag (LEVEL_CLASS) which means that the monster can appear as a variety of different classes: warrior, mage, priest, archer, thief, 5 levels deeper than it would initially appear. For each additional five levels, the monster gets an additional class - warrior and priest --> paladin, for instance. These classes have additional attacks and spells, and get a similar boost to their other stats.

So why am I not implementing these as separate monsters? Well, I could. But Unangband has 1312 different monster types at the moment, and I keep adding them: the latest is the Rotting Icky Thing which is what you get when you re-animate an icky thing - it tends not to last very long.

In fact, I'm bumping up against the re-enlarged description limits at the moment - I'll have to expand them again if I want to add too many monsters - you may notice that the last few monster descriptions have been commented out.

The disadvantages with not separating them out are many: inaccurate monster memory, possibly unbalanced class combinations, and so on. The advantage: well, a quick back of the envelope grep means that I'd have to add 172 * 5 * 4 * 3 =~ 10,000 extra races for all the possible class combinations (some of which may not be that interesting) and ~3,000 extra monster races for all the other level flags.

So I'm interested in feedback - should I separate these out as different monsters or not? Or is it not that interesting to run into Black orc scouts, Black orc archers, Black orc mages etc in all their permutations - you'd be quite happy with just Black orcs.

Poll results for 'How do you like killing monsters in your favourite roguelike'; new poll

Poll results for 'How do you like killing monsters in your favourite roguelike' were:

Bumping them, the way Rogue intended.	16 (43%)
Shooting them, the way Bard intended.	4 (10%)
Roasting them with magic, the way Nandos intended.	5 (13%)
Catching them in traps.	4 (10%)
Sneaking past them.	3 (8%)
Recruiting them to fight for you.	4 (10%)
I'll let you know in the comments thread.	1 (2%)

And the winner was Hallucination Mushroom 'with a shovel'.

Next poll up: what is your favourite tactic for starting the game?

Unangband-0.6.2-wip7a has been released

This release is mostly a bug fix revision to wip7, however, I was able to sneak in some game play changes.

For full details, please see the Unangband home page at http://unangband.blogspot.com

A stack of problems

It has been said that Angband is a game of inventory management. If so, then then the mastering the Angband item stacking algorithm is like playing invisible Tetris: possible, but you have to know the rules and what order the pieces arrive in.

The Angband inventory has 23 slots, in which each slot up to 99 items can be placed. In addition, each item has a weight, which the character's strength determines the maximum total weight that can be carried. The slot function is the most important, however, as a set of hidden rules cover how many different types of items can be carried in each slot, and these rules are known as stacking rules.

At a high level, a set of tests in object2.c in the object_similar() code test if two stacks of 1 or more objects are similar, and if so, the two stacks are combined using the object_absorb() code. I'll endeavor to describe a high level version of the algorithm:

1. Artifacts (unique magical objects) never stack.
2. Objects may not stack if their kinds are different. An object kind could be 'a set of leather gloves' or 'a wand of fire bolts'.
3. Objects may not stack if their ego_types are different. Some objects qualify for ego types, such as armours 'of resist fire' or weapons 'of acid brand'. Others, such as wands, do not have ego types.
4. An object may not stack if its to-hit, to-damage or to-ac bonuses don't match, if it has any of these properties. Other numeric values also prevent this (such as different weights) - except -
   
5. An object may be forced to stack if it only has a different 'discount percentage' if the stack_discounts option is selected.
6. Wands, staves and rods with differing charges and/or timeouts may be allowed to stack together, but the charges and/or timeouts may mysteriously disappear, or be 'averaged out' on the stack. The exact method used for this depends on the Angband variant.
   
7. An object may be prevented from stacking if the player has identified its characteristics from another identical object that the player has not identified the characteristics of, some characteristics of which the player will never actually be told about.
8. An object will not stack if the player has 'inscribed' it with a note, with an item not so inscribed, unless the stack_notes option is selected.
9. Some variants implement a quiver system, which has 10 additional slots, which can be used in exchange for 1 inventory slot for every 99 items total in the quiver (regardless of the number of quiver slots occupied by these 99 items). However, only certain equipment is allowed in the quiver.
10. Hengband allows you to collect all the different types of wands in a separate inventory screeen.
11. Unangband allows you to have magical bags which occupy a single inventory slot: each of which has 23 further slots, which can hold up to 99 items per slot. However, the kind of item (see point 2) for each slot is fixed for each magical bag type.

Simple!

The inventory slot mechanism is a great game mechanic, because it forces the player into trade offs: roughly speaking each inventory slot corresponds to one in-game function, be it healing, or attacking with arrows, or magical fire, or causing monsters to fall asleep, and so on. However, the stacking mechanic leaves a lot to be desired from a comprehensibility point of view. Which is why, I am considering simplify the mechanic in the next version of Unangband to the following three rules:

1. Artifacts (unique magical objects) never stack.
2. Objects may not stack if their kinds are different. An object kind could be 'a set of leather gloves' or 'a wand of fire bolts'.
3. Objects may not stack if their ego_types are different. Some objects qualify for ego types, such as armours 'of resist fire' or weapons 'of acid brand'. Others, such as wands, do not have ego types.

This will require amending the current inventory slot system to include a linked list of objects for each slot. The top of each linked list will be displayed in the inventory as follows:

a) 6 of 19 daggers (+1, +1)
b) 3 of 7 wands of magic missiles (10 charges)
etc.

where the 'of 9' indicates the total number of items in the linked list (each list element can hold up to 99 items as before). The top item will be shown as the 'best' identified item, and a sub-list will be shown when the slot is selected e.g.

a) 6 daggers (+1,+1)
b) 5 daggers (+1,+0)
c) 4 daggers (+0,+0)
d) 2 daggers {magical}
e) 2 daggers {cursed}

I'm also considering implementing a special inscription '=t' that will allow objects to be stacked by tval, which corresponds to 'swords' or 'wands' or 'potions' instead. This may tip the balance the wrong way too far, but it should considerably simplify the code and the number of exceptions made to the existing Unangband stacking implementation.

Oops

Less successful is an attempt to invest the cast with the sort of one-liner personality
Aliens did so well. It backfires, rendering them all unloveable.

New poll is up - how do you like killing monsters in roguelikes?

If you're stuck for ideas, I've discussed previously the number of different ways in Unangband you can kill them enemy, and even provided a handy table to help you figure out the advantages and disadvantages of each. Of course, with the introduction of allied monsters in Unangband, those methods have expanded considerably.

Please feel free to comment on the poll under this post. I'm surprised that Blogspot don't make the option available directly under the poll...

I'd particularly like to hear back from people who reported having problems getting Unangband running. You may want to look at this thread on angband.oook.cz to see if this helps you.

Unangband 0.6.2-wip7 has been released

I was hoping to make this a beta release, but there's been enough significant platform changes that will need ironing out before I can confidently call this beta.

Having said that, this version is almost feature complete. I just need to decide how to address some game balance issuses raised by Mikolaj Konarski and Matthias Rudolf. Continued thanks as well to Mikolaj for constant feedback, bug reporting and patches to the code base.

For full details, including change log, go to the Unangband homepage.

Unangband monster AI - part three (Emergence)

In part two, I mentioned that monsters were woken up as a side-effect of the monster talking code. Consider, for a moment, an AI system that only relied on monsters talking to each other, and did not implement any path or route finding algorithms. You could do this as simply as having monsters saying one of two things:

1. The player is not here
2. The player is here

The behaviours you'd then implement in a system would be:

1. If the player is here, stay where we are.
2. If the player is not here, move somewhere else.
3. Move away from positions you can hear a monster saying that the player is not, and towards positions that you can hear a monster saying the player is.

The emergent properties of that system would be that monsters would quickly move towards the player location, without having to rely on an explicit route finding algorithm.

In Unangband, such a property emerged from another AI flag I had implemented, without me even intending to do so. The flag in question is the wonderfully named MFLAG_PUSH, which I added to fix a problem I introduced modifying the 4GAI.

In Angband, particularly powerful monsters can push past weaker ones, swapping positions. The 4GAI expands on the numbers of monsters that do this, and in Unangband, I basically allow every monster to push past another. However, this can result in a deadlock situation. Consider two monsters that are running down a corridor. If the one in front is moving before the one behind, no problems occur. However, if the one behind moves first, it'll swap positions with the first. Then the first one, which is now behind, will swap positions again. The two monsters will end up effectively running in place, swapping positions and never going anywhere.

To avoid this situation, I added the MFLAG_PUSH flag, to which was set on both monsters, when one pushes past the other. And when a monster has MFLAG_PUSH set, it becomes unpushable, until the start of its next move, at which point it is cleared. The flag is set on both monsters to prevent either getting 'free moves' by being pushed around by multiple monsters: originally I did this to prevent a monster that must swim being pushed beyond the edge of water (which requires two consecutive pushes), but it equally applied to stop a powerful monster getting multiple moves against the player.

And something interesting happened. Consider the interaction of a group of monsters moving at the approximately the same speed towards the player, one behind the other. However, the monsters are moving in a larger area, like a room. At some point, the front monster will end up with the MFLAG_PUSH flag, because he'll be slightly faster than the others and pushed his way to the front. However, because he's not twice as fast, so the monster behind will get a turn first before he can move again. The monster behind clears the push flag, and considers which squares he can move into. The immediately front one is blocked, by a monster with an MFLAG_PUSH set. However, the two immediately diagonally to either side are clear. Since all Angband variants don't increase the movement cost of diagonal moves, the monster will choose to move into one of the diagonals.

And the monsters behind him will take the same approach. What emerges, is that the group of monsters naturally spread out to a wide front taking up the available width of the open area, or their group size, whichever is smaller. And it so happens, that a wide front is the smartest group for most monsters to form.

Its important to note that this occurred accidentally, without any concept of formations or other AI tricks programmed in, and is a single bit-flag setting in the monster structure. The route finding required for this formation is completely local: a simple 'can I move into the adjacent grid' test. And the emergent property is impressive, resulting in a complex looking front on the playing field.

If you look hard at the concept of using local information to guide the monster AI, suddenly a number of other useful strategies make themselves apparent. I've already discussed the monster talking above; but here's a few more:

1. Monsters should hang around dead bodies, but not too close.
2. Monsters should hang around injured fellows, but again, not too close.
3. Monsters should aggressively search, if they find a dead body (This is straight out of Metal Gear Solid: of course, remember to mark the body as having been found, otherwise the monster will keep going into high alert mode every time they trip over the same corpse).
4. Monsters should share resources they don't need with each other.
   

Point 4 is a subtle one. It's not monsters should ask for resources they need. That behaviour is too complicated, and requires all sorts of smart AI assessment. Consider the resource of ammunition. Unangband has added ammunition on top of the 4GAI, to balance monster archery. And monsters do quickly run out of ammunition, if they're given half a chance to shoot at the player. At this point, they could either do a complicated search algorithm to try to find out which of their compatriots has ammunition, or just advance on the player and try to attack in melee.

And advancing, as I've noted previously, is a lot more interesting for the player. However, the monsters directly behind the archer, if any are there, may possibly have the ammunition that the monster needs. And they're not doing anything, so they should be sharing ammunition with anything they push into. Consider it a game economy of ammunition sinks, and ammunition providers. You want the providers to share freely with the sinks. The sinks will naturally be greedy without even trying.

I've implemented (approximately) the following algorithm:

1. If the monster I walk into and I use the same ammunition, average the amount between us.
2. If I have ammunition that the monster needs, give him half my inventory, including the ammunition.
3. Otherwise, give him all of my inventory.

And the result, of a simple sharing routine, is that everyone in a group quickly ends up with approximately the same ammunition. As it gets used up, the individuals in the group ensure that overall, each has the same amount. Again, the rules are only local, not global.

I'm in the process of adding a second emergent property to the same MFLAG_PUSH flag. The MFLAG_PUSH is another way of saying 'don't walk through me'. And when you think about it, the time you don't want that the most, is when you are doing useful work. The most useful work a monster can do, is successfully attack the player. By adding an MFLAG_PUSH to the monster when they've successfully attacked the player, a number of other useful emergent properties occur. And I'll talk about those in part four.

[Edit: Actually I won't. I end up introducing the allied monster AI in part four, because it's hard to talk about the effectiveness of AI, without having a playable demonstration, and showing off the ally AI is the easiest way of doing this. Basically, as pointed out in the comments, you don't want to have ranged attacks being marked as 'useful work' because you can have archers blocking melee monsters in corridors, but you do want melee monsters to be marked as doing useful work, for other reasons].

And now for a message...

One of the problems with adding friendly monsters, or for that matter talkative monsters, is that they generate a lot of additional message traffic. The Angband message UI is not great: messages are displayed at the top of the screen on one line, and you have to press a key to see the next message in the sequence. The alternative is to display auto_more, which means you don't see any messages at all. Auto_more is intended for use in conjunction with displaying the message history in one of the Angband term windows. The disadvantage with that is that you devote a lot of screen real estate to what may be one message, or one hundred. And if its one hundred, you'll only see the last 20 messages or however big the term window you use is.

The Angband variants haven't improved on this much. Sangband allows you to have a larger message line size, which is a slight improvement on both auto_more and the Angband default, but not significantly so. In general, no one seems to have come up with a good solution. Until now.

I've added an easy_more interface, which I'm going to try to make the default for the next release of Unangband. The easy more interface overwrites the whole display (actually preferring to use the top half of the screen for readability), including the playing field with game messages, as in this screen shot.

The big disadvantage with that is you may have important display information obscured by the messages, including e.g. the location of the player. But a quick press of the escape or return key, allows you to dismiss the messages and see what you're doing. And if there's more than a screenful of messages displayed in a round, you can use space bar to scroll through them all. Its important to note here that (except on Windows - see below for why) you'd never have to make more key presses than you would under the existing message implementation.

More importantly, I allow the player to continue without being interrupted at all. At the point you could press space or return, you can also enter an actual command. So if you don't see anything important happening, you can continue to do whatever you want. So easy_more acts like auto_more in that the messages don't (usually) interrupt your play.

So what do I end up doing with the top line of the screen, the one that used to show messages, now that easy_more overwrites the playing field with messages?

Well I have this great mouse implementation in windows, that allows you to move the mouse pointer over anything in the playing field, to see what it is. It's windows only at the moment, because I haven't been able to do platform specific code for any other platform (Linux, I'm looking at you), which is basically just polling the mouse pointer position, and sending a key event with mouse button set to zero, if the mouse moves over a different grid.

But that kills two birds with one stone. And I'm happy with that message...

(I'll be doing the 3rd AI article later today).

Unangband monster AI - part two (What is worth doing?)

Part one of this article is here.

I want to expand on that idea of 'if the player can't see it, its not worth doing', which R. Dan Henry, current maintainer of Gumband is a big exponent of. There's a great article on artificial intelligence in F.E.A.R. called 'Three States and a Plan: The A.I. of F.E.A.R.' which anyone who is serious about artificial intelligence development for games should read. While the technical details are interesting, the key point worth making is that player's don't want realistic AI in games. They want AI that tells them what their opponents are thinking.

A player in a game will be frustrated if while they're hiding in a vent, an opponent rolls a grenade in and kills them without warning. That would be the realistic AI option, but that development effort ends up with the unintended result that the player just thinks the game is hard, not that the enemies are smart. What the player instead wants, is to hear the enemy say 'Gordan Freeman is hiding in the vents. I'm using a grenade.' That's not realistic at all. In a movie, you'd cut away to show the enemy soldiers signalling with their hands (and it'd still be exaggerated). But because the player can't see this, the AI actions have to be telegraphed to them. And audio dialog is used in a FPS engine to do this.

One of the most effective AI actions in F.E.A.R. is when the player has killed all but one of their enemies and they hear the radio message 'Man down, I need support. Calling for reinforcements.' broadcast by the last remaining survivor.

The equivalent AI action is: do nothing at all. No additional backup arrives. The designers didn't need to worry about developing this code. The player perception is that the backup is coming, so they have an incentive to hunt down the last survivor. And the designers know that there are more soldiers around the next corner, which the player will perceive as the reinforcements arriving a little to late. It may sound like a cheap trick, but it is a huge saving in development cycles and CPU time.

So what does Unangband do?

I try to find cheap answers, as opposed to smart answers. I'm not going to exhaustively catalog them here, more give you tasters of the various techniques I use. A lot of developers equate Artificial Intelligence in gaming with computer science AI, in particular, route finding or path finding. These are more the domain of operations research, which concerns itself with finding the best solution. AI should be more about finding a 'good-enough' solution: for local agents using limited information. The local agents, in the Unangband case, are monsters, and where possible, I strengthen the use of local information, rather than global solutions.

The Unangband monster structure contains the following 'local AI state' which is inherited from the 4GAI:

1. A target (x,y) which the monster is heading towards.
2. A minimum range that the monster wants to stay away from the target.
3. A best range, that the monster wants to ideally be at.
4. A set of flags which contain some AI state information: in particular, did the player attacked me the last turn.
5. A set of smart flags indicating what resistances the monster has learned about the player.

Other than adding a few flags in 4, I did not expand at all on the existing monster AI structures. In return, I've been able to add the following additional behaviours:

1. Monsters talk to each other, conveying information about the player position, resistances or lack of resistances.
2. Monsters wake up their fellows nearby when they are under attack.
3. Archers will share ammunition with each other, so that each monster in the group will usually have ammunition available.
4. Monsters will eat when they are hungry, to help them recover from injuries.
   
5. If a group of monsters is fighting the player and the player can be flanked, some will sneak off and take the back route to the player.
6. Added friendly monsters, which intelligently move around the player and get out of their way, and attack targets, all done without adding a single 'order a monster to do something' command.
   
7. When fighting another group of monsters, archers and spell casters will stay at the back while warriors will move up and form a front line.
8. Faster monsters like wolves will attack isolated enemies, and the edges of the front line, dashing in for a bite and then retreating back.

That I've been able to achieve all of that is firstly a testament to the 4GAI code. I was amazed how readily I could add friendly monsters, despite Leon's opinion to the contrary. The concept of minimum range and best range is brilliant, and most of the formation code relies on this idea. But its also shows that you don't have to write particularly intelligent or deep code if you rely on using local agents 'naturally' and stick to local information. In the rest of today's article, I'm going to discuss point 1, and in follow up articles how I achieved the rest.

There are AI routines which already exists in the Angband code that allow the monster to learn about a player resistance, and then base the spell to cast on the information available. For instance, a vampire with several different elemental bolt spells might try the strongest fire bolt first, and, learning that the player resists fire, switch to lightning, then cold, and so on as additional resistances are learned. 4GAI provides much of the improvements to the code to allow this natural progression to occur, including adding monsters that rely on this.

In Unangband, if a monster learns about a player resistance, it tells all the other monsters around it. The player sees a message similar to 'The goblin wizard casts a fire bolt. The goblin says "The player is resistant to fire"'. Other information gets conveyed the same way, such as if the player is doing cheap exploits like hack-and-back or pillar dancing, the detection routines which come from improvements in the NPPAngband code. Pillar dancing may be seen as cheating by the august fellows of Rogue Basin (And I think John Harris would disagree), but in NPPAngband, monsters notice you doing it to them, and in Unangband, they tell everyone else around them as well, so the advantage of doing so is lessened.

The information communicated includes a state change on the listening monsters so that the talker knows not to provide redundant information if someone nearby has already mentioned it. This state change already exists in the monster structure, either being the player resistance flag, or other local information (such as am I awake?). And there's some nice gloss to requiring that the player speaks orc, to understand what those Uruk are saying, and so on.

The talkers will wake up monsters near them, which lessens the ability of super-stealthy characters to wake up and fight one monster in a room at a time, which always feels unrealistic to me in Angband. Of course, to counter this, if you manage to stun or cut a monster badly enough, it loses its ability to talk, so a backstab with a blade or blunt weapon becomes more worthwhile. And if you go around beating up the townsfolk, they run away, and tell everyone around them to run (or turn the tables on you if the listener happens to be a battle-scarred veteran), because they don't clear the particular 'I've been attacked' state flag, and pass it on.

There's nothing complicated about the code used to add monsters speaking. In fact it turns out that the problematic code that in the latest version causing monsters to randomly note you have incorrect resistances was me trying to be too clever, and simplifying the code was the correct fix. The incidental effects greatly improve the player perception of the AI. And, it makes a 'hidden' feature that has been in Angband for a long time: the fact that monsters learn about your resistances, a lot more obvious to the player.

In part three, I'll discuss other local monster interactions.

Unangband monster AI - part one (History and Context)

(This article is in six parts: parts one, two, three, four, five and six, and is also available as a PDF).

Unangband monster artificial intelligence routines have evolved from the Sangband and Oangband's so-called 4GAI which is short-hand for Leon Marrick and Bahman Rabii's "4th generation Artificial Intelligence". It's a set of common functions and algorithms used across a number of Angband variants: in addition to Sangband and Oangband (and FAAngband), its been adopted separately by NPPAngband and Unangband, both versions of which have evolved in different directions.

Its called 4th generation, because it's the fourth major evolution of the monster AI routines in Angband's history. Leon Marrick has written extensively about it in the comprehensive design manual.

I'm going to quote the development history liberally from this manual as the original is a text document which likely won't format well in your browser. The history is interesting reading and written with Leon Marrick's usual mix of enthusiasm and iconoclasm:

History: Standing on the shoulders of giants

The history of coding monster intelligence ("monster AI") in Moria and Angband is a long one. You will not be reading the true history here; the following is one man's (i.e. LM's) opinion and viewpoint on previous AIs. If you don't disagree with me at least once in the next six paragraphs, you need to learn more about this subject!


The First Generation:

The first generation AI was mostly the work of Robert Koeneke. Each turn, a monster would attempt to cast a spell, if it had any. If it passed the spell frequency test, it would pick a spell at random. Although a primitive method, choosing spells at random had the great advantage of keeping the monster true to character. Not only was every spell guaranteed to be used, but monster designers could tweak the frequency of, say, harassment spells against attack spells by changing the number of each.
Monsters that didn't cast spells entered the movement code. This involved choosing a direction that best approached the character, plus the two directions that flanked it on either side, for a total of five possible directions. The monster would then try these five choices in order, testing any doors or glyphs, moving as soon as it found a grid it could enter or succeeded in clearing. Again, to say that this was crude is less important than to note that, in the conditions of Moria, it worked acceptably.
The young Angband added many spells and new features, but made few changes to this basic system. However, at or before version 2.6.2, intelligent monsters were made to cast better spells if desperate, and the first monster terror code appeared.

The Second Generation:

When Ben Harrison took over, things started to change. First came a massive code cleanup. David Reeve Sward contributed the basic monster learning system we still use today; by storing information about character resists and immunities, monsters could learn to probe for missing resists - and then exploit them cruelly! William Tanksley came up with a way for monsters to target the character, which allowed them to track their enemies down in a realistic, limited fashion. Ben Harrison introduced the famous monster flow, which stored the route distance from the player up to a range of 32 every time the player moved. Although extremely CPU-intensive, and criticized as giving monsters too much of an advantage over the player, the monster flow code made such a difference to monster intelligence as to become almost indispensable. It eventually replaced the monster tracking code. This, then, is the suite of features of the second generation of monster AIs, and the common possession of all modern Angbands.

The Third Generation:

When the Keldon Jones AI came out, it caused a sensation. Monsters stopped killing each other off with magic missiles, Zephyr Hounds starting luring the player into rooms, orcs started to surround the player, and monsters chose spells according to their tactical situation so cleverly that some of them became nearly unkillable. It took a while, but eventually almost every major variant and Standard Angband adopted this code with greater or lesser modifications. The best word on the Keldon Jones AI is that of Greg Wooledge, explaining why he included this code in his variant: "I simply couldn't stand watching the novice rangers act like Keystone Kops any longer.".

The Fourth Generation:

But the Keldon Jones AI was by no means perfect. For starters, it was extremely slow. In addition, this system made many monsters act out of character by discriminating against certain classes of spells or by making monsters suppress their most useful attack, and was difficult to fine-turn, either by the monster designer or the coder. Because of this, Standard Angband, Angband/64, Drangband, Oangband, and Zangband all made significant improvements at one point or another.

In the minds of Bahman Rabii and Leon Marrick, the work appearing in Oangband (remember, that's short for Opinion-Angband) 0.5.1 and 0.5.2 is the first of these efforts to go decisively beyond the level of the third generation, and merit the title:

"The Fourth Generation AI".

The manual is full of implementation details and notes for Angband variant writers, and is probably useful for most other roguelike developers as well.

NPPAngband has evolved the 4GAI in a number of interesting ways, with a primary focus on getting the correct route across multiple different types of terrain. Jeff Greene and Diego Gonzalez adopted parts of the Unangband terrain code, and decided to extend the existing flow code to use multiple per-terrain flows with varying movement costs based on the type of terrain and the 'native-ness' of the creature to the terrain it is planning a route through. More than enough improvements to the 4GAI were done to justify the moniker of "4.5GAI" when looking at the NPPAngband source code (unfortunately not available to browse online).

Increasing the different types of terrain complicates a lot of the monster AI route finding, because it is no longer possible to guarantee that the route the player and the monster takes is the same. It also exponentially increases the number of routes to be computed based on the number of different types of terrain restrictions. For instance, the shortest route may require that a monster swim through lava, then fly over a chasm, then open a door. Up to eight flows would have to be computed in this instance, based on the combinations of lava-nativeness or lack of nativeness, and ability or lack of ability to fly and open doors. Efficiencies can of course be gained by noting which monsters on a level have these capabilities.

However, in the long run, I've decided the effort to handle these combinations is probably not worth it. Even with perfect path finding, the player may be able to freeze the water, preventing a swimming monster swimming through it. Or a door may be opened or bashed down by a monster capable of doing so, thus allowing other monsters through that may be not so capable. The dynamic flow should pick up and allow the monsters to notice the changes, but in the mean time, they may have moved down a less efficient route, taking them away from the player. And the most interesting monster is one that is walking towards the player, trying to attack, as opposed to one that is moving away.

So I've decided to stick with the existing 4GAI 'flow-by-scent' and 'flow-by-noise' approximations, even if I have yet to adopt the 4GAI noise-making routines. They are good enough approximations for the moment, and have a credible real-world explanation for how the monster finds the player. And I will do some route-finding improvements at some point. I've tentatively sketched out extending flow scent to have a separate 'scent through water' flow, that monsters may or may not be able to take advantage of. And I definitely want smarter fleeing routines, and improved ability to escape hazardous terrain.

I'd also like the ability for monsters to try and 'sneak up' on the player without them being invisible - the current Unangband implementation just doesn't work very well on this account. I've developed some currently commented out code for the monster equivalent to the player running algorithm, to try to get monsters moving between rooms in an interesting fashion. But, as the denizens of rec.games.roguelike.development note: if the player can't see it, it isn't worth it.

More coming in part two.

Battlefields

I want to make battle field locations a lot more interesting than they currently are. At the moment, a battlefield consists of a big open area which is filled with a little bit of water and a mountain, with monsters scattered around it. You have to find the enemy unique leader and kill them to complete the battle.

I've just added allies based on your race, so you arrive in the battle with friends on your side.

However, I want the battlefield to consist of hundreds, if not thousands of monsters, and to be interesting to navigate, which is not the case currently.

So I suspect I'm going to do the following and create a 'battlefield' terrain, which consists of three states: a picture of an allied monster, a picture of an enemy monster, and a 'stack of bodies' picture. The battlefield terrain will be impassable and be laid out on the map as walls in a maze that spans the whole map.

Its such a big hack, I'm cringing internally as I write this. However, it seems to be the only way of conveying a huge battle scene without it slowly emptying out, or grinding the CPU to a halt emulating thousands of monsters.

Any other suggestions?

Polling your opinion

Occasionally, I can't make my mind up. Which is why I like asking the public. Which is why I take advantage of the handy polling feature on angband.oook.cz. There are currently two polls running on Unangband, in which you get to give your opinion about in game features. I'll add a polls link to the Unangband website as well for these, so you can come back and give your opinion at any time.

The polls are currently:

1. What is stopping you from playing Unangband?
2. Should Hobbiton be accessible after you leave it?

Edit: Coincidentally, Blogger has a new online polling function. For those of you who don't want to vote on angband.oook.cz, you can now click on the handy feature on the right, which I'll be updating on a regular basis.

The mother of all assumptions

I've just fixed a long outstanding set of bugs to do with automatically learning about the various properties that your equipment has. It was a subtle class of bug: I had made and documented the assumption that the object_can_flag() function and family is only called on objects in the inventory, and immediately broken that assumption in lots of places. I'm now passing around a floor flag to indicate that the object is not in the inventory.

As for the next release: I'm aiming for the end of October, as the next Angband competition is concluding then.

Turtles

Because real life has to intrude occasionally.

Character beats

Watching the trailer and downloading the demo at the moment for Jericho. I'm slightly optimistic about this one, but I know I'll be disappointed. Simply because the games seems to take itself way too seriously, and, as Alec Meer from Rock Paper Shotgun notes:

Without going into too much detail on Jericho because I’m reviewing it elsewhere, one thing that bothered me about it was that its squad are arrogant dicks.

which is a shame because the concept is great. It sounds like the developers needed a Harvey Smith to work on the character interactions a little. In fact, they probably needed to go back and study the best action movie ensemble cast to figure out how to play the character interactions. And I'm not talking about Predator.

To recap on the characters in Jericho, I'll quote Wikipedia:

The Jericho Squad consists of several team members, each with their own special weapons and paranormal powers:

• Capt. Devin Ross – the protagonist, Jericho Squad captain, team telepath and healer. At one point, Ross is killed, allowing him to possess his squadmates and control them directly.
• Father Paul Rawlings – the dual-pistol-wielding priest and exorcist.
• Sgt. Frank Delgado – a minigun-wielding alchemist and pyromancer with a fire-demon encased in his right arm.
• Lt. Abigail Black – a telekinetic sniper who can control bullets in mid-flight, enabling multiple strikes in a single shot.
• Sgt. Wilhelmina "Billie" Church – a ninja-esque blood mage who uses her own blood to cast spells and wards. She uses a machine pistol as her main weapon and a katana as her secondary.
• Capt. Xavier Jones – a seer who uses astral projection for reconnaissance and possibly even possession of enemies.
• Cpl. Simone Cole – the Jericho Squad's reality hacker who can alter time and teleport supplies and personnel

Now that should be enough variety for a huge number of possible character interactions, used to build the relationship between the player and the team. Taking a leaf from Left4Dead, you'll want each character to have several pieces of dialog for common situations, so that it doesn't get repetitive: reloading, out of ammunition, reporting the presence of a particular monster, and so on. It looks like the monster design in Jericho requires a particular way of defeating it, such as shooting a weak spot, or using a particular weapon against it. This should mean that a particular character is most effective against it. So you'll also get call-ups when one character wants another to assist in a particular fire fight.

And from that point, you inject the ironic wit, humour, and pathos and so on: the character beats that build up the players perception of the characters. The dialog and character types naturally support this: people will talk to Rawlings or Ross (yourself) for healing, Cole for ammunition, Cole or Black for when they're pinned down and so on. Its just a matter of building up enough character beats to keep it interesting. For instance, Jones might be the sarcastic guy:

• for reloading: 'Reloading, again. Can I get something better than this pea shooter?'
• for new target appearing: 'Oh, you want some too'
• for healing needed: 'Father, is bleeding out of my ass a bad thing?'
• for out of ammuntion: 'Cole, could you warp me in some ammo? No, make that a cheese burger. No, make that Nicole Kidman.'
  
• for saving another player: 'Delgado, did you see that? He tried to grab your ass. I think he liked you.' Church: 'Don't say that. His dentist did that to him in Milwaukee.'

And the movie? Aliens. It has the wise-cracking happy-go-lucky flack out who ultimately redeems himself (Hudson), the calm and quiet hero (Hicks), the quirky out there superhuman (Bishop), the tough as nails bitch (Vasquez) and so on, that would have been ideally suited as models to adapt to the Jericho cast. All those characters are believable and endearing, even the slimy ones like Burke who ultimately betray the team. And they have just enough beats before the shooting starts to make the audience like them.

Level regeneration

I'll be finally getting a working internet connection this evening, which explains why I haven't been posting frequently. I'm currently unemployed, so I've been taking the opportunity to work on Unangband off-line. Btw: if anyone is looking for an IT Manager / Tech Architect in the Sydney area, preferably in the CBD, feel free to drop me a line.

This has conveniently allowed me to ignore the online bug list and work further on level generation.

I've greatly expanded Eric Bock's maze generation algorithm, which I borrowed from Sangband, to allow maze walls and paths of any width; and added a dead-end filler, to allow irregularly shaped mazes. The trickiest part of this was ensuring that the outermost walls of the maze were 'outer' and 'solid' tiles to allow correct tunnel connections, without allowing the maze to be swiss-cheesed by tunnels.

I fixed a lot of generation bugs that were causing disconnected rooms, and to make room descriptions more exactly match the contents of the room.

I've also worked on improving terrain generation, so that lava, ice, water and so on are generated in more interesting ways. For example, it now possible, but risky to walk over lava without damage, provided you time your movements right. I've also tried to improve the consistency of graphics a little more, so that its easier to 'grep the matrix' as one player puts it.

I've also changed how monster ecologies work, so that parts of the ecology are confined to sections of the level. This also will improve the association between rooms and monster types, so if you run into iron thrones, chess boards and weapon racks, you know you're about to encounter warriors of some kind.

That'll probably be it for level generation for the moment with just a couple of fix-ups. I'm going to add some maze theming so that mazes look appropriately 'crypt-like' or 'cave-like' depending on the level they are generated on. I'll also change trap generation slightly, so that you have to find traps first if they are themed to be a particular type.

If you have any requests for further changes to the way levels are generated, please let me know.

Free Burma

I don't tend to believe in too many 'good causes' or political movements. But a popular uprising against an undemocratic system is one that I will support.




Of course, an undemocratic uprising against a popular system is not in the same category.

Ironband

Antoine is a roguelike developer I have a lot of respect for. He's written Guild and Quickband and his game designs focus on how to make game play more interesting. Quickband is an attempt to shorten the admittedly sometimes tedious game-play that Angband suffers from. It distills the game down to a much more limited number of levels and has Saruman as the final boss monster. You should be able to win a game of Quickband in an afternoon of play. Guild is a roguelike where you control multiple characters. Both are based on a greater or lesser degree on the Angband code base: Quickband is a variant of NPPAngband and Guild uses the Angband term code.

I believe Antoine's working on a roguelike in Python, which hasn't been released yet, but which he occasionally discusses on rec.games.roguelike.development. But more importantly, he's just posted an update to another Angband variant he is working on, Ironband. Again, he's distilling part of the Angband game-play to make the game more interesting. In particular, he's removing shops from the game, which is one of the features of so-called Ironman play. Ironmen in Angband traditionally exit the town level straight away and take the first down stair that they encounter until they reach the bottom of the dungeon and kill Morgorth or (more usually) die trying.

What's interesting about Ironman play is not just that the game is a lot harder. Its that many in-game resources become more important, because they cannot be reliably restocked from the shops. As a result, an Ironman character is forced to evaluate the utility of every item that they find, as opposed to just ignoring less than useful equipment in the dungeon. This takes Angband back to the much more traditional Rogue style of play. Food becomes a critical game-play counter as opposed to a minor inconvenience. The player may be forced to move around the dungeon without light, healing or escape mechanisms. And money becomes just a measure of in-game score, as opposed to a fungible resource that can be earned via patient play.

But Antoine's gone beyond just recreating an enforced Ironman style game in his variant. He's added a whole lot of in-game statistics (Stealth, Perception and so on). He's removed stat gain potions and instead decided to distribute a certain amount of stat increases on level-up. And he's gone classless. I'm really happy to see this last decision. I'm sure it'll work out, just as I argued in one of the first posts to my blog. And it increases my respect for Antoine even more. After all, he's clearly a braver developer than I am.