New year, new Pterosaur!
Wait, no, is that how the saying goes?
Anyway, as the calendar year ticks up one and we all return from a well deserved Christmas break, we get right back to work on DInolords, and a bunch of cool stuff is going on right now.
In this monthly, we will have a look at some new 3D models and go on a bit of a technical journey into navmesh and the intricacies of making our own bespoke navmesh system for Dinolords.
Dinolords Unscaled 7
In case you didn't know or hadn't seen yet, we put a new episode of our behind-the-scenes video series up on Youtube you can watch it here!
We finally give a tiny tour of our new - slightly smaller but much newer - office and Michael talk about some of the new combat-units that have made it into the game as well as a little reflection on a year of development past.
Making the world 'lived in'
In Danish we say "Mange bække små gør en stor å", I guess the closest translation is "Little strokes fell great oaks", and making the world of Dinolords come alive and feel as it is actually lived in takes a bunch of effort. Loads of small touches ranging from making the layout of a level, placing just the right tree in a specific spot, to making and texturing the 3D models that can be found across the world make up a large bulk of work.
We want to start out by showcasing some of the things that might seem like small things in isolation, but in reality are key to making the world tangible.
Small cart in both a working and less-than-working condition.
One of these I'd be careful before using.
I wonder if this water is safe to drink?
A small boat that has clearly seen better days.
Models like the ones above really add a bunch of visually interesting elements to a level, but they also serve a more functional purpose. In a level that can be constantly changing with buildings being constructed or destroyed, trees getting cut down and walls be put up, having some sorts of 'landmarks' to help you navigate is critical so you don't have to consult the minimap every time you want to find your way back to a specific spot. It allows for much more fluid navigation of a level when you see something familiar and remember "Ah yeah, I had to go left at the old well", even if its subconscious.
Details and smaller objects like the ones above can also be thematic and help to convey a story, and for that we are going to need some Viking encampment gear:
Apart from the spear-rack, this looks cosy!
Having different 3D models, all carefully made by our 3D team, helps us create interesting encounters that feel much more real and like they are part of the world, as opposed to the crude gameplay-test setups I have been messing around with consisting of enemy units standing in the middle of nowhere just waiting for a Lord to run by to fight.
Navigating treacherous terrain
All right, this next bit might get a little technical, but it is a super important integral part of Dinolords, and we are very proud of it so it definitely deserves its own segment here. But before we dig in, there is a little preface with some terminology and a description of some technical functionality we have to get through first - just to make sure we are all on the same page.
All the units, including the Lord (aka Agents), need to be able to move around in a level in a meaningful way; this means being able to walk from point A to point B while avoiding obstacles like trees and rivers, but being able to cross bridges or climb towers or ladders on walls. To achieve this, it's most common to use something called a Navmesh.
A navmesh visualisation
Imagine a large, blue blanket spread out over the entire landscape, with holes cut in it wherever there is some sort of obstacle like a tree, a building, a river, a rock etc. This would be the visualisation of the underlying data that makes up the navmesh.
By absolute magic wizardry, some arcane incantations can then use complicated math to calculate a route between a point A and a point B, based on various parameters like the shortest in distance. This is called pathfinding.
Now I will pass the torch to Ulrik, our lead programmer, who will take us along a journey into the depths of navmesh generation:
"
After doing the prototype of the game using Unity’s built-in NavMesh system, and just kind of ignoring all the problems that came with it, we finally decided that it was time to build something real.
We had a few requirements for the system:
- We needed a triangle mesh, not a grid. There’s a lot of grid based games out there, and we want the freedom to place buildings at whatever rotation we want. Also, building castle walls in a grid-based system just makes your castle turn into a box, and we want the freedom to build great castles.
- It needed to be accurate. We want to have bridges for units to cross over, and castle gates to pass through. It couldn’t be an approximation.
- It needed to be fast to update. When we place down a wall, it needs to start blocking paths straight away.
- It needed to support a fair number of units pathing and avoiding each other at the same time.
- It needed to support big units, for obvious reasons.
- It needed to be ready for networking.
We had a decision to take, on wether to build this system ourselves, or find something off the shelf. Using something someone else has build is a way to get done faster, at the risk of it not fulfilling all our requirements in exactly the way we want it, and having to work around that. In the end, we decided to take the plunge, and build our own system.
And that’s what we now have a 1.0 version of in the game. All the navmesh generation, pathing and avoidance are now our own system that we control. The navmesh will look at the terrain and all the obstacles on it, and dynamically update only the parts of it that has changed. It’s very fast to update, and the results are perfectly accurate. It’s built entirely on DOTS ECS, and is Burst compiled and multithreaded.
The way there was not easy, and it took a bunch of research into triangulation, avoidance/pathfinding/path funneling algorithms, DOTS entities and multithreading, and while there’s still features to be done and places for optimization, all the hard work has turned into a very well running system. For the technically curious crowd, we use chunked, constrained Delaunay triangulation to build the navmesh, using rectangle and polygonized circle obstacles to cut out features. When a unit moves, it uses a raycast through the navmesh to detect line-of-sight to its target, and if no direct path can be taken, it does a triangulation pathfind, to find the route through the triangles to the destination, and then runs a funneling algorithm to find the final path. To move, it then combines the vector pointing to the next waypoint with the vector from the RVO2 unit avoidance implementation to get the final movement vector. When the navmesh changes, all affected paths are recalculated. There are more pieces, like avoidance obstacles and navmesh links, but going into detail would need a whole blog post in and of itself.
On of the more challenging parts of building a system like this is finding an optimal path between two points. This is something that is rather easy in a normal grid-based system (why do we make this so hard for ourselves), but in a triangle-based system, it’s not as straight forward. A lot of scientific papers was read, trying to get a fast, optimal path calculation, that is optimized for this kind of game, and we still have the occasional issue of units really wanting to take the long way around building. This is strangely reminiscent of older RTS’s like the Warcraft I and II, where unit pathing definitely still wasn’t a solved problem. The reality is that, while we’ve gotten much further since then, both in terms of algorithms and computing power, it’s still not a completely solved problem; there is not just that one solution that you just use. But really, the most complicated part is just putting all the pieces together in a way that works, and is performant.
There’s a lot of pieces that goes into getting a system like that to work, and each piece is like a whole project in and of itself. There are still a few pieces missing, like weighted paths, to make unit path around places that will slow them down, but the most important thing is that we now have a working system, that we can customize to our needs. If we want to do a special unit, that needs custom pathing or avoidance, we can just build that. We’re very excited about the possibilities this is going to give us.
"
Thank you Ulrik for the more in-depth explanation of how all this works, and super cool to hear some of the more nitty-gritty under the hood of how all this works.
Work in progress of the pathfinding and avoidance in the new navigation system
In-editor screenshot of how the raycasts spread from a unit to check whether or not it has line of sight with objects and units in the level
Raycasts used to check if a unit has direct line of sight
While there is still some ironing to be done to work out some of the quirks in the system, as seen in the gifs above we can now reliably ask large groups of units to move somewhere and more or less expect them to go where we ask them to. Sometimes a couple of them stray and find their own path, but we made sure they get reprimanded by the Lord and fall back in line soon (e.g. after a little more tweaking of some code).
We are all very excited about this. For such a core system of Dinolords to be working buttery smooth and being a lot nicer to interact with when designing levels, is making future work a lot more efficient.
TAGS - Tomorrow's Awesome Games Showcase at Copenhagen Gaming Week
If you happen to find yourself in Copenhagen on the 13th-15th of February, come say hi!
We will be showcasing a demo of Dinolords as part of the TAGS section of the exhibit.
There's also a bunch of other cool stuff to check out at the event, check the program and get tickets over at https://www.copenhagengamingweek.dk.
Hope to see some of you there.
Until Next Time
That was all for this edition of Dinolords Monthly.
As always, you can find us on Twitter and Youtube, or have a more informal chat with us over on Discord.
Catch you in the next one!
-panxter