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

Question

I'm currently looking at a way to visualize the data, and part of the algorithm needs something 99% the same as A * Path Finding, but I can't completely wrap it around. I know that this will be a fairly simple modification. (unit cost instead of least cost)

Basically I need to build a path (2D grid, without diagonals) from point A to point B in X steps.

eg. If the start and end points were next to each other, and I needed a 3-step path, it would have a tiny loop. (move: up, right, down).

Is there a known name for this algorithm, or is it so rare?

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

Any advice / help is greatly appreciated ...

John

Answer 1

I like this question - it's interesting.

I'm not sure how I encoded this, but these are just thoughts from my head.

Basically, you are dealing with the Manhattan distance here, since you are not using diagonals. Thus, you need to know the shortest path and get from there. If your specific cost is less than your Manhattan distance, the path is impossible. If it is equal, the ideal path is your shortest path.

Once you go beyond that, things get a little more complicated because you have several solutions to your problem. You could send an answer, but I don't know if he has a naive way of doing this. (Note, however, that these are just thoughts from the head, so ...)

Also note that in some situations there will be no solution because you are using the Manhattan distance! For example, if you have a 6x6 grid with a start point in one corner and an end point in the opposite corner, you can end at the end point in 10 steps, but not 11 (because you need to double yourself). I am sure this is the rule, but I would have to get it. (Again, from my head.) ( EDIT: I realized that this is not really the rule as such, but your specific cost cannot fall between the shortest path distance and the second shortest path distance. The second shortest path in the Manhattan grid should be n + 2, I suppose.)

So basically ... I think you can write something like this, but I don't think you can easily figure it out without checking many possibilities. You can optimize specific cases using rules, but as soon as you do this, I think you're stuck.

Give him a chance. That sounds pretty interesting!

SECOND EDITING: I just realized ... your travel expenses will always increase by two (again, due to the Manhattan distance). This means that you can optimize a bit more as long as you know your shortest distance; Your specific cost should be a multiple of 2, plus the shortest distance. In algorithmic terms, you will have a certain cost = 2n + shortest distance.

After that, however, you will have to go too far.

Hope this helps.

THIRD CHANGE (and hopefully the last): I’m probably a little pedantic here (and I’ll probably find out that others guessed me), but here's the deal, If you know your specific cost and know your shortest distance, you you can actually distinguish between both and divide by two to find out how many cycles you need on your way. The loops can "stack" (and I mean that you can start a cycle and continue it at a distance, this is "doubling back"), and you can optimize even further by only checking paths that have a certain number of cycles. However, by this time, you pretty much found a possible path to the end of the node (assuming that the obstacles do not block all the possible paths that you found). Thus, gross coercion would be necessary only to avoid any obstacles. Hope that made sense.

Answer 2

A * by design cannot do this. I would use Dijkstra’s algorithm and brute force through all possible paths (starting with the shortest) until I find one that matches your criteria. I can’t think of an easier way, as there can be any number of paths that fill these criteria (including 0).

Answer 3

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

The first thing that is connected with the problem is that since you cannot move along the diagonals, some value values ​​will not be possible. I assume that there are blocks of obstacles in the grid that cannot be passed; if it is not, A * is not a good starting point.

Your question needs more explanation, but I will give answers to both possibilities that I found:

Path without duplicate points :

Modify the A * algorithm so that it continues to work until a path with a direct value or above the required value is found. Just use this as a path, as there is no other way to reach another way.

Repeated Spot Path

Find the shortest path with the base A *, and then, if it is less than the required value, increase the value by moving back and forth (you add +2 to the value, going back) to your path or by converting a simple step into a cycle (you add + 2 to the cost with each cycle).