Any plans to make it so it will also do paths from common teleport/item teleport locations?

[FowD8]

e.g. combat bracelet, amulet of glory, achievement diary items such as addey cape?

i know this plugin updates have been kind of stale (3 months since the last update), but i'm super surprised this isn't an already existing feature?

[Skretzo]

From issue https://github.com/Skretzo/shortest-path/issues/16#issuecomment-1254233022:

This is not currently possible. It might be added in the future, but that will probably have to be combined with a substantial overhaul of the plugin.

Explanation as to why it is not yet a feature: Teleportation on its own is easy enough to add, but combining it with standard pathfinding where you walk tile by tile is quite hard. Currently, adding more teleports will actually significantly slow down the speed of the plugin. The plugin is already not very powerful, as it is merely a simple, client-sided pathfinder and not a robust server-sided implementation like e.g. Google Maps. The official OSRS Wiki has a cartography (and pathfinding) project. Maybe this is better suited for them?

[FowD8]

I haven't had a chance to look through the source code but are you not using some BFS algorithm? they're generally pretty efficient

[FowD8]

just a random thought, I wonder if it'd be more efficient to do only a 4 axis search (diagonal not being a valid path) to calculate the shortest path then use that result and "smooth" it by adding possible diagonal paths

[Skretzo]

Yes, the initial version of the plugin made by Runemoro is a plain BFS algorithm.

Cyberlarino has attempted a rewrite of the plugin which is looking very promising, but I have not had the time to look at it yet.

[FowD8]

interesting, i'll look into the source code, maybe if i have time i can try to contribute, thanks

[Skretzo]

just a random thought, I wonder if it'd be more efficient to do only a 4 axis search (diagonal not being a valid path) to calculate the shortest path then use that result and "smooth" it by adding possible diagonal paths

The intention of the plugin is to reproduce in-game pathfinding perfectly. Maybe this is unreasonable in the long run?

[FowD8]

The intention of the plugin is to reproduce in-game pathfinding perfectly. Maybe this is unreasonable in the long run?

yeah i was thinking that, if you only search the shortest path by 4 axis directions and then run a "smoothing" algorithm, then there's probably a few cases where it wouldn't technically be the absolute shortest path

but honestly, i think in like 99% of cases, it'd still be the shortest path while reducing calculations exponentially (not just by 1/2, because while you're removing half the possible directions, it'll propagate exponentially through the BFS recursive function). and i'd imagine a smoothing algorithm would be fairly low cost efficient O(log N)

so yeah.. i guess it'd be a matter of if you want to be technically absolutely shortest path, or, shortest path 99% of the time but waaay more efficient

[Skretzo]

I am open to changing the pathfinding if it becomes much more efficient, but many users of the plugin would maybe not trust the name of the plugin anymore if your in-game character suddenly takes frequent detours from the highlighted path.

You clearly know more than me about graph theory so maybe you should talk to wiki admin Cook Me Plox who is looking for graph algorithm wizards. Here is a link to the wiki pathfinding project document, which is probably interesting for you.

[SpecialMike]

I'd like to revisit this now that it seems like a lot of improvements were done to the pathfinding algorithm. I put together a PoC for using items from your inventory/equips to teleport and it doesn't seem to have much of an effect on performance with just the teleportation jewelry data (9 items, 32 destinations that I am able to test and Ardougne Cloak 1). Using it with the Ardougne Cloak and nearby fairy ring and spirit tree has really made a lot of trips easier.

As for having users pick which items are used for teleportation, I was thinking of having a dropdown for this feature with options:

• No item teleports
• Item teleports in inventory (non-consumable)
• Item teleports in inventory
• All item teleports

Item use is communicated to the user is by re-using the transport detail rendering from #65 at the location the user is at. It worked out well as a byproduct of how the item transportation is done - refreshTransportData inserts transports that are from the player's inventory.

For example: and

Just wanted to get some feedback before putting it in a PR - unless you'd like me to go ahead and do that. I need to actually make the option, and I'd like to get a lot more item teleportation data in before merging it.

[FowD8]

that's probably a really good idea to be able to pick just items in inventory or all items, makes it so you can pick and choose if you want to go grab stuff or just based on what you can currently do

On Fri, Mar 8, 2024, 8:42 PM Michael Chisolm @.***> wrote:

I'd like to revisit this now that it seems like a lot of improvements were done to the pathfinding algorithm. I put together a PoC for using items from your inventory/equips to teleport and it doesn't seem to have much of an effect on performance with just the teleportation jewelry data (9 items, 32 destinations that I am able to test and Ardougne Cloak 1). Using it with the Ardougne Cloak and nearby fairy ring and spirit tree has really made a lot of trips easier.

As for having users pick which items are used for teleportation, I was thinking of having a dropdown for this feature with options:

• No item teleports
• Item teleports in inventory (non-consumable)
• Item teleports in inventory
• All item teleports

Item use is communicated to the user is by re-using the transport detail rendering from #65 https://github.com/Skretzo/shortest-path/pull/65 at the location the user is at. It worked out well as a byproduct of how the item transportation is done - refreshTransportData inserts transports that are from the player's inventory.

For example: image.png (view on web) https://github.com/Skretzo/shortest-path/assets/12124561/49108541-6420-49c5-95f4-668482825e87 and image.png (view on web) https://github.com/Skretzo/shortest-path/assets/12124561/2c2967d8-817c-46c1-a16a-f74c1815394d

Just wanted to get some feedback before putting it in a PR - unless you'd like me to go ahead and do that. I need to actually make the option, and I'd like to get a lot more item teleportation data in before merging it.

— Reply to this email directly, view it on GitHub https://github.com/Skretzo/shortest-path/issues/27#issuecomment-1986682654, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACCEHA7W7OIMTWFLH5IZQ63YXJSHHAVCNFSM6AAAAAATHFJEJ6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSOBWGY4DENRVGQ . You are receiving this because you modified the open/close state.Message ID: @.***>

[Skretzo]

Yes, teleports would be a good addition to this plugin now that it is able to handle it.

Any reason why you chose not to include two options for all item teleports, e.g. All item teleports (non-consumable) and All item teleports?

Also, why does your example image have ===== under the destination info? When displaying transports a = is used to indicate that it goes up or down a plane, e.g. z=0 to z=1, but those item teleports don't do that in your examples? Edit: you are right, I forgot how it worked.

[SpecialMike]

I actually found a bug in the transport rendering code that I fixed in that screenshot, but = is supposed to be if the plane stays the same, + and - if the plane is different. Currently, renderTransports is comparing the transports' origin with itself. In that case, I had the ardy cloak 1 and an amulet of glory for 5 destinations at that location.

I like splitting All item teleports up into consumable and non-consumable as well. I'd imagine in the future, the user could set a cost threshold for teleports (probably gp/distance), but I guess we'd have to wait until plugin communication is a possibility so this plugin can get price info.

The other remaining issue on this is around the wilderness. The fastest path would likely be to run to the closest non-wilderness tile or wilderness level < 20 (30 for some cases), then use the item. The only ways I can think of to do this are to either:

• Do a first pass to just find that nearest tile you can teleport from, then setup the transports at that location. The first pass would likely be fairly quick, since the destination tile we're looking for wouldn't be too far away. Being a BFS pathfinder, it wouldn't take much to refactor it to have a different mode where it's searching for a tile destination and end as soon as it's found.
• Detect that the player's in the wilderness at level > 20 when the pathfinder runs, then as soon as the player is somewhere that a teleport is possible, re-run the pathfinder with the item transports. This won't be the absolute shortest path, but better than the final option.
• Just don't worry about item teleportation in the wilderness level > 20.

Edit: I may actually be able to defer adding item transports until the first valid teleportation tile is encountered in addNeighbor to solve this.

[SpecialMike]

Ok, I got wilderness working well I think. This is an example shortest path to the GE from a random spot in the wilderness with an amulet of glory in the inventory (before I fixed the amulet to be able to teleport from < level 30):

Not 100% sure I got the exact spot where wilderness level 20 starts, still have to double check that 😅. I'll get that and the user options done then submit a PR.