Magic & Effects Back-End

In my previous article, I showed progress on the visual side of spell-slinging and had lots of fun with casting animations and throwing around missiles with lighting effects. Now I have to regard the business end of the spell system and how all of this holds together under the hood. This article will be a lot more tech-oriented than my previous one, but may still be of interest if you’re curious about how spells will operate in Dagerfall Unity.

Please keep in mind this is all under active development so concepts discussed here are likely to be refined or expanded by the time everything rolls out.

 

Magic & Effects System

One major shift in this process was changing how I think about the spell system. I have a long list of goals I want to achieve during this stage of development, above and beyond just emulating Daggerfall’s classic roster of spells. Primarily, I want to create a central way of handling the majority of effect-based gameplay. This means advantages/disadvantages, diseases, poisons, spells, magic items, potions, and so on should all come together under the one system or group of related systems. Once I had made that decision, it no longer made sense to call it the “Spell System” as spells are just one part of the collective. So the Magic & Effects System was born.

This is why you won’t see the word “spell” very much moving forward but you will see the word “effect” a lot. In this context an effect isn’t something visual, it’s how something works. For example, an effect that heals the player is a script which increases their current health. This naming is taken from Daggerfall itself where spells and magic items reference effects directly using a type and sub-type.  You can read more about classic Daggerfall’s spells and their effect indices on this UESP page.

You will also see the term effect used by Daggerfall’s Spell Maker UI when creating a new spell. You can add up to three effects per spell as shown in screenshot below from classic Daggerfall (spell maker is not yet implemented in Daggerfall Unity).

 

Overview

If you’re familiar with the Quest System and how registered Quest Actions execute inside of a Quest – then you’re already familiar with the Magic & Effects System. I’m iterating on some of the concepts for Magic & Effects, but the broad design remains very similar. There are a couple good reasons for this: I want a consistent approach so developers can apply learning from one system to another, and both systems do something very similar which is execute a script inside a framework of some kind to perform work for the game. Here’s a nifty overview of the classes so far before I break it down further:

 

EntityEffectBroker

The EntityEffectBroker singleton lives within the game scene at all times, and will be involved any time a new effect enters the game. It fills a similar niche to the QuestMachine in that it helps coordinate everything and provides a common entry point for execution. At startup it uses reflection to enumerate all classes implementing IEntityEffect inside the main assembly and registers them using an “effect key” presented by the effect itself. Eventually, mods will be able to inject new effects at startup without needing to rely on the reflective enumeration.

 

DaggerfallEntityBehaviour

This MonoBehaviour-derived class has existed for a long time but deserves a revisit to explain how it fits into Magic & Effects. Everything that walks, crawls, flies, or swims in Daggerfall is considered an entity and carries a DaggerfallEntityBehaviour component. This in turn holds the DaggerfallEntity instance which defines their career (class / monster type) and all of their stats, skills, health, spellpoints, etc. Most effects will operate directly upon an entity in some manner, which is why the EntityEffectManager is peered with this component.

 

EntityEffectManager

This component stores effect collections (called bundles) that are currently operating on the entity. At runtime, it will step through all effect bundles assigned to the entity and execute them. It will also remove bundles when they have expired. Generally speaking, this class is responsible for handling the lifetime, execution, and persistence of effect bundles related to a single entity.

 

EntityEffectBundle

The aforementioned bundles come to life through the EntityEffectBundle class. This is both a collection of effects and an execution container for them. A spell is just one example of a bundle – spells have one to three effects that share a common duration, chance, magnitude, magic type, etc. Every effect that exists in the game will be contained by an EntityEffectBundle. It’s similar to a Quest object in that effect bundles execute child effect scripts in a similar manner to how Quests execute child action scripts. Besides all of that, effect bundles are used to transport effects from one place to another, for example via a spell missile. The variety and management of effect bundles will see heavy work over time.

 

IEntityEffect

This is an interface to the effect. An interface is like a contract that defines what properties, methods, etc. a class must implement. The EntityEffectBundle will store a collection of effects using their IEntityEffect reference.

 

BaseEntityEffect

A default abstract implementation of the effect interface used to reduce workload by effect authors. The base class handles most of the common boiler-plate for any effect.

 

Effect

The effect itself. This is the script which actually performs work against the world, target entity, or whatever else the effect is designed to do. Just like a QuestAction, an Effect class is C# code executed by the owning EntityEffectBundle, which in turn is executed by the parent EntityEffectManager. Each effect is enumerated, keyed, and later factoried by the EntityEffectBroker when being added to a bundle. The effect itself should be very atomic, performing only the job it was intended to do. Effects will be insulated from the gory details of the wider systems and only need to take care of their own execution and persistence.

 

DaggerfallMissile

This is a mobile object like a fireball the player shoots into the world. Missiles aren’t just a visual thing, they are also used to carry effect bundles from one place to another, such as the fireball mentioned a moment ago. However, the appearance of the missile will depend on the magic type property of the effect bundle it carries (e.g. frost, fire, poison). Any entity hit by the missile will find the effect bundle payload added to their EntityEffectManager and they will suffer the consequences.

 

FPSSpellCasting

This is purely the visual side of casting spells for the player. It is the glowing hand attack you saw in my previous article. It deserves a mention because just like missiles, the casting animation will be selected based on the magic type the player is using (e.g. frost, fire, poison).

 

Immediate Mode Effects

Now you have a high-level overview of the major classes making up the Magic & Effects System, but something I haven’t talked about is how execution itself operates. I liken effect system execution to an Immediate Mode GUI, in that every tick of the effect system will expect current state from every active effect. Rather than try to track what every single effect is doing (which is a logistical and concurrency nightmare) the entity and effect management classes work around this by just not caring about the current state of any effect.

This simplifies both ends of the execution process. First of all, the EntityEffectManager does not need to track and remove state for effects operating upon its peered entity. There’s a limitless number of permutations of what an effect could do, and the ability to execute custom effects through the mod system further expands what is possible. The EntityEffectManager can’t possibly account for everything an effect might change, so it doesn’t try. It just requests every effect to apply its current work every frame. More on this in the next section.

Second, the effects themselves don’t need to worry about what other effects are doing – they only need to worry about the work they want to perform. This work might be to increase/decrease health, or fortify an attribute, or summon an item, or open a UI, but whatever that work is the effect itself gets to manage its own execution and state with almost complete control over itself.

If that all sounds a bit complex, please don’t worry about it. Everything works out to be fairly simple in reality, and there will be dozens of effect scripts to learn from. I expect the majority of effect scripts will be no more than 20-30 lines of code.

 

Sandboxing Effects

I mention above that effects have almost complete control over their own state and that management classes don’t even try to track what those effects are doing to the entity. You’re probably asking at this point how changes to the entity like a damaged Strength attribute is removed once the effect is finished? This is where some minor sandboxing comes into play.

Rather than allow effects to operate directly on the entity’s stats and skills, each effect has a payload of modifiers that it can use to change these attributes while active. The first part of this went into the game some time ago. DaggerfallStats and DaggerfallSkills each have a “mods” array that hold potential changes for every value (note these aren’t game mods, that’s just what the array is called).

When requesting a stat such as Strength, the game can request either the LiveStrength value or the PermanentStrength value. The Permanent value is the actual value stored in the entity. This is never touched or altered by an effect script. The Live value is a combination of the Permanent value modified by all combined effect “mods” active on that entity.

At the start of every tick, the effect system will first clear the “mods” state for all attributes. Then when an effect is executed, the management classes will merge any “mods” changes emitted by that effect to the entity’s resultant “mods” array. So when a formula asks for the current LiveStrength value, it will be handed the player’s real Strength plus or minus any changes made by effects. When those effects expire, the next tick of the effect system will clear its changes from the resultant set of modifiers.

This minor sandboxing process helps ensure that effects cannot accidentally alter the player’s attributes in any permanent way, provided they follow the design in place.

Not everything will be sandboxed in this manner (which is why I called it “minor” sandboxing earlier). Some values such as Health and Fatigue are designed to be raised/lowered constantly by several external factors, and are also very easily recovered. Any effects changing these values are fine to operate directly on live state.

 

Conclusion

The Magic & Effect System still has a very long way to go, but hopefully this article will serve to ground developers on the direction it is taking and what certain concepts mean inside the code. I hope to have active test effects with a real lifecycle running soon. This will help me further build the execution framework and start rolling out actual effects.

From there, work will progress deeper into Spellbook and Spellmaker UIs until the player is more-or-less casting real spells in the game. And by then, things should be far enough along to start adding support for magic items, diseases, advantages/disadvantages, potions, and so on.

As always, I’m looking forward to progressing beyond the design and build-out stages to actual implementation. Hopefully this will be the only dry, technical article in the series.

 

For more frequent updates on Daggerfall Unity, follow me on Twitter @gav_clayton.

Guild Systems

Hi everyone, Hazelnut here. Interkarma has asked me to write a blog post about some of the work I have been doing recently, so for this post Daggerfall Workshop has been taken over by me! Muhahahaha… etc. I’m sure your regularly scheduled Interkarma posts will return soon, so don’t worry.

Anyway, allow me to introduce myself, you may know me from such features as horse riding, inventory upgrades, shopping, persistent state, icons, tavern rooms, ships and houses, as well as various other bits and bobs. So why did I spring up from nowhere and start contributing to DFU?

I bought Daggerfall on xmas after its release and played like crazy for 7 days until the end of the christmas break, then stopped. Because it’s such a huge game, never really got back into it for years due to lack of time & small children – until shortly before Morrowind came out. By then the game was simply far too dated for me to persevere, especially because I forgot about the WSAD option and I was using the default control scheme of stupid mouse pointer arrows to move. So I’ve actually never played beyond the first couple of character levels. Always wanted to, and do intend to once DF Unity is done. This is why I am absent for any discussion or work around the main quest! Spoilers! Yep even after all this time.

While the progress has been fantastic (Interkarma has Orc level stamina apparently) it’s a big project and takes a long time, and since I’m a software engineer for the past 2+ decades who now does software design so don’t get to write much code at work… I figured I’d see if I could contribute. Also my kids are all teenagers now, so I have more free time than I’ve had for 2 decades. I had no knowledge of Daggerfall and its data structures, hardly ever touched C# and never used Unity before, so it’s been quite a learning curve. Anyway, after I finished my work on ships, houses, shops and taverns I asked Interkarma what he thought I should tackle next and between us we decided it was time to implement guilds. I’d already done some work with the guild services menus, but now I needed to create the guild membership systems.

Guilds

Guilds in Daggerfall follow some common rules for promotion etc but offer different services and quests. The first thing to focus on was ranks and building some foundations that would make each guild easy to implement, allowing the common behavior to be shared. I also wanted to ensure that new guilds could be added by mods, as I was sure that several people in the community were keen to add new guilds having seen discussions on the forums, and I had some ideas of my own that would be best integrated into the base game by adding a new guild. I decided early on that the guild code should be designed to support modding from the start, and the only way to ensure this was to actually implement a guild mod early on to prove the concept.

So, quite a lot to take on. Fortunately I had 3 solid days free coming up to get started on this. The fighters guild is the simplest of them all so I started with that. First step was to test classic and see how guild membership worked with rank changes etc. To support modding, the guild classes are designed so that they know about the players membership status, rank, and what benefits and services the guild provides at that rank. Service and guild management code asks the guild class by calling the appropriate method when they need to know. They also supply guild specific messages to the ranking system which is shared. This means that a new guild can simply be added by implementing a new guild class and registering it with the guild manager.

Now by this time you could join the Fighters guild.

Join Fighters

Joining the Fighters

Next thing was to show the guild memberships in the affiliations section of the character sheet. This required orange text which I think isn’t used anywhere else in the game.

Affiliations

Affiliations

Next, I fleshed out the benefits and services being offered at each rank and integrated it with the service menu I had previously done, then moved on to detection of rank changes. For the time being this is being checked every 24 hours rather than the 28 days it’s supposed to be. Resting for a month in classic daggerfall to test rank changing was incredibly tedious, 99 hours at a time! Also, for now, you can rest in guild halls for free as soon as you join – so testing doesn’t require finding a nearby inn. To test I was modifying guild reputation in savefiles and then reloading. Once promotion, demotion and expulsion were all done and working for the fighers it was time to deal with the harder bits.

Temples

So, temples are guilds but complicated because it’s like a single guild (you can only join one Temple) in many ways and multiple guilds in others. Players get different benefits at different levels from each different Temple, and the guild system needed to be able to cope with this. Knightly Orders are similar, but a lot less complex because they don’t offer training and curing services. I decided that Temples would be a single guild, but with a Divine variable set to enable variations. Building this required changing quite a bit of what I had built for Fighters, but this was the point of tackling the most complex second. It may not sound difficult, but I found it tricky to enable temples to offer training to non-members (at a higher price) because the services system was hooked into guild membership. Solved this in a way that is not available to new guilds, but not worried because this is a unique feature of temples and is so joining one temple doesn’t prevent you from training at a different one.

Temple Training

Getting training when not a member

Proving the foundations

The next step was to prove the foundations were designed and build right by implementing the Mages guild. This took less than an hour, with most of the time spent finding the correct message id’s in text.rsc for joining and being promoted. The fact that it was so quick and easy let me know that I had things right. It had taken quite a lot of work, but the foundations were done.

Denied

Mages don’t want you

A New Guild

Now it was time to prove that a new guild could be built and added by a mod. This threw up quite a technical challenge – how to integrate a new guild into the game world. As you will be aware if you have followed Interkarma’s blog posts, Daggerfall Unity works off the original games data files. This means the game world is set in stone within these files. (contrary to some opinion, there is no runtime procedural generation – it was all done upfront) After much thought and looking through the DFU code which reads and parses the world data from original files, which I had not had much reason to look at before, I realised that this data could be saved to text files in JSON format by simply using the serializer that’s already used to create saved games. So, I created some console commands to dump Daggerfall block data into JSON files, with the thought that I could modify these files and have them override the original game data at runtime.

I’ll not go into too much depth here, if you are interested check out my Guild Mod tutorial thread: http://forums.dfworkshop.net/viewtopic.php?f=22&t=901

Anyway I got to the point where a building within a block had a completely new interior. See these before and after shots.

Before

Before the world data is overridden

After

After overriding the interior world data for this building

It was very successful, only requiring a couple of tweaks to the guild foundations in the core DFU codebase. Things were progressing very well, but I had to do some work with the mod code to enable all this to be packaged into a DFU mod file which took a while to figure out. I hope a lot of players find the Archaeologists guild mod a valuable addition to their DFU play experience. See my forum thread for more details: http://forums.dfworkshop.net/viewtopic.php?f=14&t=888

 

Questing and Reputation

The last piece of the puzle for guild foundations was to migrate the test quest dispensing over to the guild service code and have several managed pools of quests for each guild. To do this I modified the table structure for quest lists so that each quest could be restricted to members / non-members and also by guild reputation. Then it was fairly straightforward to add all the different guild quests and have the right ones selected from when you ask for a quest. Again some more work was required to enable quests and lists to be packaged into mods, which I proved by adding a single quest to the Archaeologists guild mod. Also I created a more general mechanism for adding quests to Daggerfall Unity from Interkarma’s suggestion to allow quest packs for pure quest mods so authors didn’t have to package a full mod.

This works by scanning the full directory tree under StreamingAssets/QuestPacks for quest list files named “QuestList-whatever.txt” and loading them into the guild quest pools. Jay_H will be releasing the guild quests he wrote last year as quest packs soon, so hopefully this will demonstrate how easy it is! (or possibly what needs to be re-worked, noooo)

There’s still more to do for non-quild quests, but for now the focus is just guilds. The last thing I put in place was for quest success / failure to modify the players guild reputation – I left this until last because it was so much easier to just edit this during testing. By default each guild quest successfully completed increases your rep with the guild faction by 5, and failing decreases by 2. However, some quests shown on UESP have different reputation changes.

e.g. http://en.uesp.net/wiki/Daggerfall:Still_More_Trouble_with_Orcs and http://en.uesp.net/wiki/Daggerfall:More_Trouble_with_Orcs

I don’t have any idea how this is done in classic, or even if it was ever implemented – much of the info on UESP seems to come from Daggerfall Chronicles which was written from intentions before the game was complete. So if anyone out there has any info on this, or is prepared to do some testing please drop by this thread on the forums and give me a clue: http://forums.dfworkshop.net/viewtopic.php?f=4&p=11032

So, there you have it, a brief story of my journey implementing guilds. Hope everyone enjoys them in the latest build, and please be sure to report any bugs you find!

 

Town Populations

I’ve had my head in the quest system for several months and really needed a short break. I also happened to need a solution for spawning enemies outdoors in cities (for example, the ghosts and wraiths in Daggerfall at night) and noted there was a good amount of overlap between spawning enemies and NPCs in town environments because they all need to avoid placement inside building geometry. And whatever solution I use for placement could probably be used for navigation as well. I had scheduled wandering NPCs for 0.5 cycle, but decided to make an early start on this while solving town placement and navigation. And what better way to test this solution than to actually watch NPCs walk around?

The first problem I had was how to find an appropriate placement position. My initial idea was to use the foliage placement array in exterior data. This formed a nice grid over each block, but it also marched over water and under buildings. That would not be suitable. I considered just dropping in mobiles and using a combination of rays and colliders to refine their position until they found open space, but that approach seemed way too messy and inefficient.

That’s when I had a eureka moment thinking about how perfectly automap image data lined up with the game world. Take the below screenshot as an example. In game, I’m standing outside the Odd Blades looking at the entrance door. On the automap, once unit conversions are done, I’m in exactly the same place.

 

So Daggerfall’s automap perfectly skins building footprints. This should mean I can take the inverse of automap data to work out which parts of the environment are open. I quickly prototype by placing white cubes on open environment and avoiding the building footprints. Take a look at the results.

 

This is beyond perfect. The automap doesn’t just contain data for building footprints, but for flat placement and decorative geometry as well. I have a strong suspicion Daggerfall also uses the automap data in this manner, it’s just too precise and detailed to be a coincidence.

With a solution in mind, I now have to execute the idea. I create a new class called CityNavigation which is added to the location GameObject at scene layout time by StreamingWorld. This constructs a navigation grid at the same time location and automap data is read so only a small amount of additional processing is done per location. With the inverse of automap blocked out, we get the following:

This is good – the white areas can be used for placement and navigation, but it’s not perfect. It also needs to account for tilemap under location. We can’t place NPCs on water tiles, and they should try to avoid those tiles when walking around. Rather than just block out unwalkable tiles, I take this one step further and allocate each tile a specific weight, where a higher weight means the tile is more favourable. Here’s the final navgrid where black areas are “no-go” and brighter areas are preferred over darker areas. You can probably see right away this creates a strong preference for the road network:

 

What you can’t see in the above image is that each weight occupies the upper 4 bits of a single byte. The lower 4 bits are reserved for a flag system, giving me up to 4 bits to control NPC behaviours. This will be important later in this article.

Now that I have a nice procedurally generated map of any exterior location, the next problem is converting between all the different coordinate systems. If you’ve ever tried to make a big world in Unity, you’ll know that precision problems kick in after a few thousand scene units or so from origin (position 0,0,0 in world). This manifests itself through jittery movement and shadows, imprecise feeling of control, and issues with physics system. The game map in Daggerfall rocks in over 819,000 x 409,000 scene units, way beyond what Unity can handle with fine floating-point precision. I overcame this challenge very early on by using a fixed point coordinate system for the world (Daggerfall units) and normal floating point units for the scene (Unity units). The world is built around the player in chunks close to origin, and when player runs too far in one direction, the whole world is brought back towards origin. To the player it feels like they are running continuously through a huge open world, when in fact the world is being constructed around them one chunk at a time. The player never moves more than 1000 units from origin in the X-Z plane.

What does all of this have to do with the navgrid above? Well, now I have yet another coordinate system to glue together. I have not only the Daggerfall units and Unity units, but the X,Y position inside the navgrid array where any virtual mobile objects have to move around. So the next thing I do is write some helpers in CityNavigation to convert from navgrids to world space, world space to scene space, and back again, and so on. This chewed up a solid chunk of Sunday to get working properly, and there’s still a few precision issues due to the large differences in scale. Something to refine down the track.

With all the math out of the way, I can now start placing mobile NPCs into the world. One problem though, I hadn’t written any code to render wandering NPCs yet. So I started with these guys just to confirm the navgrid through scene conversions were working. Sometimes in game development, you have to bust out some programmer art to get the job done.

 

With placement working, next came the process of building the mobile NPC billboard properly – including that stop-and-stare thing they do when you get too close to them.

Town NPC Billboards

With rendering done, I can start moving them around the navgrid using a simple motor. They will generally follow roads when encountered (because roads have a higher weight), but there’s enough randomness to let them change directions and wander around elsewhere on the grid.

And do you remember me mentioning the navgrid can store flags in the lower 4 bits? The first flag I created is an “occupied” bit that lets a mobile claim a navgrid tile before walking into it. This prevents two or more NPCs trying to occupy the same tile at a time. The next clip shows the mobile movement, path following, and dynamic avoidance of each other. I’ve cranked up the spawn count and movement speeds because it helps me observe the behaviour (and it’s kind of fun to watch).

Mobile Pathing and Dynamic Avoidance

Despite everything accomplished, I still have more to do. The next step is working out which races are placed in which towns. I put my travelling boots on and tracked around classic Daggerfall’s world until I found which races appeared in which climate zones. I built this into the helper which returns climate data for texture swaps, etc. and now the correct NPC races (either Redguard, Nord, or Breton) will appear across the game world.

 

The final step was to build a PopulationManager class. This code handles spawning/despawning of NPCs around player as you move through town environments so the location feels populated. After a bit of experimentation, I used a population index per 16 RMB blocks so that small towns feel like they have a smaller overall population than large cities. One of my challenges here is the draw distances in Daggerfall Unity are huge compared to classic Daggerfall. While classic can place NPCs safely in the fog out of sight, in Daggerfall Unity you can see two full city sizes distant across the map. This means that hiding pop-in and pop-out of NPCs is a little trickier. For now, I mitigate this by trying to only show or hide NPCs when player is not looking directly at them (as Daggerfall does) and only allow them to pop-in when a certain distance from player.

There’s still a few bugs to iron out. You can still catch them pop-in nearby if you happen to look in the right direction at the right time, and they sometimes glide slightly in the wrong direction on spawn due to precision issues as they align to the grid. And of course you can’t talk to them yet, because the “talk” system won’t be introduced until 0.5 sometime. But overall, the feeling of crowds is quite satisfactory and Daggerfall-ish, and it’s wonderful to finally see these sprite people bustling around cities.

I hope you enjoyed reading about some of the work that goes into creating even a small feature like this one. If you’d like to read more, I try to post regular micro-updates to my Twitter feed @gav_clayton.

 

Questing: Place Resource

I’ve decided to go in a slightly different direction regarding dev articles about quest system from now on. Instead of the traditional numbered sequence split into a few parts, I will post more about what I’m working on in the moment. There are two reasons for this. First, questing is a huge subject that resists being neatly split into a progressive narrative like items or streaming terrain. I often have to cross back and forth between related systems. Second, it gets a bit daunting trying to construct that narrative from such fragmented work. The end result is that I’m posting less and feeling more weight on my shoulders every time I try to construct a post. Just how do I describe to everyone I spent weeks working on research without a satisfying answer to a particular problem?

My solution is to tear the band-aid off and just post something. I’m slowly learning that many people enjoy the development process itself, including the potential for frustration and dead ends. Those outcomes aren’t particularly enjoyable for me when they happen, but maybe I can turn them into something positive and entertain my readers. This should result in more posts but they will often be shorter (which in itself might be a good thing). This post probably won’t be shorter, but it is my first in a while. 🙂

So here’s what I’ve been working through lately…

In a QBN section, Daggerfall quests defines resources that kind of glue the whole shebang together. They define places in the world, people to visit, timers, items, and enemies. Basically all the world-stuff player will contact to unroll that quest’s execution. A high-priority resource is Place, which defines locations the player must use in the quest, like a dungeon, shop, or residence. Here are some examples.

Place _mondung_ remote dungeon9
Place _house_ local house2
Place _inn_ local tavern
Place _palace_ remote palace
Place PiratesHold permanent PirateerHold1

To deconstruct the above: Place tells the compiler this is a place resource; _symbol_ is the name of that place for the compiler to reference; remote/local/permanent is where to select that place from; and the final bit is site which tells quest engine what type of place to select. The site code is actually a reference to a places data table which defines the parameters for these site types. I won’t go into these in much detail, just keep in mind they define what kind of building or dungeon to select.

Let’s use “local tavern” for now. This means find a random tavern within the same town as where player received quest. If this was “remote tavern”, we’d select a random tavern from another town in the same region. The site code “tavern” is then looked up in the places data table and the parameters tell us this is building type 15 (0x0F).

Now the quest engine knows it needs a tavern (building type 15) and it should select from the map player is currently in. Fortunately, Daggerfall keeps a handy list of buildings for every map definition in MAPS.BSA. This gives us information like the building name seed, faction, quality (“rusty relics” through “incense burning”), and best of all building type. Great! We already know we need a tavern, and it’s trivial to select taverns from this list of buildings and grab one at random. Now we have our quest location… well, almost.

A Daggerfall city is made up of geomorph-like blocks – up to 8×8 blocks for really big cities. They are like puzzle pieces laid out on a grid. Here’s the block layout for the City of Daggerfall, you might recognise this from Daggerfall Modelling.

 

Every block also carries a list of buildings it contains, sharing the same data structure as MAPS.BSA – with a few differences. One key difference is that a few of the values present at map level (e.g. name seed) are not present at block level. The reason for this is obvious when you consider how often blocks are reused across locations. If the name seed was stored in block data, our tavern would have the same name in every location that block is used. Thus the name seed is carried at map level and merged down to block level as needed. Same goes for the block texturing, which changes based on climate. Put together, this all makes blocks somewhat polymorphic in that they can take different forms depending on the location they belong to.

Back to our tavern which we found in building list at map level, how then do we map this to the actual physical building at block level? Besides other jobs like setting the correct names on automap, this is needed to determine correct physical location of quest buildings in the world. This is where some of my troubles started.

At time of writing, it is unknown exactly how Daggerfall links building data at map level down to building data at block level. To compound my problems, only a subset of buildings are represented at map level. A large city like Daggerfall will have many more physical buildings than listed for that location in MAPS.BSA. Even in small locations where the totals match, the individual building type counts don’t always match. For example, map data might define 6x House1 and 4x House2, while block data will contain 5x House1 and 5x House2. There doesn’t seem to be any consistent way to link these two sets of data together. If this were a relational database, I would expect a stable primary and foreign key matching on both sides. But not only does a key not seem to exist between them, the totals cannot be trusted to line up between map and block buildings.

Despite this, I have been able to make some good progress. I discovered that named buildings (taverns, stores, guilds, etc.) are always in the same order in the map building data as the block layout data. Couple this with the building name seed discussed a while back, it’s possible to merge down named buildings without much trouble. This is also needed for the automap like below. Credit goes to Nystul for the excellent automap implementation.

 

When it comes to generic premises like House1/House2, things become more difficult. I can’t depend on an exact match between building type distribution, and can’t find a way these could possibly be linked in a stable manner. Both Lypyl and myself have been through the binary data in great detail. Despite finding a few other interesting leads, we have not found a satisfying answer to the question of mapping non-named buildings from map level to block level.

After many frustrating weeks of searching, I’ve more or less come to the conclusion that it really doesn’t matter. The only buildings that need to be mapped 1:1 are named buildings, and I already have a working solution for this. When it comes to generic premises (which are selected randomly anyway) it should not matter which House1 or House2, etc. Daggerfall Unity selects for a quest. As long as the end behaviour closely matches that of Daggerfall by selecting a building of the correct type, I’m basically free to implement this in a manner suitable for Daggerfall Unity.

In hindsight, the apparent lack of stable linking between map and block data could account for some quirks in Daggerfall itself. For example, it’s not uncommon to find a tavern which Daggerfall thinks is a residence. And only about half the buildings in most towns can be entered anyway (“this house has nothing of value”). My feeling now is that when a location is loaded, Daggerfall simply distributes map building data amongst block buildings using some kind of algorithm where named buildings are populated first and generic buildings are distributed to best effort. As long as named buildings are handled (they are), and other buildings are selected randomly (they seem to be), then I can at least reproduce this behaviour in a way that feels exactly the same to the player. My solution might not be exactly what Daggerfall is doing, but it’s likely very close.

So that’s where I’m at right now – working through implementation of Place resource, selecting locations in the world, and ensuring this maps to physical environment correctly. During this process, I’ve added some fun bits along the way such as the flavour text when entering a dungeon area outdoors. This text is based on dungeon type and reads from strings in Daggerfall’s text database using the same variations.

The other side of a Place resource is the “pc at” condition which tests if player is at a Place or not. This is highly intertwined with Place resource handling so I’m likely to bounce back and forth between these two for a while until I’m happy.

That’s all for now. Rather than go through a long delay between posts again, I’ll try to post as regularly as possible with updates on what I’m working on at the time. Even if the post is short, I’ll try to put in some details of the development process for you to read.

If you enjoy this sort of post, please let me know! Feedback helps me work out what people enjoy reading and hopefully write better posts in the future. Thank you for reading, everyone. 🙂

Questing Part 3 – Anatomy of a Task

Example custom quest action created for this post

The quest system back-end is coming along. I’m sad it’s not further along by now, but life has a way of disrupting plans. The important thing is I’m still making progress and have some good stuff to share today.

In this post, I will dissect tasks along with their conditions and actions, which together form the meat of a quest. There’s a great deal of technical content ahead, I want this post to be a kind of primer for contributors to quest system. My apologies to those of you who don’t enjoy code-heavy updates.

Before getting started, please have a quick skim through Donald Tipton’s excellent documentation for his Template v1.11 quest compiler/decompiler. As discussed in Questing Part 1: Source, these source files are also used by Daggerfall Unity’s quest parser so we have common ground with classic. This even allows quest source to be shared back and forth with classic for testing. I’ve actually rolled back some of my ideas from that first post and will use Template source files directly as-is without any changes. This might have to change in time but right now I’m aiming for total parity.

If you’d like to see some real quest source, you’ll find all of Daggerfall’s decompiled quests in the StreamingAssets/Quests directory (link to GitHub, ignore .meta files). But today we’re just zooming in on tasks and actions to see how these are handled by Daggerfall Unity.

 

Tasks

Daggerfall quests have four distinct forms of tasks (so far). All of the examples below are from the quest _BRISIEN.

Standard – This is a basic task which does not start unless explicitly triggered somehow. The task name (e.g. _invitepc_) is also a boolean symbol which can be queried to see if task has been triggered (i.e. is active). The lines under the task header are the conditions and actions making up that task.

_invitepc_ task:
	start timer _remindpc_ 
	give pc _letter1_ notify 1026 
	create npc at _dirtypit_ 
	place npc ladyBrisienna at _dirtypit_ 

Repeating – These tasks execute continuously until the symbol they reference (the boolean state of another task or variable name) is triggered. In below case, the task will persist until _exitstarter_ is triggered. Repeating tasks appear to be triggered automatically at startup.

until _exitstarter_ performed:
	start quest 999 999 
	start quest 977 977 
	start timer _invitepc_ 
	remove log step 0

Variable – A variable is really a kind of task with trigger state only. Trigger state may be set/unset by other tasks.

variable _exitstarter_

Headless – Every quest must have a single headless task. This is the entry point to be executed automatically at quest start-up. Unlike other tasks, a headless task does not have a symbol to query trigger state. It just executes to bootstrap the rest of quest. This is the entry point of _BRISIEN:

--	Quest start-up:
	log 1010 step 0 
	pc at PiratesHold set _exitstarter_ 
	say 1025 

At time of writing, Daggerfall Unity will parse through quest source to instantiate tasks and try to match component actions to a registered template (more on this below).

 

Conditions

Other than being triggered at startup or by other tasks and clock time-outs, a task can have one or more conditions that might cause it to be triggered. For example, if player is in a specific place at a certain time (e.g. Daggerfall at night) then some action can be performed (e.g. play the “vengeance” effect). This makes it possible to chain together tasks which trigger on and off based on the trigger state of other tasks.

I won’t go much into conditions right now as they have not been implemented yet. I’ve just barely stubbed out a bit of starting code that will be replaced later. If you like, you can read more about quest conditions here.

 

Actions

A quest action is a bit of text that does something. This is usually a single thing like playing a sound, displaying a message, or starting another task. Don’t think of actions like a normal programming command though. They aren’t necessarily run and done (although they might be). Try to think of actions as components attached to a task in a similar way that Unity components are attached to a GameObject. This isn’t a perfect analogy, but its a start. Like GameObjects in Unity, tasks can switch on and off and their component actions perform bits of work over time.

Actions are a great way for contributors to help build out the quest system. There are many different kinds of actions, some will be very simple others very complex.

 

Building Actions

So how does an action go from a line of text to actually doing something in the game? The rest of this post will cover the fundamentals and show a real working example of a custom action… in action.

The bones of every action begins with the ActionTemplate class, an abstract implementation of IQuestAction interface. All actions must inherit from ActionTemplate and implement the required parts of IQuestAction. This ensures that every action template has a few key features:

  • Pattern – A regex string used to pair a line of source text with this action. Two actions cannot have the same match pattern.
  • Test – Checks if provided source string matches the regex pattern expected for this action.
  • Create – An action template is special in that it can also factory (i.e. generate) a new instance of itself with default settings. This allows the QuestMachine which hosts active quests to hold a list of self-replicating action templates that can be instantiated as required.
  • GetSaveData – Gets a data packet from action live state. This will be passed on to JSON serialization system when saving a game.
  • ResoreSaveData – Sends a data packet to action from serialized state. This will be used to restore action state when loading a game.
  • Update – Called by the task owning this action. Allows the action to do work every frame as needed.

To show all of this working, I wrote an example called JuggleAction which simulates the player juggling some number of objects with a percent chance to drop one. Click here for the full source code and I’ll break it down below. Let’s start with the pattern:

public override string Pattern
{
    get { return @"juggle (?<numberOfThings>\d+) (?<thingName>\w+) every (?<interval>\d+) seconds drop (?<dropPercent>\d+)%"; }
}

This is just a basic regex match string that looks for a pattern like “juggle 5 apples every 2 seconds drop 40%”. Everything the action needs to execute is contained in the pattern. Sometimes an action might take different forms and the pattern string must cover these variants also.

The parser uses Test to find a registered action template with pattern matching source. When a match is found, the JuggleAction template will factory a new instance of itself with default settings by way of Create.

public override IQuestAction Create(string source, Quest parentQuest)
{
    // Source must match pattern
    Match match = Test(source);
    if (!match.Success)
        return null;

    // Factory new action and set default data as needed
    JuggleAction action = new JuggleAction(parentQuest);
    action.thingName = match.Groups["thingName"].Value;
    action.thingsRemaining = Parser.ParseInt(match.Groups["numberOfThings"].Value);
    action.interval = Parser.ParseInt(match.Groups["interval"].Value);
    action.dropPercent = Parser.ParseInt(match.Groups["dropPercent"].Value);

    return action;
}

You’ll notice the action parameters are exposed directly by the Match class returned by Test. This makes it easy to read out the values involved. At this time, our new action is ready and is added to a collection stored in the Task object. During quest runtime, the task will call Update on each action to do the work required. Here it just counts off time and if still holding any objects, calls the Juggle() method. Note that we’re using Time.realtimeSinceStartup instead of Time.deltaTime. The reason for this is that QuestMachine ticks at a slower rate than Unity (currently 10 times per second). So we need to measure time without using something that only changes frame-to-frame.

public override void Update(Task caller)
{
    // Increment timer
    if (Time.realtimeSinceStartup < nextTick)
        return;

    // Juggle 'em if you got 'em
    if (thingsRemaining > 0)
    {
        Juggle();
    }

    // Update timer
    nextTick = Time.realtimeSinceStartup + interval;
}

Below is the Juggle() method for completeness. It just spits out some notification text to HUD and randomly decrements object count until none are remaining.

private void Juggle()
{
    // Juggle current things
    DaggerfallUI.AddHUDText(string.Format("Juggling {0} {1}...", thingsRemaining, thingName));

    // We might drop something!
    int roll = Random.Range(1, 101);
    if (roll < dropPercent)
    {
        thingsRemaining--;
        DaggerfallUI.AddHUDText("Oops, I dropped one!");
    }

    // Give up if we've dropped everything
    if (thingsRemaining == 0)
    {
        DaggerfallUI.AddHUDText(string.Format("Dropped all the {0}. I give up!", thingName));
        return;
    }
}

I won’t touch on GetSaveData and RestoreSaveData yet as quest state serialization has a ways to go. You can check the full source of JuggleAction linked above for an example implementation.

You might recall I said something about registering new actions with QuestMachine. This might change later, but right now our action class JuggleAction is registered in QuestMachine from RegisterActionTemplates() like below. The template is only being used as a factory so it doesn’t need to pass in an owning quest at construction.

RegisterAction(new JuggleAction(null));

Registering the action template allows the quest machine to find it (using Test) and factory a new instance from the template.

Now that we have an action and registered it to quest machine, we actually need a quest that uses this action for real. I created a cut-down quest just for this example called __DEMO01.

- Minimal example quest used to demonstrate how to script custom actions

Quest: _BASIC01

QRC:

- No text resources

QBN:

- Headless entry point with custom action
juggle 5 apples every 2 seconds drop 40%

All that remains is to instantiate the quest itself. I will add a console command soon for this, but in the meantime I’m calling the following bit of code from StartGameBehaviour.

GameManager.Instance.QuestMachine.InstantiateQuest("__DEMO01");

This loads our custom quest into the quest machine and starts executing supported actions, which right now is just the demo quest and juggle action. When starting a game, this will be the output:

 

Next Steps

For now, I will continue to work on the quest machine, parser, and related frameworks. My immediate next step will be to get the full tutorial quest working along with some foundation conditions and actions, and a few supporting user interfaces (quest log, quest debugger UI).

I would like to invite the more experienced contributors to review the quest source documentation in more detail and see if any actions might fall into their range of interest. I would also love some help with quest resources other than tasks (e.g. Place, Item, Foe, Person, etc.). I’ve stubbed out the Clock resource as a starting point. If there is something you would like to work with, please start a conversation on the forums and let’s see where it takes us.

If you have any questions or would like to dicuss this post in more detail, please don’t hesitate to find me on the forums!

 

For more frequent updates on Daggerfall Unity, follow me on Twitter @gav_clayton.

Questing Part 2 – Compiling

In the first part of this series, I discussed how I’ll be using source files output by Tipton’s Template v1.11 for quests in Daggerfall Unity. If you’d like to check these out in full, the quest source files are already on GitHub. Follow this link to view them (ignore the .meta files).

Some interesting quest files to investigate are:

  • _BRISIEN.txt – This is the quest that launches when player starts in Privateer’s Hold. It sets the whole story arc in motion and starts timers for delivering letters that prompt player to visit Lady Brisienna. Failing to visit Lady B in time is ultimately a failure condition of main quest.
  • S0000999.txt – Starts when you leave Privateer’s Hold. Delivers letters from Prince Lhotun and Morgiah and sets key global variables.
  • S0000977.txt – Also starts when leaving Privateer’s Hold. Sets up regular ghost and wraith spawns in Daggerfall and plays the VENGEANCE! sound.
  • TUTOR.txt – Is the tutorial quest started when selecting Yes to the prompt at start of game.

As another interesting tidbit, longtime players may have noticed the initial journal entry that begins with…

"I am on a mission from the emperor to investigate
the shade of King Lysandus. His spirit has been
haunting the city of Daggerfall. The emperor
himself has charged me with the duty of laying
his ghost to rest."

…will stick around in your log forever. Even after you’ve completed the game, this first journal entry will remain. As part of researching the quest system a while back, I looked into why this was happening and found the above journal entry is added twice and removed only once. The below image sums it up visually. You may have already seen this when I posted it to Twitter back in September.

 

questlogmessagestuck

So the quest system in Daggerfall is quite powerful. It’s responsible for adding and removing journal text, starting timers, delivering letters, spawning enemies, playing sounds, setting global variables, moving NPCs, and a slew of other functions. At first blush it can appear a lot like a full programming language, but it’s only superficially so. The structure is actually more like a complex INI file, or even a kind of markup file. Everything is neatly categorized into its own section and execution flow generally only happens in a few different ways. Most commonly are at startup, when a timer ends, and due to a variable or condition changing state.

Thus despite the initial similarity to a programming language, the quest source is really just a collection of defined objects with some very basic scripting functions. Most of these functions revolve around spawning something, starting something, playing something, or changing something. Complex enough to get the job done, but don’t feel like you need to be a programming expert to create new quests in the future. Using Tipton’s Template v1.11, you could even start creating quests in classic Daggerfall now and later port them into Daggerfall Unity.

Likewise, the job of compiling the quest source back into Daggerfall Unity is not that difficult. It’s going to have some challenges, but nothing on the scale of building a real compiler, something I thought I’d be facing at the outset. The problem is largely just splitting source file up into correct parts and handing that source off to classes designed to support that part. For example, messages will go to a Message class, timers will go to a Timer class, etc. When serializing live quests as part of save games, the QuestMachine will save/load JSON state for each live quest along with the global variables for the current game.

To help Daggerfall Unity re-compile Template’s source output, I’m going to make some minor changes to the expected source files. I’m trying to keep these changes to an absolute minimum.

First change is for the quest header to be uncommented in source file. For example, _BRISIEN has the following header. The dash ‘-‘ prefix starts a comment.

-- StartsBy: letter
-- Questee: anyone
-- Repute: 0
-- QuestId: 0

This reason this can be commented out is that Template is designed to re-compile quests back into the original QBN/QRC format. When commented out, Template will just use the information already in the quest QBN data. However, Daggerfall Unity relies entirely on the quest source and will need the above uncommented to:

StartsBy: letter
Questee: anyone
Repute: 0
QuestId: 0

This way the information can be parsed back into the quest data at compile time.

The second change is that I would like an explicit startup task, rather than an implicit startup after the QBN object definitions (like Person, Clock, etc.). Currently the startup task looks like this:

-- Quest start-up:
log 1010 step 0 
pc at PiratesHold set _exitstarter_ 
say 1025 

I would like to change this to:

startup:
log 1010 step 0 
pc at PiratesHold set _exitstarter_ 
say 1025 

This makes the startup task an explicit task object to be executed when quest begins. This is already the current behaviour, but I think this change makes the task clearer to identify for both quest creators (even without a comment) and for my compiler. I could definitely get away without this change, but I prefer the explicitness to the current setup.

And of course, the above is subject to change as the quest system matures. If I learned anything from rolling out items, the feature will probably look different again by the time it’s mostly complete. Daggerfall Unity is not just a game remake, it’s an ongoing research project into the guts of Daggerfall. That adds a few twists outside of normal gamedev process, and I just need to roll with it.

One of the upcoming features not shown yet is the quest debugger currently in development. Hopefully, I will have something to show on this by part 3. The quest debugger will be used to manually start new quests, terminate and restart executing quests, and inspect state of global variables and quest objects. It’s a big UI that will continue to grow as development progresses. Should turn out to be quite useful though.

 

For more frequent updates on Daggerfall Unity, follow me on Twitter @gav_clayton.

Questing Part 1 – Source

With items and loot more or less finished, it’s time to place my sights on the next big feature group. I had originally planned to work on spells and effects in the 0.4 cycle, but also had quests in mind as an equally important feature. So back in July, I used a Twitter poll to sample what the community wanted priority on. The answer came firmly in preference for quests over spells.

Fast forward a couple months: 0.3 stable is now tagged on Live Builds page and I’ve started work on the quest system in earnest. This post is the first in a series documenting the journey from raw bytes to a working feature.

When adding a big new feature, there’s always a technical planning stage before commencement. I need to understand which of Daggerfall’s binary files are involved in the feature, learn how much is already known about those files (sometimes a lot, sometimes almost nothing), map out the additional details I need to know before I can re-implement that feature, and finally start cutting some code.

Sometimes it takes a few iterations, as writing code to pull apart the binaries is itself a journey where new information is learned. I don’t know what I don’t know, and often that new information results in a new iteration with better understanding. There’s basically a research-implement-compare loop going at all times throughout development of Daggerfall Unity. It can be a bit draining.

Items for example needed considerable research to bridge the gap between “enough knowledge to make an item editor” and “enough knowledge to fully implement items in a new engine”. Believe me, there’s a huge amount of work needed between having a file spec with lots of unknowns and building a completely functional equivalent. Most of my time is spent somewhere in that gap.

So when starting quests, I set out to learn everything I could about the binary formats and the work others had done before me. I was pleasantly surprised to learn:

  • Quests are among the most well-understood formats, thanks to the work of several early Daggerfall hackers (notably Donald Tipton and Dave Humphrey).
  • Tools exist to edit live quests, but more importantly decompile the QRC and QBN files to a human-readable source file (thanks to Template v1.11 by Tipton).
  • Early Daggerfall modders already had a good understanding of creating quests for Daggerfall – there’s an established process.
  • Quest files are one of the few cleanly decoupled things in Daggerfall. Unlike items which have template data hard-coded in the executable, quests are nicely self-contained.

With the above in mind, it was no longer necessary for me write a quest decompiler from scratch, design a new file format, decouple quest data, or chase half a dozen other time sinks. I can almost go directly to implementation. Almost. But first I need quest data in a usable form.

For the first step, I’m using Template v1.11, which you can find on UESP. This tool can decompile all the QRC (quest text) and QBN (quest programming) files to a single easy-to-read text file. So the information goes from raw binary data to the following (snippet from starting quest _BRISIEN).

QBN:
Item _letter1_ letter used 1020
Item _letter2_ letter used 1021
Item stopMainQuest letter used 1022

Person ladyBrisienna face 1 named Lady_Brisienna anyInfo 1012 rumors 1013

Place PiratesHold permanent PirateerHold1
Place _dirtypit_ remote tavern

Clock _invitepc_ 7.00:00 14.00:00
Clock _remindpc_ 30.00:00 0 flag 1 range 0 1
Clock _pcfailed_ 14.00:00 0 flag 1 range 0 1
Clock _oneday_ 1.00:00 0 flag 1 range 0 1
Clock _nowwhat_ 29.09:00 0 flag 1 range 0 1

-- Quest start-up:
 log 1010 step 0 
 pc at PiratesHold set _exitstarter_ 
 say 1025

That can still look a bit daunting if you’re not comfortable with programming concepts, but the source format generated by Template v1.11 is generally very easy to read and understand – more like a complex INI file than a real programming language. It’s so good that I’ve decided to adopt Template’s output as the source data for quests in Daggerfall Unity. You won’t need to recompile quest source back to QBN/QRC, rather you will use the source directly in Daggerfall Unity where it will be compiled at runtime by the quest system.

This means the de facto standard for creating Daggerfall quests will remain essentially the same in Daggerfall Unity (with some minor differences I’ll discuss later). If you’ve ever created a quest for Daggerfall, or even seriously looked into it, then you already have the skills to create quests in Daggerfall Unity. If you’re new to Daggerfall quests then you can learn from existing quests and read Template’s excellent documentation. Just as I don’t need to start from scratch, neither do you.

I will need to change the format slightly for unique needs on my side, but I aim to keep my input format as close as possible to Template’s output format. There’s also the need to emulate support for every single condition and action in Daggerfall Unity to behave similarly to Daggerfall given the same quest source. That will probably be an ongoing process all the way through to 1.0. But we need to start somewhere, and this is a great starting point.

The next article in series will look at parsing quest source files and how quests will be executed inside Daggerfall Unity.

 

For more frequent updates on Daggerfall Unity, follow me on Twitter @gav_clayton.

Building Names

One of Daggerfall’s long-running puzzles is how to generate the correct building name for any given building in a location. Daggerfall’s binary data exposes this information only as a seed value with no obvious correlation to the final name. From today, I’m happy to say this has been solved and I will be able to generate proper building names in the future. This article is a summary of the technical journey, minus all the dead ends and frustration.

The seed value used to generate building names has been known about for some time. This can be found in the BuildingData structure (link to UESP). The first step along the way was to generate some known values by changing a known seed value in MAPS.BSA. I started at the location Ashfield Hall in the Daggerfall province, which has a single tavern and some residences. Taverns are a great place to start as they have a very obvious PartA + PartB structure. For example The Bat And Skull. In Ashfield Hall, our single tavern is the The Howling Stag with a name seed value of 27748.

The first thing I did was change the name seed value for The Howling Stag in MAPS.BSA then start up Daggerfall to see how the name changes. Here’s a small sample of names generated from seeds 0-3. Keep this list in mind as we’ll return to it later.

0 = The Dancing Chasm
1 = The Knave and Scorpian
2 = The Pig and Ogre
3 = The Thirsty Fairy

Now I have somewhere to begin. I know the building is a tavern and have a sample group of seeds that result in specific names. The next trick is to work out how Daggerfall derives these names from the seed value.

I open up FALL.EXE in a hex viewer and search through for strings like “The Dancing” and “Chasm”. These strings are easy enough to locate, but these are just resources packed into the executable. What I need is the actual PartA and PartB tables Daggerfall is selecting from at runtime.

To get this information, I first have to use the DOSBox debugger to dump out memory from Daggerfall while it’s running. I can then search not just for strings, but for memory offsets pointing to those strings. I write a small bit of code to do the searches for me, and it doesn’t take long to find the correct offset tables for Part A and Part B of tavern names. Just think of this as a pair of arrays. In this case, both arrays are 36 elements long. Here they are as captured from the spreadsheet I dumped them out to.

TavernNamePartsAB

So how do we go from a seed of 0 to The Dancing Chasm? This is where most of the difficulty started. It was obvious Daggerfall used a random number generator to pick both parts, but the trick was to find the correct random number generator used by Daggerfall’s C compiler circa 1994-1996. Fortunately, I also needed this for correct texture table generation (still an open problem at time of writing) and had previously researched the correct random generator, known as a linear congruential generator, specific to Daggerfall. Here it is for completeness.

static ulong next;
public static void srand(int seed)
{
    next = (uint)seed;
}
public static uint rand()
{
    next = next * 1103515245 + 12345;
    return ((uint)((next >> 16) & 0x7FFF));
}

There are two methods here, one to set the seed (srand) and another to generate the next random number from that seed (rand). This is pretty much the standard ANSI LCG but specific to Daggerfall’s needs. Implementing this manually ensures that critical random number generation will always work just like Daggerfall, regardless of platform.

Now that I have the right random number generator, let’s feed it our test seeds from earlier and see what comes out. Starting with seed=0 and generating two numbers (indices into Part A and Part B name tables above), I get the following results.

PartA = 0
PartB = 12

First obvious thing is the spreadsheet starts from 1, not from 0. Just need to +1 each number to match the tables above (although zero-based arrays will be used in actual code). Matching these numbers to the above name table we get: Chasm The Dancing. OK, so Daggerfall obviously generates PartB first then PartA. Let’s try that again with the +1 and order swapped.

Seed = 0
  PartA = 13 (The Dancing)
  PartB = 1  (Chasm)
  Result: The Dancing Chasm

Using our handy table we can match row 13 with row 1 and we get The Dancing Chasm. Good! Let’s run some more tests and prove the concept.

Seed = 1
  PartA = 35 (The Knave and)
  PartB = 27 (Scorpion)
  Result: The Knave and Scorpion

Seed = 2
  PartA = 30 (The Pig and)
  PartB = 9  (Ogre)
  Result: The Pig and Ogre

Seed = 3
  PartA = 16 (The Thirsty)
  PartB = 36 (Fairy)
  Result: The Thirsty Fairy

So far, so good! Building names are output just like Daggerfall given the same inputs. Let’s try the original, unmodified seed value of 27748 which should give us The Howling Stag.

Seed = 27748
  PartA = 21 (The Howling)
  PartB = 33 (Stag)
  Result: The Howling Stag

And there we have it! Building name generation from initial seed value resulting in a string exactly matching Daggerfall.

From here, I still need to extract hard-coded name tables for other building types like armorers and weapon-smiths. This isn’t hard though, I just need to find the tables using the same methods as taverns. I also need to assign full building data from MAPS.BSA to the correct models in Unity scene and wire up API methods to query this data when inspecting or entering a building. One challenge at a time though.

For regular small updates on Daggerfall Unity, I can be found on Twitter @gav_clayton.

Items Part 3 – Paper Doll

With item bitmaps and dyes out of the way, it’s finally time to begin work on paper dolls. The concept of layering cutouts of clothing and other accessories over a figure is centuries old, and a perfect solution for early video games where memory was at a premium. Daggerfall’s paper doll system is easily one of the most extensive to be found in video games of the time.

Before equipping anything to the paper doll, a few key pieces had to be researched.

  • Body Morphology. Every bit of armour and clothing has 8 variations to suit the male and female body shapes of Argonians, Elves, Humans, and Khajiit. The correct texture set must be mapped to the correct race and gender.
  • Position. The X, Y coordinates of each item on paper doll is coded into their texture files. This is tightly coupled to morphology.
  • Draw Order. Every item template has a value to determine the correct item rendering order on paper doll.
  • Equip Table. The equipment slots available to player and rules for what is equipped where.

I won’t go into detail about the first three, that information is just managed by the API as part of importing or generating items. The equip table is a little interesting however with a total of 27 slots available. I use the same index setup as Daggerfall itself.

  • 00 Amulet0 (amulets, torcs, etc.)
  • 01 Amulet1
  • 02 Bracelet0
  • 03 Bracelet1
  • 04 Ring0
  • 05 Ring1
  • 06 Bracer0
  • 07 Bracer1
  • 08 Mark0
  • 09 Mark1
  • 10 Crystal0
  • 11 Crystal1
  • 12 Head (helms)
  • 13 RightArm (right pauldron)
  • 14 Cloak1 (casual cloak, formal cloak)
  • 15 LeftArm (left pauldron)
  • 16 Cloak2
  • 17 ChestClothes (shirt, straps, armbands, eodorics, tunics, surcoats, robes, etc.)
  • 18 ChestArmor (cuirass)
  • 19 RightHand (right-hand weapon, two-hand weapon)
  • 20 Gloves (gauntlets)
  • 21 LeftHand (left-hand weapon, shield)
  • 22 Unknown1
  • 23 LegsArmor (greaves)
  • 24 LegsClothes (khajiit suits, loincloths, skirts, etc.)
  • 25 Unknown2
  • 26 Boots (boots, shoes, sandals, etc.)

The two unknowns could just be reserved indices as I was unable to find any equipment Daggerfall mapped to these slots. If there’s more to this, I’m confident it will be found in future testing.

As usual the API handles equipping items for developer, it’s easy as calling EquipItem(item) on the entity’s equip table. If an item of that type is already equipped, it will be dropped in the next compatible slot (if one is free) or swap out an existing item based on swap rules for that item template.

Now that we know which items the player has equipped, the textures to use, and their position and draw order, it’s fairly trivial to start layering down bitmaps onto the paper doll. But as usual, a couple of additional problems must be solved.

First up are cloaks, which have both interior and exterior parts drawn at different stages of the build. The below image shows how the two parts work together.

 

Cloak Components

 

The interior is drawn first, then the avatar, then the cloak exteriors. It’s actually possible to wear two formal or casual cloaks in Dagerfall (slots 14 and 16). Note: the above image was taken prior to order being fixed which is why the loincloth is slightly eroded in first and third images.

Our next problem is masking. Daggerfall has a special mask index allocated to hide hair that would otherwise be drawn outside of helmets. During the build process, the mask becomes transparent and overwrites anything else in that position. Masking is used for both helmets and hooded robes/cloaks.

 

Mask Components

 

Other items can then be drawn based on their draw order. The below animation shows a step-by-step paper doll build after sorting items by draw order.

 

 

Now that items are equipped, we need a way of removing them again. Daggerfall allows you to click directly on paper doll itself to remove an item from your avatar. This is accomplished by creating a special selection mask where each pixel is an index mapping to 0-26 on the equip table above. This isn’t actually visible, it’s just an array sampled when player clicks on paper doll. Following is how the selection mask looks when rendered out to an image using grey values to represent indices. Each grey value maps to an item slot on paper doll.

 

 

AvatarAndMask

 

I’m finally nearing the end of initial item support in Daggerfall Unity. There is still much to do (loot tables, shops, dropping items, repairing, storing items, effects, and so on) but those problems can each be tackled in turn. What I want to do now is clean up some code and begin a new test release cycle. This will allow me to fix any early bugs before moving onto the next stage of item support. I will post more news on this soon.

Items Part 2 – Dyes

Before moving on to equipping items, I thought it would be fun to show off the equipment dye system in Daggerfall Unity.

Classic Daggerfall uses a 320*200 pixel 256-colour display – or more specifically a Mode 13h display. Back in this era, bitmap graphics were typically a width*height byte array of indices into a 256-colour RGB palette. One of the coolest tricks available to graphics programmers at the time was to change index ranges to substitute colours, change brightness, animate textures, and so on. Daggerfall uses index changes and palette swaps to accomplish all of these tricks and then some – it would be possible to write a series on that subject alone. This article is just about changing dyes to re-colour weapons, armour, clothing, and how the old index swaps can be realised in a true RGBA renderer like Unity.

If all of that is difficult to visualise, let’s start with an example. Here’s a pair of basic boots without any changes.

dyes1

Every pixel above is just a single byte index into a 256-colour palette. For example, index 0x70 points to RGB #DCDCDC in the default texture palette for a very light grey. For weapons and armour, the 16 indices 0x70 to 0x7F are reserved for index swaps (clothing reserves indices 0x60-0x6F). In the case of these boots every pixel falls between 0x70-0x7F, but that isn’t true of all items. Sometimes only a small part of the image will support dyes. If we just substitute every index between 0x70-0x7F to another random index between 0x00-0xFF we get the below.

dyes2

Quite the mess, but it demonstrates that changing indices can radically change the appearance of an indexed bitmap. The important thing to keep in mind is that every pixel is not by itself a colour. Rather its just an index pointing to a colour.

The first challenge in bringing indexed colours into Unity is that every time we read in a Daggerfall bitmap it must be converted to true 32-bit RGBA values where every pixel actually is a specific colour. Fortunately converting to 32-bit RGBA in Unity isn’t difficult. The general process is:

  1. Allocate a Color32 array with the same number of elements as width*height of source bitmap.
  2. For every pixel index in source bitmap, sample the RGB colour of that index to a Color32 value.
  3. Write colour sampled from palette into correct position in Color32 array.
  4. Create a new Texture2D of same width*height as source bitmap.
  5. Promote Color32 array to our Texture2D using SetPixels32() and Apply().
  6. Use this Texture2D as needed.

When it comes to changing the dyes, all that’s required is to substitute the correct indices in step 2 before sampling palette. So where do these colour swaps come from and how does Daggerfall know which swaps to use for what items? Daggerfall actually has a couple of different methods for generating swaps. Let’s start with weapons and armour.

Buried inside Daggerfall’s executable FALL.EXE at offset 0x1BD1E2 (for DaggerfallSetup version) are the metal swap tables. There is one 16-byte swap table per metal type. For example, when encountering index 0x70 for a Daedric pair of boots, replace 0x70 with swap index found at daedricSwapTable[0]. For index 0x71 replace with index found at daedricSwapTable[1]. And so on. These swaps have been known about for some time and you can find more details on this archived page from the wonderful old Svatopluk site.

Clothing does not appear to use pre-defined tables like metals. Rather, each swap table is just 16x sequential indices. For example, purple is 0x30-0x3F and green is 0xA0-0xAF. Swap tables can be generated on the fly using a dye enum mapped to starting index. Daggerfall appears to do this as these sequences are not found in the executable like metal swap tables.

Armed with the power to create textures and swap indices, we can now generate our final boots image based on metal type. here are some examples.

dyes3

Orcish

dyes4

Dwarven

dyes5

Daedric

 

One benefit of using the same generic process for metals and clothing is that it becomes possible to use clothing dyes on armour, something Daggerfall can probably do but doesn’t make available to players. This could allow for dye station mods down the road for players to further customise their equipment. With Unity using a true 32-bit palette this could extend well beyond Daggerfall’s 256-colours. Anyway, for an example of armour dyed something different:

dyes6

Blue Chain Boots

 

The next challenge now that we’re using true 32-bit textures is a red pair of boots becomes a completely different texture to a green pair of boots. Whereas in Daggerfall the same bitmap can be used both times by just changing indices as described above in the software blitting function. Between this and the inherent (but minor) performance impact of converting indexed bitmaps to Texture2D, we need some way of minimising CPU time and garbage creation. Caching to the rescue.

Daggerfall Tools for Unity (the underlying API suite) already uses texture caching for general world materials, but items have their own set of problems to solve. To this end, I created a new item helper class to serve up equipment icons and handle the caching based on properties unique to items.

Every time an equipment icon is requested, a unique 32-bit key is generated by packing that request’s variables into a bitfield. The packing looks like below.

dye-key-bitfield

  • Colour enum index refers to the swap table in use. This value matches Daggerfall’s own colour enum stored within base item templates.
  • Variant index is an alternate image for this item.
  • Archive index is the texture file number (e.g. TEXTURE.245) containing the icon.
  • Record index is the icon index within the texture archive.
  • Mask bit is used to enable/disable a special mask used to overwrite pixels like hair around helmets. More on this in a later post.
  • There are a few reserved bits to grow the key system later.

It’s worth pointing out the end programmer doesn’t need to worry about how these values are packed. This all happens automatically under the hood when calling GetItemImage(). What matters is the API has a way of uniquely identifying any individual equipment icon based on its display properties.

When calling GetItemImage() the API will first check cache to see if this exact icon has already been converted from Daggerfall’s native file formats. If not, it is converted and stored in the cache for the next time its needed.

To wrap things up, here’s a new gfy showing a variety of dyed items in the inventory UI.

For regular micro-updates on Daggerfall Unity, I can be found on Twitter @gav_clayton.

Items Part 1 – Bootstrapping

Loot. Kit. Swag. Treasure. Whatever you call it, items are an important part of any RPG game loop. They provide the means for your character to defeat ever more powerful foes and create incentive to keep playing in search of the next big upgrade. While Daggerfall’s items don’t quite tickle the reward centres of the brain like Diablo 3 or World of Warcraft, they’re still a vital part of the play experience. Without decent gear and enchantments, you’re unlikely to survive the grueling ordeal of Mantellan Crux.

In this series, I’ll describe the process of adding items to Daggerfall Unity. I wanted to approach items early on as they will be involved at almost every level of the game. Shops sell them, blacksmiths repair them, monsters drop them, quests reward them. Your character may have a special affinity for bladed weapons, or be forbidden the use of shields. Even the biography questions when building a character can grant you items like the near-essential Ebony Dagger. With items embedded in almost every major game system, the hardest part was working out where to begin.

I decided to start with existing items as part of importing classic Daggerfall saves then bootstrap the whole item back-end from there. That way I could be certain I was dealing with the most real-world data possible. Having built support for classic saves in 0.1, I could already identify item records parented to the main character record and visualise them with a custom Unity Editor script. They looked a bit like this at first:

 

Items1

It’s not much, but at least I could find item records belonging to the character. The “Container” record is just a generic parent record. In this context, think of it as the character’s backpack.

The next step was to break apart the item record format. Fortunately the UESP came to the rescue here with most of the bytes already solved, but far from the whole story as you’ll see once the names are revealed:

Items2

A Frosty what of Ice Storms? OK, so there’s more to this than just the save record. How to we go about filling in the blanks? The key here is the “category” 16-bit field in that UESP article. This is actually a pair of 8-bit values. The first byte is the item group, the second byte is a table lookup for the item template within that group. The template indexed by this lookup has all the missing pieces of information we need to complete our item data. Now we have two more problems to solve. Where are the templates, and how to use those category bytes to find them? Let’s start with the templates.

Item templates are actually built into FALL.EXE. The offset is a little different depending on your version, but the easy way to locate them is open a hex editor and search for “ruby”. You will find the following data:

Items3

Here are all the item templates laid out one after the other. They even follow a certain kind of logic, with gems, weapons, armor, etc. all more or less grouped together. Fortunately this isn’t exactly unknown data and the UESP came to the rescue again with a good starting point for these templates. I just had to fill in some blanks.

I didn’t want to keep this data in the .exe however, it’s much harder to modify these templates later. That’s why I exported the item templates to JSON format. Once exported the above data looks like this:

Items4
Much easier to work with. There are still a few unknowns to work out but those will be solved over time. The next problem was how to link up instantiated items like our Frosty %it of Ice Storms back to their original template. I had to reproduce the lookup table Daggerfall was using internally.

It was here Lypyl provided a helping hand thanks to his research into magical items and artifacts. The file format of MAGIC.DEF is very similar to instantiated items found in save games. Furthermore, the creators of old item editors had solved quite a few of these problems back then. Armed with all this, Lypyl could derive enough information to rebuild the group and item tables which he kindly provided to me in C# enums. All I had to do then was link the enums back to their template index in the above JSON file.

The main group enum looks like below. It corresponds to the first byte of the earlier category short.

Items5

For every element in the above enum (such as Armor, Weapons, etc.) there is an enum for every individual item in that group. For example:

Items6

For the item enum, the individual item value is an index back into the template table. The order within the enum corresponds to the second byte of the category short. With a helper class to bring all this together, it was now possible to perform lookups from instantiated items back to their template data. This is how our items viewer looks now:

Items7

Success! We can now resolve an item’s template by type to discover the full name and other useful information. The next step was to determine which items are equipped on the character. Fortunately the “equipped” table is just another record in your save game, and was already known about thanks to that first UESP article. I just had to work out how that table referenced items and I could isolate which were equipped. Items marked by an asterisk are equipped to character.

Items8

There are almost two dozen equipment slots in total that map to specific parts of the character’s body and elsewhere. I will describe this in more detail in a future article.

With all of that research out of the way, my next job was even less visual than above. I had to write support classes such as API helpers and an entity item collection class. I also required a new type of image reader to handle the job of loading and caching item images for the inventory UI, tinting them based on material, cutting out unique alpha indices like the hair mask, and so on. Anyway, boring or not these new classes form the foundation of items in Daggerfall Unity and will continue to grow as needed.

With everything finally in place, I could start building the equipment UI to sort, view, and equip items imported from classic Daggerfall save games. Besides a few UI enhancements and fixes, the following came together fairly quickly.

Some of the enhancements in this gfy include a scrollbar and mouse wheel scrolling. No reason we can’t have a few light modern touches to make our lives easier.

More About Scaling

One of the issues that caught me by surprise was a UI scaling problem. This turned out to be more interesting than expected, so I decided to write up a visual diary post about it.

For those who didn’t experience the problem, this is how it looked (1280×960).

ScaleBug1

What’s happening here isn’t technically a scaling problem, it’s a positioning problem. See, Daggerfall has a fixed-size UI of 320×200 pixels. My custom UI system was designed from the ground up to scale Daggerfall’s fixed UI to any resolution while maintaining correct aspect ratio. Depending on the width to height ratio of your resolution, the fixed UI may need to be pillarboxed (black bars down the sides) or letterboxed (black bars top and bottom). The goal is to fit the entire UI into the display without any clipped off edges and keeping that pixel-perfect ratio.

So what’s going in the screenshot above? The answer is that I forgot to turn on vertical alignment in the UI for the parent panel. This means the UI is stuck to the top of the screen instead of letterboxing like it’s supposed to. This is how the above display should look (1280×960).

ScaleBug2

The scaling and aspect ratio are correct in both cases, just the UI wasn’t centering vertically like it should for the letter-box effect at that resolution.

Unfortunately, it really isn’t possible to avoid pillarboxing or letterboxing with a fixed UI, unless you have a resolution that is an exact multiple of 320×200. For example, the screenshot below is a perfect x4 multiple of 320×200 and fits the frame completely at the correct aspect ratio (1280×800).

ScaleBug3

Now it occurs to me that some people simply don’t want letterboxing or pillarboxing. The best solution I can offer is a new option in the INI called “FreeScaling”. When this is enabled, the GUI will scale width and height independently. Here’s an example with FreeScaling enabled (1280×960).

ScaleBug4

The result is the UI is stretched as required to fill entire viewport. This obviously means the aspect ratio is no longer correct, but the chunky pixels still don’t look that bad with a little stretching. I’m willing to bet a lot of people actually play this way in DOSBox without noticing. It’s all down to personal preference anyway. If you want perfect aspect ratio, just leave things at default and the UI will scale and position itself properly now. If you definitely want to get rid of the black bars, then enable FreeScale and enjoy.

It’s also worth noting this does not apply to the game view rendering, which always fills the entire viewport. Only the classic 320×200 UI has this quirk.

I’m just happy my retro UI system is robust enough to handle all these different resolutions, scales, and positions while still working as it should. That’s an accomplishment by itself.