Pathfinding – The All Consuming Chore

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.

4 thoughts on “Pathfinding – The All Consuming Chore

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

    Like

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

    Like

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

    Like

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

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: