A* algorithm that takes account velocity

Question

I'm developing a racing game like http://harmmade.com/vectorracer/ and I have implemented the A* algorithm to use for the AI players. The algorithm is working fine for 1-tile movements, but I don't want the AI players to only move 1 tile at a time (by using only their adjacent points), I need them to be able to accelerate and decelerate when they are closing in on a turn. Their next positions should depend on their previous one, just like 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) so far returns a list of the current point's adjacents. Each point's H value is calculated in their constructor, as I'm passing the finish point there and it calculates the distance between them. Each point's G value is calculated when I set a parent to it, the G value is the distance from the new point to their parent + the parent's G value.

How do I modify this code to allow acceleration/deceleration?

The code of 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());
    }

}

Added some screenshots of my failed attempt and the working simple A* version

http://tinypic.com/r/zlakg2/8 - working version

http://tinypic.com/r/2e3u07o/8 - modified version (uses velocity as a parameter in the createNextPossiblePoints method)

Answer 1

Firstly, don't use an integers for the x/y position. There should be no such thing as '1 tile' in a racing game. Your game world and output can be completely different. For example, consider using doubles to store x and y. Ssh, don't worry, your JFrame doesn't need to know.

Heuristics

You are using A* to run your AI? Consider these additional heuristics:

• Prefer high velocities; cost = max velocity - current velocity
• Stay near inside edge of turn (imagine the turn as the outside edge of a circle); cost = distance_from(focus of turn)
• Avoid walls; cost = isMovable(x, y) ? 0 : infinite/high
• EDIT Prefer shortest path to avoid taking unnecessary moves as your second image does (Breadth First search not Djikstra); cost = steps from first node

The way A* works is as follows:

1. Use Djikstra (distance from origin) + Greedy (distance to target)
2. Insert your heuristics here
3. Add them all together and choose the lowest number

There's no such thing as f, g, or h; it's just mathematical nonsense you don't need to know.

Velocity

velocity = Math.abs(position1 - position2); so... position1 + velocity = position2. You'll need to add the following variables:

• int xVelocity
• int yVelocity

Each moment, x += xVelocity; y += yVelocity. The next position will be xf = x + xVelocity; yf = y + yVelocity. Then, you draw a ring around that position as follows:

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

So the center retains the same velocity, any adjacent side changes one velocity, and any diagonal side changes both velocities. As for using A* the solution space of a turn is small enough that you can brute force it; don't add TrackPoints to the open list if you bump into a wall and prefer the highest velocity.

Really, that's all there is to it; simple stuff, but it can be tedious and difficult the first few times you need to do it.

EDIT: Just played vector racer and it's actually a lot simpler than I expected. I thought you were making a full blown 2d racing game. What I've told you is still very applicable, but you'll need to make a few adjustments, particularly to the way you handle rotation. You'll definitely want to look up the racing line. I don't have the time at the moment to go over the mathematics of the racing line, but this should help you calculate it.

EDIT2: Updated Velocity section. I'll do some calculations to figure out a faster heuristic, but what is present is enough to check 3-10 moves ahead without major performance issues.