How is pathfinding implemented in Bannerlord?

[NamingIsHard]

Just curious. When talking about pathfinding,especially for siege battle, the developers usually talk about setting path for each individual scene. But refer to what I have learnt, there are many pathfinding algorithm exist, which means this is not supposed to be a problem require manual adjustment by developers.
Edited: Ok so I know TW may be using Navigation mesh approaches for pathfinding, but still I don't understand how can this be troublesome and labor intense, any explanation?
Edited: Changed title, looks like the original title:"how does pathfinding work in Bannerlord" is misleading some people to talk about whether pathfinding in the current version of Bannerlord performs good or bad

 

[Marajah]

The thing is pure algorithm path finding would eat up any CPU, so sieges were unplayable in early versions, before some manual adjustments, because we got 2 fps.

 

[NamingIsHard]

The thing is pure algorithm path finding would eat up any CPU, so sieges were unplayable in early versions, before some manual adjustments, because we got 2 fps.

It depends on how the problem is modeled.(fk I really don't want to talk about modelling, failed my algo course once because of this) As I know most pathfinding algorithms model this problem as graph, and finding shortest path through verticles. If you model each coordinate point on map as a individual verticles, and compute for each individual character on map independently, surely CPU boom. But this problem does not have to be modeled that way.
Instead, you can model the map into sub-areas, each sub-areas as a verticles; and compute path for a soildiers at squad level instead of individual level, this will significantly reduce runtime complexity.
And the sub-area model approach lead to another way of design: neither developer nor the computer is responsible for figuring out the path, letting the player do that as a commander. The developler/computer only need to do what they are doing in field battle(sorry I'm not sure if this is the correct wording, just those battles fight outside settlement scenes, battles besides siege battles)

 

[black_bulldog]

Poorly...

 

[RecursiveHarmony]

I think these games uses "navigation meshes" (or at least for warband)

 

[Will Greaves]

Poorly...

Haha I came to this thread to write this exact reply, but you beat me to it.
: D

 

[stevehoos]

Poorly...

? haha.... yep.

 

[Marajah]

It depends on how the problem is modeled.(fk I really don't want to talk about modelling, failed my algo course once because of this) As I know most pathfinding algorithms model this problem as graph, and finding shortest path through verticles. If you model each coordinate point on map as a individual verticles, and compute for each individual character on map independently, surely CPU boom. But this problem does not have to be modeled that way.
Instead, you can model the map into sub-areas, each sub-areas as a verticles; and compute path for a soildiers at squad level instead of individual level, this will significantly reduce runtime complexity.
And the sub-area model approach lead to another way of design: neither developer nor the computer is responsible for figuring out the path, letting the player do that as a commander. The developler/computer only need to do what they are doing in field battle(sorry I'm not sure if this is the correct wording, just those battles fight outside settlement scenes, battles besides siege battles)

This was enlightening. I don't know anything about programming. I just know what it was like when the game just came out, so I made the assumption they had to do the manual pathfinding to improve performance to playable levels.

 

[guiskj]

It depends on how the problem is modeled.(fk I really don't want to talk about modelling, failed my algo course once because of this) As I know most pathfinding algorithms model this problem as graph, and finding shortest path through verticles. If you model each coordinate point on map as a individual verticles, and compute for each individual character on map independently, surely CPU boom. But this problem does not have to be modeled that way.
Instead, you can model the map into sub-areas, each sub-areas as a verticles; and compute path for a soildiers at squad level instead of individual level, this will significantly reduce runtime complexity.
And the sub-area model approach lead to another way of design: neither developer nor the computer is responsible for figuring out the path, letting the player do that as a commander. The developler/computer only need to do what they are doing in field battle(sorry I'm not sure if this is the correct wording, just those battles fight outside settlement scenes, battles besides siege battles)

I think this is the direction they went, which is why now we get units that are completely oblivious to the character. Like the clump of units by the gate, or reinforcements running to a point even though the player is freely slashing at them...

 

[AndrewArt]

it doesn't

 

[NamingIsHard]

I think these games uses "navigation meshes" (or at least for warband)

I have tried to read something about this approach, look like similar to what was described above, but just don't understand how can it be labour-intense in Bannerlord, do you have any idea?

 

[NamingIsHard]

it doesn't

Sorry but I'm confused about what you mean.

I think this is the direction they went, which is why now we get units that are completely oblivious to the character. Like the clump of units by the gate, or reinforcements running to a point even though the player is freely slashing at them...

You can check 'Navigation mesh' approach described above, guess TW need to work more on AI behaviour within a navmesh.

 

[RecursiveHarmony]

I have tried to read something about this approach, look like similar to what was described above, but just don't understand how can it be labour-intense in Bannerlord, do you have any idea?

I remember reading some guy having problem with units acting weird in sieges and some other guy said something about fixing these kind of meshes in this forum. I've also seen a simple zombie game in unity uses these for ai movement. These were a long time ago. When i saw your thread, i remembered these and googled "pathfinding mesh" and learned these are called "navigation meshes". It was just an educated guess.

In warband, units just run through a straight line to the target and if they run across an obstacle,they seem to just change the direction a little bit so they walk around it. They get stuck behind obstacles too many times. If you watch this unity tutorial, you can see it acts like warband. Objects hit the walls and change direction, and doesn't seem to follow the shortest route possible.

I haven't bought the Bannerlord yet. I played two Dead Island games and Dying Light made by Techland. When i modded those games, i've seen that these games have similar file formats like almost 90%. I assume something similar is also true for old engine Mount & Blade games and Bannerlord. It probably uses an enhanced version of old pathfinding algorithms. Considering Warband has a 150 unit cap which results in 63 vs 63 battles and Bannerlord promises for more crowded battlefields they may have dumbed down the algorithm to gain some performance.

 

[Kentucky 『 ＨＥＩＧＵＩ 』 James]

Considering Warband has a 150 unit cap which results in 63 vs 63 battles

It doesn't, you can comfortably go way higher. The bottleneck in warband isn't pathfinding, it's combat and collision, as well as some of the really badly written morale scripts.

 

[Revverie]

It works?

 

[RecursiveHarmony]

It doesn't, you can comfortably go way higher. The bottleneck in warband isn't pathfinding, it's combat and collision, as well as some of the really badly written morale scripts.

I assume you base this on general modding, programming and game development knowledge as you didn't mention why did you get that idea. I'd like to say a couple things.
I don't mean that pathfinding algorithm is the most resource eating thing. It could have a small effect on performance and there might be more downgrades. I also don't think downgrading pathfinding algorithm must be only motivated by performance concerns. Think about Cyberpunk 2077, players say ai controlled cars can't drive around you when you stand in front of them. Developers may have no time to spare or the current state of code might not allow easy addition of such system. Lots of different possibilities.
I know the Battle Size Changer and you can go higher caps with better hardware but we should consider minimum and optimal system requirements. Developers test their games and set some limitations to provide decent gameplay for people having at least those level of hardware. I think battle size limit is one of those limitations.
We should also think about how its coded or can be coded. I've written a simple empty loop in c# loops to a billion. It runs in 1.7 seconds. Bannerlord probably trillions of calculations per second but people can play it with high fps. Its related to code running on CPU or GPU and working on single thread or multiple threads (parallel processing). If pathfinding algorithm works mainly on CPU and doesn't do much parallel processing it may cause more issues than it should.

 

[NamingIsHard]

In warband, units just run through a straight line to the target and if they run across an obstacle,they seem to just change the direction a little bit so they walk around it. They get stuck behind obstacles too many times. If you watch this unity tutorial, you can see it acts like warband. Objects hit the walls and change direction, and doesn't seem to follow the shortest route possible.

That sounds weired to me. Refer to what I read, mesh is supposed to be defined as convex polygon, which means obstacles are not supposed to exist between two points within the same mesh. If the obstacles exist on boundry of inter-mesh boundry, then this two mesh is not supposed to be linked, therefore a direct route goes from A to B is not supposed to be returned by the algorithm.
And to correct my language, I mean I don't understand why defining navmesh can require large amount of manual adjustment, not only for M&B, but in general.

as well as some of the really badly written morale scripts.

Do we have morale system in Warband Native? As far as I can remember there is no such thing

If pathfinding algorithm works mainly on CPU and doesn't do much parallel processing it may cause more issues than it should.

It has been long since I learnt about parallel processing and I don't remember much about that. Kind of confused about if M&B was utilizing that, and why if not, since from what I can remember, using parallel processing to do pathfinding is supposed to help performance.

 

[MostBlunted]

it doesn't

Poorly...

It works?

Damn it! I´m too late.

 

[NamingIsHard]

Damn it! I´m too late.

Bro I really don't understand what you guys are talking about

 

[Andrei[beast]]

Bro I really don't understand what you guys are talking about

If you tried a siege in BL then you'd understand.(and I don't meant to be offensive here)
If not, from what i recall the pathfinding is pretty poorly made and in sieges units either all group up in a small area or ignore dangers around them while still doing their "chores"(shooting arrows, shield wall by the gate etc). The list can go on..