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!

Be Sociable, Share!

14 thoughts on “Important NPCs Part I

  1. Hey,
    I was wondering, one of the most interesting things, for me at least, was oral legends and stuff like that. It’d be cool if in cities and villages people would tell legends and rumours of creatures and you as a person could check them out. I don’t me the introduction of said beasts but rather the fear thereof. I know it’d be hard to program but would be really cool and also add another layer of depth.

    • I know there’s a theory that cyclops myths came from how mammoth skulls would have appeared to early Greeks, with them guessing that the nasal cavity was a giant, single eye socket. And iirc there’s an idea that stereotypical norse Dwarves (shorter stature, advanced metallurgical knowledge) came from contact between northern Europeans and travellers from southern/eastern Europe.

      If there were tales of fabulous creatures in URR, it would be cool if they were distortions of real historical phenomena in the game world.

      • How very interesting on both counts. I love reading about these origins of myths and stories and how they spiraled out of control from the original “material” – but yeah, as with my other reply below here, that’s exactly my thinking. Some myths will be completely wild and ungrounded in reality, of course, but some are definitely going to play upon the real generated world.

    • Oh, absolutely. Each nation is going to have its own pantheon of mythical beasts which appear in its legends, and my intention in man cases is to link this to the real creatures in each nation; so a place which is very mountainous and has some large rare cats in the jungle, say, might produce a myth about these giant legendary cats with mystical powers of some description… (and I don’t think it’ll be that hard to code at all!)

      • Will you be able to disguise yourself as these mythical beasts to take advantage of cultures?

        Also, I like the idea of beasts being correlated with local animals, but I hope that isn’t their only possible “origin.”

        • Heh – very neat idea, but I suspect that would stretch credibility. But… you’ve put the idea in my head, so I’ll definitely ponder it.

          Oh yeah, some will come from elsewhere and some will be very “far out”.

  2. Are you sure that picking the worst-case is the best choice? I know you want to guarantee a sense of absolute consistency that way (no “cheating” NPC’s), but perhaps it could be more plausible if you use a certain percentage (i.e. 85%) of the worst case?

    • I see your point, and perhaps with time and playtesting and so forth I’ll change it, but worst-case is the “safest” choice since it is guaranteed to NEVER be quicker than possible, so it’s definitely the right one to begin with. We’ll see though!

  3. I quite like technical entries even if I don”t understand half of what is actually explained ^^ It looks really challenging to code, this maybe one of the most difficult things to do in a gigantic game like yours that aim to be vivid and deep.

    • Yeah, this is rapidly becoming the most challenging thing I’ve coded so far… but I’ve made a good start on it in the past few days, and I’m confident a decent portion of it will be done by next week’s update!

Leave a Reply

Your email address will not be published. Required fields are marked *