(1) Who Needs Narratives Anyway?

(1) Who Needs Narratives Anyway?
Experiments in procedural generation

1. Background
So I've never played Rogue or any Roguelike or anything remotely like it, except that old Warcraft Rogue map which is apparently nothing like Rogue. (My main problem with the Warcraft Rogue map is that it's co-op rather than singleplayer. I mean, it can be played solo, but the balance is a bit off. It also doesn't have an equipment system or backpacks etc etc etc)

HOWEVER, I do have an interest in procedural ("random") level generation. It's pretty cool stuff, and actually much easier to implement than you'd think. I mean, if I can do it, anyone can! Narrative-drven games are also dreadfully unfashionable right now, whereas systemic generated content is all the rage but doesn't seem to have much traction in the WC3 community.

At the moment, I feel a bit like an alcoholic returning to the bottle. "Just one more Warcraft map, bartender. I can stop whenever I want!"

So I'm not going to be working full-time on this, but doing it during sporadic lunch hours at the office. My real game is still my primary focus at home! (Obviously I will eventually apply the techniques learnt here, if not the implementations, to that, so it's all valuable experience. )

During the construction of RDZ Industries: Project Y4, I explored two methods of procedurally generating viable levels (emphasis on the word "viable" -- anyone can throw a random number generator at a terrain plap, but only procedural techniques will guarantee that the output can be completed). Only the Growing Tree mazes made it to the final release, but the implemenation work was completed anyway (in plain old Jass, right down to manual 1D array implementations of lists and 2D arrays).

(I've also more recently done a very lightweight video presentation about them, which might be of interest for a quick overview. There are also extended C# implementations for the more hard-core among you.)

Growing Tree maze generator
Y4 dev diary 1
Y4 dev diary 2
Y4 dev diary 3
I used this mechanism to build a floating neon maze for the stylised hacking minigame; this consisted of placing 12x12 bridge destructibles over an unpathable (abyss) terrain to create a lattice of flooring from the generated maze.

Although the algorithm is built on square tiles, when printing the floor I made each tile examine its neighbours to place a more customised bridge if possible (e.g. rather than a grid of plain tiles, there were T-junctions, corners and special end pieces).

This mechanism is obviously best for man-made structures. It could easily be adapated for larger room tiles, with some other mechanism populating each room with decorations (pathable or otherwise) and the maze defining the doors between rooms.

Cellular Automata cave generator
Y4 dev diary
Use of cellular automata never panned out, unfortunately. Originally it was for a space-based Battleships-style mission that I never finished. I tried to repurpose it for an alternative hacking minigame, but I discovered that it corrupted saved games when used so it had to be abandoned.

Although cellular automata produces natural areas that are not guaranteed to be connected, you can bias the algorithm to create spaces (and walls) by carving up the initial noise grid with known paths. In my planned AoS, for example, I always drew two curved lines between the bases for lanes -- the edges and other level parts changed, but these open routes remained consistent. Obviously, by randomly selecting base locations and varying the width/wobbliness of the lines between them you can further vary the generated level.

2. The Game
So I want to put these to slightly stronger use than I did in Y4. I want to make a map built around them, rather than one that just shoves them in as tick-boxes on some cosmic bucket-list.

I am basing this map on This Wreckage. This means I have ready-made artwork and base mechanics -- and a huge selection of items and equipment to draw from, perfect features for an undirected hack 'n' slash action RPG that I don't want to spend too much time on.

Basic features:

• Heroes: normal WC3 units and abilities, customised for flavour and whatnot but no expensive triggerwork or ham-fisted full-screen inventory systems.
• Hero selection: every hero is equal, visual only; classic footmanimations all the way! (There are already loads of footmanimated Henrik clones in This Wreckage, and I definitely have a few more lying around my working directory that I never got around to using.)
• Ability selection: four abilities selected at the start (plus Attribute Bonus for everyone); identical hero units means the "skill" and balance only comes in with the abilities and use of equipment. This is the Engineering Upgrade hack, basic stuff.
• Equipment: swords and shields, though I'll rebalance the shields from This Wreckage because the numbers were shot to pieces by WC3's bonkers armour algorithm.
• Consumables: dropped by enemies, found in chests, the usual... From health potions to one-shot spells, these will all stack in the inventory so a successful character can still become a laden-down powerhouse... if s/he survives long enough.
• Backpack: obviously. Hack 'n' slashers are all about loot, right?
• Combat music: it's there, so why not?
• Kill combos: fun fun fun, though I think I'd remove the extremely cheeseable experience reward from this system.
• Scoreboard?: might be hard to balance this for "competitive" play, but definitely something to look into because everybody loves points!

The game will consist of an endless sequence of "quests", each of which is an area of generated geography with enemies, shops, chests and so on, that contains a single objective. The objective will have only a basic narrative, like kill all the enemies, retrieve an item from a villain, the usual suspects. However, there will still be at least this tiny bit of narrative to give flavour and interest and allow for applying variety to the same basic quest (i.e. not just "kill three boss enemies", but "I'm a shopkeeper and mur'gul thieves made off with three chests of merchandise! Please get them back for me, or I'm ruined!"). Fetch quests might still be fetch quests, it's the context that brings things to life.

On completion of the current objective, the player can wander about a bit more before signalling their intent to progress to the next quest. This will allow them to kill remaining bad guys for loot/experience, or buy stuff from any shops on the map before moving on. The level and its contents will then be completely destroyed, except for the player hero and their stats.

The player will choose a hero at the start of the game and stay with it through as many quests as they can until the hero dies or they abandon the game. Each quest would presumably be harder than the previous, with more or more powerful enemies spawning. Ideally this would be accompanied by changing scenery too (e.g. as with This Wreckage, early levels in breezy outdoor beaches, then swamps/forests, then omnilight caves).

There will be a maximum hero level along with equipment and item levels, so there will be some nominal "end" point. Although items could probably be randomised, I think spawning hand-crafted items randomly is more feasible and engaging (imagine the amazement as a mid-level boss is chosen to drop the Dragon's Tooth, for example... and the pain when he leaves a Phat Lewt instead).

Since this map would include "permadeath", we can safely ignore corrupted saved games from use of my Cellular Automata implementation. Long-lasting characters could still be persisted between sessions by game cache instead (even auto-saved on quest completion), but individual quest instances would not. Statistics for scoring would be applied on completion of each quest, so you can't surf up without actually completing quests by restarting the map constantly.

As for naming it... Not sure at the moment. I'd consider a riff on "Nox Quest", an endless (though not procedural) dungeon-crawl add-on for Nox, one of my fave childhood games. "Wreckage Quest"? "This Quest"? Not a priority right now anyway.

3. Thoughts?
That's where I'm aiming, and I have already got a prototype in place that allows you to select a hero and creates a reasonably basic jungle area. On death, the world is flattened and the whole thing begins again.

My prototype is 64x64 with camera borders, and with tiles of size 4x4 that leaves me a grid of about 60x60 to play with. This takes quite a bit of time to generate, though, so I think this is about as big as I can go with cellular automata (the growing tree algorithm can go a bit bigger before it takes prohibitively long, I think, but not gone there yet).

Tell me what you think!

*checks calendar*
It's not April 1st, guys! This is for real!

While procedural generation sounds interesting from a programming point of view (I thought you said "no expensive triggerwork"?), I kinda like narratives. can you think of a way to procedurally generate those?

Well, maybe I mean to say "no expensive triggerwork now". Remember, I already implemented both of these algorithms ages ago -- it took barely an hour to port them both over to the new map (though I'd deleted Cellular Automata from the latest version of Y4, had to dig into the previous release folder... good thing I kept those). All I need to do now is lightweight refactoring and parameterisation to remove all the hard-coded values.

Yeah, I like narratives too, but they're quite hard to come up with.

I've always dreamt of rendering existing narratives down to sequences of events and then feeding that data into a Markov Chain system to generate varied sets of quests (then staple those together based on the required characters/items/etc), but that's beyond the scope of this project.

So as I said, looking at individual stand-alone quests that draw from a set of possible options. Think of them as episodes in the TV show of your hero's life.

I reckon I should be able to do more than just basic fetch quests; defences, AoSes, escort missions are theoretically possible... But that's for later. Keeping it simple for now.

You've done more in however long it took you to get this working than I have in the last 3 or so years.

That said, Im really interested in the possibility of generated narrative that could flow through the whole game.

Imagine all the quests were given by a n off-screen "narrator".
You could in theory string together a narrative that makes grammatical sense, though probably not a logical sense.

Psh. I did the heavy lifting about 3 years ago, everything now is window-dressing. That's why I'm even doing this, if it required too much thinking I'd not have gone for it.

I could probably scrape together a recurring villain or something behind each individual quest, but it's an additional complication I'm not interesting in exploring right now. If I don't stick to the basics I'll never finish it!

This sounds great :) Let's see how well these automatically generated worlds will work!

Well, so far I'm thinking that a 60x60 grid is actually a reasonably large space, so I might want to integrate more than one quest into each section -- maybe two or three (in parallel rather than one quest with more objectives, though that could be a way to add variety).

Otherwise everything seems to be working well. My jungle is printing a nice mix of rocks and rock spires amongst the trees, and I've just added destructible clutter to the mix (rocks and vines). It's the clutter, the bushes and flowers and things around the edges, that make hand-crafted terrains so compelling, so I'm going to do my best to get that kind of thing engaged to round it out. I think the broad strokes look pretty nice so far, though.

Still got a long way to go, but my first prototype "kill all the mur'gul" quest is completely repeatable, either with the same hero successfully completing it or a new hero because he died. Once I have that acting more flexibly and with some alternatives, I'll start exploring different tilesets for the generated terrains.

Just announced this on my blog, so you know I must be serious about it!

In other news, screenshots!

I have been developing a few alternative tilesets to start stressing the level generator. The desert area is much more open than the jungle (and it's a chance to recycle some stuff from Brownscape!), and there is now a "ruins" version of the jungle that adds ruined bricks as well as rocks and trees. Also adding stuff for randomised shops scattered around the level, though I still need to randomise their item selections.

Yay! Are you planning on adding water / terrain deformations as well? Would spice things up a bit.

I would like to on both counts, but I'm not sure how feasible it is.

I know you can add terrain deformations by triggers, but I seem to remember that destructibles don't move up or down with them.

I'm also not sure how deformations would fit into the tile structure of the terrain generator. It's based on 4x4 (i.e. tree-sized) tiles so I reckon I'd need to do one deformation on each tile -- at 60x60 that's a maximum of 3600 deformations, which feels like it could be... problematic. I guess I could do larger deformations e.g. every 5th tile do a big lump, but not sure how that would look with some of the larger wall blockers (the 12x12 rock spires would jut out of the ground, for example).

As for water, I know you can make sure there's a water table under the terrain to lower into, but again that falls into working with deformations.

So, if you at least know a way to make created destructibles move up and down with triggered terrain deformations, that would be a start at least!

So.. first calculate at which Z they should be, place them at the correct Z, and deform the terrain around it. GetLocationZ does work correctly on terrain deforms I remember. I don't know how this CreateDestructableZ native responds to deformed terrain.

Small terrain deforms are probably not really the way to go, since they can quickly become unnatural. Larger ones might work fine. And indeed, just deform down if you want water!

Hmm!

So I would do terrain deformations first, then GetLocationZ of the deformed terrain (accounting for slope to half-bury things if necessary -- average the Z height of the surrounding tiles?) then create the destructibles with that? That sounds plausible.

I would say so. But perhaps the native also takes the Z created by triggers into account. Just test it :)

Yeah, I'd try doing the terrain deformation and then creating the destructables, maybe they'll get created at the desired height to begin with. If that doesn't work, do the whole GetLocationZ thing.

Seems like that is the case, if I create "Permanent" crater deformations before creating the destructibles they do appear at the right height.

However, permanent deformations can't seem to be removed -- I've tried Stop All Active Terrain Deformations but it seems to have no effect. Presumably because they are not active anymore, since I created them with fairly short durations.

I can't really use temporary deformations, though, because the player could stay in a particular scenario for any length of time. I guess a long duration would also mean they take ages to deform, so the player would see the terrain flexing under them... and then they'd go back to being smooth at some point.

Another problem is that the water doesn't seem to appear properly when I deform into it in-game. Footstep splashes appear, and the cursor starts to click in the "surface", but there is no water actually visible.

All in all, looks like terrain deformation is a no-go.