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.