Blog 640: A World of 1D Arrays

It’s amazing what you can do with only global state and one-dimensional arrays, when you really put your mind to it. What was supposed to be a quick fart in the general direction of a Warcraft project has grown into something quite incredible.

Well, incredible on the technical side. The game itself is no more or no less than a streamlined version of my standard WC3 RPG formula. You may or may not want this.

Before We Begin…

So I’m making a procedurally generated RPG, out of the ashes of This Wreckage. This is happening in parallel to the rest of my development/research life — during lunch hour at work (staying out of the sunshine) and using my cute laptoblet in front of the television in the evening. Two hours a day, timeboxed like a god-damn agile pro (or something).

The original plan was to generate each level containing a single quest, which you would complete and then move on. Initial trials suggested that I was generating a world that’s a little too big for that, and to be honest, one quest is pretty dull anyway — a world can’t feel truly alive unless there are multiple characters floating around, asking for different things.

This is, without a doubt, my finest piece of terrain ever.

This is, without a doubt, my finest piece of terrain ever.

I Must Ask You Some Quest-ions

The first answer is to generate multiple quests instead of just one. Considering the original constraint where each quest is to have only one objective, this is actually fairly straightforward to generalise — every quest has a quest giver, who tells the hero what to do, and a quest log entry with two requirements (one to do the objective, and one to return to collect your reward). Every quest begins with an intro conversation between the hero and the giver, updates with the objective being completed, and ends with a reward conversation.

You might think that’s an oversimplification, but take a close look at This Wreckage and you’ll see that’s all it is — the only difference there is that objectives are sometimes chained together, or run on without the intervening conversation cinematic. The flavour, the conversation text and the actions around the objectives, is nothing but window dressing on the same basic building blocks.

I didn’t generalise back then because in a hard-coded one-shot world it’s easier not to. Alas, this time the world doesn’t exist until the map generates it, so I am duty-bound to create a system.

Go here, do this, do that... Don't you ever think for yourself, Henrik?

Go here, do this, do that… Don’t you ever think for yourself, Henrik?

Warcraft III‘s scripting language Jass is not ideal for anything particularly complex. Persistent state cannot be safely enclosed in black boxes, and related items cannot be grouped in namespaces. You have global variables and one-dimensional arrays — that’s it. Suck it down, et cetera.

In This Wreckage, every quest had a group of variables and event responses dedicated to it alone. Because every quest was guaranteed to exist and was able to work independently, I could hard-code the lot and move on with my life.

Unfortunately that’s not so easy in an auto-generated world. While I believe it is actually possible to create new triggers and events at run-time, it’s a whole world of pain I don’t want to go near and would probably leak memory like a seive. So if you want the same quest framework to underpin multiple quests, you need to keep common response triggers active all the time — so that the same event can be triggered by different instances of the quest, which might be in different states.

... and that's just all the global state the terrain generator needs just to pass all its data between triggers.

… and that’s just all the global state the terrain generator needs just to pass all its data between triggers.

Each quest stores all of its details in a suite of parallel arrays. There’s no other way of doing it; I have to trust myself not to overwrite some other quest’s details by mistake, and I have to ensure that index 2 in the quest giver array definitely contains the quest giver for the quest log in index 2 in the quest log array. The more I generalise, of course, the more parallel arrays come out of the woodwork, painfully grouped by naming them with a common prefix, just like the good old days.

The key to this hilarity is the integer array called State. This gives us the single always-on event response trigger that we need — every time you talk to the quest giver, the actions that unfold are predicated on what state the giver’s quest is in. If the quest is new, you get the intro conversation; if it’s in progress, you get a little reminder; and so on.

That renders the entire quest down into two triggers in total, making it generally much more manageable — one trigger for the quest giver conversations, and one for registering objective completion. This pairing is common between all quest shapes; only the event responses in the objective triggers will change, perhaps from killing an enemy to acquiring a special item.

Either way, the state means that an event response does not need to be enabled or disabled — all that is necessary is to ensure it has an action for all quest states, and the appropriate one will be executed. (In this auto-generated world, I also have to allow for the player having completed the quest before receiving it. In this case, the intro cinematic goes straight to delivering the reward, but it’s another reason that all event responses need to be active at all times — so that the objective response trigger can still update the quest state in the background. On the plus side, no spuriously disappearing invulnerable rock chunks!)

Look! I'm finally using real all-Jass triggers! ... only 10 years behind the curve...

Look! I’m finally using real all-Jass triggers! … only 10 years behind the curve…

The final problem is simply matching an event response with the quest the player actually wants to progress. Thankfully, Warcraft III has one beautiful little ace up its sleeve — you can attach an integer “custom value” to a unit. When the quest actors are generated, I set the custom value of each to the index of the quest they’re a part of, so that all the event responses have to do is retrieve the custom value and the world of quest details unfolds.

There are more suites of arrays than just for the generated quests, though. I might be okay with having the same underlying quest objective in play multiple times, but it can’t be the exact same quest — it needs to be given by some other character and it needs to have some other target. Generating a quest giver from a selection of characters is easy enough, because he is one unit that needs no more data once he’s created, but generating targets is a little more involved — you need to generate the quest description text and modify the conversation dialogue too.

Yep, I have a suite of parallel arrays of target information. Names in singular and plural, unit types to spawn, phrases to use in dialogue… Rather than decanting these into the quest, though, I have of course added a quest array that contains an index to the target types arrays. It’s not quite a dictionary of dictionaries of lists as you might see me swoon over in C#, but using an array to get an index for an array — going up to three arrays deep in places — is surely the old-world equivalent.

Quest givers are hero units so that their names vary naturally. Agents are named after agents from the two Deus Ex games (naturally).

Quest givers are hero units so that their names vary naturally. Agents are named after agents from the two Deus Ex games (naturally).

Originally, I wanted to do this project to quickly hash out some procedural techniques for future use in stand-alone games. While I have learnt a lot about how to massage cellular automata landscapes into viable game spaces, I think I’ve learnt far more about how to make old-school scripting languages do quite incredible things. Unfortunately, C# is not an old-school scripting language so this knowledge is a mite less transferrable.

Oh well. Will the map at the end of all this be worth the pain? We can only hope.


2 thoughts on “Blog 640: A World of 1D Arrays

    • It is dead in the water. Too much pain, too little gain. I learnt lots of interesting things about procedural generation that I will apply to the real world in time, but this got to a point where WC3 just isn’t capable of supporting what I wanted to do with it.


And you tell me...

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s