In the last 2 weeks i’ve been pushing for big optimizations.
PATHFINDING
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.
REGION GENERATION
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 ).
Well this pathfinding is already affecting civilians.
All units are pathfinding with the same centralized system.
Special routine mouvements for civilians would be great indeed, but its a substential amount of work.
I don’t know when i’ll get the time to do this for now 🙁
As for sharing the pathfinding algorythm and mecanics, it’s something that would be quite time consuming for me to do and to follow up considering its all linked to many other things in the game, but thanks for proposing ^^
Great work, these new shaders bring a very nice visual effect (the sea on your screenshot looks perfect and must appear even better with animation). If shaders also optimize the FPS and loading times, the result is doubly positive!
Regarding pathfinding, will it be only applied to military troops or do you plan to give similar patterns to civilians as well? Some farmers could go in the fields to harvest the crops for example. Miners could get around the ore blocks to use their pickaxes. Fisherpigs could sail towards schooling fish to throw their nets… All these routine movements would add plenty of “life”.
Adapting the path of armies in the middle of the battle to react to deathtraps … that’s some great idea. If you can someday pull it of … Okay, I’m not sure it would be really useful in Ymir, and it’s assurely not a priority. But the concept seem exciting.
hum interesting,
I would love to take a look at the pathfinding algorithm ! for two reasons : maybe be able to help solve the problems you have, and also just try to understand it, as I love IA and want to improve my knowladge about it !
but hey, awesome to see what you did !
AI and pathfinding is a pretty complex thing ^^ . Yes i remember this in AoE.
What i assume was happening is that I think its because AoE used binary values of blocked and unblocked. It would pathfind a first time considering walls as blocked, and if failed it would pathfind ignoring walls and therefore trying to attack and breach them. Binary values on a grid make pathfinding way simplier and faster, which was probably necessary on that time.
But that meant that as soon as there was one entry, they would always try to get to it no matter what, even if it meant going through a stupid maze instead of breaching walls. Well unless they had siege in that case i think they ignored walls directly.
However in the case of variable costs for tiles like here, the maze problem wouldnt work for ever, because at some point the cost of going through the maze would be superior to breaching one wall and they wouldnt use it. Now that depends of the wall’s strenght of course, considering walls will be really resistent, if there’s an opening its still better. The other good thing is how you can modify the costs dynamically, so that if an army has lots of siege equipement, you can reduce the cost of walls and makes the decision to breach one more likely opposed to walking a way to avoid it.
Also another way to make AI aware that a path leads to certain death is to gradually modify something called the path heuristics , increasing it where units die so they then tend to choose another path. Globally you’d use this to influence the path, like increasing it near ennemy towers, known troops , ect. You could also do that by modifying the tile’s movement cost itself, so far i don’t know what’s best.
But it would be too long to go into details about that. I’ll probably have to do such thing when working on the battle’s IAs.
News !!
The current state of the pathfinding make me think to Age of Empire. The computer tend to follow a maze even if it mean getting killed easily as long as there is a hole to get inside the base. So to avoid a single wall to destroy, the ai would run a lot and attack where the player wanted them to attack.
On the other hand, higher levels of ai had siege weapons, which attacked walls, and theses made mazes useless.
One game in the campaign, I spend a lot of time making a long, long maze, with castles and lot of woodenwalls. Then the computer came with Siege Rams, attacked my walls … and dealed aoe damages to the walls. Two hits, a big hole in the maze. I felt pretty stupid. ^^
Anyway, what I was saying ? Oh, I remember : That I love hearing about pathfinding. I found it fun and interesting.
Always great to have news. Looking forward for the next one.