• 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

omaraboud said:
@Itutorial The last commit from yesterday causes crash as soon as player sees monster
Click to expand...
I have to do some more testing on it. So far I haven't had any problems including the one you mentioned but I will try some more things to cause problems.

What OS are you running your server on?

edit: I can't reproduce the crash
 
Last edited:
ralke said:
working on it, I did a clean merge, also adding his latest commits to reduce memory but I encountered two segmentation faults.

let's just be patient, @Itutorial is doing great job here
Click to expand...
thank you very much can you shre that distro or is the same one as the previous commits?
 
johnsamir said:
thank you very much can you shre that distro or is the same one as the previous commits?
Click to expand...
we're using pms so we don't spam the thread, this one is my own private repository but i'll do the merge on Greed fork as soon it works just fine (to don't merge unnecessary changes and keep it clean). But is what @omaraboud says, it crashes as soon an attack is done (either by monster or player).
 
We had an amazing session with @Itutorial, he merged the algorythm to my fork, with excellent results.
  • Checked summon behaviour, now it follows the master properly (with adjustable delay of thinking at PATH_INTERVAL/THINK_INTERVAL)
  • Checked memory usage luring monsters on screen
  • Checked map walk path and player's pathfinding
  • Checked monster behaviour
Everything worked amazing, much more faster, much more accurate, with less memory usage.
Now we need more people to test it, here's the cleanest merge I was able to upload:

github.com

NRH-AA Pathfinding · ralke23/Greed-TFS-1.5-Downgrades@570c4d7

Clean-up of pathfinding code. Made by Nathan Heinz (NRH-AA). Co-Authored-By: Nathan Heinz <[email protected]>
github.com github.com

Anything just PM me (or @Itutorial if he's avaible).
Have fun with the code! And so much thanks for making this possible @Itutorial

1712890321382.png

Regards!
 
More updates on this. First I highly recommend to disable windows update (if you're running on windows) before using this change.
  • Press the Windows key + R, type services.msc in the run bar, and press the Enter key
  • In the list of processes, locate Windows Update and open it by clicking on it.
  • To deactivate it, in the "General" tab, look for the "Startup type" field and change it to "Disabled.
  • Restart your PC, and automatic updates will be a thing of the past.
The following video shows the pathfinding running at
C++: 
static constexpr int32_t EVENT_CREATURE_THINK_INTERVAL = 200;
static constexpr int32_t EVENT_CREATURE_PATH_INTERVAL = 200;

I tracked the memory usage at the side. I really didn't want it to be interrupted by any windows proccess (as possible). This was the outcome with 1 player, i'll be tracking with more players this week, but it seems to be hold at 80%. I don't recommend to run think/path intervals in "2000", at "500" the monsters overthink a little bit before moving. My best try at the moment was on 200/200, if this memory usage can be holded at 80% like it's shown in the video i'll keep it (or also try lower values, will see...)

 
ralke said:
More updates on this. First I highly recommend to disable windows update (if you're running on windows) before using this change.
  • Press the Windows key + R, type services.msc in the run bar, and press the Enter key
  • In the list of processes, locate Windows Update and open it by clicking on it.
  • To deactivate it, in the "General" tab, look for the "Startup type" field and change it to "Disabled.
  • Restart your PC, and automatic updates will be a thing of the past.
The following video shows the pathfinding running at
C++: 
static constexpr int32_t EVENT_CREATURE_THINK_INTERVAL = 200;
static constexpr int32_t EVENT_CREATURE_PATH_INTERVAL = 200;

I tracked the memory usage at the side. I really didn't want it to be interrupted by any windows proccess (as possible). This was the outcome with 1 player, i'll be tracking with more players this week, but it seems to be hold at 80%. I don't recommend to run think/path intervals in "2000", at "500" the monsters overthink a little bit before moving. My best try at the moment was on 200/200, if this memory usage can be holded at 80% like it's shown in the video i'll keep it (or also try lower values, will see...)

Click to expand...
Do benchmarks before and after
 
Stanos said:
Do benchmarks before and after
Click to expand...
The video I attached in the upper post is still being processed (your comment just came before it ended the process hehe). But here's a before (a test with this last commit added 8 months ago) Fir3lement 0.4 goToFollowCreature · ralke23/Greed-TFS-1.5-Downgrades@404c478 (https://github.com/ralke23/Greed-TFS-1.5-Downgrades/commit/404c478dd10811a9a2275bce9e0b94c18df0923c)) in the following video:


Unfortunatelly that time I tested it with Warlocks, but you can easily notice how "sticky" the monsters now are in comparission to before. Behemoths are glued to the character's pathfiding, meanwhile, Warlocks seems to be taking really good routes, but they can't hold the target like the new pathfinding does. Notice how I walk far from Warlocks and make them loose target, I bet that would not happen now (the warlock probably do a sticky follow from far).

We also tested fleeing monsters with @Itutorial but this material is enough to give it a try and bring more feedback.

Regards!
 
Last edited:
ralke said:
The video I attached in the upper post is still being processed (your comment just came before it ended the process hehe). But here's a before (a test with this last commit added 8 months ago) Fir3lement 0.4 goToFollowCreature · ralke23/Greed-TFS-1.5-Downgrades@404c478 (https://github.com/ralke23/Greed-TFS-1.5-Downgrades/commit/404c478dd10811a9a2275bce9e0b94c18df0923c)) in the following video:


Unfortunatelly that time I tested it with Warlocks, but you can easily notice how "sticky" the monsters now are in comparission to before. Behemoths are glued to the character's pathfiding, meanwhile, Warlocks seems to be taking really good routes, but they can't hold the target like the new pathfinding does. Notice how I walk far from Warlocks and make them loose target, I bet that would not happen now (the warlock probably do a sticky follow from far).

We also tested fleeing monsters with @Itutorial but this material is enough to give it a try and bring more feedback.

Regards!
Click to expand...
Indeed, it appears better, but I'm particularly interested in how much it has improved RAM usage, as it's one of my main concerns
 
ralke said:
More updates on this. First I highly recommend to disable windows update (if you're running on windows) before using this change.
  • Press the Windows key + R, type services.msc in the run bar, and press the Enter key
  • In the list of processes, locate Windows Update and open it by clicking on it.
  • To deactivate it, in the "General" tab, look for the "Startup type" field and change it to "Disabled.
  • Restart your PC, and automatic updates will be a thing of the past.
The following video shows the pathfinding running at
C++: 
static constexpr int32_t EVENT_CREATURE_THINK_INTERVAL = 200;
static constexpr int32_t EVENT_CREATURE_PATH_INTERVAL = 200;

I tracked the memory usage at the side. I really didn't want it to be interrupted by any windows proccess (as possible). This was the outcome with 1 player, i'll be tracking with more players this week, but it seems to be hold at 80%. I don't recommend to run think/path intervals in "2000", at "500" the monsters overthink a little bit before moving. My best try at the moment was on 200/200, if this memory usage can be holded at 80% like it's shown in the video i'll keep it (or also try lower values, will see...)

Click to expand...
You should be able to leave the THINK_INTERVAL at 1000. It shouldn't effect pathfinding in any way. Make sure to update with the newest commits today. I fixed a couple problems. The system should be working 100%. Only time and testing will tell now.

Additionally, you should leave the PATH_INTERVAL at 500-1000. The only time PATH_INTERVAL really does anything is when you stop walking or if the path to the character is blocked, then unblocked. (for instance a door opening and closing). The monster will have a delay to start chasing you which is the PATH_INTERVAL delay. Unless you walk after opening the door which will cause it to update as soon as you do.

Having the path interval any faster than 500ms will be depreciating results. Increasing the CPU and ram usage for only minor gains in reaction speed of the monsters.

With that being said, the new algorithm is 2x-100x faster than the previous one depending on the path. Faster meaning the CPU can process the path faster. As for how much memory is being allocated (ram performance) it is around the same 2x-100x because we are storing and iterating over a lot less nodes to draw the paths.
Post automatically merged:

Stanos said:
Do benchmarks before and after
Click to expand...
You can see some bench marks on the pull request for the main repo


 
Last edited:
Itutorial said:
You should be able to leave the THINK_INTERVAL at 1000. It shouldn't effect pathfinding in any way. Make sure to update with the newest commits today. I fixed a couple problems. The system should be working 100%. Only time and testing will tell now.

Additionally, you should leave the PATH_INTERVAL at 500-1000. The only time PATH_INTERVAL really does anything is when you stop walking or if the path to the character is blocked, then unblocked. (for instance a door opening and closing). The monster will have a delay to start chasing you which is the PATH_INTERVAL delay. Unless you walk after opening the door which will cause it to update as soon as you do.

Having the path interval any faster than 500ms will be depreciating results. Increasing the CPU and ram usage for only minor gains in reaction speed of the monsters.

With that being said, the new algorithm is 2x-100x faster than the previous one depending on the path. Faster meaning the CPU can process the path faster. As for how much memory is being allocated (ram performance) it is around the same 2x-100x because we are storing and iterating over a lot less nodes to draw the paths.
Post automatically merged:


You can see some bench marks on the pull request for the main repo


Click to expand...
I love the videos @ralke and @Itutorial ! It's great to see the monsters finally being responsive!

I am highly appreciative of the work you guys have done, with both coding and testing, and everyone else who contributed to this cause by testing and sharing results! This is amazing work!

I just had to say thank you!
 
ralke said:
The video I attached in the upper post is still being processed (your comment just came before it ended the process hehe). But here's a before (a test with this last commit added 8 months ago) Fir3lement 0.4 goToFollowCreature · ralke23/Greed-TFS-1.5-Downgrades@404c478 (https://github.com/ralke23/Greed-TFS-1.5-Downgrades/commit/404c478dd10811a9a2275bce9e0b94c18df0923c)) in the following video:


Unfortunatelly that time I tested it with Warlocks, but you can easily notice how "sticky" the monsters now are in comparission to before. Behemoths are glued to the character's pathfiding, meanwhile, Warlocks seems to be taking really good routes, but they can't hold the target like the new pathfinding does. Notice how I walk far from Warlocks and make them loose target, I bet that would not happen now (the warlock probably do a sticky follow from far).

We also tested fleeing monsters with @Itutorial but this material is enough to give it a try and bring more feedback.

Regards!
Click to expand...
sorry to both
but these are the commits that we should add to our repositories?

  • ralke23    ralke23
    committed7 hours ago



    af9bbe3

  • NRH-AA Pathfinding​


    ralke23
    NRH-AA

    ralke23
    and
    NRH-AA
    committed15 hours ago



    570c4d7

Commits on Aug 24, 2023​


Commits on Aug 5, 2023​

 
Itutorial said:
These are the only changes you should have.
github.com

Optimize pathfinding by NRH-AA · Pull Request #4637 · otland/forgottenserver

Pull Request Prelude I have followed proper The Forgotten Server code styling. I have read and understood the contribution guidelines before making this PR. I am aware that this PR may be clo...
github.com github.com
Click to expand...
Followed the changes, using this commit (I noticed I had my own fork too much modified due the last pathfinding implementation, I mean, when the thread started like months ago). This was the outcome:

github.com

First adjustments on NRH-A Pathfinding · ralke23/Greed-TFS-1.5-Downgrades@d5670ec

There was some missing code that was needed to be merged, related mostly to map.cpp and A* Nodes. Co-Authored-By: Nathan Heinz <[email protected]>
github.com github.com

I only hesistate at this line:
C++: 
if (!lookUpdated && lastMeleeAttack == 0 && !isFleeing()) {

I remember that for some reason we used this instead:
C++: 
if (updateLook && lastMeleeAttack == 0 && !isFleeing()) {

I kept updateLook to prevent errors. But everything worked just fine.
Now, in testing enviroment I have a trouble I recorded here. When monsters have an open door, they don't choose to go for the player, I mean, they "overthink it". I suppose I must play with:

Itutorial said:
The monster will have a delay to start chasing you which is the PATH_INTERVAL delay.
Click to expand...

Anyways recorded this video for anyone who wants to try other PATH_INTERVAL values, I definitely going to decrease it a little bit, noticed ram usage was barely the same (at least with low players). As @Itutorial said this can only be properly tested with time. For sure I will not get less than 500 so we can get our best results!


PS: I also wonder what would happen if we increase sight range for monsters, so monsters that are inside walls, but have a clear path, can actually get to you. I recorded this too to show some of those situations (the test was a bit exaggerated and not so accurate, but I think the idea is there xD).


Itutorial said:
Additionally, you should leave the PATH_INTERVAL at 500-1000. The only time PATH_INTERVAL really does anything is when you stop walking or if the path to the character is blocked, then unblocked. (for instance a door opening and closing). The monster will have a delay to start chasing you which is the PATH_INTERVAL delay. Unless you walk after opening the door which will cause it to update as soon as you do.
Click to expand...
Now I tested this a bit further, I found it really important in enviroment like the one that is recorded on the video. This is only my first thoughts, but if the value is too high the pathfinding is too dependant of when you step. So being holding position can be used to confuse creature's pathfinding. Anyways, we can discuss about all this later on discord!

Thanks a lot again bro
Regards! ^^
 
Last edited:
I will look for a solution to this today. I am just trying to figure out a good time to update the path that isn't related to when the path changes (follow creature walks) and won't call paths too often. I am thinking I will have to update:

C++: 
void Creature::forceUpdatePath()
{
    if (!attackedCreature && !followCreature) {
        return;
    }

    g_dispatcher.addTask(createTask([id = getID()]() { g_game.updateCreatureWalk(id); }));
}

to

C++: 
void Creature::forceUpdatePath()
{
    if (attackedCreature || followCreature) {
        const Position& position = attackedCreature ? attackedCreature->getPosition() : followCreature->getPosition();

        if (g_game.isSightClear(getPosition(), position, true)) {
            g_dispatcher.addTask(createTask([id = getID()]() { g_game.updateCreatureWalk(id); }));
        }
    }
}

Then we can set

C++: 
static constexpr int32_t EVENT_CREATURE_PATH_INTERVAL = 200;

Without causing too much work for the cpu.
 
Mateus Robeerto said:
@Itutorial Observe the monster's behavior... What do you mean? Was it good? Or should I make changes again?
Click to expand...
That looks good to me but at the same time I don't play RL tibia which I know is what we aim for. I would still make the the two changes I made today on the official PR. They are kind of critical and shouldn't change the behavior you just showed it will however fix a couple lags in pathfinding updates.

github.com

Optimize pathfinding by NRH-AA · Pull Request #4637 · otland/forgottenserver

Pull Request Prelude I have followed proper The Forgotten Server code styling. I have read and understood the contribution guidelines before making this PR. I am aware that this PR may be clo...
github.com github.com
github.com

Optimize pathfinding by NRH-AA · Pull Request #4637 · otland/forgottenserver

Pull Request Prelude I have followed proper The Forgotten Server code styling. I have read and understood the contribution guidelines before making this PR. I am aware that this PR may be clo...
github.com github.com
 
Itutorial said:
That looks good to me but at the same time I don't play RL tibia which I know is what we aim for. I would still make the the two changes I made today on the official PR. They are kind of critical and shouldn't change the behavior you just showed it will however fix a couple lags in pathfinding updates.

github.com

Optimize pathfinding by NRH-AA · Pull Request #4637 · otland/forgottenserver

Pull Request Prelude I have followed proper The Forgotten Server code styling. I have read and understood the contribution guidelines before making this PR. I am aware that this PR may be clo...
github.com github.com
github.com

Optimize pathfinding by NRH-AA · Pull Request #4637 · otland/forgottenserver

Pull Request Prelude I have followed proper The Forgotten Server code styling. I have read and understood the contribution guidelines before making this PR. I am aware that this PR may be clo...
github.com github.com
Click to expand...
I've already made the changes, all good, that you sent with the two PR links... they seem very good. I haven't noticed anything causing CPU abuse or something similar... it's at 0%. I added many monsters and tested it, and it's still at 0% and 05%. It didn't cause any problems... it's working perfectly. It seems good... Now I want to put it on a VPS to see how it works... Thank you for your work.
 

Similar threads

alexxxxxxx
UPDATE 3: Moveitem + Antipush + Anti-Crash Elf Bot - Bug Fixes - TFS 0.4 11/04/2024
Replies
1
Views
290
Codinablack
Codinablack
P
  • Question
OTclientv8 + TFS 1.2: "ERROR: no creature found to move"
Replies
2
Views
633
pigeonchk
P
Lbtg
  • Question
Lua Convert mock portgun script to revscript
Replies
0
Views
271
Lbtg
Lbtg
J
  • Question
FireStorm Event
Replies
0
Views
367
jareczekjsp
J
Mateus Robeerto
[TFS 1.3+] Snowball Event Revscripts
Replies
15
Views
1K
abdala ragab
abdala ragab
J
  • Question
Autoloot problem
Replies
4
Views
378
jareczekjsp
J
J
  • Question
Snowball tfs 1.5 Problem
2
Replies
33
Views
1K
Heroid
Heroid
mar173
[GUIDE] [OTCV8] [TIBIA 13 MINIMAP LOADER] Easy load minimap from tibiamaps.io or gunzodus
Replies
1
Views
858
Reon
R
Back
Top