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.

Holiday Update!

I have posted a new video highlighting some features I have shown on Twitter (ready/use) and some I haven’t (ZStats).

The focus of the update is the following:

• Intro screen with FIRE animation
• Implemented “U”se interface
• Implemented “R”eady
  equipment interface
• Implemented “N”ew Order
• Implemented ZStats
  • Character Stats
  • Item Descriptions

There a number of work items that are far less visible as well. A lot of time has been spent learning the ins and outs of the Unity UI. I actually implemented the few new UI features with varying techniques depending on time of day, phase of moon and general mood 🙂

Also, I implemented the Ready/Use system first which emulates the original experience fairly close, focusing on keyboard input and a general text based interface. The ZStats was far more graphical and extended existing functionality.

I will undoubtedly spend the month wondering how or if I should re-implement the Ready/Use interface to match the aesthetic of the ZStats interface.

What’s Coming

Next up is a focus on more fundamental mechanics that actually make the game feel more polished and “more like a game”.

• Finish adding sprites and descriptions for
  remaining ZStat items
• NPC pathfinding and schedules
• Time of day/lighting change
• Save game progressions to disk
• time of day
• equipment/inventory changes
• (Maybe) some basic non-combat spells

Graphics – they're hard

With the completion of the “R”eady and “N”ew Order functions, I have opted to mix it up and move on to something quite different. I am actively working towards getting an intro screen up and running. The primary goals will be:

1. Show wicked blue/greeny Ultima logo
2. Show Warriors of Destiny animated fire logo
3. Provide load function – selecting from dynamic pick list of save directories

Other functions will follow eventually, but the biggest pain in the ass I currently suffer if manually changing my save game directory in code every time I want to test a new scenario (ie. new equipment load outs, different party members).

Progress thus far

I had in the past experimented and loosely integrated the Ultima 6 Decoder (http://nodling.nullneuron.net/ultima/code/ultima6/u6decode.zip). This uses an LZW algorithm to explode the *.16 files. The trick is then taking these exploded files and exporting them one more time – to a more commonly read format such as bitmap (.bmp).

When opening the create.16 file, I worked on spotting patterns and managed to spot what I incorrectly identified as fire.

To make sense of the specific format of the file, I looked back in time at the Ultima 4 ( http://wiki.ultimacodex.com/wiki/Ultima_IV_Internal_Formats#EGA_Files ) details. From there I created a basic program to read in and create a bitmap (https://github.com/bradhannah/Ultima5Redux/tree/master/Raw16ToBMP ). This is when i found out that my “flames” were actually the fortune teller.

Realizing I picked the wrong graphic I moved on to startsc.16.

So far so good. I have discovered a few things:

1. each pixel is encoded in 4 bit chunks
2. there are non-pixel bytes of varying sizes before each graphic which i haven’t been able to identify yet

This is what I’ve got so far – but my ultimate hope is to dynamically load the graphics at runtime from the original data files instead of exporting to BMP. I want to make sure that I am not peddling in copyrighted materials after-all 🙂

November 2019 Update Video

Novembers video includes some great updates. The project has really begun take shape and is actually starting to look like a game.

Note: All character data, inventory data and string data is gathered directly from actual Ultima save and data files

A few key changes/improvements in the November update

Visuals

• Shifted to a classic isometric angle
• Completed remaining sprite conversions to 3D model equivalents
• Upgraded lighting engine

HUD

• Implemented HUD with player characters, basic item quantities and current location (also added time into HUD!)
• Implemented new Location tracking in HUD

NPC Chat

• Reimplemented UI for NPC conversations with common look and feel

Signs

• Implemented signs (no runes yet!)

Inventory System

• Implemented basic inventory system

Basic Function

• K-limb fences and mountains
• O-pening doors
• J-immy’ing doors
• Space – pass time
• G-et torches from wall
• Porcullis drop at night

Next month brings on some new challenges I think. I will continue to work on equipping weapons and armour… you know honestly I’m not sure what else I will do – I just kind of work on the thing that most interests me that day or if I’m short on time, I just fix a bug and move on.

Signs Signs Everywhere are Signs

I haven’t found myself with much free time to work on my project in the last few weeks but I did manage to get some basic signs up and running.

It’s actually quite interesting the way that signs are stored. At least 2/3rds of them. There is a signs.dat file that contains the majority – however for some unknown reason I have unable to find a file with all the Eight Laws signs. As a result I have had to hard code them for now.

Also many signs use non english characters which I believe are indexes into a font file – but I haven’t got to the point where I can analyze them quite yet.

Lastly some signs are stuffed in the data.ovl file. I can only imagine why they needed to sink signs into any file other than signs.dat. I haven’t had to hardcode the sign text, but have had to hard code some file offsets which is a little gross, but I’ve done it before.

Thank goodness for the original rev-eng work here: http://wiki.ultimacodex.com/wiki/Ultima_V_Internal_Formats#SIGNS.DAT

Also I have begun to update some of the finer details in the wiki starting with Signs and NPCs.

Mind Mapping to Get Organized!

I often use Mind Maps at my day job to help organize my otherwise chaotic brain! I have begun to map out the entirety of what Ultima 5 boils down to in terms of function – then I overlay my personal plans for how I want to improve it. For example I have defined a number of custom UIs for functions such as buying/selling and a conversation log that you can actually refer to well after you had the conversation!

More than anything, it makes me realize how far I really have to go! But, it will serve as a de-facto project plan and feature list.

• 

October Update

Take a look at the latest video!!

Work continues slowly but surely on the project. A focus on improved visuals has gone well (but is far from complete).

Updates include:

• more 3D voxels replacing legacy sprites
• ambient lighting
• twilight lighting
• new daytime lighting
• basic NPC dialog

For the Unity nerds out there – I have switched from built-in renderer, to light weight render pipeline (LWRP) and finally to high definition render pipeline (HDRP). This has been a really neat experience and continues to strengthen the visual quality.

Next up I expect to:

• Complete all “standard” NPC schedules and textures
• Actually open a door!
• Start creating a permanent UI

The cat’s out of the bag

Well I have been developing since the beginning of July and quietly uploading to GitHub. I decided to actually tell/show people what I have been up to.

You can read some interesting Q&A on Reddit here: https://www.reddit.com/r/Ultima/comments/d2z1iu/ultima5redux_a_very_very_early_preview_i_have/

Or you can just watch the development update video here:

There will be more to come but this seems to be a good start.

Fresh Screengrabs and NPC chatting

I have been making some progress including:

Continued effort to Voxalize everything. It is worth noting after a rather mean message I saw on a forum – these initial Voxel models are pretty simple rips of the original, I hope to go from a 16x16x16 to a 32x32x32 in the future with greater detail. I’m a coder, not an artist, so I am trying not to sink too much time into the fine details yet.

I spent quite a bit of time optimizing lighting, shadows and anti-aliasing. It looks quite a bit better but I am realizing that I have to make a major shift if I want to “hide” parts of the world or town/village etc that the Avatar can’t see in the original game.

I spent quite a bit of time months ago putting together the basic NPC dialog code with simple text windows. I have since created a basic conversation UI. It’s ugly, and unpolished – but it works, at least for every example I’ve tested thus far.

Less noticeable but pretty cool (I think!) is some optimizations I did for string lookups. To restate, it is my intention to use the original string databases instead of transcribing them whenever possible. I do this, not because it’s required – but more so I can say that I literally used every bit of the original as I could to recreate the original experience.

I also added the look feature (L). It’s rough, but works on basic map elements.

That’s it for now! I will be working on doors, optimizing framerate (major problem!) and lighting/hiding as I go forward in the near future.

The world!

Starting to get more and more voxels created.

Very basic and unpolished chat interface.

Just another day of development.

Night, Textures and Logging

This latest update is relatively light.

• Improved lighting (long way to go!)
• Testing night mode lighting with blue twilight
• Added exit dialog when leaving a town with keyboard or mouse input
• Added output box in bottom left, similar to Ultima 5 output space
• Added more voxel models including some stone walls and block walls

Next up will be….

• More voxel models
• NPCs in world
• Conversation with NPCs

Iolo’s hut