How to move within Cartesian space along cardinal directions while limiting turns?

Given is a Cartesian coordiante system, a from-position A (X/Y), and a to-position B (X/Y). I want to move from A to B. However, I can only move on the eight directions N, NE, E, SE, S, SW, W, NW.

I know that I can calculate the "best" of these directions to take from the current position A via the dot product with the unit vectors of the axis (the eight directions), where the biggest dot product is the direction to tak开发者_运维知识库e. But this approach leads to some kind of "oscillation" between two directions, if A is exactly in between these two.

So I am searching for an algorithm now that sovles this problem of getting from A to B with only one or max. two directions to use. Of course I am ignoring any obstalces now, so that theoretically I can always get from A to B with a maximum of two different directions. I could probably solve this problem with a bunch of if-statements, but I would prefer a more elegant solution...

I hope that was somewhat understandable :)

Thanks in advance for any ideas!

Kind regards, Matthias

the simplest solution is to head in a "diagonal" direction until you are on the same row/column as the target, and then to use the horizontal/vertical direction.

in other words:

• check if you are horizontally / vertically aligned. if so, move in that direction and finish.
• otherwise, find the closest diagonal direction using the method you have.
• move along the diagonal until you are horizontally or vertically aligned. then move in that direction and finish.

For the case of two segments maximum, this seems relatively easy:

1. Project a line from A -> B and then from B -> A. Pick the cardinal closest to this line rounding in either a clockwise or counterclockwise direction. Be consistent. (Once the angle is determined from A -> B, it's likely best to just add Pi to minimize very odd edge-cases with math... not sure if it can actually occur.)
2. Re-project lines from A -> B and B -> A along the selected cardinal direction.
   1. If the lines are parallel (requires movement in exactly one cardinal direction and can thus also be considered a termination in step #1) there is one segment A -> B.
   2. If the lines are not parallel find the intersection of the lines, point C. Then there are two segments A -> C and C -> B.

I think a smarter solution would give weights to each turn (relative to distance) -- then by configuring the weights the number of turns allowed could be increased or decreased.

Not sure if this made/makes sense, but happy coding!

You can start by computing the actual number of steps between any given point and your destination; this will probably be something like "taxicab geometry" but more complicated. If all 8 steps are the same "real"(i.e., Euclidean) distance, your step count should be something like:

dist(dx,dy) = |dx|+|dy| + sqrt(0.5)(|dx+dy|+|dx-dy|)

Then, in general, there will be two possible steps that have the same, smallest, distance-to-destination. You can then choose the direction which is the same as the last one (where possible).

Actually, if you do the math as shown above, you will probably encounter problems with floating point precision. You should still be able to make a robust decision, though, by giving a small "discount" (say 1% of a step) to the preferred direction.

It sounds like your problem stems from re-evaluating optimal route along the way. This will lead to ongoing switches between, for example, N and NE, then N, then NE, etc. This is the optimal route based on distance, but you want optimal route based on direction changes.

The resolution to this is to either

• pre-plan the route, rather than re-evaluate along the way, and stick to the plan
• compute a number of direction changes allowed / minimum number to take, and re-evaluate only when the target can be reached within that minimum number.

To explain my second suggestion, you should know that (without obstacles) any point can be reached in two 'moves'. Initial movement is a first move, and while travelling along that path only one more direction change is allowed. You algorithm would need to allow for this 'one more' - any possible route towards the goal should not be taken unless it can be reached within the remaining number of moves.

It appears that you algorithm is focused on minimum distance rather than minimum moves - or is it some combination of the two?