• 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

sururuts

Member
Joined
Sep 14, 2010
Messages
56
Reaction score
22
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?
 

Diarreamental

Banned User
Joined
Jul 6, 2015
Messages
450
Solutions
1
Reaction score
80
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
 

ralke

(҂ ͠❛ ෴ ͡❛)ᕤ
Joined
Dec 17, 2011
Messages
1,211
Solutions
27
Reaction score
677
Location
Santiago - Chile
GitHub
ralke23
Twitch
ralke23
@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! ;)
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,285
Solutions
68
Reaction score
933
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:

sururuts

Member
Joined
Sep 14, 2010
Messages
56
Reaction score
22
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:

samco

4x4 Developer.
Joined
Jul 3, 2007
Messages
1,007
Solutions
9
Reaction score
229
Location
Spain
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?
 
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,285
Solutions
68
Reaction score
933
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.
 

sururuts

Member
Joined
Sep 14, 2010
Messages
56
Reaction score
22
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.
 

Felipe93

Ghost Member
Joined
Mar 21, 2015
Messages
1,991
Solutions
9
Reaction score
322
Location
Chile
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();
            }
        }
    }
}
 

sururuts

Member
Joined
Sep 14, 2010
Messages
56
Reaction score
22
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:

Felipe93

Ghost Member
Joined
Mar 21, 2015
Messages
1,991
Solutions
9
Reaction score
322
Location
Chile
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:
OP
OP
Itutorial

Itutorial

Excellent OT User
Joined
Dec 23, 2014
Messages
2,285
Solutions
68
Reaction score
933
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.
 

samco

4x4 Developer.
Joined
Jul 3, 2007
Messages
1,007
Solutions
9
Reaction score
229
Location
Spain
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
 

Felipe93

Ghost Member
Joined
Mar 21, 2015
Messages
1,991
Solutions
9
Reaction score
322
Location
Chile
Top