bate's blog

調べたこと実装したことなどを取りとめもなく書きます。

グリッド状モデル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();
		}
	}
}