Получение пути между двумя позициями - PullRequest
Новая
       4

Получение пути между двумя позициями

2 голосов
/ 06 апреля 2020

Учитывая позицию: 

class Position {
    private int x, y;

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

Я хотел бы рассчитать разницу между двумя такими позициями, а затем вернуть список позиций, которые дойдут до конца.

Например: 

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

Должен возвращать список с [[10,10], [11,10], [12,10]].

Мой текущий код: 

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

Это хорошо, но в сценарии ios где конечная позиция равна 12,12, возвращается список: [[10,10], [10,11], [10,12], [11,10], [11,11], [11,12], [12,10], [12,11], [12,12]], где я хотел бы, чтобы результат был [[10,10], [11,11], [12,12]].

Как бы я go добился такого решения?

Ответы [ 3 ]

1 голос
/ 06 апреля 2020

Если вам разрешено только влево, вправо, вверх и вниз, то вам нужно сначала сделать все шаги в направлении X, а затем все шаги в направлении Y. Это означает, что два цикла for друг за другом, а не вложенные.

Если вам разрешены диагональные шаги (как кажется), вам нужно посчитать, сколько шагов вам нужно сделать в целом: max(diffX, diffY). И затем сделайте столько шагов, некоторые из которых будут диагональными: 

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

0 голосов
/ 06 апреля 2020 
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) {
    if (xChange != 0) { // x only change if current position is not the same as destination
        x += xPositive;
        xChange -= xPositive;
    }
    if (yChange != 0) {
        y += yPositive;
        yChange -= yPositive;
    }
    fromOldToNewPositions.add(new Position(x, y));
}
0 голосов
/ 06 апреля 2020

Чтобы получить путь, попробуйте так: 

        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++) {
            if (x == newPosition.x) {  // that means you reach destination row. just go column only
                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));
...