考慮速度的A *算法

Question

我正在開發像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方法中的參數）

Answer 1

首先，不要使用inte gers爲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（從原點的距離）+貪婪（到目標的距離）
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添加到打開的列表中。

真的，這就是它的全部;簡單的東西，但前幾次你需要這樣做可能會很乏味和困難。

編輯：剛玩矢量賽車，它實際上比我預期的要簡單得多。我以爲你正在製作一個完整的2D賽車遊戲。我告訴你的東西仍然非常適用，但你需要做一些調整，特別是你處理旋轉的方式。你一定要查找racing line。我現在沒有時間去研究賽車線的數學，但this應該可以幫助你計算它。

EDIT2：更新了速度部分。我會做一些計算來找出一個更快的啓發式，但是現在的情況足以在未出現重大性能問題的情況下檢查3-10步。