Help with pathfinding

[Empyrean GB 7]

Hello everyone,

I've got a question centralized around what should have been Shakespeare's true question. To walk or not to walk.

In my script my agent has to travel from Location A to Location B quite often. Which raises the question. What's the most efficient way to accomplish this.

I've tried to find this out and come to some sort of a solution(which most definetly has it's shortcommings) 

 

My approach for now:

I got an own implementation of an Location which contains:

The Area its in, A List<IQuickTravelMethod> with potential shortcuts to this location.(Some child classes have more fields and overwite it's methods but for this post that isn't relevant)

The Location class also contains a travelTo() method. which basically does the following:

Determine the distance I would have to walk without shortcuts

For each shortcut: Can I use this shortcut and if so estimate the distance.

 

I got an IQuickTravelMethod interface which is for example implemented by the StandardSpellBookTeleport class.

The interface contains methods like: canUse(), gotItems(), estimeDistance(Location goal)

An implementation of this class would have a startingArea(from where can I use this shortcut), a targetArea(where do I end up if I use this shortcut)

And it implements the methods to see or the player meets the requirments(quest/level/whatevs) to use the shortcut, the player has the required gear in his inventory and an estimate distance which calculates the distance the player would need to walk to get to the goal if using this method(using the gotItems it can determine or it first has to travel to the closest bank and add this distance)

 

So in a way I can determine or it would be quicker to walk or to use a teleport or anything. However even though this is the only true solution I could come up with I think that it's a bad one. The obvious shortcommings:

-Every place where I use a Location I gotta manually add every IQuickTravelMethod associated with it.

-Chaining IQuickTravelMethods is quite hard(imagine I want to go from east of desert gate to mudskipper point. If it doesn't chain the gate shortcut and the Shanty pass NPC shortcut it would probably decide to walk the whole way as a f2p player)

-There's some shortcuts which have multiple start/end points(kanoos, wildy towers, fairy rings) For now I've no real clue on how to implement this except for changing the startingArea and targetArea to a list and having a loop city.(Don't think that's big O notation friendly)

 

I've tried looking online a bit on the matter but I did not really find a better way(which might be because I've never done anything with pathfinding lol). I did see something about an A* algoritm and stuff of which I've never heard but it seemed like a lot to read into and I'd rather here your guys opinion first on what would be a better way so I can target my research to the sugested method.

 

I hope that someone out there got's a sugestion paired with some google search terms/maybe an example

-EmpyreanGB

 

[Empyrean GB 7]

For those wondering a weighted graph paired with AStar works like a charm. After some modifications that is.