Identifying Buildings And NPCs

In my last post, I talked about the “Place” quest resource and merging map-level data down to block-level. The next step from here is to propagate this information to scene-level where the player ultimately lives. I decided to tackle this along with a start on Daggerfall’s interaction modes, i.e. Steal, Grab, Info, Talk which are by default bound to keys F1-F4. What I’m most interested in here is the ability to perform an info click directly on a building to discover its name.

First step was to quickly implement the mode switch itself. Key-kinds were already in place inside the InputManager class, all I needed were a few more lines of code to track which mode player was in and a new HUD label to present switch to user. After several minutes it was possible to flip between the 4 interaction modes.

 

Next, I needed a way of detecting when player clicks on a building. I already track player clicks in PlayerActivate class, and can detect clicks on static scenery and doors, but not on the building model itself. I go to work looking for an efficient way to manage this. Each Daggerfall model contains a radius value stating the overall size from its centre point. This seemed like a good place to start, so I overlay the radius as a sphere collider on test buildings.

 

Keep in mind that I’m not storing individual building models at scene level, the entire block of buildings above is combined into one large model. This is more efficient for rendering and results in fewer draw calls to the graphics card. So I don’t know which building player has clicked on – I just know they’ve clicked a combined block model and I need to resolve that back to a specific building. The sphere colliders would do the job, but they unfortunately suffer from a lot of overlap. Depending on where player is standing and where they clicked on the building, it’s possible for that target point to be inside two or three different building spheres. There are ways of handling this of course, but I decided to go with box colliders instead that will tightly wrap Daggerfall’s little box houses.

Before I can implement boxes, I had to go right back to the procedural mesh builders that extract data from ARCH3D.BSA (Daggerfall’s 3D model archive). During the vertex conversion process, I added some tracking for minimum and maximum vertex positions from origin to get the overall size of models in X, Y, Z space. Because the models are being constructed procedurally, and I have to process that information anyway, this step adds almost no overhead to the job of loading models at runtime. I now have what I need to construct a tight bounding box around any model effectively for free.

Then I just had to pass that information to scene builders. The end result looks like this.

 

Every building now has a nice crisp bounding box trigger collider. While this is great to visualise the bounds, I’m not happy with adding so many GameObjects to scene. A large city like Daggerfall will add around 800+ new collider GameObjects. If a few large cities are in the world at once, then it’s very possible that 2000-3000 colliders would be added to scene, the majority of which will never be used. Not ideal from an optimisation point of view.

To work around this, I used the same solution I came up with for doors. I store the box information for every building on the block GameObject itself using component DaggerfallStaticBuildings. This is just a small amount of raw data stored on each block. When the player clicks on a block in scene level, a single box trigger is instantiated and tested for each of the buildings in that block, usually no more than 5-14 buildings. The world-space point of impact for hit ray is tested against known buildings in that block (and only those buildings). If a hit point intersects with a known building trigger in world space, then everything we need to know about that building from scene layout time is returned to PlayerActivate.

The end result is zero new collider objects in the scene and only a small amount of overhead for storing building data and testing hits, which happens only when the player clicks on a city block. The net result has practically no performance impact and still fits nicely hand in glove with Unity’s physics setup. With all of that in place, player can finally make info clicks on buildings in scene.

While I was working on this, I decided to add shop quality text. When the player enters a shop in Daggerfall, the overall quality level is presented to player as a popup. Each shop has a quality value between 1 and 20 with a total of 5 different quality popups. I’ve long assumed it was just qualityValue/4 to get the popup, but testing proved otherwise. Daggerfall weights the quality text a bit more in the mid-range that the extreme low or high ends. After checking shops in Daggerfall city and Gothway Garden, I think I have the weightings worked out. Anyway, It’s something that can be easily tweaked later if needed. Now when player enters a shop, the quality text will popup like in classic.

 

Because the popup actually prevents player from entering building until they click a second time, I added a quick INI option to present quality text to HUD instead, with a configurable delay. With this option configured in INI (ShopQualityPresentation=1), you can enter every building with a single click and watch the quality text scroll off HUD. You can also set ShopQualityPresentation=2 just to turn off quality text completely.

 

While I was on a roll with the whole info setup, I made a start on identifying static NPCs. These are the flat people standing around inside buildings and interior environments like Daggerfall Castle. This will be critical to dialogue as part of questing system eventually, so might as well break some ground for later. The first part of this was simple, just detecting when player clicks on an NPC.

 

Yep, that’s an NPC alright. Exactly how an NPC is detected had to evolve a little over the process of getting this initial text in place. I previously did this by detecting if the billboard had a faction and a gender – something I assumed only NPC billboards would have. This turned out not to be the case and there are plenty of factionless NPCs standing around. Also, the NPCs in building interiors had a different metadata setup to NPCs in dungeons. Just like Daggerfall to use two different data structures for effectively similar things. I ultimately determined NPC status by the texture archive flat belonged to. There are a small range of NPC-specific texture archives and this served better than faction to determine if player has clicked an NPC or not. In the process of doing all this, I actually gained some better understanding of a particular bitfield and found a new gender bit assigned to NPC records.

Before I can identify an NPC properly, I need to use their faction information. An NPC with faction type=4 is an individual NPC which means their name comes directly from faction data. Other NPCs just get a random name generated based on their gender. So before diving any farther down this rabbit hole, I have to implement factions for the player.

I had written faction file reader around a year ago, but this just reads the initial database from FACTION.TXT in game data. In Daggerfall, this initial faction data is assigned to player character at time of creation and persists with player all through their adventuring career. Every interaction can raise or lower their standing with a particular group. To start tracking faction data properly, and to make this information available to NPC info clicks, I added the PersistentFactionData class to player entity. This class represents the player’s current standing with all factions and provides basic lookup functionality. This has already been wired up to save/load system, so when you save a game in future builds, your faction data will be saved as well. This is also an important milestone for the questing system.

With faction data on the player, we can identify individual NPCs like King Gothryd and Queen Aubk-i.

 

But it means that group-based NPCs don’t resolve properly by faction alone.

 

These NPCs need to have a random name based on gender. Thankfully I’ve already written the random name generators, as these were required for building names and elsewhere. The only thing I’m missing is the correct seed value to generate the exact NPC name that Daggerfall uses. For anyone unfamiliar with random generators, the same seed value will always output the same result. Unfortunately, I wasn’t able to find the seed value Daggerfall was using to name NPCs. You’d think this would be obvious like it was for buildings, but sadly not. I decided that one random name is probably as good as any other for these non-essential NPCs and just used their record offset as a seed value. This means they will always have the same persistent name generated each time, it just won’t be the same name as in classic. If the correct seed value is ever located, I can just feed this into the generator instead and the correct name will pop out. Until then, it probably doesn’t really matter. Say hello to random NPC Alabyval Coppersmith.

 

At the end of this little coding adventure, all of the following has fallen into place:

  • Change activation mode between Steal, Grab, Info, Talk.
  • Identify buildings and static NPCs.
  • Shop quality text is now displayed when entering a shop.
  • Faction data now exists on player entity and persists with your save games.
  • The foundation for checking NPCs in scene are ready for “Person” quest resource.
  • The raw data needed for “Place” quest resource now in scene.

With all that done, I can go back to working on “Place” resource and “pc at” condition for quest system. You can see what a rabbit-hole this whole quest setup is. It touches on so many different parts of gameplay that sometimes I need to go in a different direction for a while before I can loop back and progress on what I’m trying to build. But it all adds up, and every tiny step brings us closer to real gameplay.

For more frequent updates on Daggerfall Unity, follow me on Twitter @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. 🙂