Getting path between two positions

user_1393283 0
Viewed 92

Given a Position:

class Position {
    private int x, y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
}

I would like to calculate the difference between two such positions and then have it return a list of positions that would get it to the end.

For example:

Position oldPosition = new Position(10, 10);
Position newPosition = new Position(12, 10);

Should return a list with:

[[10,10], [11,10], [12,10]]

My current code:

Position oldPosition = new Position(10, 10);
Position newPosition = new Position(12, 12);

List<Position> fromOldToNewPositions = new ArrayList<>();
int differenceX = newPosition.getX() - oldPosition.getX();
int differenceY = newPosition.getY() - oldPosition.getY();
boolean xNegative = differenceX < 0;
boolean yNegative = differenceY < 0;


for (int x = oldPosition.getX(); xNegative && x >= newPosition.getX() || !xNegative && x <= newPosition.getX(); x = xNegative ? x - 1 : x + 1) {
    for (int y = oldPosition.getY(); yNegative && y >= newPosition.getY() || !yNegative && y <= newPosition.getY(); y = yNegative ? y - 1 : y + 1) {
        fromOldToNewPositions.add(new Position(x, y));
    }
}

Does this well, but in scenarios where the end position is 12,12 it returns a list:

[[10,10], [10,11], [10,12], [11,10], [11,11], [11,12], [12,10], [12,11], [12,12]]

where I would like the result to be:

[[10,10], [11,11], [12,12]]

How would I go about achieving such a solution?

multidimensional-array arrays java
3 Answers

If you are only allowed left, right, up and down then you need to take all steps in X direction first and then all steps in Y direction. That means two for loops after each other, not nested.

If you are allowed diagonal steps (as it seems) you need to calculate how many steps you need to take in general: max(diffX, diffY). And then take as many steps, some of them being diagonal steps:

Position oldPosition = new Position(10, 10);
Position newPosition = new Position(14, 12);

List<Position> fromOldToNewPositions = new ArrayList<>();
int differenceX = newPosition.getX() - oldPosition.getX();
int differenceY = newPosition.getY() - oldPosition.getY();

int steps = Math.max(differenceX, differenceY);
for (int step = 0; step <= steps; step++) {
    double part = step / (double) steps;
    fromOldToNewPositions.add(new Position(
            (int) (oldPosition.getX() + differenceX * part),
            (int) (oldPosition.getY() + differenceY * part)));
}

[[10 | 10], [11 | 10], [12 | 11], [13 | 11], [14 | 12]]
user_24428040

To get path try like this:

Position oldPosition = new Position(15, 10);
Position newPosition = new Position(12, 11);

List<Position> fromOldToNewPositions = new ArrayList<>();
if (oldPosition.x > newPosition.x) {
    Position c = oldPosition;
    oldPosition = newPosition;
    newPosition = c;
}
int x = oldPosition.x;
int y = oldPosition.y;
fromOldToNewPositions.add(oldPosition);
for (; x <= newPosition.x; x++) {
    // that means you reach destination row. just go column only
    if (x == newPosition.x) {
        while (y != newPosition.y) {
            if (y < newPosition.y) {
                fromOldToNewPositions.add(new Position(newPosition.x, y++));
            } else {
                fromOldToNewPositions.add(new Position(newPosition.x, y--));
            }
        }
    } else {
        if (y < newPosition.y) {
            fromOldToNewPositions.add(new Position(x + 1, ++y));
        } else if (y > newPosition.y) {
            fromOldToNewPositions.add(new Position(x + 1, --y));
        } else {
            fromOldToNewPositions.add(new Position(x + 1, y));
        }
    }
}
fromOldToNewPositions.forEach(e -> System.out.println(e.x + " " + e.y));
user_68312570 
int xChange = newPosition.getX() - oldPosition.getX();
int yChange = newPosition.getY() - oldPosition.getY();
int xPositive = 1; // each step of x
int yPositive = 1; // each step of y
if (xChange < 0) {
    xPositive = -1;
}
if (yChange < 0) {
    yPositive = -1;
}
int x = oldPosition.getX();
int y = oldPosition.getY();

fromOldToNewPositions.add(oldPosition);
while (xChange != 0 || yChange != 0) {
    // x only change if current position is not the same as destination
    if (xChange != 0) {
        x += xPositive;
        xChange -= xPositive;
    }
    if (yChange != 0) {
        y += yPositive;
        yChange -= yPositive;
    }
    fromOldToNewPositions.add(new Position(x, y));
}
user_39088140
Related