In the last 2 weeks i’ve been pushing for big optimizations.
First of all, i spent about a week on pathfinding ( pathfinding is the system used to allow things like units to move in a map and find their ways ).
The previous system was too slow to find paths on complex region grids.
I’ve first learned about an algorithm called ” Jump search algorithm ” that is incredibly faster than the basic one is was using, especially to find paths on grids with lots of open spaces.
Considering there was little complete doc or tutorials about this except the actual original academic paper , it took me a while to really understand it as it was written in a quite opaque way ( at least to me ).
But there was a downside, as this algorithm only works for grids that have 2 values: empty tiles and blocked tiles.
This is not the case in Ymir where i need each tile to have different costs. As an exemple, roads are tiles that “cost” less than regular terrain so that if there is a road available, the units will tend to walk through these instead of regular terrain, as a unit will always try to find the path with lowest cost.
So i then had to actually modify this JPS algorithm to work with this type of grids and values. Its not perfect but its now incredibly more fast than my previous system and it should now be enough for the release standard i’m aiming, andenough to allow the more complex battles with walls.
This is to give you an idea ( and as its pretty much the only visual thing i have to show ).
Below is one of the exercises i made to test the pathfinding.
The left one is the pathfinding result and the right one represents the terrain where lowest costs are light green and highest one is purple.
Starting from left blue point, the objective is to reach the other blue point on the right.
The light green line would be a road. In the middle you have a vertical river with shallows in dark green in the north and a bridge in the south. On the left is a vertical cliff that the road crosses where its less sharp, and some buildings. On the right, there’s a ‘fort’ with walls in purple and a few buildings in it. The road goes through gates that are weaker than the plain walls. There’s a second wall south, and it has a weak point in green.
On the left you have the resulting path : the troop would reach the road going left, then follow it, cross the river south , follow the road to the gate and then go to the wall’s weak point. They then breach it and attack the left gate to enter the fort and reach the objective.
If there was no weak point , the would choose to cross the river north through the shallows and attack the northern gate. If there was no bridge and no shallows, they would have to cross the river itself.
No matter what , the path cannot fail and will always find a solution that will define the best available strategy, even if it means crossing river with small rafts, climbing cliffs with ladders or breaching walls.
However it can still be improved as its doing mistakes here : its doing 2 weird diagonal movements instead of going straight after the wall weak point, and it should stop following the road and go directly to that weak point instead of going up to the gate on the right and then back.
The time to generate a procedural region has been divided by 2 ( From about 8 sec to 4 sec ).
Its still not enough though for the release standard : because this has to be done by the server during the game whenever a player goes to a new region for the first time, it has to be really efficient so it doesnt make the server “hang” as it’s constantly busy doing all the other things of the game. So it has to happen while allowing the server to keep doing all its other tasks. The problem is not really the total amount of time it takes to make the region, but how its splitted : the server does it little by little so it can keep doing other things instead of just doing only this for seconds. So each little step has to be really short in itself, and that can be quite complicated to do. This is what’s been improved as well , though it might not be enough and will require more work.
FPS OPTIMIZATIONS WITH SHADERS
Using shaders i’ve made 2 big optimizations to improve framerate in regions. Animated grass and trees is now done by shaders, and the static grass drawn on top of the terrain cubes as well. Bottom line, the result is that regions have had their FPS greatly increased and also their loading time reduced. Its now satisfying enough for the release standard ( at least empty regions ).