Advanced pathfinding with teleports/shortcuts

[DragonAlpha]

Doing A* pathfinding with a web is pretty good. A* heuristic ensures that the most likely path is taken being more efficient.

 

Let's take the Manhattan heuristic. Where the node closest to the goal node is considered the most likely/valuable one. What about when you are trying to write a web-walker-and-traveller. When you walk to say Port Sarim docks, and travel on the boat, you are instantly teleported from a node and put somewhere totally different. This renders any a* heuristic worthless, right? What alternative heuristic can we use, or should a* be scrapped altogether and just use DJkstra which does not rely on heuristics?

 

Any advice appreciated.

 

Teleports/shortcut examples:

port sarim docks

charter ships

fairy ring teleports

pull lever -> deep wilderness

 

 

Why do this?

You start in Draynor Village. Your code does: WebWalk.walkTo(ardougneMarketPos);

A webwalker will WALK all the way there. A really long way, all over white wolf mountain.

Well there is a much faster and efficient way to do it:

starting in draynor village, walk to port sarim, get the boat to karamja, walk to brimhaven, get the boat to ardougne, then walk to market.

 

This is why I am asking about web walker with shortcuts/teleports.

Edited March 12, 2015 by MegaManAlpha

[Swizzbeat]

In my implementation I subclass my base connection type and connect all my "walkable" nodes that way. My algorithm then recognizes these connections and adjusts itself accordingly.

[DragonAlpha]

In my implementation I subclass my base connection type and connect all my "walkable" nodes that way. My algorithm then recognizes these connections and adjusts itself accordingly.

 

Are you using heuristics? I can't see how a heuristic can have any value when a node's neighbor is somewhere else on the map (instead of all the adjcacent tiles).

 

Since the goal of the heuristic is to favor a tile that is closest to the destination. But what if in the exact opposite direction, just 5 tiles away there is a charter-ship which takes you much closer to the goal tile. If you are using a standard a* heuristic such as manhattan, then that won't take teleports/shortcuts into account.

 

I see each tile as having 8 neighbors. (each tile around it). However, for tiles that contain a "Boat Charter Ship Npc", I class that as having 9 neighbors (all the tiles around it, and also a tile far away on the map where the boat takes you).

 

I can only see Dijkstra being useful for this, unless there is some heuristic method that can take these wormholes/shortcuts/jumps into account?

[Swizzbeat]

Are you using heuristics? I can't see how a heuristic can have any value when a node's neighbor is somewhere else on the map (instead of all the adjcacent tiles).

 

Since the goal of the heuristic is to favor a tile that is closest to the destination. But what if in the exact opposite direction, just 5 tiles away there is a charter-ship which takes you much closer to the goal tile. If you are using a standard a* heuristic such as manhattan, then that won't take teleports/shortcuts into account.

 

I see each tile as having 8 neighbors. (each tile around it). However, for tiles that contain a "Boat Charter Ship Npc", I class that as having 9 neighbors (all the tiles around it, and also a tile far away on the map where the boat takes you).

 

I can only see Dijkstra being useful for this, unless there is some heuristic method that can take these wormholes/shortcuts/jumps into account?

I wrote my own algo. You're not being forced into using A* or Dijkstra.