• 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
21
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,202
Solutions
27
Reaction score
671
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,279
Solutions
68
Reaction score
919
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
21
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
993
Solutions
9
Reaction score
225
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,279
Solutions
68
Reaction score
919
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
21
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,825
Solutions
9
Reaction score
301
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
21
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:
Top