Skip to main content

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.

Comments

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 :)

Popular posts from this blog

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 Bukkit s…

Apple: iPad and Emacs

Someone asked my boss's buddy Art Medlar if he was going to buy an iPad. He said, "I figure as soon as it runs Emacs, that will be the sign to buy." I think he was just trying to be funny, but his statement is actually fairly profound.

It's well known that submitting iPhone and iPad applications for sale on Apple's store is a huge pain--even if they're free and open source. Apple is acting as a gatekeeper for what is and isn't allowed on your device. I heard that Apple would never allow a scripting language to be installed on your iPad because it would allow end users to run code that they hadn't verified. (I don't have a reference for this, but if you do, please post it below.) Emacs is mostly written in Emacs Lisp. Per Apple's policy, I don't think it'll ever be possible to run Emacs on the iPad.

Emacs was written by Richard Stallman, and it practically defines the Free Software movement (in a manner of speaking at least). Stal…

Creating Windows 10 Boot Media for a Lenovo Thinkpad T410 Using Only a Mac and a Linux Machine

TL;DR: Giovanni and I struggled trying to get Windows 10 installed on the Lenovo Thinkpad T410. We struggled a lot trying to create the installation media because we only had a Mac and a Linux machine to work with. Everytime we tried to boot the USB thumb drive, it just showed us a blinking cursor. At the end, we finally realized that Windows 10 wasn't supported on this laptop :-/I've heard that it took Thomas Edison 100 tries to figure out the right material to use as a lightbulb filament. Well, I'm no Thomas Edison, but I thought it might be noteworthy to document our attempts at getting it to boot off a USB thumb drive:Download the ISO. Attempt 1: Use Etcher. Etcher says it doesn't work for Windows. Attempt 2: Use Boot Camp Assistant. It doesn't have that feature anymore. Attempt 3: Use Disk Utility on a Mac. Erase a USB thumb drive: Format: ExFAT Scheme: GUID Partition Map Mount the ISO. Copy everything from the I…