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.
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!
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.
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.