Search code examples
c#path-findinga-star

2D pathfinding algorithm

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

Solution

  • 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.