Add penalty to previous path on point graph to prevent u-turns? A* Pathfinding Project

alt text

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;
	} 
} 

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.