Where The Moon Meets The Sun

In my Unity-based tactical RPG, I implemented the A* algorithm for efficient pathfinding. This algorithm finds the shortest path from one tile to another by evaluating nodes based on cost and heuristic values. Starting with the open and closed lists, it continuously updates the path cost for neighboring nodes, adding them to the open list if they present a better route. The algorithm calculates distances using the Manhattan method and retraces the path from the destination to the start node. This algorithm has been useful for developing the enemies AI, as it allows enemies with tracking behavior to pursue player units from anywhere on the grid.

        public List FindShortestPath(int startX, int startZ, int endX, int endZ) {
            PathTile startTile = pathTiles[startX, startZ];
            PathTile endTile = pathTiles[endX, endZ];

            List openList = new List();
            List closedList = new List();

            openList.Add(startTile);

            while (openList.Count > 0) {
                PathTile currentTile = openList[0];

                for (int i = 0; i < openList.Count; i++) {
                    if (currentTile.fValue > openList[i].fValue) {
                        currentTile = openList[i];
                    }

                    if (currentTile.fValue == openList[i].fValue && currentTile.hValue > openList[i].hValue) {
                        currentTile = openList[i];
                    }
                }

                openList.Remove(currentTile);
                closedList.Add(currentTile);

                if (currentTile == endTile) {
                    return RetracePath(startTile, endTile);
                }

                List neighborTiles = new List();
                for (int x = -1; x < 2; x++) {
                    for (int z = -1; z < 2; z++) {
                        if ((x == 0 && z == 0) || (x != 0 && z != 0)) {continue;}
                        if (!gridTraverse.IsValid(currentTile.x + x, currentTile.z + z)) { continue; } //?
                        
                        neighborTiles.Add(pathTiles[currentTile.x + x, currentTile.z + z]);
                    }
                }

                for (int i = 0; i < neighborTiles.Count; i++) {
                    if (closedList.Contains(neighborTiles[i])) { continue; }
                    if (!gridTraverse.GetGridTile(neighborTiles[i].x, neighborTiles[i].z).GetPassable()) { continue; }

                    float moveCost = currentTile.gValue + CalculateDistance(currentTile , neighborTiles[i]);

                    if (!openList.Contains(neighborTiles[i]) || moveCost < neighborTiles[i].gValue) {
                        neighborTiles[i].gValue = moveCost;
                        neighborTiles[i].hValue = CalculateDistance(neighborTiles[i], endTile);
                        neighborTiles[i].parentTile = currentTile;

                        if(!openList.Contains(neighborTiles[i])) {
                            openList.Add(neighborTiles[i]);
                        }
                    }
                }
            }

            return null;
        }


        private int CalculateDistance(PathTile currentTile, PathTile targetTile) {
            int distX = Mathf.Abs(currentTile.x - targetTile.x);
            int distZ = Mathf.Abs(currentTile.z - targetTile.z);

            if (distX > distZ) { return 14 * distZ + 10 * (distX - distZ); }
            return 14 * distX + 10 * (distZ - distX);
        }

        private List RetracePath(PathTile startTile, PathTile endTile) {
            List path = new List();

            PathTile currentTile = endTile;

            while (currentTile != startTile) {
                path.Add(currentTile);
                currentTile = currentTile.parentTile;
            }
            path.Reverse();
            return path;
        }

                

        public void calculateMovement(int startX, int startZ, int charMovement, UnitManager unit){

            //cellList is used to keep track to cells that need to be processed
            List cellList = new List();
            List processedList = new List();

            bool [,] discard;

            //Adds the starting cell to both cellList and movableCells
            cellList.Add(gridTraverse.GetGridTile(startX, startZ));
            processedList.Add(gridTraverse.GetGridTile(startX, startZ));

            //creates arrays that store the distance number and which cells have been visited
            moveDistances = new int[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            moveVisited = new bool[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            canAttack = new bool[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            canMove = new bool[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            Debug.Log(startX + " " + startZ);
            canMove[startX, startZ] = true;

            //Initilizes all distances with the max interger
            for (int i = 0; i < gridTraverse.GetWidth(); i++)
            {
                for (int j = 0; j < gridTraverse.GetLength(); j++)
                {
                    moveDistances[i, j] = int.MaxValue;
                }
            }

            moveDistances[startX, startZ] = 0;
            canMove[startX, startZ] = true;

            while (cellList.Count > 0)
            {
                GridTile currentCell = cellList[0];
                cellList.RemoveAt(0);

                int currX = currentCell.GetGridX();
                int currZ = currentCell.GetGridZ();

                if (moveVisited[currX, currZ]) { continue; }

                moveVisited[currX, currZ] = true;
                discard = CalculateAttack(currX, currZ, unit.primaryWeapon.Range, unit.primaryWeapon.Range1, unit.primaryWeapon.Range2, unit.primaryWeapon.Range3);

                for (int x = -1; x < 2; x++)
                {
                    for (int z = -1; z < 2; z++)
                    {
                        if ((x == 0 && z == 0) || (x != 0 && z != 0)) { continue; }

                        int nextX = currX + x;
                        int nextZ = currZ + z;

                        if (gridTraverse.IsValid(nextX, nextZ))
                        {

                            //If implementing flier class later on change this to check that case
                            int currCost = gridTraverse.GetGridTile(nextX, nextZ).GetMovementCost();

                            if (currCost == int.MaxValue || ((gridTraverse.GetGridTile(nextX, nextZ).UnitOnTile != null && gridTraverse.GetGridTile(nextX, nextZ).UnitOnTile.stats != null ) && gridTraverse.GetGridTile(nextX, nextZ).UnitOnTile.stats.UnitType != unit.stats.UnitType))
                            {
                                continue;
                            }

                            int newDistance = moveDistances[currX, currZ] + currCost;

                            if (!moveVisited[nextX, nextZ] && newDistance <= charMovement)
                            {
                                canMove[nextX, nextZ] = true;
                                moveDistances[nextX, nextZ] = newDistance;
                                if (!processedList.Contains(gridTraverse.GetGridTile(nextX, nextZ)))
                                {
                                    cellList.Add(gridTraverse.GetGridTile(nextX, nextZ));
                                }
                            }
                        }
                    }
                }
            }     
        }


        public bool[,] CalculateAttack(int startX, int startZ, int attackRange, bool canAttack1, bool canAttack2, bool canAttack3){
            List cellList = new List();
            List processedList = new List();

            sX = startX;
            sZ = startZ;

            cellList.Add(gridTraverse.GetGridTile(startX, startZ));
            processedList.Add(gridTraverse.GetGridTile(startX, startZ));

            attackDistances = new int[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            attackVisited = new bool[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            canOnlyAttack = new bool[gridTraverse.GetWidth(), gridTraverse.GetLength()];
            

            for (int i = 0; i < gridTraverse.GetWidth(); i++)
            {
                for (int j = 0; j < gridTraverse.GetLength(); j++)
                {
                    attackDistances[i, j] = int.MaxValue;
                }
            }

            attackDistances[startX, startZ] = 0;
            canAttack[startX, startZ] = true;

            while (cellList.Count > 0)
            {
                GridTile currentCell = cellList[0];
                cellList.RemoveAt(0);

                int currX = currentCell.GetGridX();
                int currZ = currentCell.GetGridZ();

                if (attackVisited[currX, currZ])
                {
                    continue;
                }

                attackVisited[currX, currZ] = true;

                for (int x = -1; x < 2; x++)
                {
                    for (int z = -1; z < 2; z++)
                    {
                        if ((x == 0 && z == 0) || (x != 0 && z != 0))
                        {
                            continue;
                        }

                        int nextX = currX + x;
                        int nextZ = currZ + z;

                        if (gridTraverse.IsValid(nextX, nextZ))
                        {

                            //If implementing flier class later on change this to check that case
                            int currCost = gridTraverse.GetGridTile(nextX, nextZ).GetAttackCost();

                            if (currCost == int.MaxValue)
                            {
                                continue;
                            }

                            int newDistance = attackDistances[currX, currZ] + currCost;

                            if (!attackVisited[nextX, nextZ] && newDistance <= attackRange)
                            {   
                                if (attackRange > 3 && newDistance > 3) {
                                    canAttack[nextX, nextZ] = true;
                                    canOnlyAttack[nextX, nextZ] = true;
                                }

                                if (canAttack1 && newDistance == 1) {
                                    canAttack[nextX, nextZ] = true;
                                    canOnlyAttack[nextX, nextZ] = true;

                                }
                                if (canAttack2 && newDistance == 2) {
                                    canAttack[nextX, nextZ] = true;
                                    canOnlyAttack[nextX, nextZ] = true;
                                }
                                if (canAttack3 && newDistance == 3) {
                                    canAttack[nextX, nextZ] = true;
                                    canOnlyAttack[nextX, nextZ] = true;
                                }
                                
                                attackDistances[nextX, nextZ] = newDistance;
                                if (!processedList.Contains(gridTraverse.GetGridTile(nextX, nextZ)))
                                {
                                    cellList.Add(gridTraverse.GetGridTile(nextX, nextZ));
                                }
                            }
                        }
                    }
                }
            }
            return canOnlyAttack;
        }