* Алгоритм, учитывающий скорость

Question

Я разрабатываю гоночную игру, такую ​​как http://harmmade.com/vectorracer/ и я реализовал алгоритм A* для игроков ИИ. Алгоритм работает хорошо для движений с 1 плиткой, но я не хочу, чтобы игроки ИИ перемещали только 1 плитку за раз (используя только их смежные точки), мне нужно, чтобы они могли ускоряться и замедляться, когда они приближается на повороте. Их следующие позиции должны зависеть от предыдущей, как у Vector Racer.

public boolean createRoute() {

    // The list where the points will be added in reverse order (from finish_point)
    ArrayList<Track_Point> path = new ArrayList<>();
    // The list where the unchecked points will be stored
    ArrayList<Track_Point> open = new ArrayList<>();
    // The list where the checked points will be stored
    ArrayList<Track_Point> closed = new ArrayList<>();
    // The starting point is always added as the first point to be checked
    open.add(starting_point);
    Track_Point current;

    while (true) {
        current = null;

        // If all points from the open list have been removed (be being checked), it means that there isn't a possible path from the starting to the finish point
        if (open.isEmpty()) {
            System.out.println("no route available");
            return false;
        }

        // Selects the point with the lowest F value from the open list
        for (Track_Point temp : open) {
            temp.show();
            if (current == null || temp.getF() < current.getF()) {
                current = temp;
            }
        }

         // If the current point has reached the finish point, break the loop to construct the path
        if (current.equals(finish_point)) {
            break;
        }

        // Removes the current point (with the lowest F value) from the open list
        open.remove(current);
        // Adds the current point (with the lowest F value) to the closed list
        closed.add(current);
        ArrayList<Track_Point> possible_points = createNextPossibleTrackPoints(current);
        //Sets the parent of the possible points
        for (Track_Point tp : possible_points) {
            if (!tp.equals(current)) {
                tp.setParent(current);
            }
        }

        for (Track_Point possible_point : possible_points) {
            double nextG = current.getG() + current.distance(possible_point);
            if (nextG < possible_point.getG()) {
                open.remove(possible_point);
                closed.remove(possible_point);
            }

            if (!open.contains(possible_point) && !closed.contains(possible_point)) {
                possible_point.setParent(current);
                open.add(possible_point);
            }
        }
    }
    //Track_Point current = finish_point;
    while (current.getParent() != null) {
        path.add(current);
        current = current.getParent();
    }
    // optimalRacingLine is the list where all the points will be held in the correct order
    optimalRacingLine.add(starting_point);
    for (int k = path.size() - 1; k >= 0; k--) {
        optimalRacingLine.add(path.get(k));
    }
    return true;
}

createPossiblePoints (Point current) пока возвращает список смежных точек текущей точки. Значение H каждой точки вычисляется в их конструкторе, так как я передаю точку финиша и вычисляю расстояние между ними. Значение G каждой точки вычисляется, когда я устанавливаю для нее родительский элемент, а значение G - это расстояние от новой точки до их родителя + значение G родительского элемента.

Как мне изменить этот код, чтобы разрешить ускорение / замедление?

Код Track_Point:

package model;

import javafx.geometry.Point2D;

public class Track_Point extends Point2D {

    private Track_Point parent, velocity;
    private double f, g, h;

    public Track_Point(double x, double y) {
    super(x, y);
    }

    public Track_Point(double x, double y, Track_Point f) { // f is the finish point
    super(x, y);
    h = distance(f);
    }

    public void setParent(Track_Point tp) {
    parent = tp;
    g = distance(tp) + tp.getG();
    f = g + h;
    velocity = new Track_Point(getX() - parent.getX(), getY() - parent.getY());
    }

    public Track_Point getParent() {
    return parent;
    }

    public double getG() {
    return g;
    }

    public double getH() {
    return h;
    }

    public double getF() {
    return f;
    }

    public Track_Point getVelocity() {
    return velocity;
    }

    @Override
    public String toString() {
    return "( " + (int) getX() + " , " + (int) getY() + " )";
    }

    public void show() {
    System.out.println(toString());
    }

}

Добавлены скриншоты моей неудачной попытки и работающей простой версии A*

http://tinypic.com/r/zlakg2/8 - рабочая версия

http://tinypic.com/r/2e3u07o/8 - измененная версия (использует скорость в качестве параметра в методе createNextPossiblePoints)

Answer 1

Во-первых, не используйте целые числа для позиции х / у. Не должно быть такого понятия, как "1 плитка" в гоночной игре. Ваш игровой мир и результаты могут быть совершенно разными. Например, рассмотрим использование double для хранения x и y. Ssh, не волнуйтесь, ваш JFrame не должен знать.

Эвристика

Вы используете A* для запуска AI? Рассмотрим эти дополнительные эвристики:

• Предпочитаю высокие скорости; cost = max velocity - current velocity
• Оставайтесь рядом с внутренним краем поворота (представьте поворот как внешний край круга); cost = distance_from(focus of turn)
• Избегайте стен; cost = isMovable(x, y) ? 0 : infinite/high
• РЕДАКТИРОВАТЬ Предпочитайте кратчайший путь, чтобы избежать ненужных ходов, как ваше второе изображение (Breadth First search не Djikstra); cost = steps from first node

Способ работы A* заключается в следующем:

1. Используйте Джикстра (расстояние от источника) + Жадность (расстояние до цели)
2. Вставьте свою эвристику здесь
3. Добавьте их все вместе и выберите самый низкий номер

Нет такой вещи как f, g или h; это просто математическая ерунда, которую вам не нужно знать.

Скорость

velocity = Math.abs(position1 - position2); так... position1 + velocity = position2, Вам нужно будет добавить следующие переменные:

• int xVelocity
• int yVelocity

Каждый момент, x += xVelocity; y += yVelocity, Следующая позиция будет xf = x + xVelocity; yf = y + yVelocity, Затем вы рисуете кольцо вокруг этой позиции следующим образом:

         +yVelocity
            \|/
-xVelocity  -0-  +xVelocity
            /|\
        -yVelocity

Таким образом, центр сохраняет ту же скорость, любая смежная сторона меняет одну скорость, а любая диагональная сторона меняет обе скорости. Что касается использования A*, то пространство решения хода достаточно мало, чтобы его можно было перебором; не добавляйте TrackPoints к открытому списку, если вы наткнетесь на стену и предпочитаете самую высокую скорость.

На самом деле, это все, что нужно сделать; простые вещи, но это может быть утомительно и сложно в первые несколько раз, когда вам нужно это сделать.

РЕДАКТИРОВАТЬ: Просто играл вектор гонщик, и это на самом деле намного проще, чем я ожидал. Я думал, что вы делаете полноценную гоночную игру. То, что я сказал вам, все еще очень применимо, но вам нужно будет внести некоторые коррективы, особенно в способ обработки вращения. Вы определенно захотите посмотреть гоночную трассу. На данный момент у меня нет времени изучать математику гоночной трассы, но это должно помочь вам рассчитать ее.

EDIT2: обновлен раздел Velocity. Я сделаю некоторые вычисления, чтобы выяснить более быструю эвристику, но того, что имеется, достаточно, чтобы проверить 3-10 шагов вперед без серьезных проблем с производительностью.