Category: Random

Posted: 12/19/07 Ideas on how to procedurally generated a closed set murder mystery and the mechanics of how to solve it.

Once again, I turn my sights towards procedural generation. I know what you are thinking, but this time I'm going a very different route. Usually, when one talks about procedural generation, one talks about some sort of over arching procedural holding it all together. But there's another approach that is perhaps more complicated, yet more realistic, and that is systematic generation. It's largely a matter of semantics, but the core difference is that in one, you generate a specific outcome based on specific inputs and in the other, you provide a closed system and the outcome is just a snapshot of that system at a specific moment in time.

Let's look at an example. If you wanted to generate a dungeon for an RPG, you might decide to create an algorithm for laying out rooms and filling them with creatures and loot. Another approach would be something like SimCity, where little sim-creatures come in an domesticate a cave and build rooms and facilities according to their sim-needs.

The beauty of the latter approach, though significantly more involved, is that it will naturally create a more realistic environment and that the environment will grow and change over time. The negative is, of course, that it is a lot of god damned work creating a simulated dungeon and creature AI just to build something that you could do with less than a hundred lines of code otherwise.

I think there is a place for both approaches. Algorithmic content generation will work in most cases just fine. You don't need to systematically model, for example, carpenters building a house from wood planks. Just go to the end result. I think for large scale designs that change over time, like a city or a culture, a systematic approach from beginning to end would yield significantly improved results with a greater variety and consistency.

I want to generate a detective mystery. That is not nearly as simple a process as it may initially seem. The easiest approach is something like Clue, where one simply randomly selects the who, what, and where - but that approach won't get you far. After all, why did Professor Plum kill Mr. Body with the lead pipe in the Conservatory? Clue is a game of deduction largely external to the crime and environment. The rooms exist only so that you must go between them before suggesting a theory.

There are essentially two problems that must be solved in order to generate a murder mystery. The first is that you must generate a murder. The second is that you need the tools in order to collect information and solve that mystery. Because of the latter requirement, just using a "murdering" algorithm to select a killer won't work because you need to generate information about the murderer (and everyone else) when the murder wasn't happening.

That's why, when creating the murder, you do it systematically. You build a house, fill it with a variety of potential weapons, you select the occupants and then you model them, Sims-style, as they go about their business. This will generate a history of actions and events that can be tracked with an information system based on [#040 - Paranoia].

The first step is to generate a closed set in which the murder takes place. All suspects will be together will all potential weapons and all potential locations. The typical mansion murder mystery, not unlike Clue. The reason it is closed is because the actions of each character will be modeled completely so as to generate the possibility of clues.

Each sim will be given a variety of needs and wants and the game will model their actions from the start of the dinner party to the point where the body is found. One of the sims will be given a need to kill character X before 9 pm without being seen. The house will be populated with a variety of weapons, both concealable and not, from which the sim-murderer can select the way of dispatching his foe. Basically, if the murderer and victim are ever in a room alone together, that's when it happens.

Granted, a lot of magic happens in this step but I still think it is not an impossible thing to do. After getting just the basic elements working, I don't think it would be much more difficult to add in different twists, like the murderer trying to frame another character or perhaps four potential murders or even planned murders where the murderer tries to influence others to be at specific places at specific times.

At the end of simulation, you'll end up with a chart like this. Every character is either in a room or moving between rooms. As you can see, from this chart, it becomes a little more obvious which information each character has access to. Ms. Scarlet, for example, can tell you about Mr. Plum ONLY after he joins her in the Conservatory or earlier when they are in the Library together.

The way the game progresses from there is that you go around and talk to different suspects. You are able to ask four of the five Ws: who, what, where, and when. You phase questions by supplying some of these things and the suspect will respond with the missing parts.

For instance, you can ask Col. Mustard WHO he saw in the Conservatory at 3:30, or what he saw Ms. Scarlet doing in the Lounge. Col. Mustard would then know whether he was in the Conservatory at the specified time and who he was with, and whether or not he ever was in the same room with Ms. Scarlet in the Lounge. Basically, you can ask anything, and the suspects know whether they know the answer or not.

The way this works is each event is stamped in the memory of each suspect with the four Ws. For instance, Mustard is in the Lounge when Ms. Scarlet walks in. He will receive an event LOUNGE 3:29, SCARLET ENTERS (where, when, who, and what). If Scarlet picks up a knife from the table, he'll remember it. Also, each time a suspect encounters another, he will remember all the appearance changes from the last time. If Professor Plum isn't wearing his watch the second time Mustard sees him, that's information he will remember. Same thing with rooms. If the knife isn't in the Lounge the next time he enters, he'll make note of it.

By systematically creating the entire night, beginning to end, one can store each event as it pertains to each suspect. The trick of the game is to continually ask questions to figure out what happened - in short, trying to recreate that character of who was where and when.

To make it more realistic, all memories shouldn't be treated equally. That is, if Plum is missing a watch, that may not register as strongly as if the knife was missing. Each even will be labeled with an appropriate level of suspicion and notice. This is where you can narrow down the queries using the ANYTHING STRANGE input. For instance, if you ask whether Mustard saw Plum in the Library, you'll get a "yes" and little more. Then you ask if Mustard noticed ANYTHING STRANGE about Plum's actions or appearance. Depending on how strange it would be for Plum to not wear a watch, you might hear about it.

You can increase suspicion levels by indicating other suspects as prime suspects. If you suggest that Plum is your prime suspect, all the suspicion levels will increase. The watch difference wasn't suspicious before, but now that Plum himself is suspicious, so too becomes the watch.

Again, you can increase the complexities numerous ways. You can have each character treat each other one with varying levels of trust. For instance, a husband and wife team may not become suspicious of each other with the prime suspect rule, or perhaps the wife is extremely suspicious of her husband's actions and will tell you everything, no matter how small. Likewise, the murderer might lie about other characters in order to frame them. Perhaps you can use other means to get information other than suspicion, like torture or bribes, and so on.

I consider this idea somewhat in its infancy. Obviously, modeling a murder and the social interactions between characters leading up to and including the interrogation is not exactly an insignificant problem. Still, I think this system for recording memories and querying them would make an excellent basis for a procedurally generated murder mystery - so long as it was a closed system.