Optimize pathfinding

[NRH-AA]

Pull Request Prelude

• [x] I have followed proper The Forgotten Server code styling.
• [x] I have read and understood the contribution guidelines before making this PR.
• [x] I am aware that this PR may be closed if the above-mentioned criteria are not fulfilled.

Changes Proposed

This is a overhaul of when and how pathfinding is done. I did attempt this before but I closed the pull request due to congestion. I believe all problems from the original pull request have been fixed.

This will change the pathfinding to work as A* algorithm rather than djikstra's. It will also add more pathfinding calls as needed fixing monster moving around slowly due to 1 second pathfinding interval. This PR also includes separation of when creatures will update their path from creatures onThink. Lastly it includes some fixes for bugs which were not detectable until pathfinding was able to be called more often.

Issues addressed: Might fix: #4617

[MillhioreBT]

I did a quick test but this PR doesn't work, the monsters walk randomly and move away from the target slowly until they disappear from sight, and the summons don't have any type of movement.

[NRH-AA]

I did a quick test but this PR doesn't work, the monsters walk randomly and move away from the target slowly until they disappear from sight, and the summons don't have any type of movement.

Seems to be fixed now. I just overlooked the method call in game.cpp.

[NRH-AA]

Alright, the code is in a good spot imo. I removed some of the functionality with checking if the path is blocked or not. Given the speed of the algorithm is far faster, actually works like A*, and I tried to mimic the patterns of the previous code. The next thing at this point I think is adding a vector or list for creatures that are attacking/following a target so whenever that target moves it updates all the paths of the creatures attacking/following it. Then we can slow down the rate paths are drawn by EVENT_CREATURE_PATH_INTERVAL because we will know we have the most current path to the target any time it moves.

With that being said here is a detailed list of where we see major improvements: 1) We are no longer assigning 512 nodes into memory without using them. 2) We are not looping through all nodes O(n) to find the best one. We are sorting them O(log n) and O(1) to select/remove the best node from the list 3) We are using half or less nodes to create paths because the old algorithm checked in a circle rather than using target position 4) Paths that are close to a straight line use D(3) nodes with D being the distance to the target instead of D(8) 5) With a fraction of the nodes being stored compared to before obviously sorting, and search happen far faster. 6) Paths can be drawn when ever needed instead of being linked to onThink.

This has been a passion project of mine for a while now. I want to thank everyone that has tested and help me improve the code by pointing out things I don't see.

[NRH-AA]

Alright, I made the final edits. Here is what was added:

1) Create a list to store creatures that are following/attack so we can update their paths with onWalk. 2) Slow down forceUpdatePath to 2000ms. This is just to fix weird situations like opening a door that was blocking path. 3) Upgraded the algorithm to use Euclidean distance. Increased performance even more and made paths a little more realistic

I tested many situations and was not able to find any problems. Here is a print out of the speed of the algorithm.

https://pastebin.com/hgtgTGBf

[Codinablack]

This is great! You definitely spent a lot of time working through all the problem! Thank you! @NRH-AA

[NRH-AA]

I had to move back to standard A apparently with the way we are using A we can't follow the Euclidean algorithm. Tested again and everything is working well including diag paths which was a problem with Euclidean.

Unfortunately we are back to a more "robotic" looking path system. I vote the trade off for performance is worth. Up to the TFS devs to decide if it is.

Here are the new calculation times: CURRENT TFS PATHFINDING: https://pastebin.com/uVJXTMzk BEST CASE: [DISTANCE]: 15 [Calculated In]: 348 Iterations and 264700 nanoseconds WORST CASE: [DISTANCE]: 15 [Calculated In]: 348 Iterations and 301800 nanoseconds

NEW PATHFINDING: https://pastebin.com/QSUejanv BEST CASE: [DISTANCE]: 15 [Calculated In]: 42 Iterations and 33300 nanoseconds WORST CASE: [DISTANCE]: 15 [Calculated In]: 80 Iterations and 81000 nanoseconds

I deem this RFR

[NRH-AA]

If I could get some help with why I am getting creature is defined but never used from the compilers in the setFollowCreature and setAttackedCreature. This is a little outside my knowledge base as creature is both defined and used :D

[Codinablack]

I can't see any logical error with the code, but I am thinking you may be able to fix it if you rename the parameter "creature" to "target" and then drop the attackedcreature = creature line, and change creature::setFollowCreature(this), to maybe target->addFollowedByCreature(this)

I am not totally sure this will work, but it seems the "label" can also be an error/warning when the method you are calling isn't used properly.... it also seems like with the Creature being the class, and creature being a parameter, perhaps it's too confusing? I am unsure, but I think that maybe those changes might resolve the warnings (which are turned into errors because of compiler flags)

[floki21uu]

The path is calculated wrongly now:

[Codinablack]

The path is calculated wrongly now:

I don't think that is wrong... I don't recall a snake deciding to walk at angles over and over again until it reaches someone because they are four squares away at an angle (this would take all day). I did quite a bit of kiting as I played a paladin, and I am certain that creatures never walk at angles unless they have no other option, and will also take the fastest path (depending on terrain), which will often times lead them to walk the exact way you are saying is the "wrong way" (due to less turns being faster)..

[EvilHero90]

The path is calculated wrongly now:

Monsters never move diagonal unless there is no other way to reach the target, atleast I have never seen that

[NRH-AA]

The path is calculated wrongly now:

This was correct. The algorithm was choosing a path that was longer than the best one which would be to move south and east to the target. Instead of moving in a straight line east then south. This is now fixed with the new algorithm. Should be gtg.

Happy hunting

[NRH-AA]

https://youtu.be/QjCR51DXTJ4

[floki21uu]

Locked 2 monsters within the square of walls. The monsters look for the path even if they are in the building - is it intended?

[floki21uu]

Also another BUG, weird monster behaviour:

[floki21uu]

Also it's possible again to do this trick:

[NRH-AA]

Not sure how I missed adding the last change here. Good catch.

As for the monster walking around the bush it will have to be fixed in another PR as it is not really related to this one.

[NRH-AA]

Alright, I believe it is ready now. I will have to look into monsters being able to get stuck around bushes in another PR. It will involve blocking pathfinding after a certain amount of failed attempts and allowing the creature to just finish the path before updating pathfinding again. With all the things that are fixed I believe that one trade off is worth it until I fix it.

All those last commits are just code optimizations and improving some of the old systems in pathfinding to allow paths that weren't allowed before. Also adding a delay in the forceUpdatePath which allows us to call it more often and have more responsive monsters, especially summons.

[NRH-AA]

Just a few minor touch ups, after which I will adapt the commit to my server and do some testing myself before giving one more final approval, as it does seem to be more things that need addressed discovered daily on this one.

All in all. Good bleeping work!

Its true that new things are discovered but the main problem is that the whole system that has to do with pathfinding needs to be recreated. I am trying to get everything working with the smallest amount of edits so that the touch ups can be done in later PR's. Then again maybe I should just revamp the whole system completely.

In the end the idea is to be able to remove things like getDistanceStep and utilize hasFollowPath, ect correctly. The code from the old system is making this kind of like putting two puzzle pieces together that do not fit.

Maybe if we can decide if the current state of the code is adequate I can focus on modifying all of the other stuff that can be changed in this PR before it gets pushed.

[NRH-AA]

Okay, with the last commit I made it so we can allow paths to be drawn farther but also lock monsters to follow the viewport + 1sqm system.

[floki21uu]

Okay, with the last commit I made it so we can allow paths to be drawn farther but also lock monsters to follow the viewport + 1sqm system.

I've tested the code in multiple ways, it works very well.

[Codinablack]

I read on otland like three minutes ago ralke said this thing has a major memory leak somewhere?

[NRH-AA]

I am on it.

[NRH-AA]

Memory leak fixed

[floki21uu]

BUG: after changing the floor for the first time, monsters have a slow walk reaction. If the monsters had seen you before, they will have the correct walk reaction.

[NRH-AA]

BUG: after changing the floor for the first time, monsters have a slow walk reaction. If the monsters had seen you before, they will have the correct walk reaction.

I am still looking into this but I seriously doubt this problem is created from this PR. The only reason you are noticing it more now is because monsters have faster reactions in 99% of cases compared to base repo

[NRH-AA]

The new constexpr update seems to have destroyed this

edit: I think changing int_fast32_t, ect is the problem.

[NRH-AA]

Can someone test the last commit. I think this should fix the pathfinding again. I also tried to fix the reaction speed when a monster first targets a player that has changed floors. @floki21uu

Keep in mind you will need to have updated to the new constexpr position methods.

[NRH-AA]

std::sqrt is running almost 3x faster than std::hypot

[ranisalt]

edit: I think changing int_fast32_t, ect is the problem.

FP math is orders of magnitude slower than integer math. I don't see why you changed the get*Cost functions to use doubles without changing how they work.

std::sqrt is running almost 3x faster than std::hypot

How did you measure it?

[NRH-AA]

edit: I think changing int_fast32_t, ect is the problem.

FP math is orders of magnitude slower than integer math. I don't see why you changed the get*Cost functions to use doubles without changing how they work.

std::sqrt is running almost 3x faster than std::hypot

How did you measure it?

I used time measurements strictly around the sqrt operation. I checked 1sqm-100sqm paths. I also created a small project just as a frame of reference using only the sqrt and hypot so there wasn't any additional bloatware. All instances were 2-3x faster from what I saw. I also tried different data types with integers giving the best results with sqrt being 3-4x faster. With that being said, I am not aware of tools, ect that can be used so its just based on time measurements. Someone with more experience may be able to look into it more.

As for what I changed to double I can revert some of the code back to using integers. I didn't realize I should leave out the heuristic from the g (walk) cost and place it in its own variable. However, I do think leaving the heuristic as a double is best as from everything I read about path finding the more precise the better for the heuristic. In other words I am still learning and did some things that weren't needed. I also didn't know it was done using order of magnitude which I am assuming is referencing the extra cost for fields and destroying creatures

5 Iterations

100k iterations

Edit: I have tried moving back to integers for the walk cost function and the result is that because of how big of a difference the integers are compared to the result of our heuristic the algorithm can no longer find the path properly. So keeping the walk cost as a float or double seems to be the best option and we will have to modify the extra costs to work properly assuming they dont. I do think it works as expected though because I have just divided the values by 10.

We also may be able to just *10 the dx and dy before running sqrt on it as well.

[floki21uu]

The new constexpr update seems to have destroyed this

edit: I think changing int_fast32_t, ect is the problem.

destroyed what?

[NRH-AA]

The new constexpr update seems to have destroyed this edit: I think changing int_fast32_t, ect is the problem.

destroyed what?

The path finding stopped working with @ranisalt's constexpr position change. I did revert the datatype changes in this repo for pathmatching so I think it should be working properly again.

[NRH-AA]

Lets get this added peeps

[Codinablack]

When you made this using the constexpr positions you had problems. It seems there were problems with that commit that have since been fixed, have you tried using the current version of the constexpr positions?

[NRH-AA]

When you made this using the constexpr positions you had problems. It seems there were problems with that commit that have since been fixed, have you tried using the current version of the constexpr positions?

Yes, and the fixes did solve the problem. The system works as it is so I will push updates to get it ready to merge with tfs master when people have tested it and say it can be merged once its updated to lastest commits. I can't keep doing micro updates.

[EvilHero90]

Feel free to update this, once 1.6 is released it'll be merged directly into 1.7 dev cycle