Jump to content

Advanced pathfinding with teleports/shortcuts


DragonAlpha

Recommended Posts

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 by MegaManAlpha
Link to comment
Share on other sites

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?

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...