using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PathFinding
{
// move from A to B
public static List<Vector2> Find(int[,] tileMap, Vector2 A, Vector2 B)
{
List<Vector2> pathTileOpen = new List<Vector2>();
List<Vector2> pathTileOpenBackTrace = new List<Vector2>(); // for back trace
List<int> pathTileOpenBackTraceScore = new List<int>();
List<int> pathTileOpenScore = new List<int>();
List<Vector2> pathTileClose = new List<Vector2>();
pathTileOpenBackTrace.Clear();
pathTileOpenBackTraceScore.Clear();
pathTileOpen.Clear();
pathTileClose.Clear();
Vector2 currentTile = A;
List<Vector2> adjacentTile = new List<Vector2>();
int score;
int lowestScoreIndex;
// First, build up the path tile that can arrive destination
do
{
adjacentTile.Clear();
// add adjacent tile to pathTileOpen
// 4 adjacent tile to current tile
// Make sure the adjacent tile is not outside the titleMap
if (currentTile.x < tileMap.GetLength(0))
adjacentTile.Add(new Vector2(currentTile.x + 1, currentTile.y));
if (currentTile.x >0)
adjacentTile.Add(new Vector2(currentTile.x - 1, currentTile.y));
if(currentTile.y<tileMap.GetLength(1))
adjacentTile.Add(new Vector2(currentTile.x, currentTile.y + 1));
if (currentTile.y >0)
adjacentTile.Add(new Vector2(currentTile.x, currentTile.y - 1));
// if adjacent tile include destination, break loop
if (adjacentTile.Contains(B))
break;
// remove non-walkable tile
for (int i = 0; i< adjacentTile.Count ; i++)
if (tileMap[(int)adjacentTile[i].x, (int)adjacentTile[i].y] != (int)MapTileValue.Empty)
{
Debug.Log(adjacentTile[i]);
adjacentTile.RemoveAt(i);
i--;
}
// adjacent title that repeat with path tile will be removed and not consider
for (int i = adjacentTile.Count - 1; i >= 0; i--)
if (pathTileClose.Contains(adjacentTile[i]))
adjacentTile.RemoveAt(i);
for (int i = adjacentTile.Count - 1; i >= 0; i--)
{
if (!pathTileOpen.Contains(adjacentTile[i]) && adjacentTile[i]!=A) // dont take point A as adjacent tile
{
pathTileOpen.Add(adjacentTile[i]);
pathTileOpenBackTrace.Add(adjacentTile[i]);
// Caculate Score for each adjacent tile
// Score = Movement Cost + Estimated Movement Cost
score = (int)(Mathf.Abs(adjacentTile[i].x - A.x) + Mathf.Abs(adjacentTile[i].y - A.y)) + (int)(Mathf.Abs(adjacentTile[i].x - B.x) + Mathf.Abs(adjacentTile[i].y - B.y));
pathTileOpenScore.Add(score);
pathTileOpenBackTraceScore.Add(score);
}
}
lowestScoreIndex = LowestScoreIndex(pathTileOpenScore);
currentTile = pathTileOpen[lowestScoreIndex];
// add lowest score to pathTileClose
pathTileClose.Add(currentTile);
// remove lowest score tile from pathTileOpen
pathTileOpen.RemoveAt(lowestScoreIndex);
pathTileOpenScore.RemoveAt(lowestScoreIndex);
} while (pathTileOpen.Count !=0);
// Second, use the open path for back trace from destination to start point
return BackTrace(pathTileOpenBackTrace, pathTileOpenBackTraceScore, B, A);
}
// back trace B to A in the exisitng path tile close
static List<Vector2> BackTrace(List<Vector2> openTile, List<int> score, Vector2 B, Vector2 A)
{
List<Vector2> backTraceResult = new List<Vector2>();
Vector2 currentTile;
List<Vector2> adjacentTile = new List<Vector2>();
int lowestEstimatedCost, lowestEstimatedCostIndex;
currentTile = B;
do
{
// Get 4 adjacent Tile, tile boundary dont matter because the tile out of the edge will never be the ptc member
adjacentTile.Clear();
adjacentTile.Add(new Vector2(currentTile.x + 1, currentTile.y));
adjacentTile.Add(new Vector2(currentTile.x - 1, currentTile.y));
adjacentTile.Add(new Vector2(currentTile.x, currentTile.y + 1));
adjacentTile.Add(new Vector2(currentTile.x, currentTile.y - 1));
if (adjacentTile.Contains(A))
return backTraceResult;
// remove tile not in the open tile list
for (int i = adjacentTile.Count - 1; i >= 0; i--)
if (!openTile.Contains(adjacentTile[i]))
{
adjacentTile.RemoveAt(i);
i = adjacentTile.Count;
}
// Set a value for lowest estimated cost, so it can used to compare in loop
// only use the estimated cost, because there will be problem if use the total score
lowestEstimatedCost = (int)(Mathf.Abs(adjacentTile[0].x - A.x) + Mathf.Abs(adjacentTile[0].y - A.y));
lowestEstimatedCostIndex = 0;
for (int i = adjacentTile.Count - 1; i >= 0; i--)
{
if (lowestEstimatedCost > (int)(Mathf.Abs(adjacentTile[i].x - A.x) + Mathf.Abs(adjacentTile[i].y - A.y)))
lowestEstimatedCostIndex = i;
}
backTraceResult.Add(adjacentTile[lowestEstimatedCostIndex]);
currentTile = adjacentTile[lowestEstimatedCostIndex];
} while (true);
//return backTraceResult;
}
static int LowestScoreIndex(List<int> score)
{
// Use the final open list title to start comparison
int lowest = score[score.Count-1];
int lowestIndex =score.Count-1;
//Debug.Log(lowestIndex);
//Debug.Log(lowest);
for(int i=score.Count; i>0 ;i--)
{
// Debug.Log(i-1);
if (lowest > score[i-1])
{
lowest = score[i-1];
lowestIndex = i-1;
}
}
return lowestIndex;
}
}
I know the error come from " adjacentTile.RemoveAt(i)", because no error when i delete it.
// remove non-walkable tile
for (int i = 0; i< adjacentTile.Count ; i++)
if (tileMap[(int)adjacentTile[i].x, (int)adjacentTile[i].y] != (int)MapTileValue.Empty)
{
Debug.Log(adjacentTile[i]);
adjacentTile.RemoveAt(i);
i--;
}