1

我正在开发像http://harmmade.com/vectorracer/这样的赛车游戏，并且我已经实现了用于 AI 玩家的 A* 算法。该算法适用于 1 块移动，但我不希望 AI 玩家一次只移动 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 方法中使用速度作为参数）

4

1 回答 1

2

首先，不要对 x/y 位置使用整数。赛车游戏中不应该有“1 块”之类的东西。您的游戏世界和输出可能完全不同。例如，考虑使用双精度来存储 x 和 y。ssh，不用担心，你的 JFrame 不需要知道。

启发式

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

  • 喜欢高速；cost = max velocity - current velocity
  • 靠近转弯的内侧边缘（将转弯想象为圆的外侧边缘）；cost = distance_from(focus of turn)
  • 避开墙壁；cost = isMovable(x, y) ? 0 : infinite/high
  • 编辑首选最短路径以避免像第二张图片那样采取不必要的移动（广度优先搜索不是Djikstra）；cost = steps from first node

A* 的工作方式如下：

  1. 使用 Djikstra（到原点的距离）+ Greedy（到目标的距离）
  2. 在此处插入您的启发式方法
  3. 将它们加在一起并选择最小的数字

没有 f、g 或 h 这样的东西；这只是你不需要知道的数学废话。

速度

velocity = Math.abs(position1 - position2); 所以position1 + velocity = position2…… 您需要添加以下变量：

  • 整数 x 速度
  • int y速度

每时每刻，x += xVelocity; y += yVelocity。下一个位置将是xf = x + xVelocity; yf = y + yVelocity。然后，您在该位置周围画一个环，如下所示：

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

所以中心保持相同的速度，任何相邻的边改变一个速度，任何对角边改变两个速度。至于使用 A*，一回合的解空间足够小，你可以暴力破解它；TrackPoint如果您撞到墙壁并更喜欢最高速度，请不要将s 添加到打开列表中。

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

编辑：刚刚玩了矢量赛车，它实际上比我预期的要简单得多。我以为你正在制作一个完整的 2D 赛车游戏。我告诉你的仍然非常适用，但你需要做一些调整，特别是你处理旋转的方式。你肯定想查一下赛车线。我现在没有时间复习赛车线的数学，但这应该可以帮助你计算它。

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

于 2014-05-04T03:12:30.200 回答