koobas.hobune.stream
Custom pathing for AI is slow and doesn't work
I'm making a racing game. In it, I want there to be AI-controlled characters. I would use a pathing algorithm like A* for this, but I want my AI to only pull from certain actions- Turn left, Drift right, boost, etc.
So I wrote a custom pathing algorithm using a special Move class and had it determine what sequence of moves to use with breadth-first search.
However, the algorithm doesn't work right. The List of Moves returned by the method is often empty, the racer often bumps into walls, the sequence of moves doesn't actually get the racer to their target destination, and there's a noticeable delay each time the game has to run the algorithm (which is often, since the List is often empty).
The only reasons I see for this happening are the displacement being wrong, the velocity being wrong, and my loop that checks for walls being wrong- but if they are, I can't figure out what to do right.
Here's all the relevant code (you may have to copy-paste it elsewhere for it to be readable):
public class Move{ //the custom move class
private int turn;
private int moving;
private int drift;
private int prevDrift;
private int dBoost;
private int power;
private Vector3 start;
private Vector3 forward;
private Vector3 velocity;
private Move previous;
private Quaternion rot;
private Vector3 trans;
private Vector3 disp;
private MovementScript movement;
public string name;
public Move (int t, int m, int d, int db, int k, Vector3 s, Vector3 f, Vector3 v, Move p, MovementScript move){
turn = t;
moving = m;
drift = d;
dBoost = db;
power = k;
start = s;
forward = f;
float dragForceMagnitude = v.sqrMagnitude * move.GetComponent<Rigidbody>().drag;
Vector3 dragForceVector = dragForceMagnitude * -v.normalized;
velocity = v + dragForceVector;
previous = p;
movement = move;
if (previous != null) {
prevDrift = previous.GetDrift ();
} else if (dBoost > 0) {
prevDrift = (int)(movement.driftDir);
} else {
prevDrift = 0;
}
rot = MakeRotation ();
trans = MakeTranslation ();
disp = MakeDisplacement ();
}
public int GetTurn (){
return turn;
}
public int GetMoving (){
return moving;
}
public Move GetPrevious (){
return previous;
}
public int GetDrift (){
return drift;
}
public int GetDriftBoost (){
return dBoost;
}
public int GetPreviousDrift (){
return prevDrift;
}
public int GetPower (){
return power;
}
public Vector3 GetStart (){
return start;
}
public Vector3 GetForward (){
return forward;
}
public Vector3 GetVelocity (){
return velocity;
}
public Quaternion GetRotation (){
return rot;
}
public Vector3 GetTranslation (){
return trans;
}
public Vector3 GetDisplacement (){
return disp;
}
private Quaternion MakeRotation (){
if (drift == turn) {
return Quaternion.Euler (0, movement.handling * turn * 4 / 5, 0);
} else if (drift == turn * -1) {
Quaternion.Euler (0, movement.handling * turn / 8, 0);
} else if (drift == 0 && turn != 0) {
return Quaternion.Euler (0, movement.handling * turn / 2, 0);
} else if (turn == 0 && drift != 0) {
return Quaternion.Euler (0, movement.handling * drift / 6, 0);
}
return Quaternion.Euler (0, 0, 0);
}
private Vector3 MakeTranslation (){
Vector3 temp = velocity;
if (prevDrift != 0 && drift == 0) {
temp += forward * Mathf.Sqrt (dBoost) * 6;
dBoost = 0;
}
if (moving > 0) {
if (velocity.magnitude < (movement.speed + 3.0) / 2 * 5) {
temp += forward * (float)((movement.acceleration + 3.0) / 2.0) * 1.0f / 2;
} else if (!sameAngle (velocity, forward)) {
temp += forward * (float)((movement.acceleration + 3.0) / 2.0) * 1.0f / 4;
}
if (moving == 2 && velocity.magnitude < (movement.speed + 3.0) / 2.0 * 5.0 * (5.7 + (movement.boost + 3.0) / 2.0) / 2.2) {
if (!movement.super || movement.special != 23)
power -= (int)((Mathf.Sqrt (movement.acceleration / 3.0f) + 1f) * 3.0f / 4.0f);
temp += forward * (float)((movement.acceleration + 6.0) / 3.0) * (float)(3.0 / 4.0);
}
}
return temp;
}
private Vector3 MakeDisplacement (){
return rot * trans;
}
}
}
public SortedDictionary<string, Move> AllMoves (int dBoost, int power, Vector3 start, Vector3 forward, Vector3 velocity, Move previous)
{ //makes the set of all possible moves
SortedDictionary<string, Move> moves = new SortedDictionary<string, Move> ();
moves.Add ("stop", new Move (0, 0, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("turn left", new Move (-1, 0, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("turn right", new Move (1, 0, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("move", new Move (0, 1, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("move left", new Move (-1, 1, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("move right", new Move (1, 1, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost", new Move (0, 2, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost left", new Move (-1, 2, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost right", new Move (1, 2, 0, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift straight left", new Move (0, 1, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift left correct", new Move (-1, 1, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift right wrong", new Move (1, 1, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift straight left", new Move (0, 2, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift left correct", new Move (-1, 2, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift right wrong", new Move (1, 2, -1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift straight right", new Move (0, 1, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift left wrong", new Move (-1, 1, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("drift right correct", new Move (1, 1, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift straight right", new Move (0, 2, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift left wrong", new Move (-1, 2, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
moves.Add ("boost drift right correct", new Move (1, 2, 1, dBoost, power, start, forward, velocity, previous, GetComponent<MovementScript> ()));
SortedDictionary<string, Move> finalmoves = new SortedDictionary<string, Move> ();
foreach (KeyValuePair<string, Move> kvd in moves) {
if (previous == null || kvd.Value.GetDrift () == 0 || kvd.Value.GetDrift () == previous.GetDrift ()) {
finalmoves.Add (kvd.Key, kvd.Value);
}
kvd.Value.name = kvd.Key;
}
return finalmoves;
}
public Stack<Move> GeneratePath (Vector3 targetPosition)
{//the algorithm that creates the path
List<Move> finalMoves = new List<Move> ();
Queue<Move> nodes = new Queue<Move> ();
while (finalMoves.Count < (cpuLevel+1)*3) {
SortedDictionary<string, Move> possibleMoves;
Move node;
if (nodes.Count == 0) {
node = null;
possibleMoves = AllMoves (driftBoost, energy, transform.position, transform.forward, GetComponent<Rigidbody> ().velocity, null);
} else {
node = nodes.Dequeue ();
possibleMoves = AllMoves (node.GetDriftBoost (), node.GetPower (), node.GetStart () + node.GetVelocity() + node.GetDisplacement (), node.GetRotation () * node.GetForward (), node.GetVelocity() + node.GetDisplacement (), node);
}
if (node != null && (node.GetStart () - targetPosition).magnitude <= (node.GetVelocity() + node.GetDisplacement ()).magnitude) {
finalMoves.Add (node);
} else {
int ignored = 0;
foreach (KeyValuePair<string, Move> kvd in possibleMoves) {
if (kvd.Value.GetPower () > 0) {
RaycastHit[] r = Physics.RaycastAll (kvd.Value.GetStart (), kvd.Value.GetRotation () * kvd.Value.GetForward (), (kvd.Value.GetVelocity() + kvd.Value.GetDisplacement ()).magnitude);
bool b = false;
for (int i = 0; i < r.Length; i++) {
if (r [i].collider.CompareTag ("Wall")) {
b = true;
break;
}
}
if (!b) {
nodes.Enqueue (kvd.Value);
}
}
}
}
}
int index = Random.Range (0, finalMoves.Count);
Move m = null;
if (finalMoves.Count > 0)
m = finalMoves.ToArray () [index];
Stack<Move> path = new Stack<Move> ();
while (m != null) {
path.Push (m);
m = m.GetPrevious ();
}
return path;
}
//the part of Update that sets the AI's movement
//targetPosition is obtained earlier in the code, and it's definitely working
if (AIpath == null || AIpath.Count == 0) {
AIpath = GeneratePath (targetPosition);
}
Move m = null;
if (AIpath != null && AIpath.Count > 0)
m = AIpath.Pop ();
if (m != null) {
turn = m.GetTurn ();
moving = m.GetMoving ();
drift = m.GetDrift ();
driftBoost = m.GetDriftBoost ();
energy = m.GetPower ();
rb.velocity += m.GetDisplacement ();
rb.MoveRotation (rb.rotation * m.GetRotation ());
}
//for reference, here is the completely working player code
moving = direction;
drift = (int)(driftDir);
if (Input.GetAxis ("Gas") > 0) {
direction = 1;
if (rb.velocity.magnitude < (speed + 3.0) / 2 * 5) {
rb.velocity += transform.forward * (float)((acceleration + 3.0) / 2.0) * Input.GetAxis ("Gas") / 2;
} else if (!sameAngle (rb.velocity, transform.forward)) {
rb.velocity += transform.forward * (float)((acceleration + 3.0) / 2.0) * Input.GetAxis ("Gas") / 4;
}
} else if (Input.GetAxis ("Brake") > 0 && ((direction == 1 && rb.velocity.magnitude > 0) || rb.velocity.magnitude > speed * 6)) {
rb.velocity -= transform.forward * (float)((acceleration + 3.0) / 2.0) / 5;
if (rb.velocity.magnitude < speed / 2 || reverseAngle (rb.velocity, transform.forward)) {
direction = 0;
}
} else if (Input.GetAxis ("Brake") > 0 && direction <= 0 && rb.velocity.magnitude < speed * 2) {
direction = -1;
rb.velocity -= transform.forward * (float)((acceleration + 3.0) / 2.0) * Input.GetAxis ("Brake") / 7;
} else if (rb.velocity.magnitude > 0) {
rb.velocity -= transform.forward / 10;
if (rb.velocity.magnitude < speed / 2) {
direction = 0;
}
} else if (direction < 0) {
rb.velocity += transform.forward / 10;
if (rb.velocity.magnitude < speed / 2) {
direction = 0;
}
}
if (Input.GetAxis ("Horizontal") != 0) {
turn = (int)Mathf.Sign (Input.GetAxis ("Horizontal"));
if (Input.GetAxis ("Brake") > 0 && direction != 0) {
if (direction == 1) {
if (driftDir == 0 || driftDir == Input.GetAxis ("Horizontal") / Mathf.Abs (Input.GetAxis ("Horizontal"))) {
driftDir = Input.GetAxis ("Horizontal") / Mathf.Abs (Input.GetAxis ("Horizontal"));
var deltaRotation = Quaternion.Euler (0, handling * Input.GetAxis ("Horizontal") * Input.GetAxis ("Brake") * 4 / 5, 0);
rb.MoveRotation (rb.rotation * deltaRotation);
driftBoost++;
} else {
var deltaRotation = Quaternion.Euler (0, handling * Input.GetAxis ("Horizontal") / 8, 0);
rb.MoveRotation (rb.rotation * deltaRotation);
}
}
if (direction == -1) {
var deltaRotation = Quaternion.Euler (0, handling * Input.GetAxis ("Horizontal") / -4, 0);
rb.MoveRotation (rb.rotation * deltaRotation);
}
} else {
var deltaRotation = Quaternion.Euler (0, handling * Input.GetAxis ("Horizontal") / 2, 0);
rb.MoveRotation (rb.rotation * deltaRotation);
//Debug.Log ("AAAAA");
}
}
if (Input.GetAxis ("Horizontal") == 0 && driftDir != 0) {
var deltaRotation = Quaternion.Euler (0, handling * driftDir / 6, 0);
rb.MoveRotation (rb.rotation * deltaRotation);
}
if (Input.GetAxis ("Boost") > 0 && rb.velocity.magnitude < (speed + 3.0) / 2.0 * 5.0 * (5.7 + (boost + 3.0) / 2.0) / 2.2) {
if (!super || special != 23)
energy -= (int)((Mathf.Sqrt (acceleration / 3.0f) + 1f) * 3.0f / 4.0f);
rb.velocity += transform.forward * (float)((acceleration + 6.0) / 3.0) * Input.GetAxis ("Boost") * (float)(3.0 / 4.0);
}
if (Input.GetAxis ("Boost") > 0) {
moving = 2;
}
if (Input.GetAxis ("Brake") == 0 && driftDir != 0 && direction != -1 && Input.GetAxis ("Gas") > 0) {
rb.velocity += transform.forward * Mathf.Sqrt (driftBoost) * 6;
driftBoost = 0;
driftDir = 0;
}
I can clarify any part of the code if it's confusing, but the main point is that the movement for the AI is exactly the same as the movement for the player, so there has to be some external factor that's making it not work.
