グリッド状モデルfbxモデルからA*用のデータ作成
グリッド状モデルからA*用の隣接リストの作成をした。
https://dl.dropbox.com/u/67579260/Unity/Test02/WebPlayer/WebPlayer.html
黄色のゴールを作ってから、緑のスタートを作る
Editorスクリプトで生成したデータをゲームシーンに渡すための中間データクラス。
using UnityEngine; using System.Collections; using System.Collections.Generic; public class Grid : MonoBehaviour { public List<MapNode> m_MapNodeList; }
グリッドの中心点と四角形頂点、隣接インデックスリストを保持するクラス。
using UnityEngine; using System.Collections; using System.Collections.Generic; [System.Serializable] public class MapNode { public Vector3 center; public int index; public List<int> nearIndexList; public List<Vector3> vertexList; public MapNode() { center = Vector3.zero; index = -1; nearIndexList = null; vertexList = null; } }
グリッド状FBXから論理グリッドデータを作成
・頂点リストをソート
・中心点リスト
・隣接インデックスリスト
using UnityEditor; using UnityEngine; using System.Collections; using System.Collections.Generic; public class WizardCreateMapNode : ScriptableWizard { class Near { public int curIndex; public int leftIndex; public int upIndex; public int luIndex; public Vector3 cur; public Vector3 left; public Vector3 up; public Vector3 lu; public int index; public Vector3 center; public bool onMap; public Near() { curIndex = -1; leftIndex = -1; upIndex = -1; luIndex = -1; index = -1; cur = Vector3.zero; left = Vector3.zero; up = Vector3.zero; lu = Vector3.zero; center = Vector3.zero; onMap = false; } }; public GameObject m_TargetMap; List<Vector3> m_CenterList; List<Near> m_NearList; List<Near> m_ResizedNearList; List<MapNode> m_MapNodeList; [MenuItem ("Tools/MapNode")] static void Init () { ScriptableWizard.DisplayWizard<WizardCreateMapNode>("Create MapNode", "Create"); } void OnWizardCreate () { CreateMapNode(); } void CreateMapNode () { if(m_TargetMap == null) { return; } List<Vector3> vertexList = GetVertexList(m_TargetMap); ReCalculateGeometry(ref vertexList); SortVertexList(ref vertexList); CalculateNear(ref vertexList); CheckOnMap(); DebugCenterList(); ResizeNearList(); ContructNodeInfo(); GameObject grid = new GameObject("GridRoot"); Grid script = grid.AddComponent<Grid>(); script.m_MapNodeList = m_MapNodeList; } List<Vector3> GetVertexList(GameObject obj) { MeshFilter meshFilter = obj.GetComponent<MeshFilter>(); Mesh mesh = meshFilter.sharedMesh; List<Vector3> vertexList = new List<Vector3>(); foreach(Vector3 vertex in mesh.vertices) { vertexList.Add(vertex); } return vertexList; } void ReCalculateGeometry(ref List<Vector3> vertexList) { Quaternion rot = m_TargetMap.transform.rotation; Vector3 scale = m_TargetMap.transform.localScale; for(int i = 0; i < vertexList.Count; ++i) { Vector3 p = vertexList[i]; p = rot * p; p = Vector3.Scale(p, scale); vertexList[i] = p; } } void SortVertexList(ref List<Vector3> vertexList) { CompareVector3 cv = new CompareVector3(); vertexList.Sort(cv); } void CalculateNear(ref List<Vector3> sortedList) {; m_NearList = new List<Near>(); float DISTANCE = CalculatePointToPointDistance(ref sortedList); Debug.Log("DISTANCE="+DISTANCE); float EPSILON = 1.0f; int cnt = sortedList.Count; for(int i = 0; i < cnt; ++i) { Vector3 p = sortedList[i]; Near near = new Near(); near.cur = p; near.curIndex = i; // left for(int k = i+1; k < cnt; ++k) { Vector3 lp = sortedList[k]; if(Mathf.Abs(lp.x-(p.x+DISTANCE)) < EPSILON && Mathf.Abs(lp.z-p.z) < EPSILON) { near.left = lp; near.leftIndex = k; break; } } // up. for(int k = i+1; k < cnt; ++k) { Vector3 up = sortedList[k]; if(Mathf.Abs(up.x-p.x) < EPSILON && Mathf.Abs(up.z-(p.z+DISTANCE)) < EPSILON) { near.up = up; near.upIndex = k; break; } } // left up for(int k = i+1; k < cnt; ++k) { Vector3 lup = sortedList[k]; if(Mathf.Abs(lup.x-(p.x+DISTANCE)) < EPSILON && Mathf.Abs(lup.z-(p.z+DISTANCE)) < EPSILON) { near.lu = lup; near.luIndex = k; break; } } if(near.curIndex != -1 && near.leftIndex != -1 && near.upIndex != -1 && near.luIndex != -1 ) { near.index = i; near.center = GetCenter(near); m_NearList.Add(near); } } } void CheckOnMap() { int cnt = m_NearList.Count; for(int i = 0; i < cnt; ++i) { Vector3 center = m_NearList[i].center; Ray ray = new Ray(center+Vector3.up, -Vector3.up); RaycastHit hit; if(m_TargetMap.collider.Raycast(ray, out hit, float.MaxValue)) { m_NearList[i].onMap = true; } } } Vector3 GetCenter(Near near) { Vector3 left = near.left - near.cur; Vector3 up = near.up - near.cur; Vector3 center = (left+up)*0.5f+near.cur; return center; } float CalculatePointToPointDistance(ref List<Vector3> sortedList) { int cnt = sortedList.Count; float dist = float.MaxValue; for(int i = 0; i < cnt-1; ++i) { float d = Vector3.Distance(sortedList[i], sortedList[i+1]); if(d < dist) { dist = d; } } return dist; } void ContructNodeInfo() { m_MapNodeList = new List<MapNode>(); float DISTANCE = CalculatePointToPointDistance(ref m_CenterList); Debug.Log("DISTANCE="+DISTANCE); float EPSILON = 1.0f; int cnt = m_ResizedNearList.Count; for(int i = 0; i < cnt; ++i) { if(!m_ResizedNearList[i].onMap) { continue; } Vector3 p = m_ResizedNearList[i].center; MapNode node = new MapNode(); node.center = p; node.index = i; node.nearIndexList = new List<int>(); node.vertexList = new List<Vector3>(); // left for(int k = 0; k < cnt; ++k) { if(!m_ResizedNearList[k].onMap) { continue; } Vector3 lp = m_ResizedNearList[k].center; if(Mathf.Abs(lp.x-(p.x+DISTANCE)) < EPSILON && Mathf.Abs(lp.z-p.z) < EPSILON) { node.nearIndexList.Add(k); break; } } // right for(int k = 0; k < cnt; ++k) { if(!m_ResizedNearList[k].onMap) { continue; } Vector3 rp = m_ResizedNearList[k].center; if(Mathf.Abs(rp.x-(p.x-DISTANCE)) < EPSILON && Mathf.Abs(rp.z-p.z) < EPSILON) { node.nearIndexList.Add(k); break; } } // up. for(int k = 0; k < cnt; ++k) { if(!m_ResizedNearList[k].onMap) { continue; } Vector3 up = m_ResizedNearList[k].center; if(Mathf.Abs(up.x-p.x) < EPSILON && Mathf.Abs(up.z-(p.z+DISTANCE)) < EPSILON) { node.nearIndexList.Add(k); break; } } // down for(int k = 0; k < cnt; ++k) { if(!m_ResizedNearList[k].onMap) { continue; } Vector3 dp = m_ResizedNearList[k].center; if(Mathf.Abs(dp.x-p.x) < EPSILON && Mathf.Abs(dp.z-(p.z-DISTANCE)) < EPSILON) { node.nearIndexList.Add(k); break; } } node.vertexList.Add(m_ResizedNearList[i].cur); node.vertexList.Add(m_ResizedNearList[i].left); node.vertexList.Add(m_ResizedNearList[i].up); node.vertexList.Add(m_ResizedNearList[i].lu); m_MapNodeList.Add(node); } } void DebugCenterList() { m_CenterList = new List<Vector3>(); int cnt = m_NearList.Count; for(int i = 0; i < cnt; ++i) { if(m_NearList[i].onMap) { m_CenterList.Add(m_NearList[i].center); } } } void ResizeNearList() { m_ResizedNearList = new List<Near>(); int cnt = m_NearList.Count; for(int i = 0; i < cnt; ++i) { if(m_NearList[i].onMap) { m_ResizedNearList.Add(m_NearList[i]); } } } class CompareVector3 : IComparer<Vector3> { public int Compare(Vector3 v0, Vector3 v1) { int z = v0.z.CompareTo(v1.z); if(z == 0) { int y = v0.y.CompareTo(v0.y); if(y == 0) { return v0.x.CompareTo(v1.x); } return y; } return z; } }; }
A*用のノード
MapNodeの情報を元に構築
using UnityEngine; using System.Collections; public class GridNode : MonoBehaviour { public enum eAttribute { None, Wall, Max, }; public enum eState { None, Start, Goal, OnPath, Max, }; [SerializeField] GridNode m_Parent; public GridNode Parent { get { return m_Parent; } set { m_Parent = value; } } [SerializeField] MapNode m_NodeInfo; public MapNode NodeInfo { get { return m_NodeInfo; } set { m_NodeInfo = value; } } [SerializeField] eState m_State; public eState State { get { return m_State; } set { m_State = value; } } [SerializeField] eAttribute m_Attribute; public eAttribute Attribute { get { return m_Attribute; } set { m_Attribute = value; } } [SerializeField] float m_F; public float F { get { return m_F; } set { m_F = value; } } [SerializeField] float m_G; public float G { get { return m_G; } set { m_G = value; } } bool m_Done; public bool Done { get { return m_Done; } set { m_Done = value; } } public void Init() { m_Parent = null; m_State = eState.None; m_F = 0.0f; m_G = 0.0f; m_Done = false; } }
選択用コリジョンとノードを結びつけるインデックスを保持するクラス
using UnityEngine; using System.Collections; public class GridNodeIndex : MonoBehaviour { public int m_Index = -1; }
A*
using UnityEngine; using System.Collections; using System.Collections.Generic; public class GridTest : MonoBehaviour { enum eState { None, Search, }; const int COST_MAX = int.MaxValue; GameObject [] m_GridNode; GameObject m_Start; GameObject m_Goal; List<GameObject> m_OpenList; List<GameObject> m_CloseList; List<GameObject> m_InfoList; eState m_State; void Awake() { m_Start = null; m_Goal = null; m_OpenList = new List<GameObject>(); m_CloseList = new List<GameObject>(); m_InfoList = new List<GameObject>(); m_State = eState.None; } // Use this for initialization void Start () { InitMapGrid(); InitHelpInfo(); } // Update is called once per frame void Update () { UpdateInput(); } void UpdateInput() { if(m_State == eState.Search) { return; } if(Input.GetMouseButtonDown(0)) { Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition); RaycastHit hit; Debug.Log("click:"+LayerMask.NameToLayer("MapTile")); if(Physics.Raycast(ray, out hit, Mathf.Infinity, 1<<LayerMask.NameToLayer("MapTile"))) { GameObject obj = hit.collider.gameObject; Debug.Log(obj); if(obj) { int index = obj.GetComponent<GridNodeIndex>().m_Index; Debug.Log(index); int st = (((int)m_GridNode[index].GetComponent<GridNode>().State)+1) % (int)GridNode.eState.Max; GridNode.eState stat = (GridNode.eState)st; m_GridNode[index].GetComponent<GridNode>().State = stat; Color [] s_Color = { Color.white, Color.green, Color.yellow, Color.black }; obj.renderer.material.color = s_Color[st]; switch(stat) { case GridNode.eState.Start: m_Start = m_GridNode[index]; break; case GridNode.eState.Goal: m_Goal = m_GridNode[index]; break; } } } } else if(Input.GetMouseButtonDown(1)) { Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition); RaycastHit hit; Debug.Log("click:"+LayerMask.NameToLayer("MapTile")); if(Physics.Raycast(ray, out hit, Mathf.Infinity, 1<<LayerMask.NameToLayer("MapTile"))) { GameObject obj = hit.collider.gameObject; Debug.Log(obj); if(obj) { int index = obj.GetComponent<GridNodeIndex>().m_Index; int attr = (((int)m_GridNode[index].GetComponent<GridNode>().Attribute)+1) % (int)GridNode.eAttribute.Max; GridNode.eAttribute attribute = (GridNode.eAttribute)attr; m_GridNode[index].GetComponent<GridNode>().Attribute = attribute; Color [] s_Color = { Color.white, Color.blue }; obj.renderer.material.color = s_Color[attr]; } } } } void InitHelpInfo() { GameObject obj = GameObject.Find("GridRoot"); GameObject root = new GameObject("NodeRoot"); Grid script = obj.GetComponent<Grid>(); List<MapNode> list = script.m_MapNodeList; Debug.Log("scale="+obj.transform.localScale); for(int i = 0; i < list.Count; ++i) { int cnt = list[i].vertexList.Count; for(int k = 0; k < cnt; ++k) { GameObject go = GameObject.CreatePrimitive(PrimitiveType.Sphere); go.transform.parent = root.transform; go.transform.position = list[i].vertexList[k]; go.transform.localScale = new Vector3(5,5,5); go.renderer.material.color = Color.red; } } GameObject center = new GameObject("Center"); center.layer = LayerMask.NameToLayer("MapTile"); for(int i = 0; i < list.Count; ++i) { GameObject go = GameObject.CreatePrimitive(PrimitiveType.Sphere); GridNodeIndex idx = go.AddComponent<GridNodeIndex>(); idx.m_Index = i; go.transform.parent = center.transform; go.transform.position = list[i].center; go.transform.localScale = new Vector3(20,20,20); go.renderer.material.color = Color.white; go.layer = LayerMask.NameToLayer("MapTile"); m_InfoList.Add(go); } } void InitMapGrid() { GameObject obj = GameObject.Find("GridRoot"); Grid script = obj.GetComponent<Grid>(); List<MapNode> list = script.m_MapNodeList; int cnt = list.Count; m_GridNode = new GameObject[cnt]; for(int i = 0; i < cnt; ++i) { m_GridNode[i] = new GameObject("GridNode"+i); m_GridNode[i].transform.parent = transform; GridNode node = m_GridNode[i].AddComponent<GridNode>(); node.Init(); node.NodeInfo = list[i]; } } void Clear() { GameObject obj = GameObject.Find("GridRoot"); Grid script = obj.GetComponent<Grid>(); List<MapNode> list = script.m_MapNodeList; int cnt = list.Count; for(int i = 0; i < cnt; ++i) { m_GridNode[i].GetComponent<GridNode>().Init(); m_InfoList[i].renderer.material.color = Color.white; } } bool Search() { Debug.Log("Search Start"); Debug.Log("start="+m_Start+",goal="+m_Goal); if(m_Start == null || m_Goal == null) { Debug.Log("start="+m_Start+",goal="+m_Goal); 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) { Debug.Log("OpenList empty"); 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) { Debug.Log("Search Failed"); return false; } minObj.GetComponent<GridNode>().Done = true; if( minObj.GetComponent<GridNode>().State == GridNode.eState.Goal) { Debug.Log("Goal"); break; } else { m_CloseList.Add(minObj); m_OpenList.Remove(minObj); } UpdateScore(minObj); } Debug.Log("Search End"); 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) { Debug.Log("UpdateScore:"+i); GameObject co = m_GridNode[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); } } void ShowPath() { GridNode node = m_Goal.GetComponent<GridNode>().Parent; while(node && node.State != GridNode.eState.Start) { node.State = GridNode.eState.OnPath; m_InfoList[node.NodeInfo.index].renderer.material.color = Color.black; node = node.Parent; } } void OnGUI() { if(GUILayout.Button("Titleに移動")) { Application.LoadLevel("Title"); } if(GUILayout.Button("Search")) { m_State = eState.Search; Search(); ShowPath(); m_State = eState.None; } if(GUILayout.Button("Clear")) { Clear(); } } }