King Arthur II - Behind the Scenes: Soldier pathfinding
Behind the Scenes: Soldier pathfinding in King Arthur II
Author: György Flórea, Senior Programmer at NeocoreGames
During the development of
King Arthur II my most important task was – apart from small things like coding the quest editor, participating in the basic code, solving the problems that came up during pathfinding, etc. – to create the battle system and the pathfinding for the soldiers and the “control” of the animations as well.
Fortunately our bosses here at NeocoreGames granted me even more freedom then they normally do. Check out the instructions I’ve got:
• the soldiers mustn’t walk through each other
• each soldier should avoid smaller obstacles
• the soldiers should be able to fight among obstacles
• units have to act like groups (they must keep the formation until they can and don’t wander away etc.)
• the engine must handle more soldiers than the previous one (which is about 4,000 soldiers)
• and yeah the whole thing has to look fabulous! =)
Not too strict, right? =) Later when I spent a lot of time with this job and we began to see what the new engine can do, the designers had lots of ideas and suggestions and yes, expectations too, but they trusted me with the details and let me work so I could cross out the items from the list with good results (okay, the last one is very subjective…) So it was like a dream come true for a game programmer: you have a creative job and no one’s bugging you with all those impossible ideas! =)
The biggest problem was the huge number of soldiers on the field. I knew that we can’t do individual pathfinding on such scale. But this messed up my plans! (See the first 3 conditions on the list?). The solution? Two words: mass simulation! The algorithms for mass simulations are not used for following strict orders or battles or soldiers working together as a unit, so I had to come up with some ideas on my own. But it was a start. Finally I chose to program the units to “forcefield following” (aka "flow field following") behaviour, which means that the soldiers follow a pre-determined path to avoid the obstacles.
The idea felt good, because it always looks nice when the individual soldiers move smoothly among the obstacles, and (it’s the most important part) it doesn’t require that much computing power. But it wasn’t so easy. The soldiers shouldn’t walk in a single line, they shouldn’t rush over each other and they shouldn’t push the others away. And while they are following the path they should be able to obey new orders, move to new destinations and of course fight when they are attacked. So this forced path is only a guideline for the soldiers and they have to interpret the changes in the given circumstances as quickly as possible. It doesn’t sound too difficult but it was tough, because I had to design scenarios that covered all the possible situations. Only to mention a few:
• When the soldiers follow the forcefield, when and how hard can they push each other?
• Should the individual soldier follow the direction of the forcefield only when he’s moving forward or can he move backwards too?
• Does the path have an effect on the actual speed and direction of the soldier and if so, to what extent?
• When could the individual soldier ignore the forcefield following?
• What shall we do with the soldiers who bump into obstacles even if they are on the determined path?
• (And so much more!)
Okay, finally I solved all these problems, but there was still one left because I had to pre-generate these forcefields. We couldn’t just draw these fixed pathways by hand around the obstacles on each battlemap (not to mention that there are obstacles that appear and disappear during the battles). And the requirements of the forcefield generation were:
• The path shouldn’t lead the soldiers into dead ends or too tight passages.
• The path should be smooth, without sharp turns.
In order to do this, I made a quick excursion into another field of programming and I used various image processing methods.
It sounds nice and easy, but it took more than a couple of days. And I wasn’t even close to get near the battle system, but that’s a story for another day… Until then you all take care, try to avoid drinking crazy stuff like Whiskey Coke, only drink whiskey mixed with apple juice 'cause Coke is bad for your teeth, and Ryan Giggs is the king of kings, right? =)
Check out the pictures about the forcefield and the soldier pathfinding:
Read the Article on the NeocoreGames DevBlog:
http://devblog.neocoregames.com/blo...scenes-soldier-pathfinding-in-king-arthur-ii/
Visit the DevBlog:
http://devblog.neocoregames.com/
See the gallery:
http://devblog.neocoregames.com/gallery/
King Arthur Facebook:
http://www.facebook.com/KingArthurGame
King Arthur Twitter:
http://twitter.com/KingArthurGame
King Arthur Webpage:
http://www.kingarthurthewargame.com/
NeocoreGames Facebook:
http://www.facebook.com/NeocoreGames
NeocoreGames Twitter:
http://twitter.com/NeocoreGames
NeocoreGames Webpage:
http://www.neocoregames.com/