Important NPCs Part II

Some Updates

A couple things before we get started this week. You can now watch my talk from the UK IRDC 2015 on URR’s general generation systems. Check them out! Also, I’ll be at this year’s ProcJam opening talks (though not speaking this time) down in London, so you should all come and say hello, both to me and other excellent PCG folk speaking. Hopefully see you there! And if not, I recommend taking part in ProcJam – a lot of awesome stuff came out of it last year and I’m sure the same will be the case this year. Also, as mentioned previously, I’ve now started a job as a three-year research fellow; currently I’m therefore working on URR at weekends and in the evenings. Progress is speeding up again now, but it’ll inevitably be a little slower than it had been pre-move. As such, I’m now seriously once more considering releasing NPCs without the conversation mechanics as 0.8… but I might not. Basically, I’m going to finish NPCs, and then take stock; but that possibility is still on the table. I don’t want people waiting ages, and I do obviously want the NPCs to be tested, but at the same time I promised gameplay and the conversation system is going to be in-depth and exciting, so I want to offer that, even if that means a longer time between releases. We’ll see.

Now, onto this week’s update, where I am pleased to report that development has now resumed after around a fortnight of moving house and starting-new-job admin, and we have some initial progress in the handling of the game’s important NPCs. So, read on…

Placing and Counting NPCs

When a world is generated there is now a block of code which looks over each tile, examines what is in the tile and the ideologies of its owning nation, religion, and all this kind of data, and comes to a conclusion about how many guards there should be, what kinds of guards these are (Mansion, Parliament, Castle, etc), where they should rest (in that same tile, as in a Fortress, or in another city district), and so forth. It does the same for all other important NPCs, and then counts up the total. Here’s a map I had the game print out where each tile was coloured according to how many important NPCs it had. A black/grey tile had none, and then the colours/numbers went through the rainbow to denote numbers of guards from 1 to 10 – dark red, red, red/orange, orange, orange/yellow, yellow, yellow/green, green, light blue, mid blue. If there are 10 or more, it uses a ‘+’ symbol. One can see roughly where all the major cities are, and get some impression of where fortresses are, and for the time being nothing spawns in towns which would “merit” a guard (though this will probably change) and so those don’t show up (same goes for tribal encampments, though I might add guards to certain buildings there in the future). I think it’s quite interesting to note how different cities have different textures of how important NPCs are laid out, depending on their ideologies and so forth. Note also that some of the fortresses have different numbers, again according to their layouts/ideologies. Anyway, here’s an example of this map:


And some zoomed-in examples of cities with very different “important NPC textures”, where in most cases the +s are indicative of things like city centers and upper-class districts and military districts, whilst the common 1/2/3/s tend to be lower-class districts where the national ideologies vary what spawns and doesn’t spawn there:


As for these important NPCs: they are stored in two areas – if it is an important NPC who will never ever leave the tile they are currently on, it saves them in the potential_npcs list on that map tile; if it is an important NPC who will be moving around the world, it saves them in the potential_npcs list in the world overall; this separation is to avoid a situation where even NPCs who never leave their map grid were in the global set of abstracted-out NPCs, there would be no point scheduling them and going over their routines/actions, since those can just be modeled when the player goes near. At this point it also (though this is not fully implemented yet) creates a bunch of tags for each important NPC. This might be something mundane and overt like “Guards the mansion of Family X”, or something covert like “Intends to murder NPC X in a plot with [list of other NPCs]”, or “Once met a mercenary who knew where [secret item X] was buried”, or whatever, which one might be able to discover. This brings us back to the previous discussion a while ago of secrets NPCs hold: a jail might have 50 prisoners, most of whom might be mundane, but a few will hold secrets which might be of use to you in some way.


Spawning Important Folks

Until the player goes near to any of the important NPCs, they remain “abstract”. They are able to act and gain connections by possessing the list of “npc_info” stuff listed above (who they plan to usurp, their other secret agendas, etc), and this also means that a spawned NPC can talk about an unspawned NPC without that NPC having to be spawned, which means that all the important NPC information is set up before the spawning of any of those NPCs. When the physical version is spawned because the player has stepped onto their map tile (or they are a roving important NPC and they have just moved into the player’s map tile), the game looks for the “npc_info” which describes an NPC of that sort and then tethers that npc_info to the physical copy of that NPC and deletes the abstract copy. That then doesn’t change the abilities of other NPCs to reference the important NPC, but it just means they now reference the physical copy rather than the abstract copy, but either way the game knows the information relevant to that NPC, and that NPC can move around the map (whether “physical” or “abstract”).


Reworking Guards

When I worked on guards in the past few weeks, I hadn’t fulled realized that guards were, basically, an “important” NPC, and therefore would actually need to be tracked to their homes and the rest of their schedules just like all the others. This means I’ve had to undo a little bit of the code I wrote before for tracking guard pairings and so forth, but this didn’t actually take as long as I’d feared. Guards now still spawn correctly and match up with their “abstract” selves, but no longer exchange their positions, as that requires me to transform some abstract guards into real ones at appropriate moments, and then get them matching up whether or not all, some, or none of them are spawned – the next step is therefore to get them (and everything else) performing according to their schedules, which is the objective for the coming week.


Next Week

Important (and unimportant) NPCs remain permanently/temporarily spawned when they cross districts, so you can follow them; guards can exchange their patrols with one another at the correct times; TIME (regular) and SCHEDULE (unique) events work, or at least have begun to be implemented. See you then for more work on the important NPCs of URR!

Important NPCs Part I

I’ve planned out how important NPCs are going to be handled, and starting tomorrow (Monday) I’ll be working on this. If all goes well… I would expect this to take a week to get all the basics going, but then some of the activities for more complex NPCs (so rulers have to find their way back to their bedrooms in castles, for instance) might take a little longer. I know I rarely write technical entries, but here’s a rare semi-technical entry about how exactly I’m designing the NPC system. Enjoy!

1) The game looks over the entire world and identifies every location where a guard should appear. This means it counts up the number of guard-worthy buildings in each city centre (mints, parliaments, etc), in upper-class districts (currently always three major families, but I do intend to change that in the near future), and stores each guard in a list. It then also looks for an appropriate place for that guard to live – if we’re in a fortress, the guard will be stored in the same map grid (i.e. the fortress) and if we’re in a city the guard will almost certainly live in a nearby lower/middle-class district. Either way, it also stores where these guards should spawn. For non-guards the game assess how many other important people should be appearing on each tile based on the ideologies/religions/etc of each area (so we’ll have ambassadors, blacksmiths, chieftains, doctors, executioners, gladiators, inquisitors, judges, monarchs, lords, ministers, officers, other nobles, regents, abbots, archivists and mercenaries). For now they cannot spawn in the middle of what I’m calling a SCHEDULE event (see below) as this would quickly increase the complexity, but I don’t think this will be an issue, since the world will be vast enough that 99.9% of important NPCs will have begun doing things by the time you ever get to see them.

2) There is now a new dictionary called abstract_creatures, who are the important creatures (I assume only people, but I’ve named it “creatures” in case there are… I don’t know, noteworthy mounts or something later?), which all of these people are put into. For each guard it places a guard in their guarding area, a guard in the district/place they would live, and then has them both schedule a time at which they cross over. For everyone else it just places them in an appropriate starting location. Whenever one of these people takes a turn, it’ll look into this list (instead of the grid-specific lists) to get the person – and as for when it does this, we then look at the kinds of event I’m creating for these abstracted-out people.

3) The game then generates two kinds of “event” for the schedules of these guards, and for all important NPCs – what I’m calling “TIME events” and “SCHEDULE” events. TIME events are those which happen at the same *time* every day – get up, go and guard the thing, stop guarding the thing once the other guard appears, return home, etc. For those in governments it’ll involve going to the appropriate buildings, for rulers it means holding councils, for gladiators going to the arena and fighting and hopefully-not-dying, etc. Then they will sometimes gain SCHEDULE events, which are one-off occurrences: talk to this diplomat, check this town out for heresy, meet secretly at this location on this date, etc. The game will track whether an important NPC is going a TIME or SCHEDULE event, and if a SCHEDULE event, it will ignore all TIME events until there are no more SCHEDULE events to complete, at which point the NPC will look at the next TIME event it would normally have, do that, and from that point onwards behave within its normal list of TIME events.

4) The NPCs use the time “quantum scheduling” system previously described, and when they are heading towards a target in a grid which has not yet been spawned, they assume the highest possible time it would take them to reach it were it spawned – so if there’s a building that could spawn anywhere, we assume it takes 200 ticks to reach it (all grids are 200×200) – if it could only spawn in the left-most side of that grid and the NPC will be approaching from the left, we assume it will take 100 ticks to reach it, etc. After the grid is spawned, the game will actually create a list of all possible timings from each gate leading into that grid to each important location on that grid; this can never be exhaustive for non-city areas or for houses (as there are simply too many), but for NPCs moving to important doors (of which there might be a dozen) from one of four city gates, one can readily see it’s the work of a moment to have the same calculate those and store them for future use after the player leaves that grid and the grid becomes abstracted once more.

5) What then happens if the player steps onto a grid with these abstract people, or leaves a grid on which there exist people who need to be abstracted? Well, this (obviously) is the tricky part, and something I know Dwarf Fortress found challenging to program, and now I’m at this point myself I see why. If you step on and there are abstract NPCs, it will have them “rewind” to the start of their most recent action, generate/reload the map, and then have them play out that action physically. This will mean creating quite a static list of “Actions” and “What This Looks Like On A Spawned Map”, but that shouldn’t be a problem (creating rigid lists is often much simpler, if more time-consuming, than writing PCG!). When the player then leaves, the game will then track how far through their latest action each NPC was, and schedule their next action for either the standard time (if a long way off) or the shortest possible length of time it would take that NPC to start doing that action when moving on the spawned map… and then save the map and do everything else as normal.

6) This means – I think – that NPCs will never wind up doing anything faster than they possibly could if they were “walking it” on an actually present map, but they will sometimes do things slower, but this is simply unavoidable without spawning every single grid at the start of the game (in this regard this is vaguely akin to a Traveling Salesman problem where the travel-length value at each vertex is unknown and/or changeable based on the actions of an external actor). This means that whether or not a particular area has yet been spawned or not, the player will be able to track with great accuracy the movements of important NPCs, and guards will change their shifts irrespective of player actions, and so forth.

I’ll be starting coding this tomorrow. I’ll start with guards since I already have most of their code, and then once I’ve checked that I’ve got them going from their guarding place to their homes and vice versa at appropriate times, and changing over their watches, I’ll move onto the more complicated important NPCs who move between more districts, might move between cities, etc, and we’ll see how it goes. An update on important NPC progress will therefore be next week’s blog post – see you all then!

Farewell, O Encyclopedia

Normal service will be resuming next week: I’ve moved house, settled in, and started planning out the final push on NPCs, which is to say tracking all the important NPCs as they move around the map – a process which has required me to do a lot of thinking about how to code it before actually getting started (this will turn into what it is effectively a Travelling Salesman problem where the time values at certain points are unknown, which I’ll write about here in the next few weeks). Anyway, here’s a post I wrote a little while ago with some of my thoughts on the future of the Encyclopedia; next week we’ll have an URRpdate as usual.


I’ve decided to remove the Encyclopedia from URR because I increasingly feel/fear it is going to end up doing the player’s “job” for them, and because my original conception of how the Encyclopedia is/was going to work is clearly going to be a programming nightmare.

Let me explain my logic. Right now, the Encyclopedia gives the player a full overview of everything in the world, though that’s only because the game is obviously not replete with gameplay as of yet. The intention was to – either this version, or more likely the version afterwards – fundamentally change the Encyclopedia so that it only starts off with information about your nation, religion, culture, histories, etc, whilst the others remain unknown. Then, each time you uncover a little nugget of information on your quest, the Encyclopedia would update itself. So when you first discovered the name of a nation, it would add in an entry for that nation, but all the information about that nation would be displayed as “????”s (or maybe just blank regions where text could be inserted) until you found those out, and then it would be added. Equally, were you to discover some piece of information that was meaningful, but you didn’t know which nation/religion/whatever it was associated with, there would perhaps be another list of entries in the Encyclopedia without names, noting that *some nation* somewhere has a given flag, but you don’t know which nation. When the player then encountered irrefutable evidence that Flag X belonged to Nation Y, the Encyclopedia would then “conflate” these two entries into a single entry, associating Flag X with Nation Y for ever more.


However, as in the first paragraph of this entry, I increasingly realize that there are some pretty major issue with this type of system. Firstly… surely this is doing the player’s job for them? Surely if the focus of the game is uncovering these cultures and how they interact and searching for the items you seek in the maze of heresies and histories and all the rest of it… surely we should be leaving these connections to the player, and getting the player to come to recognize the nations and cultures they encounter? I fear now that codifying this type of information in the Encyclopedia will run into several major issues. Firstly, it’ll “force” the player (or at least behaviourally strongly encourage) into constantly opening the Encyclopedia to check things, rather than remembering “ah yes, this is Nation X, I encountered some of their emissaries before”. Secondly, the player might not actually notice a useful bit of information, but if the Encyclopedia then updates, it tells the player that piece of information is useful! It seems to me this second one presents a major issue. Thirdly, there’s a question of what information the Encyclopedia should show. To stick with the nation example, should it show the national flag? The national dress? The national style of shoe? What vases in that nation look like? There has to be a line drawn somewhere, because if you want the Encyclopedia to potentially list everything about a given nation, you risk basically reproducing everything about that nation and leaving nothing in the actual game.

So, those are the gameplay issues. There is also a programming issue, which is that I increasingly realize this type of tracking – and perhaps most imporantly, getting the game to notice when a useful piece of information has been “seen” and then updating the appropriate Encyclopedia page – is (or would have been) a horrifying nightmare. This is a secondly concern to the gameplay, of course – if I still thought this was a good method I would certainly have done it – but it still matters somewhat.


What’s the alternative? Well, I think I’ll keep the Encyclopedia in for 0.8 and probably 0.9. Whilst the world is “open”, I think it only enhances the game to be able to see everything at the start and give new players some impression of the size/scale/scope/variation of the planet and the variation of its cultures. However, a little further down the line – shall we say 0.10? – I’m now 99% sure that I’m going to remove it permanently, and rely two things. Firstly, the player’s ability to become familiar with the interconnected world they find themselves in; and secondly, crucially, an alternative to the Encyclopedia (maybe a “Journal” or something of that sort) which records every piece of information the player character sees/hears/experiences, but not the significance of it. With this model you can once more view/read everything of note you have ever looked at/seen, but it doesn’t tell you *what does/doesn’t matter.* So once you’ve read a book, you can forever “look up” the information in that book (so it basically as if the player character has an eidetic memory). Therefore, this will be a replacement Encyclopedia where you browse “books”, “clothes”, “paintings”, and the like, but you do not browse information about “nations”, “religions”, “cultures”, since that’s what you’re piecing together. Equally, I’ll also work on a system whereby the player can “tag” certain items in their viewed history as things they think are relating to a particular riddle, and then browse according to tags and assess the data they have and what else might fit into that category.

Therefore: the Encyclopedia will survive 0.8 and 0.9, and then be replaced by this new version which records player character experience but leaves understanding up to the player – which is surely the whole point of the idea of the game and the riddle(s) hidden across the world’s cultures! For now, however, the Encyclopedia will remain to assist players as we go through the worldbuilding -> gameplay transition in looking around the world, getting some grasp on its detail/complexity, etc. See you all next week for the resumption of normal service!

Disguises and Lies

I’ve just finished reading Q, a novel by the Italian literary collective Luther Blissett (that actually being the name of a footballer, a name they deemed to be inherently comic), which I absolutely loved. I recommend that everyone interested in URR give it a look since it looks at a lot of themes similar to those I’m trying to convey in the game, and so I will avoid spoilers, but there is one crucial point here (and that is mentioned in the book’s blurb, so it’s not a spoiler) – the narrator adopts a wide range of names and identities throughout the book. The book – set during the Reformation – emphasizes, albeit implicitly, the impossibility of ever being truly secure in knowledge of someone’s identity in an era where transport is limited, countries appear “massive” without aircraft and trains and cars to traverse them, and for all except the highest-ranking members of society there are no clear records kept on who is who, who lives where, and who is from where. Reading the book managed to segue quite nicely into some thinking I’ve been doing myself recently, but the book made this all the more certain in my head: URR has got to have a disguise mechanic.


Of course, we can still have a layer where the player can “earn” permissions to certain areas via transparent means. By which I mean – bribe someone to give you documentation to access Place X, or earn the loyalty of a religion so they’ll let you into Place Y, and so on – but surely we could take full advantage of the detail of the world’s faces/clothes/cultures/social norms/etc by implementing a disguise mechanic. I think this would have several components:

  • Appearance: add items for the temporary dyeing of hair and lightening/darkening of skin tone and temporary facial tattoos, and allow for adjusting hairstyle. Other NPCs will, in part, judge whether you are part of their nation based on how your face/hair look.
  • Clothing: the player adopting certain items of clothing lends other NPCs to assuming the player belongs to certain categories. This would be both clothing, but also things like rings, necklaces, types of armour worn, weapons sheathed, etc.
  • Speech: this is a really interesting one, and I suppose ties back into the ongoing question of “how is the conversation system going to work?”. It would be amazing if there could be some kind of system where the player can try to “fake” the forms of speech expected in that nation/culture/religion, and the better they can do this, the less suspicion they fall under. Perhaps the player can offer special greetings once the player has heard them once (“Greetings of the Divine King of the Snow!”) or generic greetings if not (“Greetings”), and the more “generic” comments the player makes, the more suspicious NPCs become, but the more the player knows what needs saying, the more they’ll fit in. Equally, once one becomes used to how people of a certain nation speak, perhaps one can select what “style” of speech to speak in a given conversation? That could be so interesting (in my current ongoing drafting of how conversations are going to work, I’m working on trying to define methods for generating different styles of speech).

So once you adopt the first two – dye your skin, and find the right clothes – you’ll be able to walk around in most nations undetected. But if you want to talk to anyone there, you’ll need to mirror their patterns of speech – and, equally, perhaps a particularly isolationist nation has a lot of guards on every major trade route, and you’ll be challenged by them even if you look like you belong to that nation? I think there are so many interesting potential gameplay experiences here: to some cultures your character presents themselves as they “truly” are, in other nations you entirely try to fake it, and maybe in other nations you play it by ear? This seems like another mechanic which would really take advantage of the detail in the world if we can make NPCs very observant about when something seems to be “off” when looking at/talking to the player.

Whether this will be 0.8 or 0.9 remains contingent on precisely how large 0.8 ends up being – is it just NPCs, or is it conversation as well? – but this is definitely going to turn up very soon, though it might be in a different release to conversation per se. If anyone has any other ideas for some more details on this mechanic, or perhaps how it could work in other contexts, or other parameters we could civilizations vary by: let me know!

Not Quite The Shortest Update Ever, But Not Far Off

Just a very short one this week I’m afraid folks, with a few updates:

Employment and House Moving

So, on October 1st, I’m starting a new job! I’m going to be a postdoctoral fellow in game studies at the University of York (where I did my doctorate) for up to three years as part of this massive thing. This is the same project that Michael Cook of ProcJam fame is now part of (also as a postdoc, though in his case in Falmouth) so hopefully some awesome things will come out of that collaboration (we already have one intriguing idea vaguely in the works). Of course, moving back to York necessitates house moving, which is going to be taking up a lot of my time for the next couple of weeks – updates will still be every weekend, but I might upload some of my pre-written general games discussion/criticism/design ones rather than URRpdates for the next week or two. We’ll see how time pans out.

Houses and NPCs

I’ve been reconsidering how difficult it would be to assign NPCs like guards to specific houses in specific districts this release, and I actually don’t think it would be that tricky and shouldn’t be more than a couple of days of work… so I’ll probably do that. I have this week finished off everything to do with guards (though clearly some of it will need changing if I do indeed implement this kind of “real scheduling” for this release) and done some general bugfixing, minor improvements to the quantum scheduling system for moving around the map, etc etc. All timings are now correct, and the system will be readily transferable to important AIs whose actions around the map also need to be timed and tracked.

Roguelike Radio

I assume everyone knows this by now, but I’ve recently become the co-host of Roguelike Radio! The most recent episode (the Q&A) is a particularly good one, I think, and we have a great discussion between just myself and Darren about “information” in roguelikes coming up. Check it out here.

Next up?

Next up is still, as I’ve been saying for a little while now, day/night scheduling, shops closing up, things like that. At that point, however, it becomes apparent that we need to get people going back to their homes, which brings us back to the guards point, so actually for the next few weeks I’m going to work on some lesser things whilst I’m moving house (like improving how aristo families are generated, bug-fixing a bunch of left-overs from previous releases, more clothing generators, a few alterations I want to make to city generation, etc), and then once I’m settled back in York at the end of this month and can really focus again on a larger project, I’ll push on with a concerted effort to the final part of NPC handling, which is giving all NPCs who matter homes, and tracking them and their behaviour wherever they are in the world. Whew. See you next week!

In the mean time, a smaller and general reminder: if you ever want to keep track of URR elsewhere beyond this blog, I must humbly recommend my Twitter feed, the URR Facebook page, or IndieDB – the former particularly is full of screenshots which generally get posted before the weekly update!