23

Suppose that you have a 2D grid of cells, some of which are filled in with walls. Characters can take a step from one square to any square that is one step horizontal or vertical from it, but cannot cross walls.

Given a start position and an end position, we can find the shortest path from the start position to the end position by using the A* algorithm with an admissible heuristic. In this current setup, the Manhattan distance would be admissible, since it never overestimates the distance to the destination.

Now suppose that in addition to walls, the world has pairs of teleporters. Stepping onto a teleporter immediately transports a character to the linked teleporter. The existence of teleporters breaks the admissible heuristic given above, since it might be possible to get to the destination faster than taking the optimal Manhattan distance walk by using a teleporter to cut down on the distance. For example, consider this linear world with teleporters marked T, start position marked S, and end position marked E:

T . S . . . . . . . . . . . . . E . T

Here, the best route is to walk to the teleporter on the left, then take two steps to the left.

My question is this: what is a good admissible heuristic for A* in a grid world with teleporters?

Thanks!

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065

2 Answers2

16

If there aren't too many teleporters in your world, I would try the following heuristic, where MHD(a,b) is Manhattan distance between cell a and b and T(i) is the teleporter nearest to cell i:

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
us2012
  • 16,083
  • 3
  • 46
  • 62
  • +1, that what I had in mind as well. I took the liberty to change `d*(x,y)` to `h(x,y)`, at least AFAIK it is the convention character to denote heuristic value. – amit Jan 20 '13 at 19:33
  • @nhahtdh: It is still admissible, his approach might be overpredicting - it takes the closest teleported to the source and the closest to the destination, as far as I see it - it cannot under-predict the distance. – amit Jan 20 '13 at 19:36
  • 3
    @amit: nhahtdh was right. Admissibility requires *never overestimating*, not *never underestimating*. – us2012 Jan 20 '13 at 19:38
  • No, it requires never underestimating. `h(x,y) = 0 (for all x,y)` is an admissible heuristic function.. though not very informative one. – amit Jan 20 '13 at 19:38
  • 1
    @amit: Yeah, `h(x,y)=0` is admissible because it *always underestimates*. You are confusing something here, I fear. – us2012 Jan 20 '13 at 19:40
  • From Wikipedia: "admissible heuristic; that is, it must not overestimate the distance to the goal." – nhahtdh Jan 20 '13 at 19:40
  • yea, I was confusing myself with terminology - the heuristic suggested is never over-estimating, and thus admissible. It never gives you higher number then the true minimum. I said it cannot *underpredict* but in fact it most likely does, it never *over-predicts* – amit Jan 20 '13 at 19:43
  • @amit That's what I'm unsure about. I thought nhahtdh had a convinving counterexample, but unfortunately he deleted it. – us2012 Jan 20 '13 at 19:45
  • The example is 2 teleporter: one a bit closer from current position, and throw you to a position < Mahattan distance, the other a bit further from current position but put right next to the exit. – nhahtdh Jan 20 '13 at 19:47
  • The answer is perfectly fine and correct, I was confusing you all because I messed up terminology (sorry for that), but the bottom line is - the heuristic makes a relaxation that you can use a teleporter to move to any teleporter you want. This relaxation makes the heurisitc never overestiamte and thus admissible. – amit Jan 20 '13 at 19:47
  • @nhahtdh , hm - but that's not a counterexample! My heuristic doesn't take into account the association of teleporters, so it doesn't overestimate here! – us2012 Jan 20 '13 at 19:48
  • @us2012: Shouldn't the distance to end via teleporter (which is shorter than Manhattan, but more than the other route through the other teleporter) overestimates the distance? – nhahtdh Jan 20 '13 at 19:50
  • @nhahtdh: There is no other teleporter which is better, this answer assumes you can "chose" which teleporter you go out from in the heuristic function. This is a relaxation that makes the heuristic admissible. – amit Jan 20 '13 at 19:52
  • Nah, I don't really know since my brain does not function very well now. Please check the pastebin, SE are start and end, 12 are teleporter, numbering pairs them up: http://pastebin.com/7a65QEgD – nhahtdh Jan 20 '13 at 19:54
  • @nhahtdh My heuristic will choose the left `1` as `T(x)` and the right `2` as `T(y)`, so it will actually underestimate the distance (its estimate will be 4). It doesn't care that you can't go from a 1-porter to a 2-porter. – us2012 Jan 20 '13 at 19:55
  • @us2012: Oh, since you consider the nearest to the 2 ends, it is correct. Can you change the explanation to T(i) for generality? – nhahtdh Jan 20 '13 at 19:56
  • @nhahtdh In your example `h(S,E) = min(d(S,E), d(S,1)+d(2,E)) = min(15,3+1) = 4` which is under-predicting but not over-predicting – amit Jan 20 '13 at 19:57
  • @nhahtdh Thanks for your edit. I didn't think that this could be the source of your confusion. However I do agree that it's clearer now. – us2012 Jan 20 '13 at 20:00
  • This answer needs an update to deal with **multiple sets/pairs** of teleporters. That is, if there are two pairs of teleporters, (A, A') and (B, B'), and the shortest path happens to be start-A-A'-B-B'-end, the heuristic must consider all permutations of teleporter use - using the A set, using B set, using A then B, using B then A. – congusbongus Apr 08 '15 at 01:52
  • 1
    @congusbongus I don't think I get your point. The heuristic does NOT have to consider everything, it just has to make sure that it's admissible. Sure you may find a better heuristic (for example, you could do a complete BFS of the grid and use those exact results, but then you defeat the point of A*), but I don't think my answer is incorrect/needs an update. – us2012 Apr 12 '15 at 22:14
  • @us2012 admissible means it must underestimate the path cost, so if the shortest path happens to use two teleporters in that order, and the heuristic only considers taking one, then it may overestimate the cost. – congusbongus Apr 12 '15 at 23:36
  • @congusbongus My heuristic estimates min distance to first teleport in the solution plus min distance from last teleporter to goal. This always underestimates. – us2012 Apr 13 '15 at 04:39
7

Form a graph of the teleporters:

  • You have a node for each teleporter and a node for the end position.
  • You have an edge connecting each node to each other node, forming a fully connected graph.
  • For the edge weights, use the Manhattan distance between each node's destination cell (the one you go to when you enter the teleporter) and all the other nodes.

Use Dijkstra's algorithm to calculate the shortest distance from each node to the end.

You can now use the minimum of the distance between a particular position and all the nodes plus the pre-calculated distance from the node to the end as a heuristic function. Dijkstra's algorithm only has to be run once as a pre-processing step. However, if the number of teleporters is a large perecentage of the number of cells, you may not get any benefit over using a simpler heuristic function.

Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132
  • 1
    That makes no sense, use Dijkatra's algorithm is basically running A* with `h(x,y) =0` as "pre-processing" P.S. if any - use [floyd-warshall](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) algorithm, you need the distance for each pair (x,y) – amit Jan 20 '13 at 19:43
  • @amit: You only need to find the distance to the end point, not the distance between every pair. – Vaughn Cato Jan 20 '13 at 19:47
  • How do you assign edge weight? Manhattan? – nhahtdh Jan 20 '13 at 19:48
  • @nhahtdh: yes -- I forgot to mention that in my answer, thanks. – Vaughn Cato Jan 20 '13 at 19:49
  • Assuming a single target yes, floyd-warshall is an overkill, agreed. (But note you will have to run dijkstra on the transposed graph, with the target as the source, because you want the cost from every node). Nevertheless, running dijkstra as pre-processing is still running A* with h(x,y) = 0 (which is admissible heuristic function, btw) – amit Jan 20 '13 at 19:50
  • @amit: True -- there is really only a benefit if the number of teleporters is small compared to the overall number of cells. – Vaughn Cato Jan 20 '13 at 19:53
  • 2
    My own two cents' worth: I was planning on testing this out in a static world where precomputation is totally reasonable. I actually like this two-layer approach! – templatetypedef Jan 21 '13 at 05:36
  • @templatetypedef: I realized that it didn't state my answer correctly. It is the distance from the cell that you teleport to, and not the distance to the teleporter, that is important. – Vaughn Cato Jan 21 '13 at 16:29
  • @amit: He's talking about running djikstra over the graph formed by only the teleporters, not the entire graph. – BlueRaja - Danny Pflughoeft Feb 24 '13 at 22:09
  • Could you elaborate why the walls don't have to be considered in the teleporter graph edge weights? – Reinstate Monica Feb 24 '13 at 23:50
  • 2
    @WolframH: Because it is a heuristic function, you only have to make sure you never overestimate the actual distance. The distance without the walls will never be greater than the distance with the walls. – Vaughn Cato Feb 25 '13 at 00:59
  • 1
    @VaughnCato: Thanks, I get it now. Dijkstra, which itself doesn't use heuristics, is fed with non-overestimated heuristic values, and thus yields output (which is exact for the input to Dijkstra) that is a non-overestimated heuristic for the original problem. Nice, +1. – Reinstate Monica Feb 25 '13 at 10:22