[NOTICE] Upcoming Pathfinding Breaking Changes

[pushedx]

Exilebuddy's pathfinding code will finally be receiving a lot of updates for the 3.3 expansion. The current code is from 2012-2013, and contains numerous bugs, limitations, and is missing some new functionality that was added the past few years.

However, our version and settings were just "good enough" to last us as long as they did, even though there are some known issues and limitations that cause inconveniences. We think a lot of the problems will be solved by updating to the current library version, which contains literally 5 years of bug fixes and improvements.

But, that's not all. How we use the pathfinding library (its settings we use for Path of Exile) are also in need of changing. This is evident when the bot gets stuck in certain tilesets due to the pathfinding thinking it can travel through terrain, but the game client cannot. There's enough of a mismatch between client data and our setup to where this can result.

While it won't be possible to have a 100% accurate solution, things can certainly get a lot better, especially in regards to how obstacles are handled. As a result, we'll be upgrading the pathfinding code in three phases leading up to 3.3 and into the future.

Phase 1:

The first phase of the changes is updating the internal library code to the current version. This will result in very little user code changes, because the internal library code is the C++ code running behind the scenes. This is where the bulk of bug fixes and functionality improvement changes come in, and only a few people might be affected by the internal API changes because they are using the internal API for things like Lab.

Work on this phase has already begun and changes are being tested in the current Beta, but will not be deployed yet.

Phase 2:

The second phase is changing the pathfinding library wrapper to a modern version. This will result in major breaking changes to any code that uses ExilePather. The extent of these changes is not known yet, because it will take time to complete, but this is just a heads up that breaking changes to the public API are planned and required to fix some issues with the current system.

Phase 3:

The final phase is tweaking the settings and configuration of the new code so we get better results than before and try to solve some of the last big issues with Exilebuddy. There's different types of stuck issues that this game has, so this phase will focus on the pathfinding specific ones of trying to move through smaller areas that the client actually can't. There's no magic way of doing this though, so we'll have to go through each area and look for problems to try and tweak things. Since area generation tends to change on big expansions, this phase will start post-3.3.


The biggest concern with changes of this nature are things breaking and then having to be fixed. Since we have about a month to test and try out the Phase 1 changes, we should know by the time 3.3 releases how the new code is doing vs the old. However, it's time we transition to the new versions, and work out any new issues as Exilebuddy continues to evolve and improve. This has been on our todo list since 2014 when various pathfinding issues were starting to be seen, but we managed to get by to now with what we had.


Additional bug fixes and improvements will be included in upcoming builds as well. For example, in the next Beta:

• ExilePather.Reload will now recache the current terrain data when the 'force' parameter is true. Before, it did not update the terrain data cache if the area was still the same, even though the pathfinding data could have changed.
• LokiPoe.TerrainData.MarkCacheDirty added to support the previous change. The next access of TerrainData.Cache will update itself.
• The instance specific RDPathfinder.MeshChanged event handler has now been made static. This is so user code can more easily know when the mesh is changed due to obstacles being added/removed. Before, user code had to re-assign the event handler for each RDPathfinder instance, making it impractical to use.
• Various ExilePather bug fixes and minor improvements.
• Various AreaVisualizer bug fixes and minor improvements.
• Stuck issues in Ossuary where the bot tries to walk through the closed exit door should now be fully fixed.
• Stuck issues in Sewers where the bot tries to walk through the Undying Blockage should be reduced now.
• Stuck issues with Trial of Ascendancy doors should be reduced now.

None of these changes should break anything, but a few users might have minor code updates in private code. In any case, the changes should be immediately observable, as past bugs in the old AreaVisualizer made debugging things a lot harder than it should have been. Additional improvements to AreaVisualizer are planned for 3.3 to help users understand what is going on with pathfinding, but for now the bigger core updates are being worked on.

That about wraps up this post. This is just to let users/devs know of what our plans are for the 3.3 update in regards to pathfinding.

 

[pushedx]

In this post, I'll cover some of the long time known pathfinding issues, explain what the problems are, and what's being done for 3.3 in context of the upcoming breaking changes.

Ossuary Door Stuck - This issue came about because I didn't understand how the door actually worked. The room that is sealed off actually contains a hidden object in the dead center, and the doors that open when you throw the lever are actually a part of the main door. Our code assumed the obstacle was getting placed in a different location than it actually was, and the object data we were using for the door resulted in an obstacle too large for the pathfinding library to handle often. In the next beta, the logic is reworked so we place 2 obstacles where the fake doors are, which should prevent the bot from pathing through the sealed room.

Undying Blockage Stuck - This is a very large object, but it blocks a small pathway. The size of the obstacle has been manually set now to hopefully consistently block the path and avoid some of the issues where paths through the obstacle are generated due to data bugs. Since this is an object that is only really encountered once, we'll try the initial fix before spending more time to see if it needs adjustments. The next beta contains these changes.

Trial of Ascendancy Door Stuck - The issue has been the obstacle being placed was too large, based on the client object data being used, and because the pathfinding library was not marking all tiles inside the obstacle as unwalkable, paths through the obstacle can be found. In the next Beta, the obstacle size has been manually set to be much lower, and has consistently shown it should work in preventing paths being generated through the door. While the issue might not be 100% fixed, it should be a lot better than before.

Large Chest/Object Stuck - Often times in areas like Solaris or Lunaris, there's big chests wedged against a walkway that the bot gets stuck behind. This issue is due to how the pathfinding data was generated upon entering the area, when the object was not in view. When the client loads the object from the server, the client's pathfinding data gets updated, but the bot's is still outdated. Remeshing the entire area is expensive and not desirable while you're running the bot, so the bot thinks it can walk through an area it no longer can. This is not an easy problem to fix, but we'll be trying out a few things with the updated library.

Wall/Doorway Stuck - This is usually an issue where the client's movement is bugged along certain areas, so when the player mover attempts to move forward, the client does the wrong thing and the bot gets stuck along steep walls and doorways. Changes to the playermover can certainly help this, but there are side effects due to the way the game works. For example narrow stairs that turn, if the playermover is moving the character too far at once, the client would get stuck at the base of the stairs and be able to move forward. If the playermover is moving the character too close, then the client bugs kick in and break movement. Paths that try to get further away from the walls are desired, but the existing logic for that isn't so great, but is also old.

I think that about sums up most of the known pathfinding issues. There are a few other random issues, but most of them are due to client bugs with terrain data. There are certain cases where there's nothing we can do when the tiles in the game contain bugs and break the bot when it runs into them. For example, in the desert tilesets, there's a specific tile that gets placed in a way that should be impossible, so the pathfinding data in that tile is not correct and paths get generated across unwalkable areas as a result.

We hope to improve pathfinding quite a bit with the update going into 3.3, but please understand it will never be perfect because a lot of issues are a result of how the game itself works. In any event, things should be getting somewhat better in the near future and we'll finally have the big pathfinding update off the todo list!