CODEWITHSUNDEEP
javaarraysmultidimensional-array
Jazerix
Jazerix

Reputation: 4801

Getting path between two positions

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?

Upvotes: 2

Views: 125

Answers (3)

GolamMazid Sajib
GolamMazid Sajib

Reputation: 9447

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));

Upvotes: 0

luk2302
luk2302

Reputation: 57124

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]]

Upvotes: 1

Bejond
Bejond

Reputation: 1198

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));
}

Upvotes: 0

Related Questions