Monster AI

[Polperia]

Hello Otlanders.

Im trying to figure out how does an OT handle lot of players without risk the CPU consumption when many monsters are dealing with path calculation to a target.

The basic thing understandable is:

• Z position which is related to the floor where the target it.
• The target inside of protection zone(monster logic should avoid to calculate a path to him).
• The minimum and maximum range vision that the monster is allowed to see a target in that given range or stop following it if its far.

Well, thats the basic things to set the monster logic...

Now... the point is... how does the engine deal with it?
Does it iterate all the monsters existing in the game map or just the client sends something to the server telling about a monster is next to a target and should start dealing with path calculation?

If the case is the first one, iterating the whole monster list existing in the game world, does the TFS use different CPU threads to avoid bottlenecks?

Sorry if the explanation is hard to understand, i tried my best.
Any tips to decrease CPU usage with that heavy stuff( A* algo) is appreciated.

Thanks! <3

 

[Sorky]

As far as I know, npc are walking even without players sees them, monsters calculate path only when player is in range (gm+ does not trigger pathfinding)
Aaand tfs is running on a single core

 

[godoyxd]

Hi,

The best place to look is the code. I might have missed something but here it goes:

1. Place creature triggers onCreatureAppear
2. onCreatureAppear in Monster updates target list
   1. search for players in a 23x23 square -11<pos>+11 (canSee function)
   2. adds to target list
3. this loop is executed in buckets meaning it will update a bunch of monsters each time: Game::checkCreatures
4. Monster onthink will have the rest of the logic:
   1. check target list, set attack and start to calculate the path to the target

To find more about it you can continue from there.
As it was mentioned above, this is single threaded.

 

[Polperia]

Hi,

The best place to look is the code. I might have missed something but here it goes:

1. Place creature triggers onCreatureAppear
2. onCreatureAppear in Monster updates target list
   1. search for players in a 23x23 square -11<pos>+11 (canSee function)
   2. adds to target list
3. this loop is executed in buckets meaning it will update a bunch of monsters each time: Game::checkCreatures
4. Monster onthink will have the rest of the logic:
   1. check target list, set attack and start to calculate the path to the target

To find more about it you can continue from there.
As it was mentioned above, this is single threaded.

Hello.

Thanks for your reply, well so I can understand that the game server does a global iteration throught all monster entities matching a 23x23 square range, -11 floors and +11 floors. I suppose it might also check characters in safe zone, and such stuff...

Would you mind to tell me where could I find the pathfind logic calculation or how does the monster perform its movement towards a target found?

Thanks!

 

[godoyxd]

the game server does a global iteration throught all monster entities matching a 23x23 square range, -11 floors and +11 floors.

No, -11 and +11 are not floors. The are part of the 23x23 square. <Player pos> - 11 and <Player pos> + 11 on both X and Y axis gives a 23x23 square.
Every 100ms the game checks one of the 10 monsters buckets.
The floors are controlled by which floor the player is.

- Above ground is 8 floors, below ground is between 3 or 5 (needs confirmation).​

Would you mind to tell me where could I find the pathfind logic calculation or how does the monster perform its movement towards a target found?

You can follow Monster:nThink function.

1. addEventWalk
2. setFollowCreature(attackedCreature);

Best way is to open an IDE and follow the function calls and member variables.
Eventually you will end up in Creature::getPathTo function, which calls the A* from the Map class.

 

[Polperia]

No, -11 and +11 are not floors. The are part of the 23x23 square. <Player pos> - 11 and <Player pos> + 11 on both X and Y axis gives a 23x23 square.
Every 100ms the game checks one of the 10 monsters buckets.
The floors are controlled by which floor the player is.

- Above ground is 8 floors, below ground is between 3 or 5 (needs confirmation).​

You can follow Monster:nThink function.

1. addEventWalk
2. setFollowCreature(attackedCreature);

Best way is to open an IDE and follow the function calls and member variables.
Eventually you will end up in Creature::getPathTo function, which calls the A* from the Map class.

Seems that some TFS uses BFS and others A* with a sqaure vision of 23x23.

If im not wrong, coding a server from scratch using nodejs, it forces me to use worker threads to split the CPU loads when using BFS and mainly use raycasting from monster position to player position, the ping went down from 100 ms in local to 18 ms which is a huge improvement.

Also, I noticed that corner cutting, which has a cost or square root 2 => 1.41.... opens more nodes, so it makes more calculations to neightbours.
If just allowing diagonals when obstacles are adyacent, I could reduce a lot of nodes to inspect and find the path to the player.


Thank you for your reply, really appreciated and helped a lot!

 

[godoyxd]

Seems that some TFS uses BFS and others A* with a sqaure vision of 23x23.

If im not wrong, coding a server from scratch using nodejs, it forces me to use worker threads to split the CPU loads when using BFS and mainly use raycasting from monster position to player position, the ping went down from 100 ms in local to 18 ms which is a huge improvement.

Also, I noticed that corner cutting, which has a cost or square root 2 => 1.41.... opens more nodes, so it makes more calculations to neightbours.
If just allowing diagonals when obstacles are adyacent, I could reduce a lot of nodes to inspect and find the path to the player.


Thank you for your reply, really appreciated and helped a lot!

You're welcome.

Also, it seems that TFS does not take into account the speed of the ground when choosing paths.
That would be a cool thing to add.
Another one: in the original game "maxSearchDist" of BFS (or A*) is around 20 instead of 'maxClientViewport +1'.

The last thing I noticed is that the path is calculated too frequently. It should only be re-calculated when the target moves to a different direction of the chaser. I say direction because if the target moves just a few squares, the final path would almost be the same, and in this case the 2 second rule would apply.
The best would be to implement an algorithm that allows for the target to move, something like this: https://idm-lab.org/bib/abstracts/papers/aamas10a.pdf.