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]

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]

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]

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...

, 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.

(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"...

[Derakon]

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.

Certainly what I wrote is pushing the boundaries of being too generic. And indeed the base Thing and Thing Set classes would be very bare-bones; they're only slightly smarter than the basic components that make them. They're so generic because there's relatively little that the different possible "real objects" in the game have in common -- they need to encapsulate monsters, items, traps, walls, chests, etc.

The goals are basically:

* Accomplish this encapsulation without getting in the way. You don't want a system where everything is continually climbing inheritance trees to get anything done, for example.
* Allow objects to easily find and interact with each other. This is where the registration of verbs comes in -- the game map essentially serves as a simplified database of what objects can do what with and to what other objects.
* Allow new interactions to be inserted without having to modify existing code. This is basically where object-oriented design becomes relevant. Instead of modifying the existing door code to include the possibility of trapped doors, you can subclass the Door class to make a TrappedDoor class which accepts the Disarm verb and has special logic for the Open verb if it hasn't yet been disarmed.

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.

I agree with you -- this is the boring stuff that underlies a good rule system. In order for you to be able to implement all of these interactions you need a good object model.

[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]

Sometimes the only difference between OO code and procedural code is one of structure, yes. There's no functional difference between a method that operates on an instance of a class, and one that accepts that instance as its first argument (indeed, in many OO languages "foo.bar()" is simply syntactic sugar for "bar(foo)").

Inheritance is useful though, and is an excellent reason for going with OO over procedural code. Players are just Creatures that listen to the keyboard and end the game when they die. All Items can be picked up, but only MeleeWeapon Items can be equipped to the weapon slot(s). And so on.

[Derakon]

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 )

Interesting; I didn't know about those. Thanks! Of course, immutability makes them a somewhat niche product -- excellent for things like master stats for monsters and items, not so much for particular instances of those things.

And yeah, implicit variable creation bugs me sometimes, but it's one of those "just don't do that then" types of situations. If your style guide enforces creation of all member fields in the constructor, for example, then you don't have to worry about whether or not a given instance has a specific attribute.

[AnonymousHero]

Sometimes the only difference between OO code and procedural code is one of structure, yes. There's no functional difference between a method that operates on an instance of a class, and one that accepts that instance as its first argument (indeed, in many OO languages "foo.bar()" is simply syntactic sugar for "bar(foo)").

Perhaps my example of "f(a,b,c)" didn't convey my intended meaning very well. The idea is that the selection of a concrete implementation of "f" can actually depend on the types of any, some or all of the arguments "a", "b", and "c"... whereas in the currently popular OO models the selected implementation of "f" can only depend on the type of "a" (the first/privileged argument).

(This is also called "multimethods".)

Inheritance is useful though, and is an excellent reason for going with OO over procedural code. Players are just Creatures that listen to the keyboard and end the game when they die. All Items can be picked up, but only MeleeWeapon Items can be equipped to the weapon slot(s). And so on.

I find that people very often conflate two conceptually distinct ideas: Subtyping and implementation inheritance. (It's not really their fault -- mainstream languages practically force you into this mode of thinking.) Subtyping is an extremely stringent requirement which models an "is-a" relationship (should basically obey the Liskov substitution principle, that is you should always be able to use one in place of the other) -- very few things actually have such a relationship. Implementation inheritance is a simple matter of convenience and DRY (which is good), but in mainstream languages this automatically implies some sort of subtyping relationship (which is bad, very bad).

I'm not arguing against (implementation) "inheritance" as such, I'm arguing against the conflation of subtyping and impl. inheritance. I find that using free functions or multi-methods helps ward off this conflation.

[AnonymousHero]

(Immutability vs. mutability)

IME choosing immutability leads to more obvious code, and far fewer bugs. As a bonus it often also makes testing a lot easier since f(a) will always return the same value given the same value of "a". If you allow mutability this guarantee breaks very easily since "f" could access all kinds of more-or-less global (mutable) state. Obviously you're going to have to mutate some state at some point, but my philosophy is just that all state mutation should be pushed towards the "edges" of the program.

Perhaps Python is too much in the "mutable" camp at this point to make large-scale "immutable programs" impracticable. However, I don't see any particular reason that the monster instances, object instances, etc. shouldn't be immutable.

And yeah, implicit variable creation bugs me sometimes, but it's one of those "just don't do that then" types of situations. If your style guide enforces creation of all member fields in the constructor, for example, then you don't have to worry about whether or not a given instance has a specific attribute.

I don't see how a style guide can protect you unless your style guide specifically tells you must override __setattr__ (or whatever it's called) to forbid assignment outside of the constructor.

(Of course you could perhaps implement a @decorator which does this. I think this might already exist, actually...)

Anyway, this is all pretty vague -- I just want to caution against perceiving OO as a panacea for fixing Angband. I think most of us agree that it isn't -- I just wanted to call attention to it because people with less experience may perceive it as such... and that would be a mistake.

Over and (probably) out.

[Derakon]

IME choosing immutability leads to more obvious code, and far fewer bugs. As a bonus it often also makes testing a lot easier since f(a) will always return the same value given the same value of "a". If you allow mutability this guarantee breaks very easily since "f" could access all kinds of more-or-less global (mutable) state. Obviously you're going to have to mutate some state at some point, but my philosophy is just that all state mutation should be pushed towards the "edges" of the program.

Perhaps Python is too much in the "mutable" camp at this point to make large-scale "immutable programs" impracticable. However, I don't see any particular reason that the monster instances, object instances, etc. shouldn't be immutable.

I have to admit I haven't done much work with immutable objects being central to a large-scale project. I'm not certain what you mean by "pushing state mutation to the edge of the program"; care to explicate? I do recognize the value in being able to call a function with a specific argument and knowing that that function won't change that argument though.

I don't see how a style guide can protect you unless your style guide specifically tells you must override __setattr__ (or whatever it's called) to forbid assignment outside of the constructor.

(Of course you could perhaps implement a @decorator which does this. I think this might already exist, actually...)

A style guide protects you from people screwing up if you forbid checkins that don't follow the style guide. Of course you could still theoretically write and check in code that breaks the guide. It's like how most door locks are just there to keep honest people from being tempted, not as any significant form of security. Just because they can be relatively easily bypassed doesn't mean they will be.

Anyway, this is all pretty vague -- I just want to caution against perceiving OO as a panacea for fixing Angband. I think most of us agree that it isn't -- I just wanted to call attention to it because people with less experience may perceive it as such... and that would be a mistake.

Over and (probably) out.

Oh absolutely. You can write bad code in any language and with any particular design style you care to use. I have seen some absolutely wretchedly bad OO Python code in my time, to the extent that I'd say it was intentionally obfuscated if I didn't know better.

I've enjoyed our discussion, anyway. Being a programmer requires this weird mix of hubris and humility, as you defend your chosen design while being open to the possibility that you might be wrong.