Find a path from point A to B in X steps. (A* ish)

Question

I am currently looking at a way of visualising data and a part of the algorithm needs something 99% the same as A* Path Finding but I cannot wrap my head round it fully. I know it will be a fairly simple modification. (specific cost instead of least cost)

Basically I need to plot a path (2D Grid, no Diagonals) from point A to point B in X number of steps.

E.g. If the start and end points were right next to each other and I needed the path to be 3 steps it would have a tiny loop. (moves: up, right, down).

Is there a known name for this algorithm or is the use of this so rare it's uncommon?

I am currently looking at this AS3 Librbay for modification as it is apparently very fast and seems clean and simple to me: http://www.dauntless.be/astar/

Any advise / assistance greatly appreciated...

John

Answer 1

I like this question - it's interesting.

I'm not sure how I'd code this, but these are just the thoughts off the top of my head.

Basically, you're dealing with Manhattan distance here, since you aren't using diagonals. As such, you need to know the shortest possible path and derive from there. If your specific cost is less than your Manhattan distance, the path isn't possible. If it's equal, the ideal path is your shortest possible path.

Once you go beyond that, things get a bit tricky, because you have multiple solutions to your problem. You might be able to brute-force an answer, but I don't know if there's a non-naive way to do it. (Note, though, that these are just the thoughts from the top of my head, so...)

Also note that for some situations, there won't be a solution, because you're using Manhattan distance! For instance, if you have a 6x6 grid with a start point in one corner and the end point in the opposite corner, you can end on the end point in 10 steps, but not 11 (because you have to double back on yourself). There's a rule to this, I'm sure, but I'd have to derive it. (Again, off the top of my head.) (EDIT: I realized this - it's not really a rule per se, but your specific cost cannot fall between the shortest path distance and the second shortest path distance. The second shortest path, in a Manhattan grid, should be n+2, I believe.)

So basically...I think it's possible to write something like this, but I don't think that you can easily calculate it without checking a lot of possibilities. You can optimize out specific cases via rules, but once you've done that, I think you're stuck.

Give it a shot, though. It sounds pretty interesting!

SECOND EDIT: I just realized....your path costs will always increase by two (again, due to Manhattan distance). This means that you can optimize a little more as long as you know your shortest distance; your specific cost must be a multiple of 2, plus your shortest distance. In algorithmic terms, you'd have specific cost = 2n + shortest distance.

After this point, though, you're gonna have to brute force it.

Hope this helps.

THIRD EDIT (and hopefully the final one): I'm probably being a bit pedantic here (and I'm probably figuring out what others have figured out wayyy before me) but here's the deal. If you know your specific cost, and you know your shortest path distance, you can actually take the difference between both and divide by two to figure out how many loops you need in your path. Loops can "stack" (and by this I mean, you can start a loop, and continue it for a distance; this is "doubling back") and so you can optimize even further by only checking paths that have a specific number of loops. However, by this time, you've pretty much found a possible path to your end node (assuming that obstacles don't block all of the possible paths you've found). As such, brute forcing would only be necessary to avoid any obstacles. I hope that made sense.

Answer 2

First you need to understand that this is not a trivial question and therefore you're not gonna find the perfect answer in here, but you will find some good ideas.

First thing inherent to the problem is that as you cannot move through diagonals, some cost values will be impossible to achieve. I'm assuming that the grid has obstacle blocks that cannot be traversed through, if that's not the case, A* is not a good start point.

Your question needs more clarification, but I'll provide answers to both possibilities I have found:

Path without recurring spots:

Modify the A* algorithm to keep running until the path with cost directly equal or above your desired cost is found. Just use that as the path, as there's no other way to achieve another path.

Path with recurring spots

Find the shortest path with basic A*, then if it's less than the desired cost, increase the cost by either moving back and forth (you add +2 to the cost by going back forth) to your way or by transforming a simple step into a loop (you add +2 to the cost with each loop).

Answer 3

A* is by design not able to do this. I would use Dijkstra's algorithm and brute force through all possible paths (starting at the shortest) until you find one that fits your criteria. I can't really think of an easier way, since there can be any number of paths that fill that criteria (including 0).