Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

12
  • 10
    Worth noting that Dijkstra is just A* with dijkstra_heuristic(x) = 0 Commented Oct 9, 2017 at 11:19
  • I don't understand what you mean by [*wormholes, goal], would you explain this? Commented Oct 9, 2017 at 11:29
  • 1
    "Euclidean distance to the closest wormhole exit" is a cheaper estimate for wormhole_path_distance than the subgraph search, and less of an underestimate than the "all exits are on the goal". Commented Oct 9, 2017 at 11:52
  • 3
    @Caleth certainly! There's a lot of fine-tuning potential here, e.g. we could decide to look ahead n=3 jumps. The subgraph search corresponds to the closure of all acyclic wormhole jumps. Your suggestion to look ahead n=1 jumps is very elegant as it has basically zero extra cost :) Commented Oct 9, 2017 at 11:58
  • 1
    For the shake of simplicity, assume there are only one wormhole (two nodes), then you may convert this plane 1-wormhole into 2 mirror planes, by copying a symmetric plane with the equidistant line between these two points as symmetry axis. You now have two planes, lets call them the real plane (you don't take the wormhole) and the imaginary plane (you took the wormhole). Now, we introduce the Z coordinate. This coordinate will be 0 for every point in the real plane, and it will be dist(wormhole, point) for every point of the imaginary plane. After that, apply A* for 3-dimensional space. Commented Oct 9, 2017 at 15:49