• 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!
  • New resources must be posted under Resources tab. A discussion thread will be created automatically, you can't open threads manually anymore.

TFS A* Algorithm :D

I see I was mentioned here. So I am just going to summerize TFS's Pathfinding and what changes you can make.

1) Pathfinding (This is basically the function that finds a path. getPathMatching is the function TFS uses and I upgraded it about 7 years ago myself to be much faster. Which is what you found in my previous threads and github conversations with Mark. The changes can technically make monsters path differently around fields or when they can push monsters but no player would notice the slight differences and rare cases where the faster code would cause a change in the "most efficient path".

2) Pathfinding updates: This is WHEN TFS calculates a new path for a creature. If you have long-distance pathfinding (for example if you increased the screen size) or if you have really fast creatures this can cause some slowdowns. But honestly you shouldn't see much problems leaving the current TFS "as is".
Currently TFS updates pathfinding in the following situations:
a) When the following creature moves
b) When a follow target moves
c) If it has been 2 seconds since the last update

Monsters in TFS already react very quickly and should path efficiently to their target.

I added one more since I want my monsters to be super-responsive:
d) When a monster gets a new target in ::onThink() I immediately calculate a new path to the new target.

Some people might not like this because you cannot "outsmart" monsters by running around them, so it depends on how you want your monsters to chase.
I hope this answers some of the questions you guys might have, but if you have any ideas or problems with the current TFS pathfinding feel free to post them here and I can take a look at them.
 
as paladin player for years, I can say that updating the path every two steps (with counter resetting on reaching the target) would be close to rl servers behaviour. I don't know the cpu implications for that though.

regarding simplification, I believe that there should be two default methods that would replace "queryadd" and ifs around it (with "calm" and "enraged" pathfinding) so the function would go through less hoops when calculating the tile availability for monster.
 
Itutorial said:
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;
}
Click to expand...
Does anyone know if Nekiro's TFS 1.5 is already implementing and if it's good regarding CPU usage? Or do I need to make some changes you mentioned?
Itutorial said:
Solved - Weird monster behaviour in TFS 1.1? (Solved - Weird monster behaviour in TFS 1.1? (https://otland.net/threads/weird-monster-behaviour-in-tfs-1-1.228021/#post-2200365))
Click to expand...
What's the difference between these? Which should I change, this one or the one Mark corrected?
 
Mateus Robeerto said:
Does anyone know if Nekiro's TFS 1.5 is already implementing and if it's good regarding CPU usage? Or do I need to make some changes you mentioned?

What's the difference between these? Which should I change, this one or the one Mark corrected?
Click to expand...
Just upgrade your nekiro's downgraded with latest coding from TFS
 
Algorithm said:
Just upgrade your nekiro's downgraded with latest coding from TFS
Click to expand...
About the commits, I've updated them all, right. However, I noticed that monsters are slow to react.
Or maybe I'm wrong, I don't know. I'm going to test the behavior of the monsters again to see if they really take time to react or if they react quickly
 
Mateus Robeerto said:
About the commits, I've updated them all, right. However, I noticed that monsters are slow to react.
Or maybe I'm wrong, I don't know. I'm going to test the behavior of the monsters again to see if they really take time to react or if they react quickly
Click to expand...
i guess this can be solved if you decreased creatureCheck delay, but becareful are this makes checkCreatureWalk takes more calls = higher cpu if you don't use multi threading for TFS you are lost
 
Mateus Robeerto said:
About the commits, I've updated them all, right. However, I noticed that monsters are slow to react.
Or maybe I'm wrong, I don't know. I'm going to test the behavior of the monsters again to see if they really take time to react or if they react quickly
Click to expand...
To sum it up.

1) Marks "solution" was a work around and it was a very slow work around. Mainly because of how slow TFS pathfinding is.

2) My solution only has bugs because there is code in TFS monster behavior that works with the current pathfinding system. It needs to be updated to work properly with mine.

3) My pathfinding algorithm is so much faster than the original one that you could have it run thousands more times.
You can mess with this value for different results in the path updating speed.
C++: 
static constexpr int32_t EVENT_CREATURE_PATH_INTERVAL = 20;

I would argue if my version of the pathfinding system was implemented and all creature behavior bugs were fixed you could run tens of thousands more paths in a fraction of the time. Which is because, the faster code runs the easier it is for the CPU to run more. Kind of like when a car engine is tuned or not tuned. If it is tuned you can push a ton of gas in and the engine will respond instantly and easily. If it is not tuned correctly it will bog down or back fire and even die because it is not able to free up the system and handle what is being injected fast enough.

The same applies to the CPU. The more work it has to do and the slower that work is the slower the CPU becomes. Especially in systems that are not properly cooled, ect. You will hit many different bottlenecks.

You should read this whole thread to get an understanding of the differences between TFS pathfinding and this one.

To reiterate.

My solution only fixes the speed of pathfinding. It changes the algorithm from Dijkstra's (checks all nodes in a circle until it finds the path)
to and actual A* algorithm (Which uses the end position to weight the algorithm to the end position first, unless it is blocked.)

Other code was included in TFS for things like: Does the monster keep distance from the target. These little things that modify the way the pathfinding should be done, work differently with the new algorithm. The new pathfinding system can either make these external systems look clunky or just not work.

When I did testing I didn't find any scenarios where things flat out didn't work. At least not at the end of my updates and testing.

Finally to get into why the code is so much faster.

1) The way TFS pathfinding code was created made it so monster would check all nodes if the target was outside its range. Meaning you could have hundreds or even thousands of monsters constantly running an 80 node path over and over again.

This created huge loads on the CPU because the pathfinding was so slow AND it checked so many nodes.
In my system I created checks to determine when we should not try to find a path at all. So we never do these 80 node checks.

2) TFS pathfinding also checked all nodes in all directions. Meaning if the target was 5 squares away there were like 25 nodes checked. 20 of which didn't need to happen. Which automatically made it 5x slower than the algorithm I made.

3) There was no code to determine if nodes DIDN'T have to be checked. This is where the majority of the performance was gained in my code. A* was created exactly for this reason. Ignore nodes we don't need to check.

On top of that I included checks for when the path was clear. If the path was clear I included more checks which allowed it to ignore even more nodes. This created up to 1000x faster pathfinding. 1000x being maybe 5-10% of all paths. 100x+ being 80% of all paths and anywhere from 2x+ faster for the rest.

Now just as a note. @Flatlander solution was close to the same. The only issue is he created the A* logic on the list of nodes already generated. Essentially mixing Dijkstra's and A*. So it did find the path faster in a lot of cases BUT there were still many nodes being processed that did not need to be. They should of been ignored and NEVER checked for anything including the Tile(pos) part of the code which is a bit consuming.

Again the idea is to NOT check nodes at all if we don't need to.

TL;DR
TFS pathfinding is so slow that IMO its better to use mine and try to deal with the bugs. Otherwise you are stuck with monsters following their targets so slow they aren't even a challenge OR you increase CPU usage by a crazy amount using Marks work around.
 
Last edited:
Flatlander said:
2) Pathfinding updates: This is WHEN TFS calculates a new path for a creature. If you have long-distance pathfinding (for example if you increased the screen size) or if you have really fast creatures this can cause some slowdowns. But honestly you shouldn't see much problems leaving the current TFS "as is".
Currently TFS updates pathfinding in the following situations:
a) When the following creature moves
b) When a follow target moves
c) If it has been 2 seconds since the last update
Click to expand...
Pathfinding should only be updated when the target or follower moves. We should only need to update the path for the follower on players because they are the only one that can move off the path they are given to follow. Which is also something I checked for inside my version.

All of these little things are what allowed me to squeeze out the performance differences I did.

There is no need to redo the pathfinding if the path is still good. Which TFS pathfinding system does. It will check the path even if it doesn't need to. In many different situations too. This is a part of what made it so slow.

Keep in mind this is part of the Update pathfinding call system. Not the Update pathfinding system.
 
Last edited:
Itutorial said:
Pathfinding should only be updated when the target or follower moves. We should only need to update the path for the follower on players because they are the only one that can move off the path they are given to follow. Which is also something I checked for inside my version.

All of these little things are what allowed me to squeeze out the performance differences I did.

There is no need to redo the pathfinding if the path is still good. Which TFS pathfinding system does. It will check the path even if it doesn't need to. In many different situations too. This is a part of what made it so slow.

Keep in mind this is part of the Update pathfinding call system. Not the Update pathfinding system.
Click to expand...
What if 3rd creature appeared and stands in the way that blocks path between target and follower? Or some obstacle that blocks pathfinding appears? Shouldn't you update path in those situations?
 
Trollheim said:
What if 3rd creature appeared and stands in the way that blocks path between target and follower? Or some obstacle that blocks pathfinding appears? Shouldn't you update path in those situations?
Click to expand...
Yeah I may have misspoke. I believe it also force updates on each step of the creature following a path. I could be wrong though and that is something that needs to be added.

Perhaps on each step it checks if anything has blocked the path. I am not sure what would be more efficient.

It has been a while since I tested this stuff but I am pretty sure when I did paths were able to update as needed whenever something walked in the way. As even with 100 monsters following me they were able to walk around each other.

Itutorial said:
Pathfinding should only be updated when the target or follower moves.
Click to expand...

This means when what we are following or whenever we move.

We only need to update players on every single instance when they move because they can change their path.
For a NPC we could update it only when something has blocked our current path.
 
Last edited:
Trollheim said:
What if 3rd creature appeared and stands in the way that blocks path between target and follower? Or some obstacle that blocks pathfinding appears? Shouldn't you update path in those situations?
Click to expand...
There already is onCreatureAppear function where you can update path if the creature appeared on our path. New function could be added for items (like mwall etc), onItemAppear.
 
oen432 said:
There already is onCreatureAppear function where you can update path if the creature appeared on our path. New function could be added for items (like mwall etc), onItemAppear.
Click to expand...
That would really only work for a one-time case. A creature could already be on the following creatures screen and move into the path. The onCreatureAppear wouldn't even run at that point.

Also, if it did run for some reason. The creature could move into the path multiple times. I believe onCreatureAppear only runs when a creature first enters the view range of another.
 
Itutorial said:
That would really only work for a one-time case. A creature could already be on the following creatures screen and move into the path. The onCreatureAppear wouldn't even run at that point.

Also, if it did run for some reason. The creature could move into the path multiple times. I believe onCreatureAppear only runs when a creature first enters the view range of another.
Click to expand...
Well yeah, its just for when summons are spawned or someone jumps floors for example. I haven't looked into the code but would it be expensive to check if creature blocks other creature path when the formal creature moves?
 
How about additionally to the current algo just check once per let's say 500 ms if "I reached target", if no then recalculate path finding? For monsters it could be also based on speed (not always 500 ms) so slower monsters will trigger this state slower to save some compute power. It should be much less effort then calculating it for every monster in the view range.
 
Trollheim said:
How about additionally to the current algo just check once per let's say 500 ms if "I reached target", if no then recalculate path finding? For monsters it could be also based on speed (not always 500 ms) so slower monsters will trigger this state slower to save some compute power. It should be much less effort then calculating it for every monster in the view range.
Click to expand...

Ok. I think about edge case.
Monster cast "Haste". In this case monster should change path finding interval?
 
oen432 said:
Well yeah, its just for when summons are spawned or someone jumps floors for example. I haven't looked into the code but would it be expensive to check if creature blocks other creature path when the formal creature moves?
Click to expand...
That is the whole reason I worked on the pathfinding. It's not too expensive to call it whenever you need it.
 
prioritizing of walkable tiles with highest speed could be a thing to look into, unless it already exist?
 
@Itutorial Hi again bro! I just contacted my host provider and get the conclusion that CPU usage is being too high. By any chance I can remove this from sources? Solved - Weird monster behaviour in TFS 1.1? (https://otland.net/threads/weird-monster-behaviour-in-tfs-1-1.228021/#post-2200365), I was looking up for gesior's algo 4 solution but I don't really understand it Solved - Weird monster behaviour in TFS 1.1? (https://otland.net/threads/weird-monster-behaviour-in-tfs-1-1.228021/page-3#post-2703201), any idea of which way should I take to decrease the CPU usage a little bit even if this impacts on creature's behaviour?

I really appreciate an answer, or any tip that could guide me in the correct direction. Also here's my sources in case there could be a git compare, of if there's a line that must be changed to achieve a good result. GitHub - ralke23/Greed-TFS-1.5-Downgrades at 8.60 (https://github.com/ralke23/Greed-TFS-1.5-Downgrades/tree/8.60) Thanks a lot in advance!

Regards
 

Similar threads

A
UPDATE 3: Moveitem + Antipush + Anti-Crash Elf Bot - Bug Fixes - TFS 0.4 11/04/2024
Replies
1
Views
859
Codinablack
Codinablack
johnsamir
  • Question Question
Solved two bugs generated by me where should i look for?
Replies
4
Views
293
johnsamir
johnsamir
Back
Top