### Gaming: How Do Characters Know What to Say?

My wife and I like to play games like Paper Mario together. Paper Mario is a long game with a lot of dialog. At any point in the game, you can talk to any character, and that character will say something "sensible". For instance, they'll ask you to help them out, or they'll thank you if you've already helped them out. I've always wondered how that's coded. Similarly, I've always wondered how many ways I could think up to code it.

The simplest approach is to use a complicated set of possibly nested if/else statements. For instance, if Mario has this item, then say this. Otherwise, if he has beaten this level, say that. Certainly that's a valid approach, and it doesn't even matter if it's slow. Since people read so slowly, trying to optimize how quickly you can come up with what text to show next is absolutely the last thing you would ever need to optimize in a video game.

At the opposite extreme, this problem could be solved with a rules engines. There are libraries that let you wrangle control of complex if/else hierarchies. (The first time I heard about rules engines was when I was interviewing at a consulting company where they were building a welfare system for various counties in California. Apparently, the rules surrounding welfare systems are so complex that a rules engine is a necessity.)

You can also use a mix of if/else statements and switch statements. For instance, the main game is a mostly linear progression from one state to the next, which is easily solved by a switch statement. If you are in this state, say this. If you're in that state, say that. However, sometimes Mario goes on side quests. In cases like that, a particular character might need to have a separate switch statement to know what to say for that side quest.

Similar to using a switch statement, you can use a non-sparse array per character where each state is an index into that array, and each spot in that array has a pointer to a message. Since the array contains every state, many of the states will point to the same message.

You can create a mapping from state to message using a sparse tree. To find out what to say, traverse the tree to find the state that is closest to, but still less than the current state. A sparse tree has a benefit over a non-sparse array in that the tree is only as large as the number of messages the character might say.

Rather than having an array of states for each character, you could also have a single array of states for the entire game. When you save the player's position in the game, you simply save his index into the array. The first spot in the array has a mapping of what every character would say at the beginning of the game. Each new spot in the array has a list of updates for all the characters who would say something different for that new state. This works like a database transaction log. Since there are only a few hundred or a few thousand characters, you can easily store in memory what each character would say at the current state in the game.

I'm going to take a guess and say that they probably just used a simple set of nested if/else statements, but it's kind of fun to think of other approaches.

JJ, I'm starting to suspect that you're on nootropics this month! You've written 44 posts already and I get the feeling you're not finished yet. Keep 'em coming :)
jjinux said…
Hahahaha!!!

I was wondering how many programming languages I would have to write about before someone made a joke about it ;) I had a long list of blog posts that I wanted to write but hadn't found the time for. Since I'm between jobs, I figured I should take advantage of my free time.

Thanks for reading ;)
Leon Atkinson said…
You should check this out: http://www.robotwisdom.com/ai/racterfaq.html

In particular you will be interested in learning about the INRAC compiler.
jjinux said…
Crazy. Thanks :)

### Ubuntu 20.04 on a 2015 15" MacBook Pro

I decided to give Ubuntu 20.04 a try on my 2015 15" MacBook Pro. I didn't actually install it; I just live booted from a USB thumb drive which was enough to try out everything I wanted. In summary, it's not perfect, and issues with my camera would prevent me from switching, but given the right hardware, I think it's a really viable option. The first thing I wanted to try was what would happen if I plugged in a non-HiDPI screen given that my laptop has a HiDPI screen. Without sub-pixel scaling, whatever scale rate I picked for one screen would apply to the other. However, once I turned on sub-pixel scaling, I was able to pick different scale rates for the internal and external displays. That looked ok. I tried plugging in and unplugging multiple times, and it didn't crash. I doubt it'd work with my Thunderbolt display at work, but it worked fine for my HDMI displays at home. I even plugged it into my TV, and it stuck to the 100% scaling I picked for the othe

### ERNOS: Erlang Networked Operating System

I've been reading Dreaming in Code lately, and I really like it. If you're not a dreamer, you may safely skip the rest of this post ;) In Chapter 10, "Engineers and Artists", Alan Kay, John Backus, and Jaron Lanier really got me thinking. I've also been thinking a lot about Minix 3 , Erlang , and the original Lisp machine . The ideas are beginning to synthesize into something cohesive--more than just the sum of their parts. Now, I'm sure that many of these ideas have already been envisioned within Tunes.org , LLVM , Microsoft's Singularity project, or in some other place that I haven't managed to discover or fully read, but I'm going to blog them anyway. Rather than wax philosophical, let me just dump out some ideas: Start with Minix 3. It's a new microkernel, and it's meant for real use, unlike the original Minix. "This new OS is extremely small, with the part that runs in kernel mode under 4000 lines of executable code.&quo

### Drawing Sierpinski's Triangle in Minecraft Using Python

In his keynote at PyCon, Eben Upton, the Executive Director of the Rasberry Pi Foundation, mentioned that not only has Minecraft been ported to the Rasberry Pi, but you can even control it with Python . Since four of my kids are avid Minecraft fans, I figured this might be a good time to teach them to program using Python. So I started yesterday with the goal of programming something cool for Minecraft and then showing it off at the San Francisco Python Meetup in the evening. The first problem that I faced was that I didn't have a Rasberry Pi. You can't hack Minecraft by just installing the Minecraft client. Speaking of which, I didn't have the Minecraft client installed either ;) My kids always play it on their Nexus 7s. I found an open source Minecraft server called Bukkit that "provides the means to extend the popular Minecraft multiplayer server." Then I found a plugin called RaspberryJuice that implements a subset of the Minecraft Pi modding API for B