• 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!
  • If you're using Gesior 2012 or MyAAC, please review this thread for information about a serious security vulnerability and a fix.

TFS A* Algorithm :D

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
I spent way to long messing with this. A few hours. I am no pro but I learned how the code behaves and figured out a way IMO to make it better. It hasn't been tested to the limit but I have tested it with 50+ monsters following me and ran through a few obstacles.

There is a lot of things that can be done to make the code better as far as modifying how the paths behave based on certain scenarios.

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)

Here is a video I made to demonstrate:

I have used a lot from this community and try to give back. This is one thing I know most did not want to look at. Hopefully this will help.

creature.cpp
replace
C++:
bool Creature::getPathTo(const Position& targetPos, std::vector<Direction>& dirList, const FindPathParams& fpp) const
{
    return g_game.map.getPathMatching(*this, dirList, FrozenPathingConditionCall(targetPos), fpp);
}

with
C++:
bool Creature::getPathTo(const Position& targetPos, std::vector<Direction>& dirList, const FindPathParams& fpp) const
{
    return g_game.map.getPathMatching(*this, targetPos, dirList, FrozenPathingConditionCall(targetPos), fpp);
}

map.h
under
C++:
static constexpr int32_t MAP_DIAGONALWALKCOST = 25;

add
C++:
static int_fast32_t dirNeighbors[8][5][2] = {
        {{-1, 0}, {0, 1}, {1, 0}, {1, 1}, {-1, 1}},
        {{-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}},
        {{-1, 0}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}},
        {{0, 1}, {1, 0}, {0, -1}, {1, -1}, {1, 1}},
        {{1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}},
        {{-1, 0}, {0, -1}, {-1, -1}, {1, -1}, {-1, 1}},
        {{0, 1}, {1, 0}, {1, -1}, {1, 1}, {-1, 1}},
        {{-1, 0}, {0, 1}, {-1, -1}, {1, 1}, {-1, 1}}
};
static int_fast32_t allNeighbors[8][2] = {
    {-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}
};

replace
C++:
bool getPathMatching(const Creature& creature, std::vector<Direction>& dirList,
                             const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const;

with
C++:
bool getPathMatching(const Creature& creature, const Position& targetPos, std::vector<Direction>& dirList,
                             const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const;

map.cpp
replace this whole method
C++:
bool Map::getPathMatching(const Creature& creature, std::vector<Direction>& dirList, const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const

with
C++:
bool Map::getPathMatching(const Creature& creature, const Position& targetPos, std::vector<Direction>& dirList, const FrozenPathingConditionCall& pathCondition, const FindPathParams& fpp) const
{
    Position pos = creature.getPosition();
    Position endPos;
    const Position startPos = pos;

    int32_t bestMatch = 0;

    AStarNodes nodes(pos.x, pos.y);

    AStarNode* found = nullptr;
    while (fpp.maxSearchDist != 0 || nodes.getClosedNodes() < 100) {
        AStarNode* n = nodes.getBestNode();
        if (!n) {
            if (found) {
                break;
            }
            return false;
        }

        const int_fast32_t x = n->x;
        const int_fast32_t y = n->y;
        pos.x = x;
        pos.y = y;
        if (pathCondition(startPos, pos, fpp, bestMatch)) {
            found = n;
            endPos = pos;
            if (bestMatch == 0) {
                break;
            }
        }

        uint_fast32_t dirCount;
        int_fast32_t* neighbors;
        if (n->parent) {
            const int_fast32_t offset_x = n->parent->x - x;
            const int_fast32_t offset_y = n->parent->y - y;
            if (offset_y == 0) {
                if (offset_x == -1) {
                    neighbors = *dirNeighbors[DIRECTION_WEST];
                }
                else {
                    neighbors = *dirNeighbors[DIRECTION_EAST];
                }
            }
            else if (!fpp.allowDiagonal || offset_x == 0) {
                if (offset_y == -1) {
                    neighbors = *dirNeighbors[DIRECTION_NORTH];
                }
                else {
                    neighbors = *dirNeighbors[DIRECTION_SOUTH];
                }
            }
            else if (offset_y == -1) {
                if (offset_x == -1) {
                    neighbors = *dirNeighbors[DIRECTION_NORTHWEST];
                }
                else {
                    neighbors = *dirNeighbors[DIRECTION_NORTHEAST];
                }
            }
            else if (offset_x == -1) {
                neighbors = *dirNeighbors[DIRECTION_SOUTHWEST];
            }
            else {
                neighbors = *dirNeighbors[DIRECTION_SOUTHEAST];
            }
            dirCount = fpp.allowDiagonal ? 5 : 3;
        }
        else {
            dirCount = 8;
            neighbors = *allNeighbors;
        }

        for (uint_fast32_t i = 0; i < dirCount; ++i) {
            pos.x = x + *neighbors++;
            pos.y = y + *neighbors++;

            if (fpp.maxSearchDist != 0 && (Position::getDistanceX(startPos, pos) > fpp.maxSearchDist || Position::getDistanceY(startPos, pos) > fpp.maxSearchDist)) {
                continue;
            }

            if (fpp.keepDistance && !pathCondition.isInRange(startPos, pos, fpp)) {
                continue;
            }

            const Tile* tile;
            AStarNode* neighborNode = nodes.getNodeByPosition(pos.x, pos.y);
            if (neighborNode) {
                tile = getTile(pos.x, pos.y, pos.z);
            }
            else {
                tile = canWalkTo(creature, pos);
                if (!tile) {
                    continue;
                }
            }

            //The cost to walk to this neighbor
            const int_fast32_t G = AStarNodes::getMapWalkCost(n, pos);
            const int_fast32_t E = AStarNodes::getTileWalkCost(creature, tile);
            const int_fast32_t H = (Position::getDistanceX(pos, targetPos) + Position::getDistanceY(pos, targetPos));
            int_fast32_t newf = G + (H + E);

            if (neighborNode) {
                if (neighborNode->f <= newf) {
                    //The node on the closed/open list is cheaper than this one
                    continue;
                }

                neighborNode->f = newf;
                neighborNode->parent = n;
                nodes.openNode(neighborNode);
            }
            else {
                //Does not exist in the open/closed list, create a new node
                //g_game.addMagicEffect(pos, CONST_ME_TELEPORT);
                neighborNode = nodes.createOpenNode(n, pos.x, pos.y, newf);
                if (!neighborNode) {
                    if (found) {
                        break;
                    }
                    return false;
                }
            }
        }

        nodes.closeNode(n);
    }

    if (!found) {
        return false;
    }

    int_fast32_t prevx = endPos.x;
    int_fast32_t prevy = endPos.y;

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

        int_fast32_t dx = pos.getX() - prevx;
        int_fast32_t dy = pos.getY() - prevy;

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

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

        found = found->parent;
    }
    return true;
}
 
Last edited:

ralke

(҂ ͠❛ ෴ ͡❛)ᕤ
Joined
Dec 17, 2011
Messages
1,202
Solutions
27
Reaction score
669
Location
Santiago - Chile
GitHub
ralke23
Twitch
ralke23
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
This is great. I felt monsters much more challenging with Don Daniello's modification, but indeed, the RAM usage was totally messy.
There's other commits out there, such as this Fix monster movement for 8.6 (#20) · Znote/[email protected] (https://github.com/Znote/TFS-1.4-Downgrades/commit/f2bb40fa5e91833c1585facdc527e5a5345be48d), I saw other ones but can't remember now.

Thanks for sharing this! Gonna test it as soon I can ^^
Regards!
Yeah there has been a few fixes like that but this is the actual pathfinding itself. My method uses 1/4th the amount of squares and in some cases even less.

I did see a post with someone that messed with it before and he had a good way to test the speed of the algorithm. I might try to figure out how to do that but hopefully he will come around and do it haha.

EDIT

Here it is. @Flatlander
 
Last edited:

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,237
Solutions
25
Reaction score
2,445
Location
Poland
GitHub
Zbizu
The biggest problem of pathfinding is how often full path search is being called. I believe that a lot of CPU load could have been avoided if:
  • getPathTo gets called every x steps rather than constantly (or when cached path is no longer possible to walk)
  • path gets cached/compressed somehow (eg. with waypoints)
  • getPathTo complexity gets lowered somehow - for example if obstacle emerges on "known" path, the monster could begin pathfinding from obstacle to closest "next" waypoint/node rather than trying to calculate full path again

The solution to pathfinding problem is probably super easy and right under our noses within first page of google search considering that four german students 20 years ago managed to do it efficiently. We are probably overthinking it with those a* nodes.

Note for future releases like this one:
please also link to github commit if applicable, it has better tools to show differences than forum
 
Last edited:

ralke

(҂ ͠❛ ෴ ͡❛)ᕤ
Joined
Dec 17, 2011
Messages
1,202
Solutions
27
Reaction score
669
Location
Santiago - Chile
GitHub
ralke23
Twitch
ralke23
Yeah there has been a few fixes like that but this is the actual pathfinding itself. My method uses 1/4th the amount of squares and in some cases even more.

I did see a post with someone that messed with it before and he had a good way to test the speed of the algorithm. I might try to figure out how to do that but hopefully he will come around and do it haha.

EDIT

Here it is. @Flatlander

In case it helps, is also here on github with the discussion

And saw this too

Are bookmarks I had on old posts
Regards!
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
The biggest problem of pathfinding is how often full path search is being called. I believe that a lot of CPU load could have been avoided if:
  • getPathTo gets called every x steps rather than constantly (or when cached path is no longer possible to walk)
  • path gets cached/compressed somehow (eg. with waypoints)
  • getPathTo complexity gets lowered somehow - for example if obstacle emerges on "known" path, the monster could begin pathfinding from obstacle to closest "next" waypoint/node rather than trying to calculate full path again

The solution to pathfinding problem is probably super easy and right under our noses within first page of google search considering that four german students 20 years ago managed to do it efficiently. We are probably overthinking it with those a* nodes.

Note for future releases like this one:
please also link to github commit if applicable, it has better tools to show differences than forum
Facts. I haven't really looked into that part yet. I wanted to fix the algorithm first just because it actually is really important when finding the solution. Sometimes one thing works. You fix something, then that same thing stops working because it was set up perfect for the other code. I think using 1/4 or less of the tiles on full path search will be helpful no matter what though.
Post automatically merged:

In case it helps, is also here on github with the discussion

And saw this too

Are bookmarks I had on old posts
Regards!
Yo gigastar is me lmao. @Sarah Wesker came up with a pretty good solution based off that slope system. Really nice stuff.
I am not sure if implementing @Flatlander code would be efficient here. Someone with a bigger brain or flat himself would need to explain it.
Post automatically merged:

please also link to github commit if applicable, it has better tools to show differences than forum
I have been trying to figure out how to use github for too long now
 
Last edited:

Yamaken

Pro OpenTibia Developer
Joined
Jul 27, 2013
Messages
534
Solutions
4
Reaction score
428
Sorry if i did not read correctly but i did not understand what this code fix. As far i know there is no problem with actual TFS pathing besides how long it take to update the monster path again (it happens inside the creature onThink method which is called every 1 second which is too slow).
At the same time i'm surprised (positively) that someone is working to improve this aspect of TFS.
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
Sorry if i did not read correctly but i did not understand what this code fix. As far i know there is no problem with actual TFS pathing besides how long it take to update the monster path again (it happens inside the creature onThink method which is called every 1 second which is too slow).
At the same time i'm surprised (positively) that someone is working to improve this aspect of TFS.
TFS pathfinding right now acts like Dijkstra's when they went for A*. A* is way faster in most cases.

It does have one problem which is that it will walk you into walls in some cases before heading on the right path again because that's how the system works but its far more efficient.

I will probably look into a fix for monster walking now that im done with pathfinding. Just know this pathfinding system is more efficient which means more players can be on the server before problems start with hardware.
 

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,237
Solutions
25
Reaction score
2,445
Location
Poland
GitHub
Zbizu
Something is still odd. What's the point of searching backwards or around if straight line is available? There's still a room for improvement.
 

Silba

is stephany, the josh wife
Joined
Aug 22, 2013
Messages
436
Solutions
9
Reaction score
350
I'll check this out soon, thanks for sharing.
I'm glad this is getting some attention again, it's one of the most noticeable and impactful downsides of current TFS.
 

amatria

Well-Known Member
Joined
May 15, 2021
Messages
73
Solutions
6
Reaction score
78
Location
Spain
GitHub
amatria
Something is still odd. What's the point of searching backwards or around if straight line is available? There's still a room for improvement.
You can't avoid searching "around" or "backwards". There will always exist a time step in which searching "around" or "backwards" is a far better alternative than searching in a straight line. This behaviour is intrinsic to any heuristic-based algorithm.
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
Alright, this is something that can be done. I am pretty sure this is how it should be with pathfinding but who knows.

So, marks fix had the monster update the path anytime the monster moved and anytime the target moved.

This fix will make it so the path will only update if the end position is changed.

There is probably more code that can be removed. I only did the main things to make it work.

This will also make it so monsters don't check path every 1 second no matter what. So some CPU usage is saved there.

NOTE** this will work with default TFS pathfinding system.

creature.h
find
C++:
Creature* attackedCreature = nullptr;
under add
C++:
Position attackedCreaturePos;

creature.cpp
find
C++:
void Creature::onThink(uint32_t interval)
remove
C++:
if (followCreature) {
        walkUpdateTicks += interval;
        if (forceUpdateFollowPath || walkUpdateTicks >= 2000) {
            walkUpdateTicks = 0;
            forceUpdateFollowPath = false;
            isUpdatingPath = true;
        }
    }

    if (isUpdatingPath) {
        isUpdatingPath = false;
        goToFollowCreature();
    }
add to the bottom of onThink()
C++:
const Creature* target = attackedCreature;
    if (target) {
        if (attackedCreaturePos != target->getPosition()) {
            attackedCreaturePos = target->getPosition();
            g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
        }
    }

find
C++:
void Creature::onWalk()
remove any
C++:
forceUpdateFollowPath = true;

find
C++:
bool Creature::setAttackedCreature(Creature* creature)
under
C++:
attackedCreature = creature;
add
C++:
attackedCreaturePos = creaturePos;


You can remove any
C++:
isUpdatingPath
forceUpdateFollowPath

from creature.h / creature.cpp / player.cpp
 
Last edited:

soul4soul

Intermediate OT User
Joined
Aug 13, 2007
Messages
1,872
Solutions
3
Reaction score
125
Location
USA
nice video to show the difference, based on just the video I can't see any argument that its not better. It would be great to see a PR on TFS as other mentioned to make review easier.
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
Alright, I have made all the final edits. The last thing I added was a sightLine check to see if there is anything blocking the path between start and finish and modified which nodes are checked based on that.

I will work on getting it sent in a PR on github. This video includes my changes to when pathfinding is updated. You will notice it only updates when I move.

 

alcapone

Member
Joined
Jan 13, 2021
Messages
231
Reaction score
17
Alright, this is something that can be done. I am pretty sure this is how it should be with pathfinding but who knows.

So, marks fix had the monster update the path anytime the monster moved and anytime the target moved.

This fix will make it so the path will only update if the end position is changed.

There is probably more code that can be removed. I only did the main things to make it work.

This will also make it so monsters don't check path every 1 second no matter what. So some CPU usage is saved there.

NOTE** this will work with default TFS pathfinding system.

creature.h
find
C++:
Creature* attackedCreature = nullptr;
under add
C++:
Position attackedCreaturePos;

creature.cpp
find
C++:
void Creature::onThink(uint32_t interval)
remove
C++:
if (followCreature) {
        walkUpdateTicks += interval;
        if (forceUpdateFollowPath || walkUpdateTicks >= 2000) {
            walkUpdateTicks = 0;
            forceUpdateFollowPath = false;
            isUpdatingPath = true;
        }
    }

    if (isUpdatingPath) {
        isUpdatingPath = false;
        goToFollowCreature();
    }
add to the bottom of onThink()
C++:
const Creature* target = attackedCreature;
    if (target) {
        if (attackedCreaturePos != target->getPosition()) {
            attackedCreaturePos = target->getPosition();
            g_dispatcher.addTask(createTask(std::bind(&Game::updateCreatureWalk, &g_game, getID())));
        }
    }

find
C++:
void Creature::onWalk()
remove any
C++:
forceUpdateFollowPath = true;

find
C++:
bool Creature::setAttackedCreature(Creature* creature)
under
C++:
attackedCreature = creature;
add
C++:
attackedCreaturePos = creaturePos;


You can remove any
C++:
isUpdatingPath
forceUpdateFollowPath

from creature.h / creature.cpp / player.cpp
one problem I noticed is the player closed a 'box'
the other monsters only come to him if he moves so he needs to be always on the move
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
one problem I noticed is the player closed a 'box'
the other monsters only come to him if he moves so he needs to be always on the move
Can you explain that better? Are you saying if there is no path to the player (because he is closed in) the monster doesn't move around?
 

Oskar1121

Veteran OT User
Joined
Jul 15, 2009
Messages
610
Reaction score
436
Location
Poland
What if you go up/down and don't move? Will the monster try to find the path to the player? Also, check if monsters who don't have access to the player will find the way if the path is clear again (for example player gets all eight monsters around and kill one of them, so there is one empty spot for one monster walking around).
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
What if you go up/down and don't move? Will the monster try to find the path to the player? Also, check if monsters who don't have access to the player will find the way if the path is clear again (for example player gets all eight monsters around and kill one of them, so there is one empty spot for one monster walking around).
Yes, the monster updates its path when it walks. Head over to github for more up-to-date changes.

 

ralke

(҂ ͠❛ ෴ ͡❛)ᕤ
Joined
Dec 17, 2011
Messages
1,202
Solutions
27
Reaction score
669
Location
Santiago - Chile
GitHub
ralke23
Twitch
ralke23
Yes, the monster updates its path when it walks. Head over to github for more up-to-date changes.


Hi there! I've just updated everything, saw this post too C++ - Help me figure this out :D true A* algorithm (https://otland.net/threads/help-me-figure-this-out-d-true-a-algorithm.282176/#post-2704176) and started the testings. I have found a little issue already, when I use utevo res "any creature, the creature doesn't follow the player. This started to happen, after applied the commits, is it related to the latest changes? Regards!

Edit:
Found another one, when I click on a stair from far distance (with right click, to use it), it says "There is no way". The same thing happens when I try to use any object from far distance... Here you can see how I applied the whole code.

 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,279
Solutions
68
Reaction score
919
Creature::eek:nThink() @ralke

replace
C++:
forceUpdateFollowPath = true

with
C++:
if (followCreature) {
        goToFollowCreature();
    }

    forceUpdateFollowPath = true;

Fixes are pushed to github (only need the path call one ralke)
 
Last edited:
Top