0

I'm trying to write a piece of code that find shortest path in an 2D map, with some constraints:

  1. There is no obstacle in the map.
  2. The map is "wrap-around", meaning AI can move cross through one boundary and appear on the opposite side. (Much like the snake game on old Nokia phones)
  3. However, if there is a linked-path between starting point and destination, travel time for that path will be reduced by, for example, 10%.
  4. The shortest path must be taken.

Normal A* algorithm doesn't seem to fit these requirements, as it does not allow teleporting from one border to the other, and is Best-First. So, how should I solve this?

And since I'm doing it in C#, any relevant example in C# is appriciated

1
  • You may want to try Genetic Algorithms to solve this problem too. You just need to find an adequate fitness function. Feb 10, 2012 at 8:28

1 Answer 1

3

The A* algorithm will fit your requirements, you just have to think about it a bit differently. The A* isn't just a grid algorithm, rather it is a graph traversal algorithm.

So, in order to do this you have to represent your map as a series of interconnected points. These points can then wrap around like a big torus. Each point then has connections to other points, and those edges have a weight, so that traversing different edges is more "expensive" for your algorithm.

Wikipedia has an example of this sort of graph traversal further down the page, with weighted edges.

Edit: To elaborate on the wrap-around problem. Say you have a simple grid of points that are wrap around like this

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

Normally the edges here would be

1-2, 2-3, 4-5, 5-6, 2-5, 3-6, 4-7, 5-8, 6-9, 7-8, 8-9

To make this wrap around you would add the edges

1-7, 2-8, 3-9, 1-3, 4-6, 7-9

To the edges list. You would then apply the A* algorithm normally, storing each point that you have visited, and traversing the edges that you have from this point. Note that you can no longer just handle the points in question but you have to keep track of the edges that each point has.

To handle the problem of some parts being easier, you store an extra value on the edges to determine the difficulty to traverse them. Say that every edge has the value 1, but the edge 4-5 is twice as hard to traverse. You would then assign the value 2 to that edge, and use that value when you compute your heuristic algorithm for the distance to the goal point.

4
  • Con you elaborate? Especially on how I can deal with 2nd point above.
    – Ethan
    Feb 10, 2012 at 7:55
  • I've elaborated the answer, hope that helps you out.
    – Dervall
    Feb 10, 2012 at 8:27
  • Then when should an edge get added to the closed list?
    – Ethan
    Feb 14, 2012 at 8:23
  • The edges doesn't get added to the open and closed list, only the nodes. The edges are only used to determine which nodes are reachable from a given node and the traversal cost of the move.
    – Dervall
    Feb 14, 2012 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.