Procedurally Generated Unique Monsters

[Riff]

Hi guys! I'm doing a thesis on procedural content generation, and for that, I'm looking at ways to generate unique monsters in Angband that are meant to be enjoyable in a challenging sort of way.

To this end, I need help from you: the Angband community. See, I'm hugely into game design and development in general, but as far as roguelikes go, I've never dedicated myself to one game long enough to conquer it. In the past, I've spent some time with Nethack and DCSS. In fact, I've only just started playing Angband for this project. So it'd be great if I could get input from you as my work progresses!

It's also necessary that I get some feedback once I finish setting up my 'experiments' so I can evaluate their value; after all, the aim is to generate content that maximises your enjoyment.

The First Phase - Test Dungeon
If I were to use the game as it is and just substitute the unique monsters with my own, evaluation would take a pretty long while (though I've heard experienced players could finish in a day?) Plus, main reason for using Angband is because it already has a Borg I can use to theoretically evaluate my random unique monsters, and a shorter dungeon would help with simulation times.

My initial idea is to create a test dungeon that comprises a few deeper levels. And to ensure that the unique monsters are actually encountered, a forced quest on each level to beat them before the staircase down appears - this is similar to a boss fight in a sense.

So far, I've figured out how to start the game at a deeper level and grant bonus exp at the start to get the character level high enough. I'll be looking at how to replicate the forced quest from Sauron's level next.

These are some questions I pose for you:

1. How many levels do you think would be sufficient to get a feel for the game? 5? 10?
2. Which depths would be most appropriate for this? Somewhere in the middle or near the end, I would guess?
3. At what level should the character start off? Same as the depth level?
4. What inventory should the character start off with?
5. Should the town be available?
6. Alternatively, rather than worry about the above questions, should I do something similar to some variants and simply 'compress' the dungeon to a shorter version?

[Magnate]

Sounds very interesting, but why do you need fewer levels? Why not just make one unique for each level and set the QUESTOR flag for each of them? That would be the most thorough test of your generation algorithm, because it would use the full range of monster power (depth == monster_level). Using the borg to see how far he gets is an excellent idea.

I'm interested because of the similarities with randarts; the devteam members previously keen on random uniques are d_m and fizzix IIRC.

Good luck with the project.

[Riff]

Well the reason for shorter levels is twofold:

1. Shorter times for simulation. I haven't tested how fast the borg can complete a game, so I'm not sure how important this is. Since I'll be using simulations to evaluate each set of random uniques and that set will keep evolving with each simulation, it's best if I can run more simulations in a shorter amount of time.
2. Shorter times for human evaluation. I figured that if I made a shorter version, I'd get feedback a lot quicker and more people would be willing to give it a go, and thus, I can get more feedback to validate my findings.

[Derakon]

If you want to leverage the borg, you should probably step back a few versions. At the very least I don't think the borg's running in 3.3 yet.

The game already has monster power calculations so it can determine how valuable e.g. Slay Troll or Firebrand attributes on weapons are. It should be relatively straightforward to generate random monsters with a target "threat level".

We've discussed randomly-generated monsters in the past; if I recall correctly the big concern with implementing them was that Angband is at some level a trial-and-error game where you can make a fatal mistake because you didn't realize that the monster you were fighting had some specific ability. For example, not realizing that drolems can breathe poison (their description makes no reference to poison) or that poison's damage cap is 800HP (which isn't mentioned anywhere in-game). You can see how this could create issues when there are monsters that are different every time you play the game. Then we segued into whether or not the player should get automatic knowledge of monster capabilities and I think the discussion died off there.

As for the parameters for your experiment, I'd recommend just picking a few character dumps from the ladder and constructing a composite character based on them. Games vary heavily depending on class and gear found -- for example, while warriors can manage to keep their clvl roughly matching dlvl up to around dungeon level 20 or a bit further, most everyone else will have slowed down their dive before that point. But if you find Boots of Speed then you can dive far more aggressively.

Ultimately what I think would probably work best is a pre-set character at a pre-set dungeon depth. You start the game, get your character, a new level is created, and you seek out and fight the unique monster on the level. Constrain as many variables as you can. I'm doubtful the borg will be especially helpful for this, sadly, since its playstyle looks nothing like that of your average human.

Anyway, good luck!

[Riff]

We've discussed randomly-generated monsters in the past; if I recall correctly the big concern with implementing them was that Angband is at some level a trial-and-error game where you can make a fatal mistake because you didn't realize that the monster you were fighting had some specific ability.

But shouldn't players be cautious of unique monsters in general though? Another further extension I'll be looking at (if I have the time) would be to automatically generate the descriptions as well. I think that would be a good way to at least hint at what the unique monster is capable of.

It's worth mentioning that I'm looking at this experiment from the perspective of whether it's possible to automatically generate unique monsters as good as, or better than the default ones, which were manually crafted. The speed of the generation process will ultimately determine whether it'd be suitable to be implemented in-game. Otherwise, it still offers a glimpse at what a tool for assisting monster design could look like.

As for the parameters for your experiment, I'd recommend just picking a few character dumps from the ladder and constructing a composite character based on them.

That's a great idea! Thanks!

I'm doubtful the borg will be especially helpful for this, sadly, since its playstyle looks nothing like that of your average human.

Yeah, I've heard about that as well... Originally I was looking into coding my own bot/borg, but looking at Angband's codebase, I'm not sure how easy it would be, considering I'd want the bot to be able to look ahead and simulate different sequences of actions before deciding what to do.

The borg is better than nothing then for now, since I need a large number of simulations.

Edit:
I believe the version I have at the moment is 3.4 according to the changes file - forked the latest from github. It's already set up to compile with the borg and it seems to work properly but...from the few runs I've done, it's doing poorly(dying at the first dungeon level once, and from starvation in the town a couple of times).

I'm guessing the borg can run but can't handle the changes in 3.4? What's the latest version of Angband it can beat then? 3.2?

[buzzkill]

Z+ has random uniques. Might want to look at that.

In-depth uniques aren't always be killable. A big part of Angband is knowing when to run, and a unique even when found at it's proper depth by a well equipped character could well prove too much to handle depending on the specifics.

and what Derakon said. You typically need superior intelligence to beat in-depth uniques. The borg probably won't do you much good.

Maybe, just maybe, try creating random-unique vs. random-unique combat. If equally powerful random uniques can square off against each other without it turning into a consistently one sided romp, then you've probably achieved balance within the generation process. Then it's just a matter of pairing that level of generation against an effective approximate character level.

[Magnate]

I believe the version I have at the moment is 3.4 according to the changes file - forked the latest from github. It's already set up to compile with the borg and it seems to work properly but...from the few runs I've done, it's doing poorly(dying at the first dungeon level once, and from starvation in the town a couple of times).

I'm guessing the borg can run but can't handle the changes in 3.4? What's the latest version of Angband it can beat then? 3.2?

Yes, 3.2.0 is the last official borg release from APW. Noz has ported it to 3.4, but there were a lot of fundamental code changes so some of the functions the borg uses to understand the game are no longer effective, hence its poorer play.

Part of the problem is that (IIUC) APW wanted the borg code to be completely independent of the game, which is an admirable goal but means that it replicates a lot of the game logic. When this changes, the changes have to be replicated in the borg code. For example, the borg calculates its own blows, it does not use the game's calc_blows function. And so on for a very large number of functions.

IMO it would be a lot easier to maintain the borg if it called more of the game's own functions and only had the AI code separate - but I don't know APW's views on this. It might make it more difficult to port the borg to variants - but now we have AngbandBase it might not.

[getter77]

I can, very unfortunately, no longer get this game to run on my Win 7 PC as the dev thinks there might've been some Windows update that broke something and he's yet to figure out what on top of being totally slammed with life and his 3rd game project.

Still, this is a Roguelike completely centered on the notion in this topic, so I'd imagine there has to be some good cues that could be gleamed from it: Random Realms

http://forum.thegamecreators.com/?m=forum_view&t=178942&b=5

[buzzkill]

http://forum.thegamecreators.com/?m=...w&t=178942&b=5

I'll have to add this to my list of thing to try, after Sil. Sounds interesting and looks to have a very nice UI too.

[Riff]

Z+ has random uniques. Might want to look at that.

I had a look at the source for that. The idea is similar to Champions in the Diablo series, where they take a base monster and apply random upgrades. I was thinking along the same lines, though using the more generic monster templates in Angband rather than specific individual monsters. But the templates only exist in 3.4 and not 3.2, where the borg works best...

http://forum.thegamecreators.com/?m=...w&t=178942&b=5

That looks interesting. Might try contact him to see if he's willing to share the source code, or at least explain the monster generation algorithm...


I toyed around with the 320 borg. Now I'm not sure whether it's viable to use for my simulations. Occasionally, it just stands around doing nothing or paces back and forth repeatedly. I notice this happens when its path is blocked by rubble (doesn't seem to want to tunnel through it), or when there's no path left to explore (I thought it should skirt the walls searching for secret doors or something).

Very tempted to write my own borg. Any advice for going down that route? I already have ideas for what algorithms to use, but it'll take some time for me to get to grips with the codebase to figure out which parts I can use. For example, can I assume that I can get hints from the save/load functionality in order to be able to save/load game states for the borg's own simulations of possible move sequences?

[Magnate]

Very tempted to write my own borg. Any advice for going down that route? I already have ideas for what algorithms to use, but it'll take some time for me to get to grips with the codebase to figure out which parts I can use. For example, can I assume that I can get hints from the save/load functionality in order to be able to save/load game states for the borg's own simulations of possible move sequences?

If you're serious, please come to #angband-dev on IRC. That's where you'll find someone who knows about whichever piece of code you're asking about. We'd be very interested in using the development of a borg to streamline some of the code, so it could be a win-win.

Basically, the code revolves around four main global structs:

struct player ("p_ptr") is the player, and contains all info about stats, skills and status (hp, resists, timed effects etc.). My suggestion is that you create a struct borg which has a player struct as one of its members. That way you can use any existing function which takes a player struct and call it with borg->player, while having borg-specific functions operate on other members of borg.

struct cave ("cave") is the current dungeon level - every feature of every grid on the level, plus all the monsters (we'll get to objects in a minute). You shouldn't need to change this, unless you want to add some sort of scariness rating for your borg to assign to each grid.

struct monster ("m_ptr") is all the current info about a single monster (e.g. its current position, hp, speed etc.). These are held in the mon_list[] array, but are also accessible via cave->monster. I think the idea was that the array was phased out in favour of using cave->monster but as with so many things about this code, this migration isn't finished. Note that struct monster currently does not contain info like monster flags and spells, as these are currently the same for every monster of the same type (i.e. for every entry in monster.txt). This info is held in struct monster_type ("r_ptr"). One of the most important changes to make for any development of ego or champion monsters, random uniques etc., is to copy more of this info from r_ptr to m_ptr, and then be able to adjust m_ptr flags (and other stuff) on a per-monster basis.

struct object_type ("o_ptr") is any object (consumable, wearable, device, ego, artifact etc.). IMO one of the most difficult aspects of the game is that object data is stored in three different places:
- p_ptr->inventory contains all the objects @ is wearing or carrying
- An array of structs store ("st_ptr") contains all the objects held in shop inventories
- o_list[] contains all the objects on the current dungeon level (whether held by monsters or on the floor: note that objects in chests are not created until the chest object is opened).

Manipulating the o_list[] array is particularly difficult, with hundreds of lines of dedicated functions (see floor_carry, store_carry, mon_carry etc.). It is possible to cycle through all the objects in a particular grid, or those held by a particular monster, but it isn't as easy to understand as it ought to be. On the plus side, we already have a proper way of managing the relationship between a specific object (o_ptr) and its parent template from object.txt (o_ptr->kind). So we don't have the same issue as with monsters where some info is looked up in one struct and some in another: the object creation process starts by copying the basic data from o_ptr->kind (like dice, sides, weight etc.) and then changes o_ptr as further modifications are made (ego, artifact, etc.).

This does rather make me think that the solution to the m_ptr problem is simply to turn r_ptr into m_ptr->race!

This is all a bit stream-of-consciousness and not a proper critique, but hopefully it's a starter for then. IMO the trick is to use as many of the existing functions as possible, storing only borg-specific data separately rather than creating whole parallel structures for objects etc.

[Riff]

I'll get around to that. Currently I'm messing with the keypress hook that the borg uses. I've figured out that I can just use the borg1 file to handle most of it for me, except when it comes to parsing messages, which seems to depend on a lot of hardcoded stuff in the other borg files...

[Riff]

Started looking at what the test dungeon should be. I decided to go for halfway through the dungeon: level 50. For the preset character, I chose a half-troll warrior - pretty standard combination from what I've read. More preset characters, one for each class, might come later but for now this should suffice.

To decide on the character level, equipment, and inventory I took a look at recent characters in the ladder whose max depth were 46-54. There were only about 4 warriors. Not a large sample size to be sure, but better than nothing.

Average character level is 37. For starting gear, I prioritised the common items among the 4 warriors. However, since we're limiting the game to a single level, items such as Scrolls of Word of Recall or Teleport Level are ignored. Total number of items were averaged over the characters who had them.

Remaining equipment slots I just filled arbitrarily from the pool. Where bonus numbers are mentioned, that means I've hardcoded them in so they're fixed. The only addition I've made to the inventory is a shovel - I've yet to fill the remaining inventory slots.

Below's the list. Any suggestions for changes/additions for those more familiar with the perils at dlvl 50? I'll have my code up soon if anyone wants to give it a shot.

Lance of the Eorlingas
Short Bow of Amrod
Ring of Constitution <+4>
Ring of Speed <+7>
Jewel 'Evenstar'
Phial of Galadriel
Augmented Chain Mail of Caspanion
Elven Cloak of the Magi [6, +8]
Small Metal Shield of Thorin
Hard Leather Cap of Thranduil
Set of Leather Gloves 'Cammithrim'
Pair of Leather Sandals of Speed [1,+7] <+8>

69 Arrows
26 Arrows of Venom

41 Potions of Cure Critical Wounds
Potion of Restore Life Levels
2 Potions of Speed
4 Potions of Resist Poison
14 Scrolls of Phase Door
Scroll of Teleportation
9 Scrolls of Satisfy Hunger
Rod of Trap Location
Rod of Detection
4 Rods of Curing
Rod of Disarming
Wand of Teleport Other
2 Staves of Teleportation
Shovel

[Derakon]

All those speed items are a bit much for 2500'. Replace the Ring of Speed with a Ring of Damage (+13), at the very least.

Could you link the dumps you used to generate the composite? I'm curious how powerful they actually were.

[Riff]

Could you link the dumps you used to generate the composite? I'm curious how powerful they actually were.

http://angband.oook.cz/ladder-show.php?id=12204

http://angband.oook.cz/ladder-show.php?id=12152

http://angband.oook.cz/ladder-show.php?id=11855

http://angband.oook.cz/ladder-show.php?id=12052