• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
Question by dendens2 · Apr 19, 2013 at 11:29 PM · javascriptaipathfindingalgorithm

A* optimization and path help

Ok, so I made a A* script. My problem, however, is that I don't know how to actually get the list of nodes that leads the object to its target after all of the g, h, and f values have been checked. How do I do that? Also, with my script, the game will freeze. Partly because of the while loop never ending (since I don't know how to get the actual path). But even when I did not have it, the game still freezes up for a for a about half a sec(multiplied by the amount of zombies) every time it updates the path (every second). I need help optimizing my script. I know it is because all of the loops, but I don't know how to get around them. Also, did I do my A* script correctly? Thanks!

GridCell Class:

 class GridCell
 {
 var cellWalkable: boolean;
 var cellHeight: float;
 var cellX: float;
 var cellZ: float;
 var transformPosition: Vector3;
 var hueristicValue: float;
 var movementCost: float;
 var totalMoveCost: float;
 var onOpenList: boolean = false;
 var onClosedList: boolean = false;
 var onNeighborList: boolean = false;
 
 
 
 }

That class is located in a script called NavCube. The NavCube is taken from a tutorial, and what it does is create the cells. It is essentially a cube that is invisible and has no mesh collider, but engulfs the whole level.(The generation of a grid does not lag at all)

NavCube Script:

 //GridCell Class creation 
 
 
 
 //Other variables and the code
 
 var mapWidth: int;
 var mapHeight: int;
 var cellSize: float = 1;
 var bounds: Bounds;
 var topLeftCorner: Vector3;
 var walkableLayer;
 
 //Map of the world
 var gridCellList: List.<GridCell> = new List.<GridCell>();
 
 var square: GameObject;
 
 function Start () 
 {
 
         bounds = renderer.bounds;
         walkableLayer = LayerMask.NameToLayer("walkable");
 
 }
 
 function Update () 
 {
 //Scans the bounds of the model, then creates a grid
     //Finds the top left corner
     topLeftCorner = bounds.center - bounds.extents + Vector3(0, bounds.size.y, 0);
     
     //creates the grid map
     
     //Calculates the dimensions of the grid map.
     mapWidth = Mathf.RoundToInt(bounds.size.x / cellSize);
     mapHeight = Mathf.RoundToInt(bounds.size.z / cellSize);
     //Scans for walkable terrain in each cell
     for(var x = 0; x < mapWidth; x++)
     {
         for(var y = 0; y < mapHeight; y++)
         {
             //Gets the position for a ray
             var currentPosition = topLeftCorner + Vector3(x * cellSize, 0, y * cellSize);
             var hit: RaycastHit;
             //Creates a cell for the grid
             var cell = new GridCell();
             
             //Cast the ray
             if(Physics.Raycast(currentPosition, Vector3(0, -1, 0),hit, bounds.size.y))
             {
                 
                 if(hit.transform.gameObject.layer == walkableLayer)
                 {
                     cell.cellHeight = hit.point.y;
                     cell.cellX = hit.point.x;
                     cell.cellZ = hit.point.z;
                     cell.transformPosition = Vector3(cell.cellX, cell.cellHeight, cell.cellZ);
                     gridCellList.Add(cell);    
                     
                 }
             }
         }
         
     }
 
 }
 


After that, I have a ZombieScript. It contains the actual A* algorithm. I am not including the extra zombie part of the script in here. Again, please tell me if I am doing the actual A* correct.

ZombieScript Script:

 //Zombie code...
 
 
 //A*
 
 function UpdateGrid() //The actual A* algorithim
 {
     
     var pathFound: boolean = false;
     
     //Nearest cells and their distances from the player or zombie
     var nearestCellDistance: float = Mathf.Infinity;
     var nearestTargetCellDistance: float = Mathf.Infinity;
     var nearestCell: GridCell;
     var nearestTargetCell: GridCell;
     
     //The open list, closed list, and neighbor list
     var openList: List.<GridCell> = new List.<GridCell>();
     var closedList: List.<GridCell> = new List.<GridCell>();
     var neighborList: List.<GridCell> = new List.<GridCell>();
     
     //The node with the smallest f value, and its value
     var smallestTotalMoveCostNode: GridCell;
     var smallestTotalMoveCost: float = Mathf.Infinity;
 
     
     //Finds the nearest node to the zombie and to the player(The one they are standing on)
     
     for(var i = 0; i < navCubeScript.gridCellList.Count; i++)
     {
         if(Vector3.Distance(transform.position, navCubeScript.gridCellList[i].transformPosition) < nearestCellDistance)
         {
             nearestCell = navCubeScript.gridCellList[i];
             nearestCellDistance = Vector3.Distance(transform.position, navCubeScript.gridCellList[i].transformPosition);
         }
         
         if(Vector3.Distance(playerTransform.position, navCubeScript.gridCellList[i].transformPosition) < nearestTargetCellDistance)
         {
             nearestTargetCell = navCubeScript.gridCellList[i];
             nearestTargetCellDistance = Vector3.Distance(playerTransform.position, navCubeScript.gridCellList[i].transformPosition);
         }
     }
     
     var currentNode: GridCell = nearestCell;
     currentNode.onOpenList = true;
     openList.Add(currentNode);
     currentNode.hueristicValue = Vector3.Distance(currentNode.transformPosition, nearestTargetCell.transformPosition);
     currentNode.movementCost = 0;
     currentNode.totalMoveCost = currentNode.hueristicValue + currentNode.movementCost;
 
     while(pathFound == false)
     {
 
         //Finds the node with the lowest f score
         for(var ii = 0; ii < openList.Count; ii++)
         {
             if(openList[ii].totalMoveCost < smallestTotalMoveCost)
             {
                 smallestTotalMoveCostNode = openList[ii];
                 smallestTotalMoveCost = openList[ii].totalMoveCost;
             }
         }
         
         //Adds the node to the closed list
         smallestTotalMoveCostNode.onClosedList = true;
         closedList.Add(smallestTotalMoveCostNode);
         
         //Finds the neighbors of the cell
         for(var iii = 0; iii < navCubeScript.gridCellList.Count; iii++)
         {    
             if((Vector3.Distance(currentNode.transformPosition, navCubeScript.gridCellList[iii].transformPosition) < 0.8))
             {
                 if(navCubeScript.gridCellList[iii].onClosedList == false)
                 {
                     //Finds the temp cost of moving
                     var tempMovementCost = Vector3.Distance(currentNode.transformPosition, navCubeScript.gridCellList[iii].transformPosition);
                     
                     if(navCubeScript.gridCellList[iii].onOpenList == false)
                     {
                         navCubeScript.gridCellList[iii].onOpenList = true;
                         openList.Add(navCubeScript.gridCellList[iii]);
                     }
                     
 
                     //Checks if the open set node gscore > temp cost
                     for(var iv = 0; iv < openList.Count; iv++)
                     {
                         if(Vector3.Distance(currentNode.transformPosition, openList[iv].transformPosition) >  tempMovementCost)
                         {
                             openList[iv].movementCost = tempMovementCost;
                             openList[iv].totalMoveCost = openList[iv].movementCost + Vector3.Distance(openList[iv].transformPosition, nearestTargetCell.transformPosition);
                         }
                     }
                 }
                 
             }
         }
         }
         
     
     
 }



Thanks for taking the time to read my long post! Please keep in mind though that this is my first time using an algorithm and doing something this complicated, just in case I did something stupid. THANKS!

Comment

People who like this

0 Show 2
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image dendens2 · Apr 20, 2013 at 01:13 AM 0
Share

Anyone? :(

avatar image Jarsh13 · May 14, 2013 at 04:14 AM 0
Share

How are you handling your neighbors? How do the cells know which cells are its neighbor?

And dont worry I just finished my first A* path finding it took me a while but I got it just keep at it:)

0 Replies

· Add your reply
  • Sort: 

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Welcome to Unity Answers

If you’re new to Unity Answers, please check our User Guide to help you navigate through our website and refer to our FAQ for more information.

Before posting, make sure to check out our Knowledge Base for commonly asked Unity questions.

Check our Moderator Guidelines if you’re a new moderator and want to work together in an effort to improve Unity Answers and support our users.

Follow this Question

Answers Answers and Comments

12 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

A* Pathfinding AIFollow in JavaScript? 0 Answers

How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer

Online Advanced AI(Artificial Intelligence) with JS 3 Answers

AI Pathfinding Script 4 Answers

Basic Enemy Javascript 0 Answers


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges