Contraction Hierarchy

The first significant thing I've worked on since the last New Dawn update is something boring and technical called "Contraction Hierarchy", yet a highly important system required to improve battles.

It's a pathfinding algorithm which pretty much consists of precalculating all possible paths between all tiles on a map, so that you can then instantly know the cost and path between 2 points without having to calculate it again.
This is the kind of algorithm your GPS uses to instantly find the path between two points through the road network.

Why is this thing so important in Ymir?
During a battle, calculating the path between 2 points isn't just for the movement of troops themselves, it is also used by the AI to decide which enemy and objective to target. This means every troop needs to check the cost to reach EVERY single potential enemy or objective.
Calculating the full path for this is therefore impossible, as it would be far too slow.

So before, I would divide the map into areas of enclosed space, and then estimate the cost of navigating between these areas based on the cost of the cheapest "walls" separating them.
But this created all sorts of problems and gave very approximate results.
Not only that, but because in New Dawn terrain elevations are no longer tile-edge "walls" but slopes, it meant this old inaccurate solution would become even worse if left unchanged.

This is where Contraction Hierarchy comes in: by baking all paths at the start of the battle, it means I no longer need the old approximate solution. Now when the AI needs to know "how much would it cost for these warriors to reach the archers over there", it can retrieve a fairly accurate answer almost immediately, and that's a big deal for battles.

The problem: building a contraction hierarchy for 300×300 tiles is VERY slow. We're talking hours-slow with the default algorithm implementation.
And because maps are not static, this has to be computed in real time right as the battle starts.

So finding a way to get this thing to build in less than 10 seconds was quite challenging for me.
After many optimizations and finding shortcuts, I managed to do it. It's not perfect, it doesn't give completely accurate best-path results, and it will probably have bugs and issues to fix, but I managed to get it to build in under 10 seconds, which was the key here.


I've also added to the "movement cost" display layer the ability to test and display paths, which will give you as a player an idea of what the default path between 2 points in your fortifications would be, helping you design and test your defenses.

Particle emitters

One big remaining thing to implement in my custom 3d engine was particle emitters, used for VFXs like blood, or mostly smoke, dust and fire effects.

I've implemented a fully GPU sided system of particles, meaning the calculations of each particle movement is done in the GPU instead of the CPU, making it much more optimized.

Then i implemented particle emitters into my ingame asset editor, allowing me (and in the future hopefully potential moders) to easily design VFXs by combining various emitters, seeing the effects of tweaking its various controls in realtime.

Then i also implemented in my assets system and in my in-game editor the ability to call an asset inside another asset...
This means the VFX I've designed (for example here a fire effect combining 3 emitters) can be saved as an asset first, and then be used in the building assets as a reference.
If i update my fire asset, it will automatically be updated in all the buildings using it, making things much easier to maintain and organize in the long run.
And this system is not specific to emitters.

Battle FXs

Thanks to the completed system of emitters and sub-assets, I was then able to complete all the effects required in battles: missiles such as arrows, smoke effects, fires, explosions and wall breaches, and blood.

Buildings destruction are back ingame, with fire followed by collapse and rubble.

Now rubble also spawns debris decals surrounding the rubble, making destroyed buildings more integrated into their surroundings.

Troops in melee also now spawn dust, and blood splatters when dying.

Battle fortifications

Battle fortification mechanics are working again, including breaching gates and simple walls, climbing with ladders, or embarking in rafts to cross water.

Breaching now looks better, with impact and breaching FXs projecting rubble on the ground.

Troops will now visually embark one by one into rafts, giving a visual feedback to the slow progression of embarking into the rafts.

Preliminary work for ships

With the re implementation of rafts needed for battles, i chose to do it in a way that also laid groundwork for future implementation of Ships, making the raft a basic boat.

For this i added a system where rafts are called as an asset made in my ingame editor, and added the ability to place "unit spots" into assets.
A boat asset will therefore be an asset that contains coordinates for units to be used for its passengers.

I've also made 2 other small primitive boat models, to be used in the future for fishing buildings and such.

Had fun in the asset editor creating this small scene, completely useless!

Mounted archers

I've finally implemented a missing battle behavior for units like mounted archers, which was never properly completed in Legacy: the ability for units to move & fire.

Mounted archers also have this specificity that even when the troop is standing "still" , its units will seek to remain in movement going in circles (which is what makes them more resilient to enemy ranged attacks). This range resistance was present in legacy, but not visually represented: you'd see the mounted archers standing still in formation while firing.

Mounted Elephants

Another special battle behavior that was never properly implemented in Legacy is now completed for new Dawn: mounted Elephants.
Just like mounted archers, Elephants (the ones with archers on top) now have the ability to fire & move. But with subtle differences in behavior as Elephants will also actively engage in melee, making range attacks a secondary "opportunity" attack.
Elephants also required unit stats to become fully separated between melee and ranged, as they are in this case very different.

Future new unit types...

Thanks to the implementation of these new special behaviors, it laid the groundwork required to implement a long time missing category of military units: chariots.
I will also be able to give opportunity range attacks to some other units, like how the Porcus could mimic roman soliders throwing Pilums once before charging into melee.

Alpha completed

An with this, the "alpha" stage of New Dawn is completed (at last!).
It means all the big technical unknowns are 'solved' as my new 3d engine now has all its core features implemented and the game's adaptation to it is finished.

What remains now is adding actual graphical content (buildings mostly, which is a LOT of work), working on polishing, optimization, debugging, and user experience.

Porcopedia

Which brings me to the next big chapter: I really want to invest time into improving the accessibility of the game for new players: tutorial, in-game help, and making things more intuitive.

For this I've started implementing a fully ingame Porcopedia!
It procedurally navigates the game's database allowing players to see all building types, units, policies, knowledges, resource types, terrain tiles, terrain objects and more.

I hope it will be worth the work it requires, making it much easier for new players to understand the game's complex mechanics without requiring outside help, which has always been a big factor putting people off from Ymir.

I've kept the UI hopefully simple and intuitive, with main sections in the left, and a column with a search bar & listed items.
It includes an historic for easier navigation (so you can easily check a link and then come back to your previous page).
Content pages themselves are kept light in text, with many buttons linking to their respective pages so that players can easily understand how things are connected.

Beyond content pages, I will also try to add more text-heavy pages to explain game concepts and mechanics and a starting guide, aimed more at new players to learn the game.

Supporting New Dawn