- Home /
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!
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:)
Your answer
Follow this Question
Related Questions
A* Pathfinding AIFollow in JavaScript? 0 Answers
Generate tiles along a path a certain distance before reaching end position 1 Answer
Online Advanced AI(Artificial Intelligence) with JS 3 Answers
Basic Enemy Javascript 0 Answers
How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer