- 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