NPC AI and Pathfinding
As you may be aware since my late December update I have been focused on making the NPCs more mobile. I had been dreading the work because I feared (and was correct!) that it would be disruptive and force me to refactor my code in a big way.
At it’s most basic, every NPC has a schedule which basically has four main components:
- What time should I move to a new position?
- What X,Y coordinate should I be homed at?
- Which Floor should I homed at?
- When I get there, how should I act?
So we have interesting questions to answer like, if they aren’t on the right floor, then which ladder or staircase do they use? What do you do if two NPCs are battling for a single tile? Mix all that in with the memory and CPU constrained implementations developed by the original developers and you have a bit of a mess.
We also had the problem of reading in save game information that states where an NPC is presently and if they already had a path planned. If they did then we need to read it in and follow the original plan. One of my main goals was to have as close to 100% compatibility with the original save state as possible. To the point – ideally – where you could bounce between the original and Redux freely. That may be a pipe dream, but it is still my intention. Following this principal will also ease playtesting because I will be able to do like for like playtesting.
Code Improvements
To accommodate the additional logic and to make my life much easier I spent the better part of the month implementing a new concept called the Virtual Map (https://github.com/bradhannah/Ultima5Redux/blob/master/Ultima5Redux/Maps/VirtualMap.cs) It essentially pulls in all factors that could or would affect the map such as NPCs (dead or alive!?), open doors, keys in trees etc and give the program a single source of truth.
Secondly I fleshed out another concept called the World (https://github.com/bradhannah/Ultima5Redux/blob/master/Ultima5Redux/World.cs). As you may be aware – the project is broken into two parts; the core library Ultima5Redux and the 3D game component written for Unity called Ultima5Redux3D. The creation of the World object actually moves nearly all game logic into the core library, meaning that anyone in the future could “easily” plugin the core library and build on top of it with all the benefits of state management, world interactions, and even automated AI (crude) handling. It may seem a bit of a bore, but this was a massive shift for the project which ultimately is meant as an asset for the amazing Ultima Dragons community.
Another problem I had to solve was pathfinding. I have cringed at the thought of implementing my own pathfinding (bad college experience!). I knew everyone used the A* algorithm, so I went searching for a solution that was already baked and free OSS. I found https://github.com/davecusatis/A-Star-Sharp which is a wonderful and very C# native implementation. A small bug fix later, and the new Virtual Map function and I was up and running.
Lastly, voxels are 3D objects, and with that come with quite an expense. I managed to get around to something that has been on my list for the last 6 months. A simple voxel caching system was implemented which saved the unnecessary loading and destruction of voxels as the Avatar moved around the world and cities. It uses only basic constructs like Dictionaries and Queues to save an reuse tiles whenever possible. It more than double the framerate during my testing. As you can tell below, it had some hiccups!
Debug Console
I struggled with another issue – the debugger and debug console have become increasingly sluggish as I moved more and more into the core library. Secondly, it was very disruptive to continually break and inspect so I added a debug console which can be toggled as needed. As a bonus for any C# nerds, it is connected to the Debug/Trace handlers so all System.Diagnostic.Debug.WriteLine outputs automatically stream to it.
What’s Next?
The next month will be spent paying down some technical debt that I have accumulated as well as perhaps some core updates.
- Tidy up and debug small bugs with pathfinding and scheduling
- Improved lighting transitions from day to night to day
- Save some state to disk such as player position and movement directions
- Populate remaining item descriptions for ZStats
- Continued play testing of the original game to refamiliarize myself with the finer details (F* this game is hard)
Maybe more – but given how slow it felt like I moved last month, I will hold it there.
Ultima 5 Redux Development Blog 
That is a heavy duty sounding update. Is pathfinding working then? Or still being detailed/fleshed out? Have you started reading the schedules from the original files? Just curious.
LikeLike
Pathfinding is indeed working 🙂 They tend to take the shortest path instead of the likely path (ie. using grass instead of paths) which i intend to address, but they always get from A to B and work around each other in the process.
I read the schedules in and they adhear closely to them – going up or downstairs when it makes sense to do so as well. I even read in any paths that have already been computed by the original game because… why not!? Mark from Nox Archiast was mentioning using weights, and I am considering that to help the NPCs to make more realistic decisions when travelling.
I have the basic wander AI completed, and obviously fixed positions, but there are some odd ones to sort out including a merchant AI that is a bit inconsistent. I also have the “runaway”, “follow” and “attack” AIs to do, but have written basic steps that won’t be hard to assemble.
LikeLike
Wow, exciting stuff. I played some U5 over the past few months and remember the NPCs being quite precise in their use of paths and walkways. Rarely taking shortcuts, staying right dead center in the middle of the road, etc. I don’t envy the task, but making it line up right could be enjoyable.
I wonder if the temptation to ‘improve’ upon the ai might appear.
I also suppose your Virtual Map could be used to add weight or preference to paths, etc.
LikeLike
I actually managed to add the weighting to the pathing based on this feedback and they now generally preferring the walkways, I even managed to give even more preference to centre tiles which is pretty cool 🙂
It is tedious but I am enjoying the optimizing and am currently writing unit tests to run simulations on every single map to confirm they all work at the at least a basic level.
LikeLike
Hi, this is interesting to me as I have been working on an Ultima-esque game myself and was trying to study the way the NPCs behaved in Ultima V. As far as I could tell, they were on hard-coded paths when going from one location to another, and were put on some kind of a random walk at their destinations when awake. Is this your understanding as well, or was there more active pathfinding logic in place even back in 1988?
In an ideal world, if I can get it working, I would like to have A*-derived dynamic (or at least quasi dynamic) pathfinding for my NPCs, if that doesn’t eat up too much horsepower, but for the moment I have been working with a compromise system where the NPCs are on hardcoded paths to their various locations, random-walk when at those locations, and at scheduled times do a very brief breadth-first-search pathfind to a specific tile from which they then go on their next hardcoded path. (My random walk currently is a very simple unweighted four-way randomizer, relying mainly on the walls of the rooms to keep NPCs from straying too far.) As towns get more crowded and crossing-paths becomes an issue this might not be viable, unless I just let NPCs walk through each other…
a
I am also not quite clear how U5 handles multiple floors — I tried following NPCs directly as they went up ladders and didn’t see them ahead upon arriving at the new floor, so I assumed they were spawned at pre-determined locations. This gave me an opportunity to try to ‘one up’ Ultima 5 with NPCs that can be followed tile-for-tile as they path between town floors. (Still buggy, but coming along…)
Love the look of this game, looking forward to more updates. 🙂
LikeLike
Sounds like you are where I was not too long ago. Let me first say that everything I built, I built from the amazing work of others documented here: http://wiki.ultimacodex.com/wiki/Ultima_V_Internal_Formats#CASTLE.NPC. This data file does not provide paths, only coordinates and schedules. As far as I can tell, U5 employs an A* algorithm, but when you think of the endless obstacles and unwalkable tiles, you will find that there aren’t too many paths too compute.
For A* I started with 5 year C# implementation and forked it here: https://github.com/bradhannah/A-Star-Sharp. I fixed a few bugs and added a weighting system to allow preferred routes which I use to prefer dirt paths, walk ways, or even the centre of a path when wider than 2 tiles. It is relatively quick, but I have a backlog item to get back into it and chose more optimal data structures. Problem being is that I only understand it as far as I needed to understand it, so optimizing will requiring some focus.
I do a similar thing when it comes to collisions. I reviewed the code fro the XU4 project for pointers as well. Basically if two NPCs get in each others way, then they have a % chance of trying to move a different and random direction – but not always. It creates a neat effect similar to the original game. I have considered adding a “swap” mechanic, much like real like where they would switch positions if they are in each others way.
Another optimization is minimizing the number of times to calculate a path. When an NPC sets their sites on a new location (because of AI behaviour or schedule) then they calculate their entire path and follow it blindly until they get to where they are going or someone gets in there way. For my implementation you can review the MoveNPCs and CalculateNextPath method here (https://github.com/bradhannah/Ultima5Redux/blob/master/Ultima5Redux/Maps/VirtualMap.cs).
As for the NPCs going up and down floors – the strange behaviour you are seeing is simple teleportation. When they move up to another floor, they automatically teleport to their scheduled location. Not super exciting, but I suspect the original version only loaded a single floor at a time (as does mine!).
Lastly, I can’t confirm because I haven’t added any of my own NPCs (although I think @cambragol wants to!). I believe the developers were careful and deliberate with the number of NPCs, their schedules and locations in order to avoid potential deadlocks which are possible even in the existing game. The “swapping” mechanic would help get around this little gotcha though.
Thanks for the interest, and I am going to take a look at your blog – looks like some great stuff!
LikeLike
Thanks for those resources!
My solution to track NPCs more precisely as they move between floors is to create a ‘ghost pather’ object that invisibly continues the NPC’s schedule when it’s on a different floor. The ghost-pather’s info can then be passed to a new, corresponding NPC object when the player switches floors. I guess another way would be to just set the NPC invisible/intangible when it is on another floor, although that causes problems for me because of the object-parentage of which objects are ‘obstructions’ and which aren’t.
Anyway, it’s easier to come up with weird solutions when you don’t have the tremendous limitations on memory and CPU power that Garriott and co. had to deal with in the ’80s. Also, I spent many, many hours playing U5 over the years and I don’t think I ever once noticed that the NPCs can’t be followed tile-for-tile between floors. It was only when I deliberately tried to understand how the pathing works that I noticed it.
LikeLiked by 1 person