A*コード
A*のノード
using UnityEngine; using System.Collections; public class cNode : MonoBehaviour { void Awake() { m_parent = null; m_x = m_y = 0; m_f = m_g = 0.0f; m_attribute = eAttribute.Empty; m_state = eState.None; m_done = false; } public enum eAttribute { Empty, Wall, Max, }; public enum eState { None, Start, Goal, OnPath, Max, }; cNode m_parent; public cNode Parent { get { return m_parent; } set { m_parent = value; } } int m_x; public int X { get { return m_x; } set { m_x = value; } } int m_y; public int Y { get { return m_y; } set { m_y = value; } } float m_f; public float F { get { return m_f; } set { m_f = value; } } float m_g; public float G { get { return m_g; } set { m_g = value; } } eAttribute m_attribute; public eAttribute Attribute { get { return m_attribute; } set { m_attribute = value; } } eState m_state; public eState State { get { return m_state; } set { m_state = value; } } bool m_done; public bool Done { get { return m_done; } set { m_done = value; } } public string m_text; }
A*のパス検索部分
using UnityEngine; using System.Collections; using System.Collections.Generic; public class cPathFinding : MonoBehaviour { const int COST_MAX = int.MaxValue; static int [] checkX = { 0, -1, 1, 0 }; static int [] checkY = { -1, 0, 0, 1 }; enum eState { Search, Input, }; eState m_state; List<GameObject> m_listOpen; List<GameObject> m_listClose; [SerializeField] int m_gridNum = 30; public int GridNum { get { return m_gridNum; } set { m_gridNum = value; } } GameObject [,] m_grid; GameObject m_start; GameObject m_goal; GameObject m_quadPrefab; Vector3 m_gridBasePoint; void Awake() { m_start = null; m_goal = null; m_state = eState.Input; m_listOpen = new List<GameObject>(); m_listClose = new List<GameObject>(); m_gridBasePoint = new Vector3(m_gridNum/2, m_gridNum/2, 0); m_quadPrefab = Resources.Load("AStar/Cell") as GameObject; m_grid = new GameObject[m_gridNum, m_gridNum]; GameObject obj = null; for(int y = 0; y < m_gridNum; ++y) { for(int x = 0; x < m_gridNum; ++x) { obj = Instantiate(m_quadPrefab, new Vector3((x-m_gridBasePoint.x)*2.0f, (y-m_gridBasePoint.y)*2.0f, 0), Quaternion.identity) as GameObject; m_grid[x, y] = obj; obj.transform.localScale = new Vector3(2, 2, 2); obj.transform.parent = this.transform; BoxCollider bc = obj.AddComponent<BoxCollider>(); bc.center = Vector3.zero; cNode node = obj.GetComponent<cNode>(); node.X = x; node.Y = y; node.Attribute = cNode.eAttribute.Empty; } } } // Use this for initialization void Start () { int index = 0; for(int y = 0; y < m_gridNum; ++y) { for(int x = 0; x < m_gridNum; ++x) { cNode.eAttribute attr = cNode.eAttribute.Empty; if(y == 0 || y == m_gridNum-1 || x == 0 || x == m_gridNum-1) { attr = cNode.eAttribute.Wall; } m_grid[x, y].GetComponent<cNode>().Attribute = attr; m_grid[x, y].GetComponent<cNode>().m_text = index.ToString(); ++index; } } } // Update is called once per frame void Update () { switch(m_state) { case eState.Input: UpdateInput(); UpdateColor(); break; case eState.Search: Search(); ShowPath(); break; default: break; } } void UpdateInput() { if(Input.anyKeyDown) { if(Input.GetMouseButtonDown(0)) { SelectAttribute(); } if(Input.GetMouseButtonDown(1)) { SelectState(); } } } void UpdateColor() { for(int y = 0; y < m_gridNum; ++y) { for(int x = 0; x < m_gridNum; ++x) { CheckColor(x, y); } } } void CheckColor(int x, int y) { GameObject obj = m_grid[x, y]; CheckAttributeColor(obj); CheckStateColor(obj); } void CheckAttributeColor(GameObject obj) { cNode.eAttribute attr = obj.GetComponent<cNode>().Attribute; switch(attr) { case cNode.eAttribute.Empty: obj.renderer.material.color = Color.white; break; case cNode.eAttribute.Wall: obj.renderer.material.color = Color.red; break; } } void CheckStateColor(GameObject obj) { cNode.eState state = obj.GetComponent<cNode>().State; switch(state) { case cNode.eState.None: break; case cNode.eState.OnPath: obj.renderer.material.color = Color.black; break; case cNode.eState.Start: m_start = obj; obj.GetComponent<cNode>().Parent = null; obj.renderer.material.color = Color.blue; break; case cNode.eState.Goal: m_goal = obj; obj.GetComponent<cNode>().Parent = null; obj.renderer.material.color = Color.green; break; } } void SelectAttribute() { Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition); RaycastHit hit; if(Physics.Raycast(ray, out hit)) { GameObject obj = hit.collider.gameObject; if(obj) { cNode node = obj.GetComponent<cNode>(); cNode.eAttribute attr = node.Attribute; node.Attribute = (cNode.eAttribute)((int)(attr+1) % (int)cNode.eAttribute.Max); } } } void SelectState() { Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition); RaycastHit hit; if(Physics.Raycast(ray, out hit)) { GameObject obj = hit.collider.gameObject; if(obj) { cNode node = obj.GetComponent<cNode>(); cNode.eState state = node.State; node.State = (cNode.eState)((int)(state+1) % (int)cNode.eState.Max); } } } bool Search() { Debug.Log("Search Start"); if(m_start == null || m_goal == null) { return false; } m_listOpen.Clear(); m_listClose.Clear(); Debug.Log("start("+m_start.GetComponent<cNode>().X+","+m_start.GetComponent<cNode>().Y+")"); Debug.Log("goal("+m_goal.GetComponent<cNode>().X+","+m_goal.GetComponent<cNode>().Y+")"); m_listOpen.Add(m_start); m_start.GetComponent<cNode>().G = 0; m_start.GetComponent<cNode>().F = Heuristic(m_start); Debug.Log("start F="+m_start.GetComponent<cNode>().F+",G="+m_start.GetComponent<cNode>().G); while(true) { if(m_listOpen.Count == 0) { break; } int minCost = COST_MAX; int minX = -1; int minY = -1; GameObject minObj = null; foreach(GameObject obj in m_listOpen) { Debug.Log(obj+" in m_listOpen"); cNode search = obj.GetComponent<cNode>(); if(search.Done) { continue; } if(search.F < minCost) { minCost = (int)search.F; minObj = obj; minX = search.X; minY = search.Y; } } Debug.Log("minObj="+minObj.ToString()+","+"min("+minX+","+minY+")"); if( minObj == null) { return false; } minObj.GetComponent<cNode>().Done = true; if( minObj.GetComponent<cNode>().State == cNode.eState.Goal) { break; } else { m_listClose.Add(minObj); m_listOpen.Remove(minObj); } UpdateScore(minObj); } return true; } int Heuristic(GameObject obj) { cNode goal = m_goal.GetComponent<cNode>(); cNode node = obj.GetComponent<cNode>(); return Mathf.Abs(node.X - goal.X) + Mathf.Abs(node.Y - goal.Y); } void UpdateScore(GameObject obj) { cNode node = obj.GetComponent<cNode>(); int cx = node.X; int cy = node.Y; for(int i = 0; i < checkY.Length; ++i) { int x = cx + checkX[i]; int y = cy + checkY[i]; if( (0 <= x && x < m_gridNum) && (0 <= y && y < m_gridNum) ) { Debug.Log("("+x+","+y+")"); GameObject co = m_grid[x, y]; CalculateScore(obj, co); } } } void CalculateScore(GameObject obj, GameObject near) { cNode base_node = obj.GetComponent<cNode>(); cNode near_node = near.GetComponent<cNode>(); if(near_node.Done || near_node.Attribute == cNode.eAttribute.Wall) { return; } float nearF = base_node.G + 1 + Heuristic(near); Debug.Log("nearF="+nearF+","+"near="+near_node.F+")"); bool isExistOpen = m_listOpen.Contains(near); bool isExistClose = m_listClose.Contains(near); Debug.Log("InOpen="+isExistOpen.ToString()+","+"InClose="+isExistClose.ToString()+")"); if(isExistOpen) { if(nearF < near_node.F) { near_node.F = nearF; near_node.Parent = obj.GetComponent<cNode>(); } } else if(isExistClose) { if(nearF < near_node.F) { near_node.F = nearF; near_node.Parent = obj.GetComponent<cNode>(); m_listOpen.Add(near); m_listClose.Remove(obj); } } else { near_node.F = nearF; near_node.Parent = obj.GetComponent<cNode>(); m_listOpen.Add(near); m_listClose.Remove(obj); } } void ShowPath() { int i = 0; cNode node = m_goal.GetComponent<cNode>().Parent; while(node&&node.State!=cNode.eState.Start) { Debug.Log(i+":("+node.X+","+node.Y+")"); node.State = cNode.eState.OnPath; node = node.Parent; } } void Clear() { for(int y = 0; y < m_gridNum; ++y) { for(int x = 0; x < m_gridNum; ++x) { GameObject obj = m_grid[x, y]; cNode node = obj.GetComponent<cNode>(); node.Done = false; node.F = 0.0f; node.G = 0.0f; node.Parent = null; if(node.State == cNode.eState.OnPath) { node.State = cNode.eState.None; } } } } void OnGUI() { if(GUILayout.Button("Titleに移動")) { Application.LoadLevel("Title"); } if(GUILayout.Button("Search")) { Search(); ShowPath(); } if(GUILayout.Button("Clear")) { Clear(); } } }