Roguelike object model theorycrafting

[Derakon]

Short summary: below, I suggest a possible object model for Angband, and invite you to poke holes in it.

Every once in awhile someone will talk about how they want to rewrite Angband in some more recent language, usually Python. This isn't particularly surprising -- the Vanilla Angband codebase is around 240k lines of C, and isn't always particularly easy to understand, so the impulse to just chuck twenty years' worth of development effort and start fresh is always tempting. Especially since Angband does a lot of things "by hand" that you can delegate to libraries now -- event and window management, file handling, resource marshalling, display logic, even random number generators. Not to mention that interpreted languages tend to be much more pleasant to make cross-platform -- no more main-* files!

So there's a lot of reasons to like the idea of rewriting Angband with a more modern approach to software development. And people have tried it, too -- Sirridan was working on a Python implementation awhile back, though it appears to have stalled. Part of the problem is that Angband is so massive that just using a "better" language isn't enough on its own -- you need to have a good design too. There's a lot of detail to handle!

So just for fun, and as a design exercise, and because I only got four hours of sleep last night so hey why not, here's a somewhat vague object-model design for Angband.

We'll start with the map. The map is of course a 2D grid of containers, we'll call them Cells. Each Cell can hold an arbitrary number of Things, which are basically any "real world" thing you can interact with -- monsters, items, terrain, etc.

Since Things often need to be able to find each other in order to interact with them, the Map will have a collection of Thing Sets, which Things can register themselves with. For example, a new monster registers itself with the monster list, which can later be used when casting detection spells, targeting effects, or listing visible monsters. Thing Sets are created and destroyed on an as-needed basis; if a nonexistent list is requested then of course the result is empty. Among other things, this lets us create associations -- for example, when a group of jackals is created, they request a new Thing Set so they can associate with each other, which opens new possibilities for pack AI.

I use the term "Set" here -- if you aren't familiar with the term, sets are collections of objects where each object can be in the set only once. They have the useful property of O(1) (i.e. fast) lookup times to see if an object is in the set. You can also perform set operations on them, like union, difference, and (especially useful for us) intersection. For example, if you want to find all monsters that are evil, then you could either get the "Monster" Thing Set and then iterate over all the entries, or you could have a second Thing Set of evil Things and intersect it with the monster set.

The bulk of the game is in interactions between Things -- a collection of verbs to move Things, hurt Things, equip Things, disarm Things, etc. For now we assume that every verb is transitive (that is, it is performed by one Thing onto one or more other Things); intransitive verbs can simply have the object of the verb be the subject. Of course not all verbs can apply to all targets. We implement verbs as paired functions: one on the Thing performing the verb (the subject), and one on the Thing that is being verbed, so to speak (the object). These verbs have defined interfaces, and may have implications for the Things implementing them. For example, any valid objects of the "attack" verb must have hitpoints.

On creation, Things register with appropriate Thing Sets for all the verbs they are valid objects for. Thus, when, for example, a trap is created, it registers with the "Disarm" Thing Set, which states that it is a valid object for the "disarm" verb. When another Thing decides to perform that verb, they can go to the Map and say "What Things are available for disarming?", and the Map looks up the appropriate Set and returns them.

We can combine this with targeting filters to narrow the set of possible target Things down even further. For example, the standard Disarm action is only valid for Things adjacent to the actor. So we request from the Map a synthetic Thing Set of all Things adjacent to that actor, intersect it with the Disarmable Things, and voila -- our possible targets for disarming! Alternately, you cast the Disarming spell, which removes all traps along a line -- so you ask the Map for all Things along that line, and do the intersection that way.

This all sounds very complicated, but in implementation it should be straightforward. it has several useful features:

1) It doesn't differentiate between the player and any random monster. The only difference between the player and monsters is that the player chooses verbs based on input, while monsters choose verbs based on AI. Practically speaking, anything the player can do, a monster could potentially do.

2) Inheritance and composition make it easy to have standard responses to various verbs while still providing room for special behaviors. Trapped doors, or even equippable monsters, would be comparatively straightforward and unhackish to implement.

3) We can stuff as many things as we like into each Cell in the Map and only have to worry about them when they're actually relevant. We don't have to create a separate layer for each possible category of terrain.

Some more examples:

* The player wants to cast Detect Monsters. He queries the Map for the Monster Thing Set, filtered by the radius of effect of the spell. The spell sets the "visible" flag on the monsters in the set for one round.

* The player wants to fire an arrow at the closest monster. This requires multiple objects -- the arrow to be shot, (implicitly the bow being used), and the monster to be targeted. We assume that the player, like many other Things, has an inventory and equipment composited onto it; like the Map, these can be queried for Things that are valid targets of verbs. So we query both to get a list of valid ammo, which we present to the user to select from; then we query the Map for a list of Shootable Things in LOS of the player's location. When the arrow is fired, its quantity in the player's inventory is decremented and a new Thing is created that is a quantity-1 copy of that arrow; meanwhile, damage rolls and the like are performed on the monster.

* A monster wants to move towards the player. He requests the Player Set from the Map, gets the first (only) entry from it, and runs a pathfinding routine to generate a path from itself to the player. This routine checks squares to see if the monster can move through them via the Move verb. Every Thing that implements the Move verb has to be able to decide if it can be moved through by other Things. Some Things might be "opaque" to movement (e.g. permanent walls), some might be qualitatively opaque (normal walls, depending on if the monster is a wallwalker; monsters, depending on if the monster can trample them), and of course some are open. Based on this path the monster can then execute the Move verb into the best available Cell.

I've omitted a bunch of details -- how do we structure the monster class? How do we handle equipment bonuses? How is level generation handled? How do we plan to prompt the user for actions and selections? And so on. I consider those to be less fundamental, ergo less important. What we have here is the basic object model for the game at a very abstract level; practically everything else is filling in blanks.

[konijn_]

Greetings,

this all sounds good. The hard part for me, when I just threw up my hands, was the 'drop item' code. The logic is so unwieldy in my mind that either I drop all the items on the same square as the monster ( deviation of standard angband which spreads the goodness around ) or I would go slowly insane or I stop converting the whole thing to javascript.

One day when I'm truly bored but motivated I will get back to it.

Some nitpickings:
* "For example, a new monster registers itself with the monster list."
This is a fairly radical departure, probably the level should generate the monster ( since it knows how deep it is and whether it has a flavour ) and then have the monster registered with the level and the level registered with the monster

* "for example, when a group of jackals is created, they request a new Thing Set so they can associate with each other"
Interesting, so the 'total monster set' is a set of sets ( jackals+orcs+etc.) or would you have the jackal register to its race set and the total set ?

I can see keeping all the sets in sync a lot of fun potentially ( dead monster still visible because we forgot to move it from 1 set ? )

Still, I think Angband should move on from C at some point, getting maintainers will get too hard at some point I believe.

T.

[Magnate]

Verbing weirds language.

Thank you. You just crystallised what I've been trying to understand for months about how effects should work.

[Derakon]

Originally Posted by konijn_

this all sounds good. The hard part for me, when I just threw up my hands, was the 'drop item' code. The logic is so unwieldy in my mind that either I drop all the items on the same square as the monster ( deviation of standard angband which spreads the goodness around ) or I would go slowly insane or I stop converting the whole thing to javascript.

Heh. The proper way to handle item drops probably would be to do some kind of Gaussian distribution (where the most items are in the center of the "item explosion" and it gradually tails off as you get further away). As far as this code is concerned you just need to make certain that anything that can pick up items drops them on death by iteratively dropping each item in their inventory.

Some nitpickings:
* "For example, a new monster registers itself with the monster list."
This is a fairly radical departure, probably the level should generate the monster ( since it knows how deep it is and whether it has a flavour ) and then have the monster registered with the level and the level registered with the monster

* "for example, when a group of jackals is created, they request a new Thing Set so they can associate with each other"
Interesting, so the 'total monster set' is a set of sets ( jackals+orcs+etc.) or would you have the jackal register to its race set and the total set ?

Each monster can be part of multiple sets. The jackal would be part of the overall monster set, as well as its "pack" set. You could also have sets for monsters summoned by a given spellcaster, monsters deriving from the same initial Giant Black Louse (hey, inbreeding has to kick in eventually, right?), etc.

This is why I would have the monster register itself instead of having the level register it. Each monster is likely to join more than one set, which may well be entity-specific.

I can see keeping all the sets in sync a lot of fun potentially ( dead monster still visible because we forgot to move it from 1 set ? )

There's definitely some potential for bugs here. Each Thing is responsible for knowing which sets it is in and unregistering from them as needed. Otherwise you get memory leaks. Another reason for each entity to be responsible for all of its set memberships -- you centralize that knowledge and only have to handle deregistration at one point, in the object's destructor.

Magnate: glad to hear that this thread has accomplished something concretely useful.

Oh, and incidentally, you could think of each cell in the Map as being a Thing Set, if you wanted to. There's no functional difference between that and having the Cell as a separate datatype.

[Therem Harth]

You make it sound almost easy, Derakon. Shame I have, like, no skill in actually designing code.

I do wonder if the leap to object-oriented Angband-from-scratch might not be a bit huge. Maybe a procedural version in an interpreted language would be a better path for now? With tables or hashes replacing C structs, or something?

(NB: don't mind me, I don't know what I'm talking about!)

[Derakon]

Originally Posted by Therem Harth

You make it sound almost easy, Derakon. Shame I have, like, no skill in actually designing code.

You get skill by practicing, and by observing others. And for that matter, it's much easier to talk a good talk than it is to walk the walk -- there's almost certainly major gaps in the above design that I haven't thought of. I generally assume that any major project will have to be refactored at least once partway through. The problem is that if you just dive in and start coding without planning things out ahead of time, you need a lot more than one refactor...

I do wonder if the leap to object-oriented Angband-from-scratch might not be a bit huge. Maybe a procedural version in an interpreted language would be a better path for now? With tables or hashes replacing C structs, or something?

(NB: don't mind me, I don't know what I'm talking about!)

You could certainly write a direct port of Angband from C to Python, and it'd almost certainly get you a working game faster than redesigning everything from scratch would. There's two major difficulties, though. First, such a porting job would be deathly dull, so you'd have trouble finding anyone willing to actually do it. And second, once you have your procedural program written in Python instead of in C, you're not actually all that much closer to a cleanly redesigned program! The porting job would have done a good job of familiarizing yourself with the codebase and what everything does, which is helpful, but you'd still have to basically rewrite massive chunks of it, if not the entire thing, to get something usable.

(Also, when it comes to Python, the replacement for C-style structs is classes with no attached methods)

[Antoine]

My main concern has always been that anyone who goes to the effort of porting angband to python is likely to want to change gameplay along the way- so that inevitably the outcome will not be a python port of angband but a new python roguelike inspired by angband...

[AnonymousHero]

As far as I can tell you've just described... variables, haven't you? I mean a "Thing" is a value and a "Set" is just a collection of values (e.g. could be a list, or a bona fide set, or whatever) which is agnostic to what's actually contained in it.

To me this isn't actually the interesting bit. The interesting bit is what interactions can happen between values, i.e. "what happens when player drops an item?", "what happens when a monster shoots at the player?", etc.

[Wild tangent: The interactions is where currently popular OO languages go off the rails. They pretend that one of the values (Things) that takes part in an interaction is somehow "special" whereas it very seldom actually is -- compare e.g. "player.fire(projectile, monster)" versus the free function "fire(player, projectile, monster)". Multiple dispatch subsumes single dispatch and rids of this annoying and harmful asymmetry.... but I digress]

[AnonymousHero]

Originally Posted by Derakon

And second, once you have your procedural program written in Python instead of in C

Hey! You say that as if there's something wrong with procedural programming...

Originally Posted by Derakon

, you're not actually all that much closer to a cleanly redesigned program! The porting job would have done a good job of familiarizing yourself with the codebase and what everything does, which is helpful, but you'd still have to basically rewrite massive chunks of it, if not the entire thing, to get something usable.

... but of course here you're right. If you still have monstrosities such as m_list indexed by a "monster index", r_info indexed by a "race index", manual GC aka. "compaction", then it's pretty much moot... unless you then go on to eliminate those things.

I'm of the opinion that doing a "low-level" port to a "more batteries included" language and then getting rid of the "low-levelness" gradually might be feasible, but it would be an incredibly big and tedious job. To be at all feasible you'd probably need to have a mix of C and $HIGH_LEVEL_LANGUAGE and then just gradually moving bits from C. A good test suite (or even an external/screen-scraping borg) would be a huge help.

Originally Posted by Derakon

(Also, when it comes to Python, the replacement for C-style structs is classes with no attached methods)

Actually, I think the preferred way nowadays is to use named tuples. They have the advantage of not allowing assignment to undeclared attributes:

>>> Vec = namedtuple('Vec', 'x y z')
>>> v = Vec(1, 3, 4)
>>> v.s = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Vec' object has no attribute 's'

(EDIT: ... along with actually being immutable in general )

[ekolis]

Didn't someone a year or two ago produce a reasonable facsimile of Angband written in C#? I think it was called "Cryptband"...