الفصل الثالث: إيجاد المسار وتتبعه

العب

إحدى الوظائف الرئيسية في معظم ألعاب الفيديو هي إمكانية أن تقوم الشخصيات التي يتحكم بها الحاسوب بإيجاد طريقها من نقطة لأخرى في خريطة اللعب، بحيث يمكنها التحرك عبر الممرات والأبواب والسلالم للوصول للهدف الذي تسعى إليه. سنناقش في هذا الفصل إن شاء الله كيفية بناء نقاط الحركة لشخصيات الذكاء الاصطناعي داخل خريطة اللعب ومن ثم كيفية قيام هذه الشخصيات بإيجاد مسار الحركة عبر هذه النقاط وأخيرا التحرك وفق هذا المسار. سنفترض في هذا الفصل أن شخصية الذكاء الاصطناعي تعرف مسبقا موقع الهدف (والذي سيكون اللاعب) دون أن تضطر لرؤيته مباشرة بل ستأخذ موقعه من بيانات المشهد مباشرة. سنحتاج أولا لبناء شخصية بسيطة نضيف إليها مكوّن تصادم على شكل كبسولة مكوّن الجسم الصلب Rigid body إضافة إلى بريمج الشخصية الفيزيائية الذي سبق وكتبناه في الفصل الثالث من الوحدة الرابعة وهو PhysicsCharacter.cs (راجع السرد 47). أخيرا ستظهر هذه الشخصية كما في الشكل التالي:

شخصية الذكاء الاصطناعي

شخصية الذكاء الاصطناعي

بعد إضافة شخصية الذكاء الاصطناعي سنحتاج أيضا لشخصية اللاعب، والتي ستكون هي نفسها التي سبق وصنعناها في الفصل الثالث من الوحدة الرابعة "شخصية اللاعب الفيزيائية". ما سنقوم به تاليا هو بناء بيئة بسيطة باستخدام الأشكال الأساسية؛ وذلك من أجل أن نسمح للشخصية بالحركة داخلها والوصو إلى اللاعب متجاوزة العوائق الموجودة في طريقها. سيحتوي المشهد على أرضية عليها بعض الصناديق بالإضافة إلى جدار كبير عليه درج للصعود وآخر للنزول. كافة عناصر المشهد يجب أن تحتوي على مكونات تصادم باستثناء درجات الصعود والنزول، والتي سيكون شكل الدرجات فيها ظاهريا فقط دون أن يمكن للاعب الاصطدام بها. بدلا من إضافة مكوّن تصادم لكل درجة على حدة، والذي من شأنه أن يضر بسلاسة الحركة خاصة عند الصعود، نستخدم عادة مكعبا مخفيا (أي نقوم بتعطيل مكوّن التصيير الخاص به) ومن ثم نضعه على شكل لوح طويل مائل على امتداد الأدراج بحيث يكون التصادم الفعلي للشخصيات مع هذا المكعب وبالتالي تصعد وتنزل الأدراج بسلاسة. يمكنك ملاحظة هذه الخدعة في الصورة التالية التي تمثل المشهد الذي سنستخدمه في هذا المثال، حيث تظهر مكوّنات التصادم باللون الأخضر:

المشهد الخاص بمثال إيجاد المسار وتتبعه

المشهد الخاص بمثال إيجاد المسار وتتبعه

إذن لدينا الآن خريطة وشخصية لاعب وأخرى يتحكم بهذا الذكاء الاصطناعي من أجل تسييرها باتجاه اللاعب. من المهم أن نعمل على ترتيب هذه العناصر داخل الهرمية على شكل أبناء لكائن جذري فارغ كما سبق وشرحنا في الفصل السابق. سيكون لدينا كائن جذري يحمل الاسم SceneRoot إضافة إلى ضوء اتجاهي وكائن اللاعب Player وكائن شخصية غير اللاعب NPC وهي بالمناسبة اختصار للتسمية الإنجليزية لشخصيات غير اللاعبين Non-Player Character وأخيرا لدينا الخريطة Map. بالتالي ستكون هرمية المشهد كما هو مبين في الصورة التالية:

هرمية المشهد الخاص بمثال إيجاد المسار وتتبعه

هرمية المشهد الخاص بمثال إيجاد المسار وتتبعه

الخطوة التالية هي أن نوزع اللاعب وشخصية الذكاء الاصطناعي في أماكن بعيدة عن بعضها في الخريطة وذلك حتى تقوم الشخصية بملاحقة عند بدء التشغيل. يمكن توزيع هذه الأماكن حسب كما هو موضح في الصورة التالية:

 توزيع شخصية اللاعب (الدائرة الزرقاء) وشخصية الذكاء الاصطناعي (الدائرة الحمراء) في خارطة اللعب

توزيع شخصية اللاعب (الدائرة الزرقاء) وشخصية الذكاء الاصطناعي (الدائرة الحمراء) في خارطة اللعب

بعد أن أصبح المشهد جاهزا يمكننا الآن البدء بكتابة البريمجات الخاصة ببناء المسارات واكتشافها وتتبعها. وسنبدأ بها على هذا الترتيب تحديدا. الخطوة الأولى عند بداية التشغيل هي أن نقوم ببناء شبكة المسارات وهي عبارة عن رسم بياني مكوّن من عُقَد وحوافّ كالتي سبق شرحها في الفصل السابق. الفرق هو أننا الآن لا نتحدث عن شجرة بل نتحدث عن رسم كامل فيه الكثير من العقد والحواف المترابطة مع بعضها البعض. فكرة بناء هذه الشجرة تعتمد على معرفتنا لحدود خريطة اللعب، ومن ثم تقسيم هذه الخريطة إلى وحدات مربعة نكون قد حددنا مسبقا أطوال أضلاعها. علينا بعدها أن نقوم بعملية "مسح" للخارطة ضمن الحدود المعروفة، وذلك عن طريق بث أشعة عموديا من الأعلى ومن ثم فحص ما إذا كانت هذه الأشعة قد اصطدمت بأحد عناصر الخريطة. إذا تحقق هذا الشرط نقوم بحفظ موقع اصطدام الأشعة بالعنصر حيث سيشكل هذا الموقع أحد العُقد في شبكة المسارات. بعد الانتهاء من عملية المسح سيصبح لدينا مجموعة من العقد المنتشرة على الأسطح العلوية لعناصر المشهد، وكل ما عليها هو أن نصل كل عقدة بالعقد المحيطة بها من الجهات الرئيسية الأربعة والجهات الفرعية كذلك، بحيث تتصل كل عقدة على الأقل بعقدة واحدة وعلى الأكثر بثمان عقد. بطبيعة الحال سيكون هناك قواعد تحدد ربط هذه العقد ببعضها البعض، فمثلا إذا تجاورت عقدتان إحداهما على الأرضية والأخرى فوق سطح صندوق فلن يتم توصيلهما بسبب فرق الارتفاع؛ حيث أن الشخصيات لا يمكنها المشي من فوق سطح الأرض إلى أعلى الصناديق. بالتأكيد هناك الكثير من التفاصيل التي يمكن إضافتها كالسماح بمسار أحادي من فوق الصندوق إلى الأرض وليس العكس وتحديد ارتفاع أعلى للقفز حتى لا تتأذى الشخصية ... إلخ. لكننا لن نخوض فيها من أجل الحفاظ على بساطة المثال. البداية إذن ستكون مع البريمج الذي يقوم بمسح الخريطة وبناء شبكة العقد والحواف التي تمثل المسارات التي يمكن أن تمشي عليها شخصية الذكاء الاصطناعي. هذا البريمج هو AIGraph وسنضيفه على الكائن الجذري للمشهد SceneRoot وهو موضح في السرد التالي:


1. using UnityEngine;
2. using System.Collections.Generic;
3. 
4. public class AIGraph : MonoBehaviour {
5. 	
6. 	//المتجه الخاص بتحديد مدى عملية المسح بحيث يشمل كافة مساحة الخريطة
7. 	//X: مقدار امتداد مجال المسح من منتصف المشهد يمينا ويسارا
8. 	//Z: مقدار امتداد مجال المسح من منتصف المشهد شمالا وجنوبا
9. 	//Y: الارتفاع الذي سيتم منه بث أشعة المسح ويجب أن يكون أعلى من أعلى نقطة في الخريطة
10. 	public Vector3 scanRange = new Vector3(40, 10, 40);
11. 	
12. 	//المسافة الأفقية بين كل عقدتين 
13. 	//z و x على كلا المحورين
14. 	public float minimumNodeDistance = 2.0f;
15. 	
16. 	//العقد التي يزيد فرق الارتفاع بينها عن هذه القيمة لن
17. 	//يتم توصيلها ببعضها
18. 	public float maxVerticalDistance = 0.5f;
19. 	
20. 	//هل يجب أن يقوم البريمج برسم الشبكة الناتجة ليراها اللاعب
21. 	public bool visualizeGraph = true;
22. 	
23. 	//مصفوفة لتخزين كافة العقد التي تتكون منها شبكة المسارات
24. 	private Vector3[] nodes;
25. 	
26. 	//قائمة لتخزين حدود جميع مكوّنات التصادم الخاصة بعناصر المشهد
27. 	private List<Bounds> collidersBounds;
28. 	
29. 	//مصفوفة ثنائية الأبعاد لتخزين المسافات بين العقد
30. 	//في الشكل الشبكة المكوّنة لمسارات الذكاء الاصطناعي
31. 	private float[,] distanceMatrix;
32. 	
33. 	//يتم استدعاؤها مرة واحدة عند تحميل الكائن
34. 	void Awake () {
35. 		collidersBounds = new List<Bounds>();
36. 		UpdateGraph();
37. 	}
38. 	
39. 	//يتم استدعاؤها مرة واحدة عند تصيير كل إطار
40. 	void Update () {
41. 		
42. 		if(visualizeGraph){
43. 			DrawGraph();
44. 		}
45. 	}
46. 	
47. 	//تقوم بحساب وإرجاع المسافة المباشرة بين عقدتين متصلتين
48. 	//أو تعيد قيمة ما لا نهاية في حال كونهما غير متصلتين بشكل مباشر
49. 	public float GetDistance(int node1, int node2){
50. 		if(IsValid(node1) && IsValid(node2)){
51. 			return distanceMatrix[node1, node2];
52. 		}
53. 		return Mathf.Infinity;
54. 	}
55. 	
56. 	//تقوم بإرجاع العقدة الأقرب إلى الموقع
57. 	//المُعطى لها
58. 	public int GetNodeAtPosition(Vector3 pos){
59. 		int nearest = 0;
60. 		float minDist = Vector3.Distance(pos, nodes[0]);
61. 		
62. 		for(int i = 1; i < nodes.Length; i++){
63. 			if(IsValid(i)){
64. 				float nodeDist = Vector3.Distance(pos, nodes[i]);
65. 				if(nodeDist < minDist){
66. 					minDist = nodeDist;
67. 					nearest = i;
68. 				}
69. 			}
70. 		}
71. 		
72. 		return nearest;
73. 	}
74. 	
75. 	//تقوم بإرجاع موقع العقدة المُعطاة لها في الفضاء
76. 	public Vector3 GetNodePosition(int node){
77. 		if(IsValid(node)){
78. 			return nodes[node];
79. 		} else {
80. 			throw new System.ArgumentException("Invalid node index: " + node);
81. 		}
82. 	}
83. 	
84. 	//تقوم بإرجاع قائمة بكافّة العقد المتصلة مباشرة
85. 	//بالعقدة المزودة
86. 	public List<int> GetConnectedNodes(int node){
87. 		List<int> connected = new List<int>();
88. 		
89. 		for(int i = 0; i < nodes.Length; i++){
90. 			float dist = GetDistance(node, i);
91. 			if(dist > 0 && dist < Mathf.Infinity){
92. 				connected.Add(i);
93. 			}
94. 		}
95. 		
96. 		return connected;
97. 	}
98. 	
99. 	//تقوم بإرجاع العدد الكلي للعقد الموجودة
100. 	//في المشهد كاملا
101. 	public int GetNodeCount(){
102. 		return nodes.Length;
103. 	}
104. 	
105. 	private bool IsValid(int node){
106. 		return nodes[node].y != -1000.0f;
107. 	}
108. 	
109. 	//تقوم بمسح الخارطة وبناء شبكة المسارات بناء على جغرافيتها
110. 	private void UpdateGraph(){
111. 		
112. 		PreprocessColliders();
113. 		
114. 		//قم بحساب الحد الأقصى لعدد العقد بناء على المسافات بينها وامتداد مساحة المسح
115. 		int nodesPerRow = (int)((2 * scanRange.x) / minimumNodeDistance);
116. 		int nodesPerCol = (int)((2 * scanRange.z) / minimumNodeDistance);
117. 		int totalNodes = nodesPerRow * nodesPerCol;
118. 		
119. 		//تقوم بتجهيز المصفوفات بناء على العدد المحسوب للعقد
120. 		nodes = new Vector3[totalNodes];
121. 		distanceMatrix = new float[totalNodes, totalNodes];
122. 		
123. 		//قم بضبط جميع المسافات بين جميع العقد على ما لا نهاية - أي غير متصلة مبدئيا
124. 		for(int i = 0; i < totalNodes; i++){
125. 			for(int j = i + 1; j < totalNodes; j++){
126. 				distanceMatrix[i, j] = Mathf.Infinity;
127. 				distanceMatrix[j, i] = Mathf.Infinity;
128. 			}
129. 		}
130. 		
131. 		//قم بعملية بث الأشعة من أجل استكشاف مواقع العقد وتخزينها في المصفوفة
132. 		Vector3 rayStart = new Vector3(-scanRange.x, scanRange.y, -scanRange.z);
133. 		
134. 		//بالنظر للخريطة من أعلى، ابدأ ببث الأشعة من الزاوية السفلى في جهة اليسار
135. 		//ومن ثم نفذ المسح عمودا تلو عمود حتى الوصول لأقصى يمين حدود المسح
136. 		for(int i = 0; i < nodesPerRow; i++){
137. 			//ابدأ من الأسفل
138. 			rayStart.z = -scanRange.z;
139. 			
140. 			for(int j = 0; j < nodesPerCol; j++){
141. 				
142. 				int nodeIndex = i * nodesPerCol + j;
143. 				
144. 				//قم ببث شعاع من الأعلى للأسفل فوق موقع العقدة الحالية
145. 				RaycastHit hit;
146. 				if(Physics.Raycast(new Ray(rayStart, Vector3.down), out hit, 100.0f)){
147. 					
148. 					//اصطدم الشعاع بمكوّن تصادم، تحقق من صلاحية الموقع لإضافة عقدة
149. 					bool valid = true;
150. 					float pointX = hit.point.x;
151. 					float pointZ = hit.point.z;
152. 					
153. 					//1.25 المواقع الصالحة لإضافة العقد يجب أن تبعد على الأقل بمقدار
154. 					//متر عن حدود مكوّنات التصادم الخاصة بأجزاء الخريطة
155. 					//أي بعيدة عن الجدران والحواف بمسافة كافية
156. 					foreach(Bounds b in collidersBounds){
157. 						float minX, maxX, minZ, maxZ;
158. 						minX = b.min.x;
159. 						maxX = b.max.x;
160. 						minZ = b.min.z;
161. 						maxZ = b.max.z;
162. 						
163. 						//قم بإيجاد أقصر مسافة بين موقع اعقدة وحدود
164. 						//Z و X مكوّنات التصادم على المحورين
165. 						float minDistX, minDistZ;
166. 						
167. 						minDistX = Mathf.Min(
168. 									Mathf.Abs(pointX - minX), 
169. 									Mathf.Abs(pointX - maxX));
170. 						
171. 						minDistZ = Mathf.Min(
172. 									Mathf.Abs(pointZ - minZ),
173. 									Mathf.Abs(pointZ - maxZ));
174. 						
175. 						//إذا كانت المسافة على أحد المحورين أقل من 
176. 						//1.25 فهذا يعني أن الموقع غير صالح لإضافة عقدة
177. 						if(minDistX < 1.25f && minDistZ < 1.25f){
178. 							valid = false;
179. 							break;
180. 						}
181. 						
182. 					}
183. 					
184. 					if(valid){
185. 						//في حال صلاحية الموقع قم بتخزين نقطة اصطدام الشعاع كموقع للعقدة
186. 						nodes[nodeIndex] = hit.point;
187. 					} else {
188. 						//الموقع غير صالح لإضافة عقدة هنا لذا نقوم بإعطاء قيمة مميزة
189. 						//نعرف من خلالها أن هذا ليس موقعا صالحا Y للعنصر
190. 						nodes[nodeIndex] = new Vector3(rayStart.x, -1000.0f, rayStart.z);
191. 					}
192. 				} else {
193. 					//لم يصطدم الشعاع بأي عنصر بالتالي لا يوجد أرض هنا
194. 					//Y يمكن المشي عليها. إذن نخزن قيمة مميزة في العنصر
195. 					nodes[nodeIndex] = new Vector3(rayStart.x, -1000.0f, rayStart.z);
196. 				}
197. 				
198. 				//تحرك خطوة لأعلى نحو الموقع التالي
199. 				rayStart.z += minimumNodeDistance;
200. 			}
201. 			
202. 			//تحرك خطوة إلى اليمين نحو العمود التالي
203. 			rayStart.x += minimumNodeDistance;
204. 		}
205. 		
206. 		//قم بتوصيل العقد المحاذية لبعضها مستخدما المسافة الثابتة بين العقد
207. 		float radialDistance;
208. 		float minDistSquared = minimumNodeDistance * minimumNodeDistance;
209. 		radialDistance= Mathf.Sqrt(minDistSquared * 2);
210. 		
211. 		for(int i = 0; i < nodesPerRow; i++){
212. 			for(int j = 0; j < nodesPerCol; j++){
213. 				int nodeIndex = i * nodesPerCol + j;
214. 				
215. 				//افحص إذا ما كان العنصر الحالي في المصفوفة يحتوي على عقدة صالحة
216. 				if(nodes[nodeIndex].y > -1000.0f){
217. 					//العقدة صالحة، بالتالي نقوم بملئ المواقع الخاصة بها في مصفوفة المسافات
218. 					//بمقادير المسافات الأفقية والعمودية والقطرية بينها وبين العقد المجاورة
219. 					
220. 					//المسافة بين العقدة ونفسها تساوي صفرا
221. 					distanceMatrix[nodeIndex, nodeIndex] = 0.0f;
222. 
223. 					int x, z, otherIndex;
224. 					//جد العقدة إلى الغرب من العقدة الحالية
225. 					x = i - 1;
226. 					z = j;
227. 					if(x >= 0){
228. 						//هناك عقدة إلى الغرب
229. 						//تأكد من صلاحيتها وقم بتوصيلها
230. 						otherIndex = x * nodesPerCol + z;
231. 						ConnectNodes(nodeIndex, otherIndex, minimumNodeDistance);
232. 					}
233. 					
234. 					//إلى الشرق
235. 					x = i + 1;
236. 					z = j;
237. 					if(x < nodesPerRow){
238. 						//هناك عقدة إلى الشرق
239. 						//تأكد من صلاحيتها وقم بتوصيلها
240. 						otherIndex = x * nodesPerCol + z;
241. 						ConnectNodes(nodeIndex, otherIndex, minimumNodeDistance);
242. 					}
243. 					
244. 					//إلى الشمال
245. 					x = i;
246. 					z = j + 1;
247. 					if(z < nodesPerCol){
248. 						//هناك عقدة إلى الشمال
249. 						//تأكد من صلاحيتها وقم بتوصيلها
250. 						otherIndex = x * nodesPerCol + z;
251. 						ConnectNodes(nodeIndex, otherIndex, minimumNodeDistance);
252. 					}
253. 					
254. 					//إلى الجنوب
255. 					x = i;
256. 					z = j - 1;
257. 					if(z >= 0){
258. 						//هناك عقدة إلى الجنوب
259. 						//تأكد من صلاحيتها وقم بتوصيلها
260. 						otherIndex = x * nodesPerCol + z;
261. 						ConnectNodes(nodeIndex, otherIndex, minimumNodeDistance);
262. 					}
263. 					
264. 					//إلى الشمال الغربي
265. 					x = i - 1;
266. 					z = j + 1;
267. 					if(x >= 0 && z < nodesPerCol){
268. 						//هناك عقدة إلى الشمال الغربي
269. 						//تأكد من صلاحيتها وقم بتوصيلها
270. 						otherIndex = x * nodesPerCol + z;
271. 						ConnectNodes(nodeIndex, otherIndex, radialDistance);
272. 					}
273. 					
274. 					//إلى الشمال الشرقي
275. 					x = i + 1;
276. 					z = j + 1;
277. 					if(x < nodesPerRow && z < nodesPerCol){
278. 						//هناك عقدة إلى الشمال الشرقي
279. 						//تأكد من صلاحيتها وقم بتوصيلها
280. 						otherIndex = x * nodesPerCol + z;
281. 						ConnectNodes(nodeIndex, otherIndex, radialDistance);
282. 					}
283. 					
284. 					//إلى الجنوب الغربي
285. 					x = i - 1;
286. 					z = j - 1;
287. 					if(x >= 0 && z >= 0){
288. 						//هناك عقدة إلى الجنوب الغربي
289. 						//تأكد من صلاحيتها وقم بتوصيلها
290. 						otherIndex = x * nodesPerCol + z;
291. 						ConnectNodes(nodeIndex, otherIndex, radialDistance);
292. 					}
293. 					
294. 					//إلى الجنوب الشرقي
295. 					x = i + 1;
296. 					z = j - 1;
297. 					if(x < nodesPerRow && z >= 0){
298. 						//هناك عقدة إلى الجنوب الشرقي
299. 						//تأكد من صلاحيتها وقم بتوصيلها
300. 						otherIndex = x * nodesPerCol + z;
301. 						ConnectNodes(nodeIndex, otherIndex, radialDistance);
302. 					}
303. 				}
304. 			}
305. 		}
306. 		
307. 	
308. 		PostprocessColliders();
309. 	}
310. 	//collidersBounds تقوم بتعطيل مكوّنات تصادم الشخصيات وتضيف حدود وحدات بناء الخريطة لقائمة
311. 	private void PreprocessColliders(){
312. 		
313. 		Collider[] cols = FindObjectsOfType<Collider>();
314. 		
315. 		foreach(Collider col in cols){
316. 			if(col.tag.Equals("Player") || col.tag.Equals("NPC")){
317. 				col.enabled = false;
318. 			} else if(col is BoxCollider){
319. 				BoxCollider box = (BoxCollider) col;
320. 				collidersBounds.Add(box.bounds);
321. 			}
322. 		}
323. 		
324. 	}
325. 	//تقوم بإعادة تفعيل مكونات تصادم اللاعب وشخصيات الذكاء الاصطناعي
326. 	private void PostprocessColliders(){
327. 		
328. 		Collider[] cols = FindObjectsOfType<Collider>();
329. 		
330. 		foreach(Collider col in cols){
331. 			if(col.tag.Equals("Player") || col.tag.Equals("NPC")){
332. 				col.enabled = true;
333. 			}
334. 		}
335. 	}
336. 	
337. 	//تقوم بفحص كون العقدتين صالحتين مع كون
338. 	//maxVerticalDistance فرق المسافة العمودية بينهما أقل من
339. 	//ومن ثم تقوم بتوصيلهما مستخدمة المسافة المزودة حال تحقق الشروط
340. 	private void ConnectNodes(int node1Index, int node2Index, float distance){
341. 		float node1Height = nodes[node1Index].y;
342. 		float node2Height = nodes[node2Index].y;
343. 		
344. 		if(node1Height > -1000.0f && node2Height > -1000.0f &&
345. 			Mathf.Abs(node1Height - node2Height) <= maxVerticalDistance){
346. 			
347. 			Vector3 node1Pos = nodes[node1Index] + Vector3.up * 0.2f;
348. 			Vector3 direction = nodes[node2Index] + Vector3.up * 0.2f - node1Pos;
349. 			
350. 			if(!Physics.Raycast(new Ray(node1Pos, direction), distance)){
351. 				distanceMatrix[node1Index, node2Index] = distance;
352. 				distanceMatrix[node2Index, node1Index] = distance;
353. 			}
354. 		}
355. 	}
356. 	//ترسم شبكة المسارات في شاشة تحرير المشهد
357. 	private void DrawGraph(){
358. 		for(int i = 0; i < nodes.Length; i++){
359. 			bool isolated = true;
360. 			for(int j = i + 1; j < nodes.Length; j++){
361. 				if(distanceMatrix[i, j] < Mathf.Infinity){
362. 					Debug.DrawLine(nodes[i], nodes[j]);
363. 					isolated = false;
364. 				}
365. 			}
366. 			
367. 			if(!isolated){
368. 				Debug.DrawLine(nodes[i], nodes[i] + Vector3.one * 0.5f, Color.red);
369. 			}
370. 		}
371. 	}
372. 	
373. }

البريمج الخاص بمسح الخارطة وبناء مسارات حركة شخصيات الذكاء الاصطناعي

حتى يقوم البريمج ببناء شبكة المسارات فإنه يحتاج منا لعدد من المدخلات. أول هذه المدخلات هو المساحة التي يجب أن تغطيها عملية المسح والتي يجب أن تكون أكبر بقليل من مساحة الخريطة حتى نضمن تغطية كافة أجزائها. هذه المساحة تحسب من منتصف المشهد - أي نقطة الأصل - وتمتد يمينا ويسارا على المحور X إضافة لامتدادها أماما وخلفا على المحور Z. علاوة على ذلك يجب أيضا أن نحدد أقصى ارتفاع لأعلى نقطة في الخريطة على المحور Y، وبالتالي نضمن تغطية الخريطة بالكامل على الأبعاد الثلاث. كل هذه القيم يتم إدخالها في المتغير scanRange والذي ستعتمد عليه جميع وظائف البريمج في حساباتها. بما أن الشبكة الناتجة ستكون عبارة عن عقد موزعة على شكل مربعات متراصة مثل رقعة الشطرنج، علينا أن نحدد المسافة الأفقية بين كل عقدتين عبر المتغير minimumNodeDistance، والتي كلما قلت زاد عدد العقد وأصبحت الحركة أكثر سلاسة وتنوعا، بيد أن هذا بالمقابل سيؤثر سلبا على الأداء مما يوجب علينا أن نحدد قيمة معتدلة ولتكن مثلا 2. أخيرا وبما أن الخريطة ثلاثية الأبعاد، سيكون علينا تحديد المسافة العمودية التي يمكن للشخصيات صعودها دون القفز من خلال maxVerticalDistance، وبالتالي نصل فقط العقد التي يقل الفرق بين ارتفاعها عن بعضها عن هذا المقدار وليكن نصف متر مثلا.

إضافة لهذه المتغيرات الرئيسية هناك خيار يمكننا من رؤية الشبكة الناتجة عن طريق المتغير visualizeGraph والذي سنناقش لاحقا آلية عمله. كل ما يهمنا معرفته هو أن أوامر الرسم هذه خاصة بالمحرك فقط ولن تعمل عند تصدير اللعبة للمنصات المختلفة. علاوة على ذلك فإن عملية الرسم هذه قد تؤدي لبطء ملحوظ في الأداء نظرا لكلفتها الحسابية العالية.

بالحديث عن الشبكة نفسها، سنقوم بتخزينها في مصفوفتين هما nodes و distanceMatrix. هذه الطريقة في تخزين الرسوم البيانية حاسوبيا شائعة في تراكيب البيانات وعادة ما تتم بمصفوفة المسافات distanceMatrix وحدها. إلا أننا هنا نحتاج لمصفوفة أخرى هي nodes وذلك من أجل تخزين مواقع العقد في فضاء اللعبة وليس فقط من أجل حساب المسافات بينها كما هو الحال في كثير من الحالات. الطريقة التي سنتبعها في تخزين الرسم البياني هي أن كل عقدة ستكون في عنصر من عناصر nodes مثل 0، 1، 2، ... وفي كل عنصر سنقوم بتخزين قيمة موقعها في الفضاء ثلاثي الأبعاد. أما مصفوفة المسافات distanceMatrix وهي ثنائية الأبعاد فستعمل على تخزين المسافة المباشرة بين كل عقدتين متصلتين. فمثلا المسافة للانتقال من العقدة في العنصر 5 إلى العقدة في العنصر 7 من المصفوفة nodes ستكون مخزنة في [5,7]distanceMatrix أما مسافة العودة من 7 إلى 5 فستكون في [7,5]distanceMatrix. رغم أنه من الناحية النظرية يجب أن تكون المسافة نفسها؛ إلا أن تخزين المسافة في الاتجاهين يعطينا مساحة إضافية لتحديد الحركة في اتجاه واحد إن احتجنا لذلك، مثل القفز من مكان مرتفع بحيث لا يمكن الصعود إليه مرة أخرى. من المهم تذكر أن المسافات المباشرة بين العقد المتجاورة هي ما نعرفه ونخزنه فقط، أما الطريق بين نقطتين بعيدتين يتم حسابه حين الحاجة إليه كما سنرى حين الحديث عن آلية إيجاد المسار. أخيرا قد تتساءل عن أهمية وجود مصفوفة المسافات distanceMatrix بينما يمكننا بسهولة حساب المسافة بين العقد في أي وقت طالما نعرف مواقعها، والجواب هنا هو أن هذا أفضل بكثير للأداء لأن عملية حساب المسافة مكلفة من ناحية استخدام المعالج، بينما المصفوفة مكلفة في مساحة ذاكرة التخزين. وبطبيعة الحال الذاكرة متوفرة أكثر من طاقة المعالج في معظم الأحيان لذا نستغلها ونخفف عن المعالج للقيام بعمليات أخرى.

المتغير الأخير الذي سنتناوله هو قائمة حدود مكوّنات تصادم عناصر المشهد collidersBounds. الهدف من هذه القائمة هو أن نعرف أين هي حواف كل عنصر من عناصر المشهد في الفضاء، وذلك حتى نتجنب إضافة عقد شديدة القرب من هذه الحواف. هذا الأمر سيجنبنا إضافة عقد ملاصقة للجدران بالتالي لا يمكن المشي عليها، كما يجنبنا إضافة عقد قريبة من الحواف لدرجة أن تسقط عنها الشخصية التي تحاول المشي عليها. باختصار فنحن لا نريد أن نضيف العقد والحواف الواصلة إلا في الأماكن الصالحة للمشي، ومعرفة حدود مكوّنات التصادم للعناصر الموجودة في المشهد سوف يساعدنا في حساب هذه الأماكن.

عند بداية التشغيل تقوم الدّالة ()Awake بتعريف القائمة collidersBounds ومن ثم استدعاء ()UpdateGraph وهي الدّالة الرئيسية والأهم في هذا البريمج. هذه الدّالة معرفة في الأسطر 110 إلى 328 وهي طويلة نسبيا نظرا لأنها تقوم بعميلتي المسح وبناء شبكة المسارات. الخطوة الأولى في عملية بناء الشكبة هي تعطيل أي مكوّنات تصادم لا تخص عناصر خريطة اللعب، وتحديدا اللاعب وشخصية الذكاء الاصطناعي، وذلك حتى لا تعترض بث الأشعة الذي سيعمل على بناء الشبكة. إضافة لذلك يجب أن يتم ملء القائمة collidersBounds لتحتوي على جميع حدود مكوّنات تصادم عناصر بناء الخريطة. هاتان العمليتان تقوم بهما دالّة واحدة هي ()PreprocessColliders والتي يتم استدعاؤها كخطوة أولى من قبل ()UpdateGraph.

بعد ذلك سيكون علينا معرفة العدد الكلي للعقد التي ستشكل المشهد، أو بالأحرى الحد الأقصى المحتمل لعدد العقد حيث قد يكون هناك أماكن ضمن نطاق المسح لا تصلح لإضافة عقد كما سنرى. مستخدمين قيم الامتدادات يمينا ويسارا وأماما وخلفا وهي المخزنة في scanRange، نقوم بحساب عدد العقد في كل سطر أفقي من اليمين لليسار عن طريق ضرب الامتداد في 2؛ وذلك لأن الامتداد محسوب أصلا من نقطة الأصل باتجاه واحد، أما المسح الفعلي فسيتم في اتجاهين يمينا ويسارا. بعد ذلك نقسم هذه المسافة الكاملة من أقصى يسار نطاق المسح إلى أقصى يمينه على المسافة الأفقية بين كل عقدتين متجاورتين، وبالتالي نحصل على عدد العقد التي نحتاجها لتغطية هذه المساحة الأفقية. هذه العملية الحسابية الموجودة في السطر 115 نقوم بتخزين ناتجها في المتغير nodesPerRow. بطريقة مشابهة تماما نقوم في السطر التالي بحساب عدد العق في كل عمود وتخزينها في nodesPerCol. أخيرا سيكون العدد الكلي للعقد هو حاصل ضرب هذين المتغيرين وسنعمل على تخزينه في totalNodes. هذا المتغير الأخير هو الذي سنعتمده لتعريف المصفوفتين nodes و distanceMatrix في السطرين 120 و 121. الصورة التالية توضح الخريطة ونطاق المسح والمسافات بين العقد.

نطاق المسح حول الخريطة باللون الأصفر إضافة للامتدادات التي تحدده على المحورين أفقيا وعموديا. المسافة المحددة بالأحمر هي المسافة بين العقد أفقيا وعموديا

نطاق المسح حول الخريطة باللون الأصفر إضافة للامتدادات التي تحدده على المحورين أفقيا وعموديا. المسافة المحددة بالأحمر هي المسافة بين العقد أفقيا وعموديا

بعد تعريف المصفوفات نفترض مبدئيا أن جميع العقد مفصولة عن بعضها البعض وذلك عن طريق تخزين قيمة الما لا نهاية Mathf.Infinity في جميع عناصر distanceMatrix؛ أي أنه لا يمكن الوصول من أي عقدة لأي عقدة أخرى.

المتغير rayStart والمعرف في السطر 132 سيكون هو النقطة التي يتم منها بث الشعاع نحو الأسفل من أجل الكشف عن وجود مكان صالح لإضافة عقدة على أرضية المشهد. لاحظ أن الشعاع يبدأ من ارتفاع فوق المشهد حيث قيمة scanRange.y الموجبة وبالنظر من الأعلى ستكون المنطقة التي نفحصها في الجهة السفلى من يسار المشهد إذا نظرت إلى الصورة السابقة، أو لنقل منعا للالتباس أنه يبدأ من الجنوب الغربي للمشهد حيث القيم السالبة لكل من scanRange.x و scanRange.z.

بعد ذلك تدخل العملية في حلقتين تكراريتين متداخلتين، حيث الحلقة الخارجية تتحرك عمودا بعمود من الغرب إلى الشرق ابتداء من العنصر صفر إلى nodesPerRow، والحلقة الداخلية تتحرك عقدة بعقدة في كل عمود من الجنوب إلى الشمال من صفر إلى nodesPerCol. بما أننا نتحرك في فضاء ثنائي الأبعاد في الاتجاهات الجغرافية الأربع بينما لدينا مصفوفة أحادية الاتجاه لتخزين العقد وهي nodes فإننا سنحتاج إلى معادلة تحسب لنا موقع كل عنصر بناء على رقم صفها وعمودها وستكون رقم العمود مضروبا في عدد العقد في كل عمود ومن ثم مضافا إليه رقم الصف ومن ثم تخزينه في المتغير nodeIndex كما في السطر 142. إذا لم تكن متأكدا مما نعنيه هنا بالصفوف والأعمدة فهي الخطوط الأفقية والعمودية البيضاء التي تراها في الصورة السابقة والتي تشكل نقاط التقاطع بينها مواقع العقد المفترضة. بالتالي سيكون موقع العقدة الأولى التي يتم إنشاؤها هو نقطة التقاطع في أسفل يسار الصورة ومن ثم صعودا لأعلى حتى أعلى اليسار، بعدها يتم الانتقال خطوة إلى يمين الصورة والعودة من الأسفل مرة أخرى. لاحظ أننا في السطر 138 نعيد قيمة الموقع إلى أقصى الجنوب مرة أخرى قبل أن نبدأ في مسح عمود جديد من الجنوب للشمال. قبل الدخول في تفاصيل آلية عملية المسح والتعرف على المواقع الصالحة وغير الصالحة لإضافة العقد، أود الإشارة سريعا إلى السطرين 199 و 203 حيث يمثلان نهاية كل دورة من الحلقة الداخلية والخارجية. لاحظ عند نهاية كل دورة من الحلقة الداخلية في السطر 199 نقوم بزيادة rayStart.z بمقدار وحدة واحدة أي minimumNodeDistance بالتالي يكون الموقع التالي للدورة القادمة وحدة واحدة نحو الأعلى. أما في السطر 203 والذي يمثل نهاية الحلقة الخارجية نقوم بزيادة rayStart.x بمقدار وحدة واحدة لننتقل خطوة نحو اليمين.

لنتحدث الآن ببعض التفصيل عن آلية اكتشاف مواقع العقد ابتداء من الشعاع الذي ينطلق من rayStart نحو الأسفل وهو ما نقوم به في السطر 146. كل الخطوات التالية حتى السطر 191 تعتمد على وجود اصطدام بين الشعاع وأحد عناصر بناء الخريطة في المشهد. بمجرد وجود اصطدام نقوم بتخزيين الإحداثيات x و z لموقع الاصطدام في المتغيرين pointX و pointZ. إضافة لذلك نفترض تلقائيا أن الموقع صالح عن طريق تعريف المتغير valid بالقيمة true والتي سنغيرها إذا ثبت العكس من خلال الخطوة التالية. كما سبق وذكرنا يجب أن تكون العقد بعيدة عن الجدران والحواف بمقدار 1.25 مترا على الأقل. من أجل ذلك نقوم في الأسطر 156 إلى 182 بالمرور على كافة حدود مكوّنات التصادم المخزنة في القائمة collidersBounds. في كل مرة نقوم بحساب أقصر مسافة على المحور x بين نقطة التصادم والحدين الأيمن والأيسر لمكوّن التصادم، كما نقوم بحساب أقصر مسافة على المحور z بين نقطة التصادم والحدين الأمامي والخلفي لمكوّن التصادم. إذا قلت إحدى هاتين القيمتين عن 1.25 فهذا يعني أن الموقع غير صالح ليكون عقدة تتحرك عليها شخصية الذكاء الاصطناعي. ما عدا ذلك فإن العقدة تكون صالحة. لاحظ في السطرين 190 و 195 أن العقد غير الصالحة والتي سوف تستبعد من الشبكة يتم تمييزها عن طريق تخزين القيمة 1000- في العنصر y الخاص بها.

بنهاية الحلقتين الداخلية والخارجية في السطر 204 نكون قد انتهينا من تحديد مواقع العقد في الأبعاد الثلاث وتحديد المواقع غير الصالحة وتمييزها عن طريق القيمة 1000- في العنصر y. الخطوة التالية إذن هي أن نمر على جميع العقد الصالحة والتحقق من وجود عقد حولها ومن ثم توصيلها بهذه العقد عن طريق ملئ القيم في المصفوفة distanceMatrix. المساحة الأفقية معروفة لدينا مسبقا وهي minimumNodeDistance، أما المساحة القطرية radialDistance فنحسبها مستخدمين قاعدة أضلاع المثلث القائم أي الجذر التربيعي لمجموع مربعي الضلعين، وهذا الضلعان لهما نفس الطول وهو minimumNodeDistance. كل ما بقي علينا الآن هو المرور على العقد واحدة تلو الأخرى، ومن ثم اكتشاف العقد المجاورة لها إن كانت صالحة. إذا كانت العقدة المجاورة صالحة فإننا نقوم بتوصيلها بعد فحص فرق الارتفاع والتأكد أنه أقل من maxVerticalDistance. لاحظ أننا في السطر 221 نحدد المسافة بين العقدة ونفسها على أنها صفر، ومن ثم نتحرك في الأعمدة والأسطر من أجل الوصول للعقد المجاورة. لنأخذ مثلا العقدة إلى جهة اليسار أو الغرب من العقدة الحالية كما في الأسطر 223 إلى 232. هذه العقدة ستكون في نفس صف العقدة الحالية بالتالي فإن z = j أما من ناحية العمود فهي تقع عمودا واحدا إلى اليسار أي x = i - 1. بعدها نستخدم نفس المعادلة السابقة لقيمة الصف والعمود من أجل حساب موقع العقدة الغربية otherIndex في السطر 230. أخيرا أصبح لدينا العقدتان وهما العقدة الحالية nodeIndex والعقدة التي تقع إلى الغرب منها otherIndex والمسافة بينهما وهي الأفقية في هذه الحالة minimumNodeDistance وهي المتغيرات التي نحتاجها لاستدعاء الدّالة ()ConnectNodes والتي تتحقق من فرق الارتفاع بين العقدتين وتصلهما مستخدمة المسافة المزودة في حال قل فرق الارتفاع عن maxVerticalDistance، إضافة لشرط آخر سنناقشه بعد قليل. هذه الدّالة معرفة في الأسطر 340 إلى 355. تتكرر هذه العملية بنفس الطريقة مع الجهات الرئيسية الأربعة مع اختلاف قيم x و z التي تحسب موقع العقدة المجاورة. نفس العملية أيضا تتكرر مع الجهات الفرعية، مع مراعاة اختلاف واحد وهو استخدام radialDistance بدلا من maxVerticalDistance. بعد المرور على جميع العقد وتوصيل كل عقدة مع ما حولها تكون شبكة الحركة جاهزة ومتفقة مع جغرافية الخريطة.

بالعودة للشرط الإضافي الذي يجب التحقق منه قبل توصيل العقد من قبل الدّالة ()ConnectNodes، لاحظ في الأسطر 347 إلى 353 أننا نقوم ببث شعاع بطول المسافة بين العقدتين بين موقعيهما على ارتفاع طفيف من الأرض، وأن عملية التوصيل تتم فقط في حال فشل البث الإشعاعي في الاصطدام بأي مكوّن تصادم. القضية هنا تتعلق بالعقد التي تتصل مع بعضها لتشكل استدارة حول زوايا الأجسام مثل زوايا الصناديق، والهدف هو أن نتأكد أن زاوية الصندوق البارزة لا تقع بين موقعي العقدتين. في حال وُجدت هذه الحافة بين الموقعين سيصطدم بها الشعاع ولن يتم توصيل العقدتين كما هو موضح في الشكل التالي

العقد الظاهرة باللون الأحمر لم يتم توصيلها لوجود فاصل وهو حافة الدرج والتي تحول بين التنقل المباشر بينهما. بالتالي ستستدير الشخصية حول الحافة عن طريق العقدة الظاهرة في الزاوية

العقد الظاهرة باللون الأحمر لم يتم توصيلها لوجود فاصل وهو حافة الدرج والتي تحول بين التنقل المباشر بينهما. بالتالي ستستدير الشخصية حول الحافة عن طريق العقدة الظاهرة في الزاوية

إذا قمت بتشغيل اللعبة الآن سترى أن البريمج قد قام ببناء الشبكة ورسمها لك في شاشة المحرر وستظهر كما في الصورة التالية

شبكة مسارات الذكاء الاصطناعي حيث تظهر العقد بالأحمر والحواف بالأبيض

شبكة مسارات الذكاء الاصطناعي حيث تظهر العقد بالأحمر والحواف بالأبيض

بعد أن انتهينا من بناء شبكة الحركة لشخصية الذكاء الاصطناعي، ستكون الخطوة التالية هي أن نمكّن هذه الشخصية من إيجاد أقصر طريق عبر هذه الشبكة للوصول إلى موقع الهدف. هذه المهمة سيتولاها البريمج PathFinder والذي سنقوم بإضافته لكائن شخصية غير اللاعب التي سبق وقمنا ببنائها ووضعها في المشهد. يستخدم البريمج المذكور خوارزمية معروفة لإيجاد أقصر مسار بين عقدتين في رسم بياني وهي "خوارزمية دايجسترا" (يمكنك قراءة المزيد عنها في ويكيبيديا أو بالبحث في جوجل عن Dijkstra's algorithm). قبل الانتقال للبريمج وشرحه سأقوم بشرح أهم خطوات هذه الخوارزمية بشكل مختصر. لإيجاد أقصر مسار من العقدة أ إلى العقدة ب نتبع الخطوات التالية:

  1. نفترض مبدئيا أن المسافة التي تفصلنا عن العقدة أ هي صفر بينما المسافات التي تفصلنا عن باقي العقد الأخرى هي ما لا نهاية (أي لا يمكن الوصول إليها). تذكر: هذا مجرد افتراض مبدئي سيتغير خلال عملية استكشاف المسار.
  2. قم بوضع علامة على جميع العقد دون استثناء تشير إلى أن هذه العقد لم يتم استكشافها بعد (أي لم نقم بزيارتها).
  3. اذهب إلى العقدة أ، وبالتالي تكون هي العقدة الحالية التي نتعامل معها.
  4. افترض أن لكل عقدة غير العقدة أ مدخلاً، هذه العقدة المدخل ستكون الأقرب مسافة من العقدة أ. مبدئيا ستكون جميع هذه المداخل غير معروفة، بينما لا يلزمنا مدخل للعقدة أ طالما أننا أصلا نبدأ منها.
  5. قم بتكرارا الخطوات التالية إلى أن تصل إلى العقدة ب أو تتم زيارة كل العقد دون أن تتمكن من الوصول إلى ب. في الحالة الثانية تكون النتيجة أنه لا يوجد مسار من أ إلى ب:
    1. قم بوضع علامة على العقدة الحالية أنه قم تم زيارتها.
    2. إذا كانت العقدة الحالية هي ب نكون قد وصلنا إلى هدفنا. بالتالي بقي علينا تتبع المداخل من ب رجوعا إلى أ حتى نحصل على المسار الأقصر الكامل بين العقدتين.
    3. إذا لم نصل بعد للعقدة ب، قم بحساب المسافة بين العقدة الحالية وجميع العقد المجاورة لها والتي لم نقم بعد بزيارتها.
    4. أضف للمسافة المحسوبة في الخطوة السابقة المسافة التي قطعناها للوصول للعقدة الحالية. في حالة كوننا لا نزال في العقدة الأولى أ فإن المسافة المضافة ستكون صفرا.
    5. إذا كانت المسافة المحسوبة للعقدة المجاورة أقل من المسافة المعروفة لدينا قم باعتماد المسافة المحسوبة على أنها المسافة المعروفة لدينا لهذه العقدة، وقم كذلك باعتماد العقدة الحالية كمدخل للعقدة المجاورة. في حال كنا نزور العقدة المجاورة لأول مرة فإن المسافة المعروفة لدينا هي الما لا نهاية، بالتالي فالمسافة المحسوبة أقل منها في جميع الأحوال.
    6. قم بإيجاد العقدة ذات المسافة المعروفة الأقصر شريطة أن تكون هذه العقدة لم يسبق لنا زيارتها. اذهب لتلك العقدة بعد إيجادها واعتمدها لتكون العقدة الحالية وأعد الخطوات السابقة حتى تحقق أحد الشرطين في الخطوة الرئيسية.
  6. إذا انتهت جميع الخطوات دون الوصول إلى ب قم بإرجاع قيمة تدل على أنه لا يوجد أي مسار يصل أ و ب على الإطلاق.

بعد الاطلاع على آلية عمل خوارزمية دايجسترا لنر الآن كيف يمكننا الاستفادة منها في إيجاد المسار داخل خريطة اللعب اعتمادا على شبكة المسارات المتوفرة لدينا. كما سبق ذكره فإن عملية إيجاد المسار سيتكفل بها البريمج PathFinder والذي سنضيفه لكائن الشخصية التي ستلاحق اللاعب. هذا البريمج موضح في السرد التالي:



1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4. 
5. public class PathFinder : MonoBehaviour {
6. 	
7. 	//هل يجب أن يقوم البريمج برسم المسار في شاشة تحرير المشهد؟
8. 	public bool drawPath = false;
9. 	
10. 	//الهدف الذي نريد إيجاد المسار إليه
11. 	private Transform target;
12. 	
13. 	//قائمة تحتوي على جميع العقد ضمن المسار إلى الهدف
14. 	private List<int> pathToTarget;
15. 	
16. 	//مرجع إلى شبكة المسارات الموجودة على الخارطة
17. 	private AIGraph graph;
18. 	
19. 	//مرجع إلى كائن شخصية اللاعب
20. 	private Transform player;
21. 	
22. 	// يتم استدعاؤها مرة واحدة عند البداية
23. 	void Start () {
24. 		//(أي لا هدف محدد)الهدف مبدئيا هو الكائن نفسه
25. 		target = transform;
26. 		//قم بإيجاد بريمج شبكة المسارات وخذ مرجعا إليه
27. 		graph = FindObjectOfType<AIGraph>();
28. 		pathToTarget = new List<int>();
29. 		//Player ابحث عن كائن اللاعب عن طريق الوسم
30. 		player = GameObject.FindWithTag("Player").transform;
31. 	}
32. 	//عدد الإطارات التي يجب أن تمر بين كل عمليتي تحديث للمسار
33. 	int updateFrames = 30;
34. 	
35. 	// يتم استدعاؤها مرة واحدةعند تصيير كل إطار
36. 	void Update () {
37. 		//اتبع اللاعب
38. 		SetTarget(player);
39. 		if(Time.frameCount % updateFrames == 0){
40. 			FindShortestPath();
41. 		}
42. 		UpdateDrawPath();
43. 	}
44. 	
45. 	//تقوم بتحديد الكائن الهدف الذي نريد البحث عن مسار إليه
46. 	public void SetTarget(Transform newTarget){
47. 		target = newTarget;
48. 	}
49. 
50. 	//تقوم بإرجاع الكائن الهدف الذي نلاحقه
51. 	public Transform GetTarget(){
52. 		return target;
53. 	}
54. 
55. 	//تقوم بإرجاع قائمة تحتوي على جميع العقد
56. 	//الموجودة على المسار بدءا من الموقع الحالي وحتى الهدف
57. 	public List<int> GetPathToTarget(){
58. 		return pathToTarget;
59. 	}
60. 	
61. 	//تقوم برسم خط المسار إلى الهدف في حال تمكين هذا الخيار
62. 	private void UpdateDrawPath(){
63. 		if(drawPath){
64. 			if(pathToTarget != null){
65. 				for(int i = 0; i < pathToTarget.Count - 1; i++){
66. 					Vector3 start = graph.GetNodePosition(pathToTarget[i]);
67. 					Vector3 goal = graph.GetNodePosition(pathToTarget[i + 1]);
68. 					Debug.DrawLine(start + Vector3.up * 0.2f, 
69. 								    goal + Vector3.up * 0.2f, Color.red);
70. 				}
71. 			}
72. 		}
73. 	}
74. 	
75. 	//تقوم بتطبيق خوارزمية دايجسترا من أجل إيجاد أقصر
76. 	//مسار بين الموقع الحالي وموقع الهدف
77. 	private void FindShortestPath(){
78. 		
79. 		int startNode, goalNode;
80. 		startNode = graph.GetNodeAtPosition(transform.position);
81. 		goalNode = graph.GetNodeAtPosition(target.position);
82. 		
83. 		//أحص العدد الكامل للعقد في الخارطة
84. 		int nodeCount = graph.GetNodeCount();
85. 		//تعريف مصفوفة المسافات الموصلة للعقد
86. 		float[] distances = new float[nodeCount];
87. 		//الخطوة 1 - حدد المسافة صفر لعقدة البداية وما لا نهاية لباقي العقد
88. 		for(int i = 0; i < nodeCount; i++){
89. 			if(i == startNode){
90. 				distances[i] = 0.0f;
91. 			} else {
92. 				distances[i] = Mathf.Infinity;
93. 			}
94. 		}
95. 		
96. 		//الخطوة 2 - قم بتحديد جميع العقد بأنها لم تتم زيارتها
97. 		bool[] visited = new bool[nodeCount];
98. 		for(int i = 0; i < nodeCount; i++){
99. 			visited[i] = false;
100. 		}
101. 		
102. 		//قم بتحديد المدخل الموصل لكل عقدة على أنه غير موجود
103. 		int[] prev = new int[nodeCount];
104. 		for(int i = 0; i < nodeCount; i++){
105. 			prev[i] = -1;
106. 		}
107. 		
108. 		//الخطوة 3 - علّم عقدة البداية على أنها العقدة الحالية
109. 		int currentNode = startNode;
110. 		int visitedCount = 0;
111. 		
112. 		//ستبقى هذه الحلقة التكرارية تدور حتى يتم إيجاد أقصر مسار
113. 		//أو تتم زيارة جميع العقد دون إيجاده
114. 		while(visitedCount < nodeCount){
115. 			
116. 			//قم بتحديد العقدة الحالية على أنها تمت زيارتها وزد عدّاد الزيارات
117. 			visited[currentNode] = true;
118. 			visitedCount++;
119. 			//تأكد من كوننا وصلنا العقدة الهدف أم ليس بعد
120. 			if(currentNode == goalNode){
121. 				pathToTarget.Clear();
122. 				//وصلنا العقدة الهدف، تتبع المداخل وصولا إلى البداية
123. 				//من أجل الحصول على المسار الكامل
124. 				int prevNode = currentNode;
125. 				do {
126. 					pathToTarget.Add(prevNode);
127. 					prevNode = prev[prevNode];
128. 				} while(prevNode != -1);
129. 				
130. 				//تم إيجاد المسار، علينا الآن أن نرجع العقد
131. 				//مع عكس ترتيبها حتى تصبح عقدة البداية في أول القائمة
132. 				pathToTarget.Reverse();
133. 				return;
134. 			}
135. 			
136. 			//الخطوة 4 - قم بحساب المسافة اللازمة للوصول لجميع العقد المجاورة التي لم تتم زيارتها
137. 			List<int> neighbors = graph.GetConnectedNodes(currentNode);
138. 			
139. 			foreach(int neighbor in neighbors){
140. 				if(!visited[neighbor]){
141. 					float distToNode = distances[currentNode];
142. 					distToNode += graph.GetDistance(currentNode, neighbor);
143. 					//الخطوة 4.1 - إذا كانت المسافة المحسوبة أقل من المعروفة لدينا حاليا
144. 					//قم باستبدالها وتحديث المدخل إلى العقدة الجديدة ذات المسافة الأقل
145. 					if(distToNode < distances[neighbor]){
146. 						distances[neighbor] = distToNode;
147. 						prev[neighbor] = currentNode;
148. 					}
149. 				}
150. 			}
151. 			
152. 			//الخطوة 5 - قم بإيجاد عقدة الدورة التالية وهي العقدة ذات مسافة الوصول الأقل
153. 			//على الإطلاق شريطة ألا تكون قد تمت زيارتها قبلا
154. 			float minDist = Mathf.Infinity;
155. 			int nextNode = -1;
156. 			
157. 			for(int i = 0; i < nodeCount; i++){
158. 				if(!visited[i]){
159. 					float nodeDistance = distances[i];
160. 					if(nodeDistance < minDist){
161. 						minDist = nodeDistance;
162. 						nextNode = i;
163. 					}
164. 				}
165. 			}
166. 			
167. 			if(nextNode == -1){
168. 				//لم يتم العثور على عقدة تالية وفق الشروط، أي لا يوجد مسار إلى الهدف
169. 				return;
170. 			}
171. 			
172. 			//قم بتحديث العقدة الحالية لتصبح العقدة التالية وأعد الدورة من جديد
173. 			currentNode = nextNode;
174. 		}	
175. 	}
176. }

البريمج الخاص بتطبيق خوارزمية دايجسترا لإيجاد أقصر مسار بين عقدتين

يعتمد إيجاد المسار في هذا البريمج على موقعين: الموقع الحالي للكائن نفسه transform.position و والموقع الخاص بالكائن الهدف target.position. القائمة pathToTarget ستكون موقع تخزين تسلسل العقد في المسار الذي سنسلكه للوصول إلى الهدف. إضافة لهذه المتغيرات لدينا خيار رسم المسار عن طريق المتغير drawPath إضافة لمرجع ضروري لشبكة المسارات على الخارطة والتي نصل لها عن طريق المتغير graph. لعل المتغير updateFrames هو الأكثر لفتا للانتباه في هذا البريمج من حيث وظيفته، حيث أنه يحدد عدد الإطارات التي يجب أن يتم تصييرها قبل أن يسمح بتنفيذ دالة إيجاد المسار ()FindShortestPath مرة أخرى كما في السطر 39. الهدف من مرور عدد من الإطارات بين كل عمليتي تحديث للمسار هو أن عملية إيجاد المسار طويلة واستدعاؤها في كل إطار سيؤثر سلبا على الأداء. والأمر البديهي هنا هو أننا نقوم بتحديث المسار بين فترة وأخرى لأن الهدف قد يكون متحركا بالتالي يصبح المسار القديم غير صالح إذا تحرك الهدف من موقعه. الدّالة الرئيسية في هذا البريمج كما هو واضح هي ()FindShortestPath وهي التي تقوم بتطبيق خوارزمية دايجسترا حرفيا، بالتالي لن اخوض في شرحها مرة أخرى كونها تطبق الخوارزمية على بين العقدتين الأقرب للكائن الحالي والأقرب للكائن الهدف. للحصول على قائمة بالعقد التي يجب أن نسلكها حتى نصل للهدف يمكن لأي بريمج آخر أن يستدعي الدّالة ()GetPathToTarget، وهذا تحديدا ما سيفعله البريمج الآخر الذي سنضيفه لكائن شخصية الذكاء الاصناعي وهو PathFollower. ما يفعله هذا البريمج ببساطة هو قراءة مدخلات المسار من البريمج PathFinder ومن ثم التحكم بالشخصية من خلال البريمج PhysicsCharacter من أجل تسييرها باتجاه عقد المسار واحدة تلو الأخرى إلى أن تصل الشخصية إلى موقع الهدف. السرد التالي يوضح هذا البريمج:



1. using UnityEngine;
2. using System.Collections.Generic;
3. 
4. [RequireComponent(typeof(PathFinder))]
5. [RequireComponent(typeof(PhysicsCharacter))]
6. public class PathFollower : MonoBehaviour {
7. 	
8. 	//سرعة استدارة شخصية الذكاء الاصطناعي
9. 	public float turnSpeed = 10.0f;
10. 	
11. 	//مرجع لبريمج إيجاد المسار الموجود على نفس الكائن
12. 	private PathFinder finder;
13. 	
14. 	//مرجع لبريمج التحكم بحركة الشخصية والموجود على نفس الكائن
15. 	private PhysicsCharacter character;
16. 	
17. 	//مرجع إلى بريمج شبكة المسارات
18. 	private AIGraph graph;
19. 	
20. 	//تستدعى مرة واحدة عند بداية التشغيل
21. 	void Start () {
22. 		//قم بتعريف المراجع إلى البريمجات الأخرى
23. 		finder = GetComponent<PathFinder>();
24. 		character = GetComponent<PhysicsCharacter>();
25. 		graph = FindObjectOfType<AIGraph>();
26. 	}
27. 	
28. 	//تستدعى مرة واحدة عند تصيير كل إطار
29. 	void Update () {
30. 		float dist = Vector3.Distance(transform.position, finder.GetTarget().position);
31. 		//تحرك في حال كان الهدف يبعد أكثر من متر ونصف
32. 		if(dist > 1.5f){
33. 			FollowPath();
34. 		} else {
35. 			//إذا لم يكن الهدف بعيدا توقف وانظر إليه
36. 			Vector3 lookPos = finder.GetTarget().position;
37. 			lookPos.y = transform.position.y;
38. 			transform.LookAt(lookPos);
39. 			//أرسل رسالة لإخبار البريمجات الأخرى بالوصول إلى الهدف مرفقة بمرجع لكائنه
40. 			SendMessage("TargetReached", finder.GetTarget(), 
41. 									SendMessageOptions.DontRequireReceiver);
42. 		}
43. 	}
44. 	
45. 	//تقوم بالتقدم خطوة واحدة باتجاه الهدف
46. 	void FollowPath(){
47. 		List<int> path = finder.GetPathToTarget();
48. 		
49. 		if(path != null && path.Count > 1){
50. 			Vector3 moveTo = graph.GetNodePosition(path[1]);
51. 			moveTo.y = transform.position.y;
52. 			
53. 			//قم بالدوران بشكل تدريجي للنظر إلى جهة العقدة التالية
54. 			Quaternion newRot;
55. 			newRot = Quaternion.Lerp(transform.rotation, //الدوران الحالي
56. 					 		Quaternion.LookRotation( //تحسب دوران النظر من نقطة لأخرى
57. 								moveTo - transform.position), //الدوران المستهدف
58. 								Time.deltaTime * turnSpeed); //سرعة الاستدارة
59. 			//فقط y بعد حساب الاستدارة نحتاج لتطبيقها على المحور
60. 			newRot.eulerAngles.Set (transform.rotation.x, newRot.y, transform.rotation.z);
61. 			//قم باعتماد الدوران الجديد للكائن
62. 			transform.rotation = newRot;
63. 			
64. 			//تأكد من أننا وصلنا للعقدة التي نتوجه إليها واحذفها من القائمة في هذه الحالة
65. 			if(graph.GetNodeAtPosition(transform.position) == path[1]){
66. 				path.RemoveAt(0);
67. 			}
68. 			
69. 			//حرك الشخصية للأمام
70. 			character.WalkForward();
71. 		}
72. 	}
73. }

البريمج الذي يتحكم بشخصية الذكاء الاصطناعي من أجل تحريكها نحو الهدف عبر المسار المكتشف

يلاحظ في هذا البريمج أنه يؤدي وظيفة بسيطة اعتمادا على البريمجات الثلاث AIGraph و PathFinder و PhysicsCharacter. بما أن هذا البريمج سيقوم بتحريك الشخصية لتتبع المسار إلى الهدف فهو بحاجة لمعرفة العُقَد الموجودة في المسار من خلال PathFinder ومواقعها في المشهد من خلال AIGraph. بعد معرفتها سيتوجه للعقدة الثانية في القائمة حيث أن الموقع الأول فيها هو للعقدة التي تقف عليها الشخصية، وسيعمل على تدوير الشخصية تدريجيا حتى تنظر باتجاه العقدة التالية في المسار ومن ثم يمشي خطوة باتجاه هذه العقدة. في حال وصلت الشخصية للعقدة يقوم البريمج بحذفها من القائمة والسير نحول العقدة التالية بنفس الطريقة. لاحظ أنه عند كل عملية تحديث يقوم البريمج بحساب المسافة شخصية الذكاء الاصطناعي التي تحمله وبين موقع الهدف، فإذا قلت هذه المسافة عن متر ونصف تتوقف الشخصية عن الحركة وتبدأ بإرسال الرسالة TargetReached للبريمجات الأخرى مصحوبة بمرجع لكائن الهدف. باكتمال هذه الخطوة أصبح المشهد جاهزا وبإمكانك تجربته لرؤية كيفية تتبع شخصية الذكاء الاصطناعي للاعب أينما تحرك في الخريطة.

المسار المكتشف من شخصية الذكاء الاصطناعي باتجاه الهدف

المسار المكتشف من شخصية الذكاء الاصطناعي باتجاه الهدف

السابقالتالي

تعليقات واستفسارات