java - 考虑速度的 A* 算法

Question

我正在开发类似 http://harmmade.com/vectorracer/ 的赛车游戏我已经实现了 A* 算法以供 AI 玩家使用。该算法适用于 1 个方 block 的移动，但我不希望 AI 玩家一次只移动 1 个方 block (通过仅使用它们的相邻点)，我需要它们能够在它们移动时加速和减速接近转弯。他们的下一个位置应该取决于他们之前的位置，就像 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

首先，不要对 x/y 位置使用整数。赛车游戏中不应该有“1 个方 block ”这样的东西。你的游戏世界和输出可以完全不同。例如，考虑使用 double 来存储 x 和 y。 Ssh，别担心，您的 JFrame 不需要知道。

启发式

您正在使用 A* 来运行您的 AI？考虑这些额外的启发式方法:

• 喜欢高速； cost = 最大速度 - 当前速度
• 靠近转弯的内侧边缘(将转弯想象成圆圈的外侧边缘)； cost = distance_from(转弯焦点)
• 避开墙壁； cost = isMovable(x, y) ? 0:无限/高
• 编辑 首选最短路径以避免像第二张图片那样采取不必要的移动(广度优先搜索不是 Djikstra)； cost = 从第一个节点开始的步骤

A* 的工作方式如下:

1. 使用 Djikstra(到原点的距离)+ Greedy(到目标的距离)
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*，一个回合的解决方案空间足够小，您可以对其进行暴力破解；如果您撞到墙并且喜欢最高速度，请不要将 TrackPoint 添加到打开列表中。

真的，仅此而已；简单的事情，但在您需要做的前几次可能会很乏味和困难。

编辑:刚刚玩了 vector racer，它实际上比我预期的要简单得多。我以为你在制作一款成熟的 2d 赛车游戏。我告诉你的仍然非常适用，但你需要做一些调整，特别是你处理旋转的方式。您肯定会想查找 racing line .我现在没有时间复习赛车线的数学，但是this应该可以帮你计算。

EDIT2:更新了速度部分。我将进行一些计算以找出更快的启发式算法，但目前的情况足以检查 3-10 步，而不会出现重大性能问题。