- Home /
Add penalty to previous path on point graph to prevent u-turns? A* Pathfinding Project
Hello,
I am using Aron Granberg's A* Pathfinding Project. So I have a point graph set up in the above picture. I have each car choosing a random node on the point graph and following a path to it. Right now, the cars traveling on the road have a tendency to make u-turns to get to their next destination. For example, suppose the original path was from point A to point B. Once the car reaches point B, it then randomly chooses to travel to point C. Is there any way where I can force it to always take the yellow path instead of the purple path to prevent u-turns? I was thinking something along the lines of setting penalties for the previous path, but the penalties would have to only apply to a single agent as I don't want the penalties to apply to the other cars on the road. Is there a feasible way to do this? I have included my pathfinding code below.
using UnityEngine;
using System.Collections;
using System.Linq;
//Note this line, if it is left out, the script won't know that the class 'Path' exists and it will throw compiler errors
//This line should always be present at the top of scripts which use %Pathfinding
using Pathfinding;
public class newPathfind : MonoBehaviour {
//The point to move to
private Vector3 targetPosition;
private bool pathComplete;
public bool ManualList = false;
public GameObject target1;
public GameObject target2;
public GameObject target3;
public GameObject target4;
public GameObject target5;
private GameObject[] Waypoints;
private GameObject[] oneway;
private GameObject[] twoway;
public static int randomPoint;
private Seeker seeker;
private CharacterController controller;
//The calculated path
public Path path;
//The AI's speed per second
public float speed = 500;
//The max distance from the AI to a waypoint for it to continue to the next waypoint
public float nextWaypointDistance = 3;
//The waypoint we are currently moving towards
private int currentWaypoint = 0;
public void Start () {
seeker = GetComponent<Seeker>();
controller = GetComponent<CharacterController>();
Vector3 randomLoc = Vector3.zero;
if (ManualList) {
Waypoints = new GameObject[5];
Waypoints[0] = target1;
Waypoints[1] = target2;
Waypoints[2] = target3;
Waypoints[3] = target4;
Waypoints[4] = target5;
} else {
//Waypoints = GameObject.FindGameObjectsWithTag("network");
twoway = GameObject.FindGameObjectsWithTag ("network");
oneway = GameObject.FindGameObjectsWithTag ("oneway");
Waypoints = oneway.Concat (twoway).ToArray ();
}
do {
randomPoint = Random.Range (0, Waypoints.Length-1);
randomLoc = Waypoints[randomPoint].transform.position;
targetPosition = new Vector3 (randomLoc.x, gameObject.transform.position.y, randomLoc.z);
} while ((Vector3.Distance(gameObject.transform.position, targetPosition) < 50f));
//Start a new path to the targetPosition, return the result to the OnPathComplete function
seeker.StartPath (transform.position,targetPosition, OnPathComplete);
}
public void OnPathComplete (Path p) {
Debug.Log ("Yey, we got a path back. Did it have an error? "+p.error);
if (!p.error) {
path = p;
//Reset the waypoint counter
currentWaypoint = 0;
pathComplete = true;
}
}
public void FixedUpdate () {
if (path == null) {
return;
}
if (currentWaypoint >= path.vectorPath.Count && pathComplete == true) {
Debug.Log ("End Of Path Reached");
Start();
pathComplete = false;
return;
}
//Direction to the next waypoint
Vector3 dir = Vector3.zero;
if (currentWaypoint >= 0 && currentWaypoint < path.vectorPath.Count) {
dir = (path.vectorPath [currentWaypoint] - transform.position).normalized;
}
if (dir != Vector3.zero) {
transform.rotation = Quaternion.LookRotation (dir);
}
dir *= speed * Time.fixedDeltaTime;
controller.SimpleMove (dir);
//Check if we are close enough to the next waypoint
//If we are, proceed to follow the next waypoint
if (Vector3.Distance (transform.position,path.vectorPath[currentWaypoint]) < nextWaypointDistance) {
currentWaypoint++;
return;
}
}
public void OnDisable () {
seeker.pathCallback -= OnPathComplete;
}
}
Answer by MakeCodeNow · Mar 05, 2014 at 07:23 PM
I've not used Aron's code, but with A* in general the correct thing to do is to modify the cost calculations in the A* search to include changes in orientation. By default, A* uses simple distance as the cost estimate, which means a node one unit ahead of you is just as good as a node one unit behind you. For your cars, though, a node behind you is more expensive than a node ahead of you, and you want the pathfinder to take that into account.
Even with this penalty, you may find cases where a U turn is the best option (i.e. where the forward distance is much longer than just pulling a U turn). In this case a lot of games implement a custom maneuver in the higher level AI that can execute a U turn that looks decent, and then go back to regular pathfinding.
Right, that's pretty much what I was thiking. I guess my question is more towards how to actually implement this specifically in Aron's engine. I'll keep your advice in $$anonymous$$d though. Thanks for the reply.
Your answer
Follow this Question
Related Questions
Pathfinding with Roads 2 Answers
Is there a way for an A* gridgraph pathfinding to consider the collider of terrain trees ? 0 Answers
A* Pathfinding Project Problem with Obstacles 2 Answers
A* Algorithm Node Grid Generation 2 Answers
How to reach 2D Grid from script? How to reach every tilemap location and use them for pathfinding? 1 Answer