Lots of further work on important NPCs (this “Important NPCs” series of blog posts is probably going to hit at least eight or so in total). The major developments this week: the game now assigns nearby home districts to each important NPC, and in turn an actual house when their district is actually spawned; the game now adds in naval trade routes and creates a range of maps for optimizing NPC pathfinding around the world; and NPCs now move around the world map and take an appropriate length of time to make moves! Read on:
Homes are Assigned
Homes are now assigned to all important NPCs, and each NPC has a “work” location and a “home” location (although special events, like a gladiator being pulled away from their training to fight in any one of many possible arenas, will add another “work” location). In some cases these are the same districts – so the guards who guard castles are also guards who live within castles, and their work and home districts are the same, and the same goes for every guard in a one-tile fortress, town, etc – whereas other guards will live elsewhere. There are no homes in a city centre, but the guards who guard the mints or parliaments have to live somewhere, and so they now live in other districts, where the district depends on the NPC (so the guards of mansions are better-off and live in middle-class districts, whilst the guards of arenas will live in lower-class districts, and so forth). When the player then enters a district with homes in for the first time, the game will look over which important NPCs are housed in that district, and will assign actual doors and houses to those NPCs, and ensure that random NPCs in crowds will never enter these houses. Here’s a little output noting which guard in a pairing each guard is (“first guard” or “second guard”, their form of guarding, where they begin the game (whether on duty, or not on duty), and then where they work and where they live; and you’ll notice a range of living districts for the mint guards.
Ocean Trade Routes
The game now generates ocean trade routes. All settlements except hunter-gatherer encampments which “touch” the coast now count as being a “dock” (even if these do not physically spawn yet, but will soon), and the game now has an algorithm for attempting to piece them together in a reasonably interesting, efficient, and wide-reaching way. The player will be able to jump onto these shipping routes, as will important NPCs who need to travel very long-distance (which will be rare, and mostly for mercenaries, soldiers, ambassadors, diplomats, plotters in various schemes, explorers, inquisitors, preachers, etc). I’m very happy with the kinds of shipping patterns this produces, and is something I’ve been meaning to add for a while, since it connects up parts of the map not ordinarily connected and thereby allows important NPCs to potentially travel to places they couldn’t travel to before (more on this below). These routes will show up on the world map once you find them, and when you consider boarding a ship in 0.9 (probably) onwards, you’ll be told where that lane stops, how long it will take you to each location, how safe from pirates etc each part of the route is, and so forth.
Road and Off-Road Pathfinding
When an NPC is looking for a path between settlements, the NPCs consider two possible routes – one using any tile they’re able to use, whether something fast like a road or something slow like an ordinary piece of terrain, and another using only “special” forms of travel, meaning roads, naval trade routes, and (in the future) desert caravans and mountain passes. Whichever one is faster (and safer) will be the one the NPC selects. So in this first picture, we see the terrain of a given world. In the second picture we see “all valid tiles”, and we can see that oceans are excluded aside from shipping routes, deserts are entirely excluded (since caravans do not yet exist), mountains are excluded (since mountain passes do not yet exist) and rivers are excluded, except on tiles where a road crosses them. In the third picture we see the final map which only uses roads and shipping routes, which might take longer paths to a given location but each particular tile will be faster – and so the game will check them both whenever an NPC wants to move. I debated going even further and weighting every single tile and using some kind of A* with Bounded Costs system, but a) that would be a surprising nightmare, b) it’s very CPU-intensive and this multi-settlement pathfinding has to be done effectively instantly, and c) I actually think this can have gameplay value: if you are told Person X is travelling to Y, you can be told if they’re travelling by road, or not, and can try to catch up with them that way, rather than knowing they’re going by the absolute optimal route, which might be very challenging for a human player to deduce.
A final interesting note: we can see in both of these pictures that the area in the northwest is cut off from the rest of the world. That area happens to have no towns which are on the coast and therefore have docks, and same goes for cities, and it is separated from the rest of the world by mountains and desert, and cannot therefore be accessed by land (unless the player is willing to move through desert or mountains without caravans/passes, which will cause each turn to take many many times longer than normal; NPCs will not have this option). Therefore a future (but probably quite simple) system will be required to floodfill the world and to ensure that every settlement, no matter how obscure and hard to reach, can always be reached via land, road, shipping route, caravan route, or mountain pass, or some combination – something this particular generation doesn’t achieve.
NPCs Moving Around the World Map
Although this is all snazzy and important, the most important thing by far is that all important NPCs now move around the map on their standard schedules. They will not yet appear and spawn if the player enters the same tile, and they are not yet able to be given one-off tasks (“Come together in Parliament for a vote”, “Go to this arena for a fight”, “Present your latest artistic work in front of the King”, etc), but they all correctly make their way around cities and towns, they perform their actions at the right times, they get up and go to sleep, change watches if they’re guards, tend to vegetable gardens if they’re monks, and so on and so on. Now, naturally making sure that the player can physically see this happening is the next step – and a big one – but at any moment in time I can now check what every single important NPC across the world is doing, or in the process of doing, and when they’re going to stop doing that and start doing something else. There isn’t really a nice picture I can put up for this, but it’s happening, and that’s crucial and very exciting.
The next two weekends are both free for me to focus entirely on coding (as well as ongoing evenings etc), so I’m hoping for a lot of progress. For next week I’ll be continuing to inch forwards on castle generation, hoping to get guards once more changing over their patrol timings with each other, and start to get all the important NPCs spawning when the player steps onto those tiles and being tracked whether abstract or spawned. That’s quite a lot, so we’ll see how it plays out, but I’m very pleased with my speed of development at the moment, particularly considering how many other professional (and personal) commitments I have at the moment. See you next week!