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!