astrosilverio

[astrosilverio]

How not to hack Python’s virtual memory

On Friday I decided I wanted to muck around with a Python process's virtual memory, do something simple like change a value from outside the process. There are blog posts describing how to do this and I expected to be up and running and causing havoc after an hour or so of light effort.

I should probably mention that I have no good reason for attempting this. There are good reasons for peeking at a process's memory; for example, I kept getting hits on Julia Evans' ruby profiler blog posts while googling for how macOS even /procs (bear with me, explanation later). If you're writing a profiler, you definitely want to peek at other process' stacks, heaps, VM, etc. I am not doing that. I just have bad ideas.

First steps

I started out with a vague directive ("change something in a Python process from elsewhere") and started investigating naively, before reading any blog posts or digging around on stack overflow. [Not that there is anything wrong with using tools; I just tend to retain information better when I start from first principles]. I had some facts on hand:

Processes use virtual memory, an abstraction in which physical memory addresses (actual locations on your hardware) get mapped to virtual addresses. As far as I understand, this system provides security (as an attacker, I can't meaningfully guess what addresses contain useful information) and simplifying abstractions for the process itself (as a user, you can run multiple processes at once without having to worry that they might both be using hardcoded addresses that overlap).

Python objects have ids that correspond to the objects' addresses in virtual memory.

I can use id(obj) to see where particular objects live in Python's virtual memory space, and I can even use a module in the standard library called ctypes to set particular bytes in memory and therefore modify VM from inside Python (theoretically; I haven't gotten it to work yet). However that's not quite what I want, and I was still curious about how Python allocates virtual memory anyway.

"Aha", I thought. "There must be something in /proc for this." One of my standard debugging techniques is to just ls /proc/$pid and see if I can find anything relevant in there. For the uninitiated, /proc is a pseudo filesystem in Linux that provides interesting system information in a format consistent with the rest of your, real, filesystem. Every process has a "folder" in /proc indexed by process id that contains "files" full of juicy tidbits; try cat /proc/$pid/status for starters.

Dear readers, I am on MacOS. MacOS does not have /proc. I'm honestly a little embarrassed that it took me so long to notice that I do not have /proc. This is the exact moment that I started frantically googling.

MacOS has tools too! and we get an interesting-ish result

Light digging reveals that there is a /proc/$pid/maps that shows you what each block of a process's VM is for, and that the MacOS equivalent is vmmap. Default output of vmmap includes the type of block and a brief description of what it's for; for a Python process, you'll see non-writable blocks of type __TEXT that are labelled with the path to your local copy of Python and its libraries. There are also address ranges, sizes, and a column for "sharing mode" that describes if and how pages are shared between processes. The C code objects used by the standard library, for example, frequently are stored in "copy-on-write" share-mode blocks. The vast majority of the time, you won't be modifying the datetime library and that code can be shared etween processes. However, if you are modifying that library in one process, you would not necessarily want those changes to suddenly appear in another process; the logical solution is to share that code by default but copy if if you write it, hence the name "copy-on-write". It's abbreviated COW which is why it captured my interest in the first place.

Next I messed around and imported libraries and created objects in the repl and looked up the regions where they lived. Even at the edges of my creativity, most of my objects lived in blocks of memory labelled "DefaultMallocZone" of type "MALLOC_" like MALLOC_TINY or MALLOC_LARGE. That they all belonged to "DefaultMallocZone" made sense to me--after all, everything that I was examining lived in the heap, and I would be concerned if the heap was not all contained under the same label. The different size blocks are an optimization enabled by the operating system that facilitates garbage collection. As explained in this post, different size MALLOC regions have different "resolutions"; MALLOC_TINY, for example, quantifies its allocations in units of 16 bytes whereas MALLOC_LARGE has page-level granularity. Finer grained MALLOC regions let you pack tiny objects in more densely and enables finer-grained garbage collection. However, fine-grained garbage collection is a poor choice for larger objects, which will cause a lot of scanning. The upshot for us is that integers end up in MALLOC_TINY regions and functions end up in MALLOC_LARGE regions.

At this point I realized that I was having a lot of fun but had digressed from my mission. Moving forward.

I miss you, /proc

Next, I found a blog post that describes step-by-step a method for modifying Python objects at the VM level. I gave it a skim and learned that there is in fact a /proc tool that will let you look at a process' VM--/proc/$pid/mem. Once the authors find where the variable they want to modify lives, they overwrite it in /proc/$pid/mem.

Well, /proc/$pid/maps has a MacOS equivalent, so now I just have to find the /proc/$pid/mem counterpart, right?

Wrong.

Turns out MacOS is safe or something? There's a Mach (Mac Kernel) function called task_for_pid that "gives you access to a process's port" which seems useful, but also can do bad things to your computer and requires some security work and I don't want to deal with either.

Next steps? Lessons learned?

I crashed and burned at task_for_pid after a day of frustration. I still don't really have a good reason to be messing with Python's VM, but now I am annoyed and need to do something bad. Therefore, the next step is to figure out how to get ctypes.memmove working so that I can at least muck with a Python process from inside it.

While I'll be ultimately dissatisfied if my day's worth of effort does not result in at least some chaos, I have actually learned some useful things about Mac vs Linux, malloc on Mac, and how Python manages memory (see this transcript).

Until next time,

Your local frustrated agent of chaos

[astrosilverio]

MVCC in PokeDB

As I alluded to last week, a database engine involves a fair number of parts, and implementing each one requires solving different, interesting problems. I just demoed my transaction manager, which necessitated throwing together a storage system, an access manager, and a locking manager with read committed isolation and hoping that it all hung together well enough to present a functional and fun demo (it did, or at least the functional part). The problems that most interest me are concurrency problems, partially out of necessity (I want PokeDB to be able to support concurrent transactions) but also because it’s just plain cool. Databases that allow concurrent transactions frequently allow the user to choose between various isolation levels, so there’s precedent to justify shipping a few different options for PokeDB. Isolation level refers to what guarantees a database provides for how one transaction may be impacted by another transaction; for example, at the read committed isolation level, the database guarantees that transactions cannot read data that other transactions have not committed. Read committed also guarantees that transactions cannot write over data that other transactions have modified but not committed. Those operations are called dirty reads and dirty writes respectively, and can lead to weird behavior if permitted. To illustrate how dirty reads and writes can cause bad states, imagine that transaction 1 is allowed to dirtily read data that transaction 2 has written and make decisions based on that read. What happens if transaction 2 is then rolled back, reverting all its writes? The application connected via transaction 1 has now done business logic using incorrect data. Alternatively, imagine two separate transactions simultaneously want to increment a counter; if dirty writes are allowed, one of the increments will be written over. Not all concurrency problems, however, can be distilled into the two categories of dirty read and dirty write. Sometimes, a system can incur concurrency-related bugs even when transactions cannot read or write over uncommitted data. For example, if one transaction reads the same row multiple times, it is possible under read committed isolation for another transaction to modify that row and commit in between the first transaction’s reads. The first transaction will see data changing seemingly without cause, which could be alarming to end users. A commonly-used solution to that problem is to use an isolation level that restricts each transaction to a view, or snapshot, of the database as it existed when the transaction started. That level of isolation (which I’ll call snapshot isolation but has many names) is the default isolation level for many databases. MVCC or Multi-Version Concurrency Control, is a common way of implementing snapshot isolation. In MVCC, each row of data has two extra columns that store the transaction that wrote it and the transaction that overwrote it, if any. Multiple versions of each row are kept around, one for each update. A transaction will read the most recent version of the row that existed when it began, meaning the version of the row with the highest transaction id that is also less than or equal to the reading transaction id. Once a version of the row is no longer depended on by any open transactions, it can be deleted. I’ve actually already laid most of the rails necessary for MVCC (I knew it was coming). I already keep track of writes by transaction id, although I am only keeping around one version of each row. I record which transactions are open, so calculating which versions should be visible to each transaction will be easy. On each transaction close (or less often, if that is too expensive), I can asynchronously decide which versions can be garbage collected. The main difficulty will be, as far as I can tell, in how to index the multiple rows and how to page them. The worst case read scenario is if there were so many versions of the row that they spread across multiple pages, and the index only pointed you to the first page so you end up pulling multiple pages from disk to find your row. Given that my index will live in-memory, I don’t have that many restrictions on what the values of the BTree leafs are, so I am leaning towards indexing each version separately so that an MVCC read will not necessitate page scans. Stay tuned next week to see if it works out.

[astrosilverio]

Database Design, Pt 2

In terms of actually implementing a piece of software that stores and retrieves data transactionally given requests from multiple clients, I have spent the past week doing a fair bit of reading and have an architecture!

The BerkeleyDB architecture diagram was particularly helpful--not only does it show the various pieces of bits of code and their relationships to each other, it defines the APIs each part uses to talk to the other parts.

I'm modeling PokeDB (ask if you wanna) on BerkeleyDB--transaction control statements will get routed to a Tranaction Manager, data access statements will get routed to an Access Manager, and those two parts will coordinate with a Lock Manager, a Buffer Pool, and a logging system to get everything done right.

There's a diagram of my proposed architecture here. Code lives here.

The core concept is that all requests to a PokeDB database currently fall into two categories: transaction management commands (start/commit/rollback) and data access requests (select these rows / write this data). Those categories are quite distinct; the transaction management needs to keep track of transaction states, and mostly does not care what data access each transaction has done. The data access requests need to know where data live on disk (how else will it retrieve / write anything), but do not care about transaction statuses.

That division of concerns means that the data access path should be separated from the transaction management path. The Access Management package should contain indexes. PokeDB uses an in-memory BTree that gets rebuilt on startup from the datafile. The access manager's job is to take SELECT / INSERT requests, use the BTree(s) to figure out what rows it needs to read/write and where they are in storage, talk to the lock manager about acquiring the relevant locks, talk to the storage layer to get or write the relevant data, and then report back.

The Transaction Management package should only field BEGIN TRANSACTION, COMMIT, and ROLLBACK statements. It maintains an in-memory store of transaction states, and talks to the lock manager on commit/rollback to release locks.

The Lock Management package is mostly where the magic happens. Its API will be pretty simple (basically just acquire / release), but behind the scenes what acquire_lock actually does will be specified by what isolation level you choose to use (more on isolation levels in a later post).

The storage layer will handle modification of and retrieval of data. If you choose to keep your data on-disk, it'll be responsible for pulling pages into a buffer pool and flushing them to write them. It'll also contain a serializer to transform data into a format that the access manager can use from whatever binary format that we use to store the data on-disk. Not only is this the logical design, but also it allows us to start easy and write things in CSVs without making all of the database engine know that we're using CSVs so that later if and when we migrate to a more efficient on-disk format we won't have to change everything.

There are several bits that I am glossing over / have left out, but I am pretty confident that implementing all of the above will result in a piece of software that can be termed a database engine, and that's basically all I care about.

[astrosilverio]

Database Design, Pt 1

It turns out that if you try hard enough, every programming project can be linked back to a text adventure framework in Python. Try me.

The latest installment of the "everything is related to text-based games" game is "WELL it might be nice to have a backing database for the text adventure framework, so UH ISN'T THAT CONVENIENT."

In other words: I have found it useful to think about choices I want to make for the database I am writing in terms of "what would I want if I were to use this database for the text adventure framwork?"

The ultimate goal of the framework is to support multiplayer games with many game objects. The ratio of writes to reads will probably be fairly high--text adventures involve a lot of picking up and dropping objects, and players moving around will cause a write (Location). Reads need to be pretty fast. I can easily imagine cases where everyone in a game is in the same room trying to interact with the same objects, so a strong level of transactionality is desirable. I can also imagine cases where game logic needs to grab all objects with a particular characteristic (maybe you turn gravity off in a room, all objects in that room start floating), so indexes are probably helpful. Finally, my state system centers heavily on relations between entities and components, with components having really specific sets of attributes, which sounds relational to me. These product requirements result in the following design specs:

Relational, yay. Components have well-defined schema and are related in a simple way to entities. Game logic itself will not at all be relational but I envision that as being encapsulated in yaml files and just loaded at game start--this database at least is just for stateful objects.

In-memory storage for fast reads. The framework will be used for probably one silly little game, so Ultimate Xtreme Performance is not strictly speaking necessary, but where I can optimize why not. No text game should require more data than can easily fit in RAM anyway. It should flush to disk periodically and easily be able to rebuild from backup.

In-memory indexes. These'll get rebuilt from disk on game load.

Supporting multiple connections is a must.

Not 100% settled on this but Probably will do actual serial execution. I need strong isolation. The most common way to achieve serializable isolation is two-phase locking, in which reads block writes and writes block reads (as opposed to snapshot isolation, in which reads do not block writes). That pattern is achieved with different types of lock, shared for reads and exclusive for writes. Reads can access data that already has a shared lock taken out on it, but writes must take out their own exclusive lock to be able to modify data. I am worried that using two-phase locking for a game would result in most of the database being locked at any given time (again, it's probably likely that a group of players would all be hanging out in the same place doing similar things). If so, I'd be doing a lot of work taking out and releasing the locks and resolving deadlocks that I just wouldn't have to do with actual serial execution. Serializable Snapshot Isolation or SSI, another alternative to serial execution, tries to calculate whether or not transactions have interfered with each other, which also seems like too much work in a game scenario where certain rows will be hot at any given time. With in-memory storage, the main barrier to serial execution (travel time to disk) is removed (Redis actually does serial execution). I'll definitely implement alternative levels of isolation (have already done read committed, more later), but true serial execution might not be the worst choice.

tl;dr I'm remaking Redis...but relational. For games.

[astrosilverio]

Meta: What even is a database

A big question that didn't make it into my pre-RC database question write-up is: what is the general architecture of a database? I didn't explicitly ask that question because to a certain extent I thought I had an answer--between resources like this paper on database anatomy and this tutorial on writing a clone of sqlite, I felt like I implicitly had a good idea of what a database generally looks like. However, after a conversation at RC last week, I realized that by immediately settling on a relational architecture, I was missing out on the important pedagogical exercise of defining my terms, namely specifying what, exactly, I mean by a "database".

If you just google "database definition", the only actual requirement for a piece of software to be a database engine is that it has to be able to hold structured data, and support accessing that data. It turns out that those are not especially stringent requirements, and there's a lot of wiggle room in what can technically be considered a database. If you want to write your own database, ask yourself some questions:

Do you want to store data on-disk or not? You don't have to store the data on-disk. It can be in memory. In a sense, this was already obvious because Redis exists. However, if you take the concept of an in-memory key-value store to its most basic level, anyone who has created a Python dictionary has in some sense written a database.

Do you want to support indexing? Technically, indexes are just a way to access data efficiently. If you don't care to support fast querying, you don't need to implement indexes. Think about dumping data into a CSV and then reading the whole file back into memory and using application code to pull out the rows you're interested in. Awful, but still in some sense a database.

If you do have indexes, will you write them to disk or not? Never writing an index to disk means not having to worry about moving the index data between disk and RAM and back again. Every time you stop and start your database process you'll have to rebuild your indexes in memory by scanning over your entire dataset but maybe that's an inexpensive operation for you.

Do you want to support multiple connections to your database? You don't really have to, but if you do you'll need to build out a lock system to ensure consistency.

Answering "no" to these questions will allow you to implement a piece of software that is technically a database with a very simple architecture. In Python, you could create a single class with CRUD methods that would add dictionaries and keys to them as attributes on an instance of the class, which would represent an individual database. Because of my industry experience, I was implicitly considering the most "vanilla" database I could think of to be one that would answer "yes" to the above questions. I still think I want to answer "yes" to them, but I think there's value in acknowledging that that's a choice.

[astrosilverio]

Database Adventures

Big news: I have just started another batch at the Recurse Center and have 3 whole months to learn things! You might assume that that means I'd be working on braga full-time. The thing is, though, I already have the motivation and skills to work on braga outside of my 9-5, and the rate at which I learn things from it has dramatically decreased. Therefore, I'm using the bulk of my time at RC for other things, primarily building my own database.

Why a database? There are a lot of aspects of databases that I quite frankly find mysterious and the best way I could think of to de-mystify them was to work on one, so here we are. To facilitate my investigations I brainstormed a list of questions before batch, and now that it's been two weeks I think I have some perspective on some of them at least. So without further ado, for posterity, here's where I was at at the end of August, with notes from this past week.

"indexes are just b-trees" but what are b-trees besides :diagram of tree:? how do you balance them?

Wikipedia and this tutorial page have pretty much sorted this out for me, with nice diagrams of b-trees and descriptions of the algorithm for adding / removing nodes.

when do you do an index write?

I think what I was getting at here is, if you are writing a row to a transactional database that has additional indexes other than the primary, are the updates to the additional indexes included in the transaction or can they be done async. This is something that I could almost definitely get from documentation for any transactional DB, don't think it's particularly interesting.

what does a database file look like?

I can actually wave my hands and say something intelligible here. The SQL table definitions that I am familiar with generally specify sizes for each field, and it turns out that is extremely important, because each byte of a DB file is essentially counted off. They do not look like pretty CSVs or human-readable representations of tables; they're generally just really large collections of bytes and you figure out where the data you're looking for lives by counting bytes.

is all the data just stuck in one file?

Not necessarily.

does a lack of schema buy you any inherent performance gains?

There's a lot to unpack here. I think I was looking for a reason to use NoSQL other than "I don't want a schema". However, there's such a wide variety in both NoSQL and relational systems that I think it's kinda a nonsensical question.

how does one get from SQL to "I want this node in the tree"?

Eh. I'll write it.

how does INFORMATION_SCHEMA work?

Fun fact about me: I am fascinated by INFORMATION_SCHEMA. You learned it here, kids. I will tooooottaaaalllly implement it.

how does the optimizer optimize? presumably indexes and cardinality thereof

what are some good ways to confuse an optimizer?

This brought to you by that one time at work when the optimizer got confused. I am also super excited about optimizing.

how many of these questions can I answer from books?

Meta time! I was concerned that I wasn't thinking deep enough, and would end up just doing a lot of reading and not writing any code and kinda giving up with a surface level knowledge of how databases work. I was forgetting the phenomenon of question spiraling though--I wrote a pager in Python this past week and it ended up just being a large series of rabbit holes. Maybe this batch of questions is surface level, but the next batch is not.

[astrosilverio]

Things that are better in Python 3, in no particular order

There's a big disclaimer here, which is that I still use Python 2 for my personal projects (and work, but that's less in my control). However, I've bumped up against several problems with Python 2 that have since been fixed in Python 3. The title of this post is a lie--these are organized by decreasing annoyance of the Python 2 problems.

Exception chaining -- Python 2 exceptions swallow previously incurred exceptions, Python 3 tracks exception chains. See PEP 3134. I encounter this one frequently at work in our API tests, where the more recent "oh noes the server returned a 500!" trample the more informative "you're trying to friend...yourself? wat??" or similar errors that occur in the API endpoints themselves.

No scope leakage from comprehensions -- in Python 2, variables defined inside list comprehensions persist outside the comprehension. In Python 3, they very rightly don't. I probably shouldn't be in-comprehension variables the same names as out-of-comprehension variables, but I didn't expect them to leak out, in the same way I don't expect local variables to leak into the global scope.

Function arguments -- in Python 2, you can't call a function with a keyword argument and an arbitrary number of position arguments. In Python 3 you can, like this: myfunction(*many_args, some_keyword=True). I'd do the same thing in Python 2 by splatting both args and kwargs and explicitly checking for some_keyword in the kwargs. It's way more annoying that way. Furthermore, the ability for keyword arguments to follow a * or varargs argument means that you can enforce certain args to be called by keyword only instead of position. For the function defined like so def myfunction(arg1, arg2, *, some_keyword=True): ..., any and all positional arguments after the first two will go into the unnamed vararg, and the only way to define some_keyword is to define it as a keyword argument. See PEP 3102.

Returning to exceptions, in Python 3 you can no longer raise a class, you have to raise an instance of a class. Variable syntax can be difficult for people trying to learn a language, so simplifying the syntax of raise is a big win!

Also in the context of simplifying syntax, I think that print probably will make more sense to new Pythonistas as a function than as a statement.

[astrosilverio]

Introducing Braga!

The big update from like months ago is that I'm working on a package called Braga, which models "things" and their abilities and relationships between them. I will use Braga to make the Rooms and Things and Players in my text adventure. I'm using a pattern called ECS (Entity-Component-System) that is primarily used for graphics games, but hey, it'll do the trick.

Naming is hard, but I'm kinda proud of this one--Braga is both the name of female blacksmithing god (relevant to the package's goal of "making things") and a totally badass character in one of my favorite comics. Keep reading for a brief intro to my latest pet project.

ECS In a Nutshell

Entities represent whole "things"--like a cat. Components are groups of attributes or methods that represent abilities or qualities of things. To give an Entity, like a cat, abilities, the cat needs to be associated with Components, specifically instances of Components. For example, Location could be a Component class; or Portable, or Container or CanBeSwitchedOn or Flying or something else of the sort. To give the cat the quality of being alive, give the cat an instance of the Alive Component class; that Alive instance will store whether on not the cat is alive.

The S of ECS is for System; Systems let you group together Entities for simultaneous updates, and provide a service interface for making changes to Entities with a specified Component profile.

One of the tenets of ECS is that the Entities should not store any information about their abilities or traits; they are just an identity that ability-bearing Components get tacked on to. This setup obviates the problem of complex inheritance trees--if you want two types of Entity to share a behavior, give them both an instance of the appropriate Component instead of having them inherit from each other or a parent class. It prevents classes from growing to gigantic proportions--in my original text adventure, my Room class was quite large, now a Room is just a collection of the appropriate Components, which taken individually are a manageable size. However...

Fake Object-Orientation

When I started playing with ECS, the first thing I noticed was that I was annoyed that attributes did not belong to Entities. While that is the design feature that makes ECS so extensible / unique / useful, it is also really irritating if every time you want to check if the cat is alive, you have to check that attribute on a Component on the cat instead of the cat itself.

Besides making it annoying for me to mess around with Entities in the repl, I realized that the extra overhead required to access attributes would complicate my text adventure code. I don't want hogwarts to know how its Rooms and Things and Players work under the hood. So I violated the guiding principle of ECS a bit and am faking object orientation by rewriting __getattr__ on Entities.

The familiar way of accessing attributes with dots, like cat.components, is just sugar for getattr(cat, 'components'). Normally, __getattr__ will raise an AttributeError if an attribute is not found. If I wasn't faking object-orientation, then cat.components would not raise an AttributeError but cat.alive would, because the cat Entity does not have an attribute alive. But if you hack the Entity's __getattr__ like so:

def __getattr__(self, name): for component in self.components: try: attr = getattr(component, name) except AttributeError: pass else: return attr raise AttributeError

Then the Entity will search through all of its Components to see if any of them have the attribute before throwing up its hands to say "I don't have that attribute". The result? I can access attributes that are stored in the Entity's Components as if they were actually stored on the Entity itself. Fake object orientation! For example, in the case of a cat with an Alive Component attached to it...

> cat = Entity() > cat.components.add(Alive()) > cat.alive True > cat.die() > cat.alive False

[astrosilverio]

? Stuff works ?

It's Open Dev Day and I get to work on my text adventure for the first time in. SO. Long.

I'm really really psyched about building out my entity-component-system-like system, but I decided to be a grownup and write some tests for hogwarts to see if the fancy Command system I built actually plays well with the Parser, which I mostly imported from the old text adventure.

Shockingly, everything mostly just works! I really expected to get a blog-post worth of exciting bugs out of this endeavor, but instead I have half of Open Dev Day left to keep building stuff out...good for me I guess?

[astrosilverio]

OSB Retro

Open Source Bridge was so much fun! My talk went fine and people had a lot of questions / ideas / comments that I should document before completely forgetting.

"make it a package!" yep, good call.

"how to do fights?" I think have players have fighting skill attributes and then implement a fight command that, well, makes them fight. can elaborate more later. def a good call tho

"rooms inside of rooms?" I think just clever definition of paths will sort that one out.

"make a room of requirement!" I can do dynamic path redefining, I know game state -- so it's probably currently possible.

"only state-changing commands should count towards total turn count for a player, right?" YES I had not thought of that and wow, YES / OOPS

Most of the above requests, I think, fall into the category of feature requests. They are things that a gamemaker should be able to do with my engine. They are things that I think you can currently do with my engine, but I haven't actually tested that assumption. Sure, I've written plenty of unit tests, but the unit tests are necessarily toy cases, not more complicated things like a Room of Requirement, which involves different paths being exposed to the player at different points in the game. Therefore, the biggest takeaway for me is "TEST YR DUMB CODE ALREADY!"

I'll report back on the results.

I've also stumbled into what hopefully is not a rabbit hole of Entity-Component-System design for stateful things, which should probably be another blog post.

[astrosilverio]

OSB Talk Script Pt 4: Funtimes with a Framework

Customizable commands can also be used to make things happen at scheduled times in your game! I made the logic handler optionally have a set of commands that it runs after dealing with user input, so you can add commands with rules that allow game state to change once the player has progressed far enough in the game. For example, maybe you want to release the basilisk from the Chamber of Secrets after 100 turns. You'd need a function that, well, releases the basilisk, and a function that return True on the 100th turn. Then just add basilisk to the commands that are run after every turn, and you're set for castle-wide petrification!

Similarly, you could decide to sort people after a particular turn. Assuming you have a reasonable algorithm for sorting players based on their move history, you could just add schedule the algorithm to run on a player after a particular number of turns. Sorting is particularly exciting because the house attribute that gets set on the player can impact them at other points in the game (cough Sword of Gryffindor).

Furthermore, it turns out that customizable commands make spells a lot easier to write. For example, you can implement spells just like any other command, but with a rule that ensures that the player is carrying a wand.

Finally, you can force players to practice spells before they can actually perform them! Imagine that you increment an attribute on the Player every time they (try to) cast a spell. You can add a rule that will not allow the spell's state change to happen unless the Player has practiced a particular number of times.

[astrosilverio]

OSB Talk Script Pt 3: Let’s make a framework!

To make a framework, we have to abstract game data out of the parser, the logic handler, and the state. Creating a game instance then becomes initializing the engine with game data.

Let's start with the parser. The parser's job is to pass an instruction to the logic handler from the player's input, so the only game knowledge it needs is what words to recognize. My text adventure game has a whitelist of accepted words that represent commands, players, things, rooms, and directions -- in other "words", only words that represent concrete things or concepts in the game are recognized. Imagine my parser was given this sentence to parse for a Pride and Prejudice themed game:

"It has been coming on so gradually, that I hardly know when it began. But I believe I must date it from my first seeing his beautiful grounds at Pemberley."

Of all the words in this sentence, only two words represent concepts or things in the game: "date", which is a game-specific command that takes a character name as an argument; and "Pemberley", which is a location in the game. The parser passes ["date", "Pemberley"] off to the logic handler--which doesn't make sense to the logic handler, but hey, the parser tried. This approach means that abstracting game data from the parser becomes a matter of just initializing the parser with a custom list of words.

Abstraction in the logic handler is a little more difficult. We can keep the same general principle--logic handler receives instructions from parser, dispatches instructions to appropriate Command--but Commands have to be totally customizable. I want my HP-themed game to have accio, for example, but I don’t want accio to exist in a great American road-trip adventure. Some commands should come built-in with the engine. Chances are very high that you’ll need go, for example, and you shouldn’t have to re-implement it for every game. But you should be able to modify the built-in commands. Maybe in your road-trip adventure, go west will move you one unit west if you’re not in a car, and will move you and your car 10 units west if you are in a car.

So how do we do this?

Well, first we have to decide what we mean by a command. What does a command need to do? I expect the command to do something based on my input, if my input is valid, and then return a response. For example, if I type some garbage like go wand, I expect the go command to do nothing and return something like “I don’t know where you want me to go.” If I type go south and there is a room to the south, the go command should move me south and then return the description of my new location. If there is not a room to the south, the go command should not move me.

I distilled those requirements down to four responsibilities (syntax checks, logic checks, (optional) state change, and response formulation), and wrote a Command class that is instantiated with helper functions for each of these responsibilities and that, when executed, calls those helper functions in this order.

[astrosilverio]

OSB Talk Script Pt 2: Why Write a Text Adventure Framework?

As much as I love working on my Harry Potter game, it's not inconceivable that sooner or later I'd want to make another text adventure game. While I could, with my text adventure game code, create a map of new Rooms with new Things and new Players for, say, the Firefly 'verse, I wouldn't be able to reuse any of my logic code, which would try to turn lights on if the player user types "lumos".

In order to be able to be able to write more than one text adventure, I need to have a system that not only will allow me to use or not use Filch's Office, but also will allow me to use or not use logic such as when to release the Sword of Gryffindor.

I promised some bug stories in the abstract, and you've been very good listening to me go on about state and logic and parsers for a bit, so let's take a detour and talk about the Sword of Gryffindor.

Most text adventures have a command called "examine", which returns a detailed description of, well, the thing you're examining. If you examine, say, the sorting hat, you'd expect a comment describing the hat's appearance. But, in the Harry Potter universe, the sorting hat, when examined by a member of Gryffindor house, will release the Sword of Gryffindor.

So I added some logic to the function examine that checks if the thing being examined is the sorting hat and if the player is a Gryffindor. If both of those checks are true, than I change the output of examine to include a line about the sword, and as a side effect add the sword to the player's inventory. This implementation results in a lot of complexity being added to an otherwise simple function for the sake of an edge case. There's a surprise state change, and to cap it all off, it doesn't work.

Imagine that your house happens to be Gryffindor, so you can release the sword from the hat. You examine the hat, get the Sword of Gryffindor, examine the hat again, get another the Sword of Gryffindor... Either there's an arbitrary number of Godric Gryffindors in the world, all of whom have swords and are involved with the education of British teenagers, or something's wrong here.

The solution that I hit on was checking to see if the sword existed in the game somewhere, and only dropping the sword from the hat if the sword wasn't already in the game. This is a solution to the problem. But it's a bad solution, partly because complex if-statement-ridden code is dirty code, and partly because the UX for the game developer is terrible. If I want to write another text adventure, my examine command has to be completely rewritten. The experience that I, as a gamemaker want, is the freedom to write game-specific state and rules for changing state without having to rewrite code that will be common to all text adventures.

In short, if a gamemaker is writing a Harry Potter-themed text adventure game, they should be writing Harry Potter things and not text adventure game things.

That's what I mean by a text adventure framework--a program that lets me write other programs.

[astrosilverio]

OSB Talk Script Pt 1: How does a text adventure game work?

When you play a text adventure there are some things that you'll notice. First off, the game has state. For example, at this point in my Harry Potter game:

Filch's Office You are in a small, spotless room. A filing cabinet stands in the corner and a discontented cat hisses at you from the floor. The door is to the south.

there is a room. The room contains a cat. The cat is alive. There is a player. The player is in Filch's Office. These states can change -- this player might not always be in this room. The cat might not always be alive. However, there are rules about how that state can change. Try interacting with the things in the room.

> take cat You can't take that. > examine cabinet You pull open a drawer labeled "Confiscated and Highly Dangerous". Something falls out. > look You are in a small, spotless room. A filing cabinet stands in the corner and a discontented cat hisses at you from the floor. The door is to the south.

A shimmering cloak lies crumpled in liquid-like folds.

If you try and take the cat -- change the cat's state from being in the room to being in the player's possession or inventory -- the game doesn't let you do that. If you try to open the filing cabinet, the game adds an invisibility cloak to the things in the room (the room's inventory).

If you've ever played a Twine game, or another choose-your-own-adventure game, you may already be familiar with this state-machine kind of setup. The difference between a choose-your-own-adventure and a text adventure is that as a player you're not at all limited in what kind of (text) input you can give the game, and the game has a little bit more work cut out for it in interpreting your input.

What needs to happen when a player user types some input? Well, first the game has to figure out what they're talking about -- parse their input into an instruction for the game. Once it thinks it knows what the player wants, it has to try and do that thing. So the game state has a nice conversation with the game rules, and between them they decide whether the change that the player wants to make can happen. Finally, it reports back to the player.

For my text adventure game, I chose to implement three types of stateful things. Rooms, like Filch's Office, have descriptions, can connect to other Rooms, and can contain Things and Players (in other words, have an inventory). Things, like the filing cabinet, have descriptions, may have an inventory, may be edible, etc. Players ("you") have a location, an inventory, and if they've progressed far enough in the game to be Sorted, have a House. The entire state of the game is represented by the collective state of all the Rooms, Things, and Players in the game.

Why? The short answer is, it's easier this way. Imagine if the state was NOT split up. The game state at the point where I try to pick up Mrs Norris is "Player in Filch's Office, Filch's Office contains cat and cabinet, cabinet contains cloak, player holds wand, player's house is Gryffindor..." and much much more (Hogwarts is a big place with a lot of things in it!). When I try to execute "take cat", the game has to decide if I can go from that initial state (call it State A) to "Player is in Filch's Office, Filch's Office contains cabinet, cabinet contains cloak, player holds wand and cat, player's house is Gryffindor..." etc.

In theory, the game would do this by looking up in a table of allowed transitions whether it is allowed to go from State A to State B. That is very simple for the game to do. However, generating a complete list of states and allowed transitions between states, is an absolute nightmare for a gamemaker when the number of possible states, and the number of allowable transitions between states, are as huge as they are in even a moderately sized text adventure.

So then how does the game decide whether or not a transition is allowable, if it can't look for a link between two global states? Well, in a word: logic. Instead of writing out all the situations in which the player could pick up the cat, the gamemaker instead writes out all the conditions that would have to be true for the player to be able to pick up the cat. I find it easiest to encapsulate known potential player requests as functions that I call Commands, which make the requisite state checks and changes. The logic handler's job on receiving processed input from the parser become calling the correct Command with the appropriate arguments.

And here we have an example of generalization improving UX -- to make it easier for the gamemaker to set and regulate game state, we split the game state up into bits and use commands with logic (if statements) to determine whether the request change can happen.

[astrosilverio]

Introducing Commands!

One of the ideas I've been most stubborn about clinging to is that game devs should be able to implement custom commands. I want my HP-themed game to have accio, for example, but I don't want accio to exist in a great American road-trip adventure. Some commands should come built-in with the engine. Chances are very high that you'll need go, for example, and you shouldn't have to re-implement it for every game. But you should be able to modify the built-in commands. Maybe in your road-trip adventure, go west will move you one unit west if you're not in a car, and will move you and your car 10 units west if you are in a car. Customizable commands are just as important to effective text adventures as being able to design your own maps and add your own objects.

So how do we do this?

Well, first we have to decide what we mean by a command. What does a command need to do? In my framework, by the time a command is called, we've already processed the text input, removing unrecognized words. Commands are then called with the other recognized input words as arguments. I expect the command to do something based on my input, if my input is valid, and then return a response. For example, if I type some garbage like go wand, I expect the go command to do nothing but return something like "I don't know where you want me to go," but if I type go south and there is a room to the south, the go command should move me south and then return the description of my new location.

To define a command, therefore, we need to define what it should (at least try) to do with your input, and what kind of response it should give. What about deciding if your input is valid? Well, there are two ways to do this: the command can either ask forgiveness or ask permission.

To ask forgiveness, just try to do what the input specifies, and handle the errors if something goes wrong. If you use this approach, then a command is basically a try-except block. Let's write go in this style. Assume that Player objects have a location attribute that points to the room they are currently in. Room objects will have a dictionary called paths with directions for keys and other rooms for values. Further assume that the direction that you want to go in is the first argument to go. To successfully execute go, there must be a path leading out of your current location in the appropriate direction; if there is not, current_location.paths[args[0]] will raise a KeyError. Your command should look something like this:

def go(*args): try: current_location = player.location new_location = current_location.paths[args[0]] player.location = new_location except KeyError: return "I can't go that direction" else: return player.location.description

That's fine, but what if you want to add some logic that you can only go somewhere if you shoes aren't covered in oobleck? Well, according to our ask-forgiveness philosophy, we can't put that logic in here. You decide to make a method on Player objects that will only allow player.location to change if the player's shoes are not covered in oobleck. If they are, it raises an OobleckError. Now, you need to modify your command:

def go(*args): try: current_location = player.location new_location = current_location.paths[args[0]] player.change_location(new_location) except KeyError: return "I can't go that direction" except OobleckError: return "Your shoes are covered in oobleck and are affixed firmly to the ground." else: return player.location.description

Every new condition you add to go will result in another type of exception that you have to handle, and (more importantly, because adding excepts is not that hard) will result in logic being added somewhere else in your codebase.

Cue scary music. Imagine Peeves, wearing a sweater that says "LOGIC", dropping broken umbrellas in your models.

Why am I so upset about this? Well, consider my dedication to easily customizable commands. In this model, changing how go works will involve modifying bits of code that are not go. Adding a new command will involve not just defining a new command, but also finding the relevant places in the codebase to add logic, and making sure that your new logic plays nicely with the logic that is already there. By removing responsibility from commands, we make them less modular.

Let's go back to the oobleck example. I modified my Player class, a stateful class, so that it contained game logic. That is what will happen when you allow logic to creep out of your commands: the reunion, or at least un-separation, of logic and state. As well as making the stateful classes unwieldy, the ask-forgiveness solution makes it difficult to impose a boundary between game state and game logic.

Therefore, I opted for an ask-permission approach, and made my commands do syntax validation and game logic checks before executing. This approach allows my stateful classes to remain lightweight, enforces a boundary between logic and state, and keeps my commands modular and customizable.

My base Command class has three, optionally four responsibilities:

syntax check -- "do these arguments make sense? I can't exactly take east."

logic check -- "can I do that? I can't go west if there's a brick wall in that direction."

(optional) state change -- "ok looks like I can take that book for you, let me modify your inventory accordingly"

formulate response -- "I've moved you south, here is the description of the new room you're in"

To define a command, simply instantiate a Command object with helper functions that take care of those responsibilities. The Command, when called, will call the syntax check functions, then call the game logic functions, then, if nothing has thrown an error, will call the state change functions and the the response function. For example, go now looks something like this:

def is_a_direction(map, word): if word not in map.directions: raise CommandError("Where do you want me to go?") def path_exists(map, player, direction): if direction not in player.location.paths: raise CommandError("You can't go that way.") def move_player(map, player, direction): new_location = player.location.paths[direction] player.location = new_location def location_description(map, player): return str(player.location) go = Command( name='go', syntax=[is_a_direction], rules=[path_exists], state_changes=[move_player], response=location_description)

Granted, it's a bit wordy. But now, if I want to include the oobleck rule, all I need to do is write a function check_for_oobleck and add it to the rules for go, no sticking logic in stateful classes necessary.

Coming soon: more examples of commands. Until then, happy adventuring!

[astrosilverio]

Honey, I'm home

So much for the regular updates :-/

In case anyone cares, I've been scarce because:

I submitted a talk to PyCon;

We're rolling out a big new feature at work;

My aunt got married;

I had to do some maintenance on another personal project.

That's not stuff that happens every month. And in the meantime, I've been doing research on unittest.mock, come up with a plan for implementing custom commands, and straightened out some misconceptions I had about how Python works. So that's not so terrible.

[astrosilverio]

Hey. So.

Here is the current state of affairs.

In general, I have a theory about how to build a system that runs text adventures.

After many adventures (haha) with the creatively named project "game", I've come to the conclusion that game state and game logic have to be separated if you want to have even a prayer of your game being robust. You should also separate the input-processing. So we need something that holds state and mutates state, something that looks at the ball of state and decides what to report to the player and how the state ball should change, and something that parses player input and delivers a response to the player.

Or, more readably, the essential game engine consists of the following classes:

MaraudersMap -- holds state, changes state

Rowling -- logic. takes processed player input, decides on appropriate state change (if any), tells MaraudersMap what changes to make, prepares response to player

Legilimens -- processes raw player input*, delivers response

I also have a class that just keeps track of player input and results thereof. I'm not actually using it anywhere, but I think logging is a good idea.

I'm pretty sure that those are the main pieces you need to run a game, at least if your logic is hard-coded. Now, what if we want customizable logic?

Commands should be separate from MaraudersMap and Rowling, so writers can add Command objects as if they were adding Rooms, etc.

Rules for the commands should be separate from Commands, so writers can use the same Rule for multiple Commands (e.g. expecto_patronum and lumos should both have require_wand as a Rule), writers should be able to add their own rules

Writers should be able to subclass Rooms, Things*, and Players to make interesting new doodads* (check out Inform 7, where if I remember correctly a Computer is a Device is an Object*)

The game engine (MaraudersMap + Rowling + Legilimens) needs to know about the custom classes. This feels different to me from custom state -- you could write many different games set in, say, Oz, but once you add a Phaser(Thing) and Teleport(Command), you're not in Kansas anymore even if your initial state is exactly the same.

There should be a standard library of Commands, Rules, and base classes (Room, Thing, Player) so writers can hit the ground running.

* I'm going to great and annoying lengths to avoid using the word object :(

Great. Now the whole shebang needs to be saddled to a compiler that processes writer input.

So the way I see it, there are three levels:

Make an engine that works. If I get lazy I can stop here and use the better working engine to finish my HP game.

Add support for customizable Commands and subclasses of Room, Thing, and Player. This, I believe, will be the hard part.

Add a compiler. Opportunity to inflict users with horrible syntax ;-P

I'll attack them in that order.

See you on the other side.