1

I'm in need of an algorithm that provides me with information about the shortest path between two points. The path should have as few edges as possible since every waypoint, every turn costs time and time - in my case - is expensive.

The path should be calculated to lead around obstacles of certain shapes (mostly circular or rectangular).

The information that the path is stored in should either be cartesian coordinates of the waypoints of the path or alternatively polar coordinates (that is commands for my unit to perform, like turn to angle alpha, move distance b). I'd however prefer cartesian coordinates of each waypoint.

There's no navigation net or something, just the coordinate system and information about where the obstacles and other no-go areas are from which some are fixed and some might (and quite likely will) move.

Ah, and all this should be somehow available in .NET.

Thanks

//edit: to make things little bit clearer, here's a picture of what I intend to do: https://dl.dropbox.com/u/8802336/path.png

Hendrik Wiese
  • 2,010
  • 3
  • 22
  • 49
  • It is unclear what you have problem with - does A* or normal Dijkstra's [path finding](http://en.wikipedia.org/wiki/Pathfinding) not work for you? Particular reasons/problems/restrictions? – Alexei Levenkov Mar 13 '13 at 23:39
  • See http://stackoverflow.com/questions/5303538/algorithm-to-find-the-shortest-path-with-obstacles – Mihai8 Mar 13 '13 at 23:39
  • I assume I'll need some pictures to explain my problem... just give me a second to come up with them. – Hendrik Wiese Mar 13 '13 at 23:44
  • Your question is not complete enough - HOW expensive is making a new edge, compared to making the path shorter? Should I optimize for lowest number of edges possible (e.g. around a circle I would make a large L shaped path) or are there compromises? – Patashu Mar 13 '13 at 23:44
  • Alright. For every new edge I need to stop the unit, turn it into the direction of the next edge and speed it up again. That consumes time. So I need to minimize the amount of stopping, turning, accelerating. I'll add a picture of what I need to my question in a second... – Hendrik Wiese Mar 13 '13 at 23:51

2 Answers2

2

Your question can be interpreted two ways.

1. I want to find the shortest path, breaking ties by choosing the one(s) with the least number of edges

You can do this by adding some very small number ε to the weight of every edge of the graph. The number must satisfy ε < 1/numberOfEdges. This will increase the length of every path by edges*ε, meaning shorter paths will be preferred. This works even with negative-weight edges. Be careful of floating-point inaccuracies.

2. I want to find the path with the least number of turns, breaking ties by choosing the one(s) with the shortest path

You can do this by adding some large number E to the weight of every edge on the graph. The number must satisfy E > sumOfAllEdgeWeights. This will ensure that only paths with the least possible number of edges are considered. This does not work with negative-weight edges. Be careful of integer overflows.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • Number 2 is a good solution - just A* and making it so changing direction costs a large amount (and the large amount can change based on rotation, how long you've accelerated for and so on). It will only give 8-way movement though. – Patashu Mar 14 '13 at 00:02
  • That 8-way movement and its precision regarding precise pathway of the edges is makeing A* inapplicable, unfortunately. I only need the corners of the path, the waypoints that is. Information about the edges isn't necessary. – Hendrik Wiese Mar 14 '13 at 00:06
  • 1
    @SeveQ: Based on your image, it seems what you're really looking for is an any-angle algorithm. See [here](http://stackoverflow.com/questions/14326654/how-to-find-where-to-cast-a-ray-to-avoid-collision-in-bullet/14328161#14328161). – BlueRaja - Danny Pflughoeft Mar 14 '13 at 00:08
  • @BlueRaja-DannyPflughoeft, that one looks promising. I'll have a look at it. – Hendrik Wiese Mar 14 '13 at 00:12
  • @BlueRaja - Danny Pflughoeft, I am reading this and loving it :) – Patashu Mar 14 '13 at 00:17
0

If the goal is:

1) Minimize number of edges.

2) Minimize distance.

In that order, then one thing you can try like this:

1) Draw a line from start to end.

2) Calculate every object that your line collides with.

3) For each of those objects, calculate both points perpendicular to the object that allow you to split the path into two path segments. You can do this for rectangles by splitting the line into two segments, for the segment A seeing which of the four corners it can pass through, for the segment B seeing which of the four corners it can pass through and trying all combinations until you find the two that gives the least displacement. For circles, I forget how to do it, but there's only one solution on either side where the two path segments are flush to the circle, so you can do it using trigonometry or something (I'll try and figure it out :) )

For both new paths, call 4) in a recursive branching fashion.

4) For both line segments you've generated, repeat the calculation until there are no collisions left. Similar to A*, you should calculate for paths that seem the best, first (have the fewest collisions left, or just do shallowest first if that's too hard).

5) Pick the best path via whatever metric you please. In an A* fashion you should keep your list sorted so the path that's the best via your metric is on top, and so you can just pick the first path to finish.

I can't prove in my head that this will always work, but I've seen something similar to it before.

EDIT

To calculate the closest path of two line segments in one direction around a circle, do for each line segment

-Side A: Goes from start of line (or end of line) xs,ys to circle's center xc,yc, length = a

-Side B: goes from center xc,yc to somewhere on the circumference, so length = r

-Side C: goes from side B's endpoint to xs,ys (hypotenuse)

The angle formed by A and B is a right angle, and we know A and B's length, so we can calculate C's length as sqrt(A^2+B^2)

Finally, we know C's length = A's length/sin(angle(B to C)) = B's length/sin(angle(A to C)), meaning we can do trigonometry to find out the angle A to C and the angle B to C.

This lets us fully construct one side of the path segment. Repeat for the other side, and we have the path split in two that is flush on both segments against the circle -> minimizes distance added.

Patashu
  • 21,443
  • 3
  • 45
  • 53
  • Alright, I've got to go through that a few times to understand it. At least I can confirm that the order is right: first minimize number of edges, then minimize distance. Our main problem is acceleration. Speed isn't that much of a problem. So edges do indeed cost more than distance. – Hendrik Wiese Mar 13 '13 at 23:59