Monday 14 May 2007

Summoning the Borg

One of the great things with the borg in Angband is that you spend a great amount of time staring at what amounts to a screen saver. I mean, its seriously addictive.

But its also a great diagnostics tool, because it automates the checking of a lot of code paths - which is why even if the variant of Angband you're developing is too complicated, you can grab Leon Marrick's dumbborg and see if the code you've written crashes or infinitely loops. I'm using it at the moment to try to help diagnose up a weird object corruption bug, where an object gets stacked on itself, and breaks all the object list traversal code horribly. I don't particularly feel like manually generating thousands of item drops under 'real conditions', and the borg is quite happy to run around killing monsters, or at least zapping them while completely immune to damage.

It was during these diagnostic runs that I noticed in the monster display list: 76 Tyrants of Hell. Now, a Tyrant of Hell is a deep summoning demon, that likes to summon other demons. And having 76 in line of sight is probably not a good thing, in fact, it looks suspiciously like a bug of some kind.

Rogue-likes have a tradition of what is known as 'chain summoning', where a monster summons a monster which has summoning spells, which then summons a monster which has summoning spells and so on. Its usually associated with demons, in fact IIRC, its possible to die from 'Too many demons' on a level in some early ancestral roguelike.

'Chain summoning', when it occurs, is probably at the point where you want to get off the level. Your ability to do damage will be exceeded by the rate at which new monsters are appearing, and you'll be quickly overwhelmed. I say quickly, because unlike monsters that breed explosively, chain summoners tend to be quite tough.

And running the borg in Unangband, I was seeing chain summoning a lot. In fact, a couple of monsters (Tyrants of Hell, Beholder Hive-mothers) dominated this.

Some analysis of why this was happening was in order, and I quickly found the culprit. In Unangband, the monsters are restricted to only appear in a narrow band of levels. In Angband, they can appear on any level from (close to) their native depth onwards.

What was happening, as a result, is that its highly likely that the monster a Tyrant of Hell summons, is another Tyrant of Hell. In fact, its so likely, that they may as well just breed explosively, except by spawning more than one copy of themselves at each turn. This is reinforced by another piece of code in Unangband called ecologies which restricts the total different types of races on a level, but the problem is still there without it.

Which is not what I wanted at all.

So I've added some code, to enforce 'strict summoning' under some instances. 'Strict summoning' basically states, that if a monster can summon itself, then the monster will only summon weaker races than itself instead. This means the summoning chain will go in one direction, so I can guarantee a Tyrant of Hell will summon some kind of lesser demon, and that will summon a lesser demon and so on, ad infinitum.

However, its still not good enough. Because we are summoning summoners, the rate of growth is still exponential. With summoning in Unangband being permitted out of sight, the only restricting factor is monster mana. And the rate of monster mana regeneration over a large number of summoners is such that enough mana will be generated per turn to allow additional summoning. This lowers the curve, but still permits it to grow exponentially.

Since the only monsters I want growing exponentially is breeders, I've got to come up with some other strategy. And any strategy that I choose, I have to be able to cull very quickly summoning from the list of monster spells very cheaply, because monster AI is a frequently called routine.

I've got a couple of options:

1. Total monster population limits.
2. Allies.

Total monster population limits means that when a fixed number of monsters of a race has been created on a level, that's it. No more are generated. The two problems with it are: I don't want population limits for breeders, and I'd have to check the list after each monster death, and flag whether or not anything is left alive that is a candidate for each summoning spell.

Allies is where a monster can only summon a total number of allies, and no more. When a monster is summoned, the allies are shared between the summoner and the summoned, plus a small increment (most of their friends are common to each other). The problem is: killing one of the monsters should add allies to others nearby.

I'm probably going to go with the first one: I can work around the breeding limits by limiting total summons only, not total population. And while I like the concept of allies, I don't think the behaviour is as interesting. And conceptually, the allies pool for a level is the total summons limit.

What should result is monsters who summon from a large range of different allies, and then restrict their summons to allies they haven't yet called on. I might even recycle existing monsters, and allow summons in the instance where the 'summon pool' is exhausted to instead teleport far away monsters nearby that qualify.


Andrew Doull said...

On 2007-05-14 13:46:06, Gerry Quinn wrote on the newsgroup:

> "Because we are summoning summoners, the rate of growth is still
> exponential. With summoning in Unangband being permitted out of sight,
> the only restricting factor is monster mana."

> In Lair, I limited summoning by forbidding monsters from doing it when
> no enemies are in sight. Have you considered this?

In most Angband variants, the standard way to fight summoners is building an anti-summoning corridor and standing in it, waiting for the monster to navigate its way through, which it will obediently do.

In Unangband, if you do this, the summoner is likely to keep summoning out of sight, and flood your position with its summoned enemies.

I think the Unangband way is more 'intelligent' monster behaviour. The downside is balancing this behaviour so it doesn't scale the difficulty up too much.

Mikolaj said...

Frankly, I wouldn't complain if the number of breeders concurrently on the level was limited. I think infinitely many breeders are just an annoyance. What is lethal for weak characters is the fact that the breeders around him are not diminishing if he doesn't kill them fast enough. The fact that they breed also in many other rooms is often irrelevant: either he has enough HP to survive until WOR kicks in with the breeders around or he is quite likely to die after teleport to random monsters, even with no breeders in the target location. (Not to mentions if he ends up confused, etc.)

So perhaps limit the total number of monsters on the level and check this one number every time a monster is created. (Say, there is not enough air on the level for more monsters.) Moreover, perhaps try to generate monsters close to the player first, so that distant breeding flies don't stop Major Demons' summoning feast around the player. :)

About the item stacking bug --- I messed with the code a lot to correct the drops from Wormy disappearing under the created stairs, but probably created some other bugs. Then you changed the code a bit, then I counter-changed ;>, and I'm not sure if it's not the cause of the current problems. Good luck, anyway. :)

Andrew Doull said...

I don't think its your code that's causing the problem. There are very few parts of the code that actually modify o_ptr->next_o_idx. So I suspect its a 'race condition' somewhere that is placing the item on the floor after deleting it. Or something similar.

njerpe said...

IIRC, in Angband the likelihood of a breeder spawning an offspring is inversely proportional to the number of directly-adjacent monsters, or neighbors, that it has.

Why not do the same for summoners?

Unknown said...

Sorry if I'm being dim, but isn't one solution simply to crank up the monster mana required for summoning? Or make it proportional to the power of the summoned beastie, or something? The point is, you can use monster mana to control summoning without introducing arbitrary limits and suchlike. You just have to make summoning expensive enough that it's not always the obvious spell for the AI to cast.

Andrew Doull said...


The monster AI does some similar checking for availability of space around it in order to ensure the summoning spell can fit monsters in.


Altering the mana cost just alters the slope of the exponential curve. It doesn't stop exponential growth happening. For instance, if I e.g. made summoning cost 40 mana and monsters regenerate 1 mana per round, 1 summon per round can still occur if there are 40 summoners.

And I've seen plenty of instances of 400 summoners being active...

Unknown said...

What about allowing the dungeon to have an external summoning "resistance". Many frequent summons in a short length of time could lower the chances of successfully summoning in the near future. The summoner population would eventually approach a fixed value. The summon failure script would say something like "The fabric of space is too weak to summon another demon."

Unknown said...

I know I am kind of late in this thread but I was wondering what if for a monster to summon another it required all of his mana and could only be done with if the monster has full mana. This would give the player some time to try and kill off all the monsters before they could summon more. The only problem i see is if the first thing a monster does upon being summoned is to summon more monsters.

Shoku said...

Because they can summon out of sight it seems like you could crank the curve down even more by having summoned monsters start out with 0 mana. Any monster that really needs mana would likely have time to get some before the player showed up.

Alternatively if you want a hard cap on the number of summoners you could just apply some flag to summons that makes them unable to summon. It wrecks the fun chain of weaker familiars but because that chain becomes problematic in this setting and because you've got to suspend your disbelief to keep from asking "if they do this when I'm not in sight why didn't the fill up the place before I got to this floor?" it seems like a necessity.

I don't quite like the idea of powerful demons not being able to summon more of themselves though.
This might not be practical to code into the game but I've always liked the idea of demons summoning several of themselves into an area just so they could combine their efforts to summon a major demon.

Near the bottom of the dungeon players might need to kill certain demons just to stop a big bad from popping up- perhaps if it had some way of making it harder to get to a lower level?

Euphemism said...

This may be pointless at this point, more than four years after the original post, but here's two ideas:

1) Establish a way of defining monster 'groups'. Then, set things up so that the number of monsters in a group becomes a value accessible for each monster. Each monster then has a preferred group size, and will not summon once the group size has been reached. This eliminates the exponential unchecked growth, but may not eliminate the issue of monsters summoning replacements as fast as you can kill them, which may or may not be an issue.

2) There may be a summon control failure chance, not just on newly summoned monsters, but also on current summons (e.g. when a new summon enters, lose control of any summon at random, or check for loss of control every X turns). This chance should be 0 for low numbers of summons but increases to moderate levels as the number of summons grows. Of course, the 'controller' in all cases should be the topmost summoner of the tree. When a summoning fails, the summon turns hostile to the summoner. In the case that a summoner loses control of a summoner, all of that summoner's summons switches allegiance as well. This would result in the monsters occasionally fighting each other (if Unangband supports that - it may not) which would be amusing at the very least. I'm not sure how this would effect experience gain, however.

3) Something along the lines of idea 2, there may be some sort of upkeep cost with maintaining a summon. The only change that needs to be made is if a summon is capable of summoning, then assign the cost of upkeep to the ultimate summoner. This would mandate a change to the monster AI to have it actively dismiss summons when its own summoners go out of control and summon too many creatures, or simply have a triggered effect on hitting 0 current/maximum mana due to upkeep issues that automatically dismisses a summon.