List<GameObject> list = m_PathFinding.GetPath(m_Start, m_Goal);
foreach(GameObject obj in list) {
GridNode node = obj.GetComponent<GridNode>();
if(node.State == GridNode.eState.OnPath) {
m_InfoList[node.NodeInfo.index].renderer.material.color = Color.black;
}
}
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class PathFinding {
const int COST_MAX = int.MaxValue;
GameObject m_Start;
GameObject m_Goal;
List<GameObject> m_RefGridNodeList;
public List<GameObject> RefGridNodeList {
get { return m_RefGridNodeList; }
set { m_RefGridNodeList = value; }
}
List<GameObject> m_OpenList;
List<GameObject> m_CloseList;
public PathFinding() {
m_Start = null;
m_Goal = null;
m_RefGridNodeList = null;
m_OpenList = new List<GameObject>();
m_CloseList = new List<GameObject>();
}
public List<GameObject> GetPath(GameObject start, GameObject goal) {
if(m_RefGridNodeList == null) {
return null;
}
m_Start = start;
m_Goal = goal;
if(!Search()) {
return null;
}
return CreatePathList();
}
bool Search() {
if(m_Start == null || m_Goal == null) {
return false;
}
m_OpenList.Clear();
m_CloseList.Clear();
m_OpenList.Add(m_Start);
m_Start.GetComponent<GridNode>().G = 0;
m_Start.GetComponent<GridNode>().F = Heuristic(m_Start);
while(true) {
if(m_OpenList.Count == 0) {
break;
}
int minCost = COST_MAX;
GameObject minObj = null;
foreach(GameObject obj in m_OpenList) {
GridNode search = obj.GetComponent<GridNode>();
if(search.Done) {
continue;
}
if(search.F < minCost) {
minCost = (int)search.F;
minObj = obj;
}
}
if( minObj == null) {
return false;
}
minObj.GetComponent<GridNode>().Done = true;
if( minObj.GetComponent<GridNode>().State == GridNode.eState.Goal) {
break;
}
else {
m_CloseList.Add(minObj);
m_OpenList.Remove(minObj);
}
UpdateScore(minObj);
}
return true;
}
int Heuristic(GameObject obj) {
GridNode goal = m_Goal.GetComponent<GridNode>();
GridNode node = obj.GetComponent<GridNode>();
return (int)Vector3.Distance(node.NodeInfo.center, goal.NodeInfo.center);
}
void UpdateScore(GameObject obj) {
GridNode node = obj.GetComponent<GridNode>();
foreach(int i in node.NodeInfo.nearIndexList) {
GameObject co = m_RefGridNodeList[i];
Debug.Log(co);
CalculateScore(obj, co);
}
}
void CalculateScore(GameObject obj, GameObject near) {
GridNode base_node = obj.GetComponent<GridNode>();
GridNode near_node = near.GetComponent<GridNode>();
if(near_node.Done || near_node.Attribute == GridNode.eAttribute.Wall) {
return;
}
float nearF = base_node.G + 1 + Heuristic(near);;
bool isExistOpen = m_OpenList.Contains(near);
bool isExistClose = m_CloseList.Contains(near);
if(isExistOpen) {
if(nearF < near_node.F) {
near_node.F = nearF;
near_node.Parent = obj.GetComponent<GridNode>();
}
}
else if(isExistClose) {
if(nearF < near_node.F) {
near_node.F = nearF;
near_node.Parent = obj.GetComponent<GridNode>();
m_OpenList.Add(near);
m_CloseList.Remove(obj);
}
}
else {
near_node.F = nearF;
near_node.Parent = obj.GetComponent<GridNode>();
m_OpenList.Add(near);
m_CloseList.Remove(obj);
}
}
List<GameObject> CreatePathList() {
List<GameObject> list = new List<GameObject>();
GridNode node = m_Goal.GetComponent<GridNode>();
list.Add(node.gameObject);
node = node.Parent;
while(node && node.State != GridNode.eState.Start) {
list.Add(node.gameObject);
node.State = GridNode.eState.OnPath;
node = node.Parent;
}
list.Add(node.gameObject);
return list;
}
}