• There is NO official Otland's Discord server and NO official Otland's server list. The Otland's Staff does not manage any Discord server or server list. Moderators or administrator of any Discord server or server lists have NO connection to the Otland's Staff. Do not get scammed!

TFS A* Algorithm :D

This does not fix the problem with monsters not following correctly. However, it will help decrease the CPU usage a lot if you apply this fix for their following:
Solved - Weird monster behaviour in TFS 1.1? (https://otland.net/threads/weird-monster-behaviour-in-tfs-1-1.228021/#post-2200365)
I wonder if this still apply in the most updated version, since in your code you deleted the whole "isUpdatingPath" declaration, and it can't be used anymore
and this "isUpdatingPath" is needed in the solution you mention

Should I ignore this solution you mentioned and go full with your code?
 
I wonder if this still apply in the most updated version, since in your code you deleted the whole "isUpdatingPath" declaration, and it can't be used anymore
and this "isUpdatingPath" is needed in the solution you mention

Should I ignore this solution you mentioned and go full with your code?
wonder the same
 
@Itutorial I been using this algorithm these last days in my server and received very positive thoughts about the monsters difficulty from the players. Just came back to say that this is working really good! ;)
 
I wonder if this still apply in the most updated version, since in your code you deleted the whole "isUpdatingPath" declaration, and it can't be used anymore
and this "isUpdatingPath" is needed in the solution you mention

Should I ignore this solution you mentioned and go full with your code?
Yes, I would not use that solution if you are planning to implement my changes.

Instead implement both:
Update pathfinding call
Update pathfinding system

The final results showed that my system is 10x faster on the lowest ends (most complex paths) and up to 100x faster in 90%+ of cases. The rate was:
200k Nanoseconds -> for most pathfinding calls even when only a few sqm away with default.
100-20k nanoseconds -> with 20k being 5-10% of the more complex paths.

With my system the pathfinding is called more often but not as much as you would think as the paths that execute the full loop (80 nodes I believe) checked. This would be whenever the monster can't find a path. DO NOT execute with my code. On default every 1 second every monster will update their path even at the worse cases which is where most of the CPU usage was really coming from.

Based on the data I collected calling the pathfinding whenever the player moved was still a fraction of the cost that default was using even only executing once a second.
 
Last edited:
Yes, I would not use that solution if you are planning to implement my changes.

Instead implement both:
Update pathfinding call
Update pathfinding system

The final results showed that my system is 10x faster on the lowest ends (most complex paths) and up to 100x faster in 90%+ of cases. The rate was:
200k Nanoseconds -> for most pathfinding calls even when only a few sqm away with default.
100-20k nanoseconds -> with 20k being 5-10% of the more complex paths.

With my system the pathfinding is called more often but not as much as you would think as the paths that execute the full loop (80 nodes I believe) checked. This would be whenever the monster can't find a path. DO NOT execute with my code. On default every 1 second every monster will update their path even at the worse cases which is where most of the CPU usage was really coming from.

Based on the data I collected calling the pathfinding whenever the player moved was still a fraction of the cost that default was using even only executing once a second.
yes, that's what I did, but I still had some problems with monster that have higher speed, as you can see in the gifs, their movements are a little strange and easy to avoid

pathfinding.gifpathfinding2.gif


So I added this piece of code from that solution in your first post together with those changes you mentioned in creature.cpp

Lua:
if (hasFollowPath) {
    if (getWalkDelay() <= 0) {
           g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
    }

The monsters seems to be a little faster after this change.
Im not very good at c++, can this mess your code or bring the efficiency down??
 
Last edited:
yes, that's what I did, but I still had some problems with monster that have higher speed, as you can see in the gifs, their movements are a little strange and easy to avoid

View attachment 71718View attachment 71719


So I added this piece of code from that solution in your first post together with those changes you mentioned in creature.cpp

Lua:
if (hasFollowPath) {
    if (getWalkDelay() <= 0) {
           g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
    }

The monsters seems to be a little faster after this change.
Im not very good at c++, can this mess your code or bring the efficiency down??
Offtopic: Love your sprites. Who made them? Hirable?
 
yes, that's what I did, but I still had some problems with monster that have higher speed, as you can see in the gifs, their movements are a little strange and easy to avoid


So I added this piece of code from that solution in your first post together with those changes you mentioned in creature.cpp

Lua:
if (hasFollowPath) {
    if (getWalkDelay() <= 0) {
           g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
    }

The monsters seems to be a little faster after this change.
Im not very good at c++, can this mess your code or bring the efficiency down??
Is this a problem more people have? I don't have much time right now but if this is an actual problem I will try to look into it.
 
Is this a problem more people have? I don't have much time right now but if this is an actual problem I will try to look into it.
I Followed the github changes and compilled without errors, but I don't know if more people did the same tests as I did.

by the way, monsters with lower speeds won't stop walking everytime like my second gif, but they can easily be avoided when you are walking in circle around them as well.
 
yes, that's what I did, but I still had some problems with monster that have higher speed, as you can see in the gifs, their movements are a little strange and easy to avoid

View attachment 71718View attachment 71719


So I added this piece of code from that solution in your first post together with those changes you mentioned in creature.cpp

Lua:
if (hasFollowPath) {
    if (getWalkDelay() <= 0) {
           g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
    }

The monsters seems to be a little faster after this change.
Im not very good at c++, can this mess your code or bring the efficiency down??
where did you added that?
i have this but nothing else related to ifhasfollowpath
C++:
void Monster::onFollowCreatureComplete(const Creature* creature)
{
    if (creature) {
        auto it = std::find(targetList.begin(), targetList.end(), creature);
        if (it != targetList.end()) {
            Creature* target = (*it);
            targetList.erase(it);

            if (hasFollowPath) {
                targetList.push_front(target);
            } else if (!isSummon()) {
                targetList.push_back(target);
            } else {
                target->decrementReferenceCounter();
            }
        }
    }
}
 
where did you added that?
i have this but nothing else related to ifhasfollowpath
C++:
void Monster::onFollowCreatureComplete(const Creature* creature)
{
    if (creature) {
        auto it = std::find(targetList.begin(), targetList.end(), creature);
        if (it != targetList.end()) {
            Creature* target = (*it);
            targetList.erase(it);

            if (hasFollowPath) {
                targetList.push_front(target);
            } else if (!isSummon()) {
                targetList.push_back(target);
            } else {
                target->decrementReferenceCounter();
            }
        }
    }
}

On creature.cpp, inside the function
Code:
void Creature::onCreatureMove(Creature* creature, const Tile* newTile, const Position& newPos,
                              const Tile* oldTile, const Position& oldPos, bool teleport)


Find this if:
Code:
if (creature == followCreature || (creature == this && followCreature)) {

and put this inside:
Code:
g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
Im not sure this will make the monsters faster, but to me they look a little faster

Still, they are not perfect yet
 
Last edited:
Help adding missing code
C++:
"there does not exist any constructor to convert from const creature to creature"
have been stuck on this pls help
bool Map::getPathTo(const Creature* creature, const Position& destPos,
    std::list<Direction>& listDir, int32_t maxSearchDist /*= -1*/)
{
    if (canWalkTo(creature, destPos) == NULL) {
        return false;
    }

    listDir.clear();

    Position startPos = destPos;
    Position endPos = creature->getPosition();

    if (startPos.z != endPos.z) {
        return false;
    }

    //AStarNodes nodes(pos.x, pos.y);
    AStarNodes nodes;
    AStarNode* startNode = nodes.createOpenNode();

    startNode->x = startPos.x;
    startNode->y = startPos.y;

    startNode->g = 0;
    startNode->h = nodes.getEstimatedDistance(startPos.x, startPos.y, endPos.x, endPos.y);
    startNode->f = startNode->g + startNode->h;
    startNode->parent = NULL;

    Position pos;
    pos.z = startPos.z;

    static int32_t neighbourOrderList[8][2] =
    {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1},

        //diagonal
        {-1, -1},
        {1, -1},
        {1, 1},
        {-1, 1},
    };

    const Tile* tile = NULL;
    AStarNode* found = NULL;

    while (maxSearchDist != -1 || nodes.countClosedNodes() < 100) {
        AStarNode* n = nodes.getBestNode();
        if (!n) {
            listDir.clear();
            return false; //no path found
        }

        if (n->x == endPos.x && n->y == endPos.y) {
            found = n;
            break;
        }
        else {
            for (int i = 0; i < 8; ++i) {
                pos.x = n->x + neighbourOrderList[i][0];
                pos.y = n->y + neighbourOrderList[i][1];

                bool outOfRange = false;
                if (maxSearchDist != -1 && (std::abs(endPos.x - pos.x) > maxSearchDist ||
                    std::abs(endPos.y - pos.y) > maxSearchDist)) {
                    outOfRange = true;
                }

                if (!outOfRange && (tile = canWalkTo(creature, pos))) {
                    //The cost (g) for this neighbour
                    int32_t cost = nodes.getMapWalkCost(creature, n, tile, pos);
                    int32_t extraCost = nodes.getTileWalkCost(creature, tile);
                    int32_t newg = n->g + cost + extraCost;

                    //Check if the node is already in the closed/open list
                    //If it exists and the nodes already on them has a lower cost (g) then we can ignore this neighbour node

                    AStarNode* neighbourNode = nodes.getNodeInList(pos.x, pos.y);
                    if (neighbourNode) {
                        if (neighbourNode->g <= newg) {
                            //The node on the closed/open list is cheaper than this one
                            continue;
                        }

                        nodes.openNode(neighbourNode);
                    }
                    else {
                        //Does not exist in the open/closed list, create a new node
                        neighbourNode = nodes.createOpenNode();
                        if (!neighbourNode) {
                            //seems we ran out of nodes
                            listDir.clear();
                            return false;
                        }
                    }

                    //This node is the best node so far with this state
                    neighbourNode->x = pos.x;
                    neighbourNode->y = pos.y;
                    neighbourNode->parent = n;
                    neighbourNode->g = newg;
                    neighbourNode->h = nodes.getEstimatedDistance(neighbourNode->x, neighbourNode->y,
                        endPos.x, endPos.y);
                    neighbourNode->f = neighbourNode->g + neighbourNode->h;
                }
            }

            nodes.closeNode(n);
        }
    }

    int32_t prevx = endPos.x;
    int32_t prevy = endPos.y;
    int32_t dx, dy;

    while (found) {
        pos.x = found->x;
        pos.y = found->y;

        found = found->parent;

        dx = pos.x - prevx;
        dy = pos.y - prevy;

        prevx = pos.x;
        prevy = pos.y;

        if (dx == -1 && dy == -1) {
            listDir.push_back(DIRECTION_NORTHWEST);
        }
        else if (dx == 1 && dy == -1) {
            listDir.push_back(DIRECTION_NORTHEAST);
        }
        else if (dx == -1 && dy == 1) {
            listDir.push_back(DIRECTION_SOUTHWEST);
        }
        else if (dx == 1 && dy == 1) {
            listDir.push_back(DIRECTION_SOUTHEAST);
        }
        else if (dx == -1) {
            listDir.push_back(DIRECTION_WEST);
        }
        else if (dx == 1) {
            listDir.push_back(DIRECTION_EAST);
        }
        else if (dy == -1) {
            listDir.push_back(DIRECTION_NORTH);
        }
        else if (dy == 1) {
            listDir.push_back(DIRECTION_SOUTH);
        }
    }

    return !listDir.empty();
}
On creature.cpp, inside the function
Code:
void Creature::onCreatureMove(Creature* creature, const Tile* newTile, const Position& newPos,
                              const Tile* oldTile, const Position& oldPos, bool teleport)


Find this if:
Code:
if (creature == followCreature || (creature == this && followCreature)) {

and put this inside:
Code:
g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
Im not sure this will make the monsters faster, but to me they look a little faster

Still, they are not perfect yet
I tested and with this it work way better, there are any new upgrades or implementations for this code?
i've used ralke commits
@sururuts
Post automatically merged:

On creature.cpp, inside the function
Code:
void Creature::onCreatureMove(Creature* creature, const Tile* newTile, const Position& newPos,
                              const Tile* oldTile, const Position& oldPos, bool teleport)


Find this if:
Code:
if (creature == followCreature || (creature == this && followCreature)) {

and put this inside:
Code:
g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
Im not sure this will make the monsters faster, but to me they look a little faster

Still, they are not perfect yet
I tested and with this it work way better, there are any new upgrades?
when monster are being chased and they get reached they still behave a bit dumb
 
Last edited:
I am currently in university for software engineering. When I have more time I will go back through this code and all the code it effects to update it. There are a lot of things that need to be re-made/factored. Like removing extra code for pathfinding that is no longer needed or giving values to the fpp. @ralke made a clean version to look at for installation. The monsters being dumb isn't a result of the pathfinding it is a result of the code for how they should respond to situations.
 
I am currently in university for software engineering. When I have more time I will go back through this code and all the code it effects to update it. There are a lot of things that need to be re-made/factored. Like removing extra code for pathfinding that is no longer needed or giving values to the fpp. @ralke made a clean version to look at for installation. The monsters being dumb isn't a result of the pathfinding it is a result of the code for how they should respond to situations.
Good luck. You are in university and people here have worked long term already
 
yes, that's what I did, but I still had some problems with monster that have higher speed, as you can see in the gifs, their movements are a little strange and easy to avoid

View attachment 71718View attachment 71719


So I added this piece of code from that solution in your first post together with those changes you mentioned in creature.cpp

Lua:
if (hasFollowPath) {
    if (getWalkDelay() <= 0) {
           g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
    }

The monsters seems to be a little faster after this change.
Im not very good at c++, can this mess your code or bring the efficiency down??
Im facing problem if i add this
Lua:
    if (creature == followCreature || (creature == this && followCreature)) {
        if (hasFollowPath) {
            if (getWalkDelay() <= 0) {
        g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
            }
        if (newPos.z != oldPos.z || !canSee(followCreature->getPosition())) {
i have to use the code like this
Code:
    if (creature == followCreature || (creature == this && followCreature)) {
      
        g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
       
        if (newPos.z != oldPos.z || !canSee(followCreature->getPosition())) {

how to fix?
 
i found an issue in the new codes related to monster behavior GitHub - ralke23/Greed-TFS-1.5-Downgrades: Alternative forgottenserver versions for older protocols support (https://github.com/ralke23/Greed-TFS-1.5-Downgrades)
when a monster is fleeing it seems to turn back to player very fast is very noticeable with dragon or bigger monsters and look very ugly is there a way to fix to the monster will keep trying to attack but not to turn around to player while doing it every milisecond?

They do that on real tibia aswell
 
Im facing problem if i add this
Lua:
    if (creature == followCreature || (creature == this && followCreature)) {
        if (hasFollowPath) {
            if (getWalkDelay() <= 0) {
        g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
            }
        if (newPos.z != oldPos.z || !canSee(followCreature->getPosition())) {
i have to use the code like this
Code:
    if (creature == followCreature || (creature == this && followCreature)) {
    
        g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
     
        if (newPos.z != oldPos.z || !canSee(followCreature->getPosition())) {

how to fix?
There is a 7 years old report about monsters walking on github:
There are tests of different reaction time using 5 algorithms:

Many big OTSes use custom 'AI' for monsters, that does not use A* for monsters, if there is walkable path using basic 'plan next step' algorithm - as monsters do on real tibia.
Someone even sold it for 1000$ on otland.
 
There is a 7 years old report about monsters walking on github:
There are tests of different reaction time using 5 algorithms:

Many big OTSes use custom 'AI' for monsters, that does not use A* for monsters, if there is walkable path using basic 'plan next step' algorithm - as monsters do on real tibia.
Someone even sold it for 1000$ on otland.
I have sent you a pm. thanks for reply
 
Back
Top