Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

کیسے  جمپ پوائنٹ سرچ الگورتھم  (Jump Point Algorithm) سے *A  پاتھ فائنڈنگ (Pathfinding) کی رفتار بڑھا سکتے ہیں

by
Difficulty:IntermediateLength:LongLanguages:

Urdu (اُردُو) translation by Shaan (you can also view the original English article)

Pathfinding گیمز میں ہر جگہ ہے۔ لہذا ان پوشیدہ معنوں کو سمجھنا ضروری ہے جو الگورتھم *A کا استعمال کرتے وقت سامنے آتے ہیں۔ اس ٹیوٹوریل میں ہم  گرڈ کی بنیاد پر بنی ہوئی دنیاؤں کو ڈھونڈنے کے لئے نسبتاََ نیا طریقہ استعمال کریں گے: جمپ پوائنٹ سرچ، جو کہ جسامت (magnitude) کے اعتبار سے *A کی رفتار کو تیز کرسکتی ہے۔

نوٹ: اگرچہ یہ ٹیوٹوریل AS3 اور Flash (فلیش) کا استعمال کرتے ہوئے لکھا گیا ہے، پر آپ کو تقریبا کسی بھی گیم ڈیولپمنٹ کا ماحول (environment)  بنانے کے لئے انہی تکنیک اور تصورات  کا استعمال کرنے کے قابل ہونا چائیے۔

یہ عمل یہاں پر پائے جانے والے JPS کے اصلی کاغذ اور آرٹیکل پر مبنی ہے۔ Jump Point Search (جمپ پوائنٹ سرچ): The 
Lua کی بنیاد پر عمل درآمد میں، Jumper (جمپر)، عمل کے کچھ حصوں پر  مدد کے لئے استعمال کیا جاتا تھا۔


جمپ پوائنٹ سرچ ڈیمو (Jump Point Search Demo)

اس پر توجہ دینے کے لئے SWF پر کلک کریں، پھر اپنے ماؤس کو نقشہ نہ روکنے والی جگہوں (non-blocking areas) پر بڑھائیں تاکہ NPCs اس قابل ہوں کہ وہ اسے حاصل کر سکیں۔ *A، جمپ پوائنٹ سرچ، یا دونوں، کے درمیان سوئچ کرنے کے لئے اسپیس دبائیں۔

Flash نہیں ہے؟ اس کی بجائے YouTube ویڈیو کو چیک کریں:


سیٹ اپ (Setup)

اوپر دی گئی demo implementation میں GPU سے تیزی سے رنڈرنگ کرنے کے لئے AS3 اور Flash کا استعمال سٹارلنگ فریم ورک (Starling Framework) کے ساتھ ہوتا ہے اور اعداد و شمار کے ڈھانچے یعنی data structures کے لئے polygonal-ds لائبریری کا۔


پاتھ فائنڈنگ (Pathfinding) 

Pathfinding اکثر ویڈیو گیمز میں استعمال کی جاتی ہے اور آپ  یقیناََ  اپنے گیم ڈویلپمنٹ  کے کیریئر میں کسی وقت بھی اس میں ٹکرایں گے۔ اس کا بنیادی استعمال مصنوعی اداروں (NPCs) کو ایک ذہین دیکھائی دینے والے تحریکی رویے دینا ہے۔ اور(اکثر) انہیں چیزوں میں ٹکرانے سے بچانا ہے۔

کچھ گیمز میں کھلاڑی کا avatar  بھی pathfinding سے مشروط ہوتا ہے (حکمتِ عملی کی گیمز، بہت سی تھرڈ پرسن RPGs اور ایڈوینچر گیمز)۔ تو آپ فرض کر سکتے ہیں کہ pathfinding کا مسئلہ حل ہو گیا ہے، لیکن بد قسمتی سے یہ صورت حال نہیں ہے؛ کوئی چاندی کی گولی نہیں ہے کہ جو آپ استعمال کرتے ہیں اور اسیے پورا کر لیتے ہیں۔

اور یہاں تک کہ بڑی AAA گیمز میں، آپ کو اب بھی اس طرح کی مضحکہ خیز چیزیں مل جائیں گی:

بےشک یہاں ایک چاندی کی گولی نہیں ہے، پر یہاں پر ایک گولی ہے: ایک *A الگورتھم (A star algorithm)۔ اس ٹیوٹوریل میں ہم *A کا ایک مختصر جائزہ لینے جا رہے ہیں اور (دیکھیں گے کہ) ایک اور الگورتھم Jump Point Search (جمپ پوائنٹ سرچ)، کے استعمال سے کس طرح  اس کی رفتار تیز کرنی ہے۔

سب سے پہلے ہمیں ایک طریقے کی ضرورت ہے کہ جو ہماری گیم کی دنیا کی نمائندگی اس طرح سے کرے کہ ایک pathfinding الگورتھم  اسے استعمال کر سکے۔


دنیا کی نمائندگی (World Representations)

جب ہم اپنی  گیمز کے لئے pathfinding کے بارے میں سوچ رہے ہوتے ہیں تو غور کرنے کے لئے سب سے اہم چیز دنیا کی نمائندگی (world representation) ہے۔ بغیر رکاوٹ کے گزرنے والے راستوں (passable areas) اور راہ میں حائل رکاوٹوں (obstacles) کے اعداد و شمار کو کس طرح پروگرامنگ سٹکچر کے ڈیٹا میں منظم کرنا ہے؟

ایک سادہ ترین نمائندگی جو آپ استعمال کر سکتے ہیں، وہ ایک گرڈ کی بنیاد پر سٹکچر (grid-based structure) ہے، جہاں پر path nodes گرڈ میں منظم کی جاتی ہیں اور 2D array سے ظاہر کی جا سکتی ہیں۔ ہم اس ٹیوٹوریل میں اس نمائندگی (representation)  کا استعمال کرنے جا رہے ہیں۔ خاص طور پر یہ ایک آٹھ سمتوں والی گرڈ کی نمائندگی (eight-way grid representation) ہو گی: جو سیدھی اور ڈائیگنل سمتوں میں حرکت کی اجازت دی گی۔


تصویر میں سیاہ پکسلز(pixels) مسدود خلیات (blocking cells) کو ظاہر کر رہے ہیں۔

آپ کی ضروریات مختلف بھی ہو سکتی ہے، لہذا اس کی ساخت آپ کے مطابق نہیں بھی ہو سکتی۔ اچھی بات یہ ہے کہ کچھ پروسیسنگ (عام طور پر آف لائن کی جانے والی) کے ساتھ آپ pathfinding representations کو دیگر فارمیٹس میں تبدیل کر سکتے ہیں۔ گرڈ کی ایپروچ کے متبادل میں یہ  چیزیں شامل ہوں گی جیسے کہ پولی گان ( پولی گان سے رکاوٹوں کی نمائندگی کرنا) یا نیویگیشن میشز (navigation meshes) (نیویگیشن ایریا کی نمائندگی پولی گانز سے کرنا)؛ یہ ایک ہی ڈیٹا کی کم نوڈز (nodes) کے ساتھ نمائندگی کر سکتے ہیں۔

ایک اور ڈیٹا جو نقشہ کی نمائندگی یعنی map representation  میں محفوظ کیا جا سکتا ہے وہ کاسٹس (costs) ہیں: کہ ایک سے دوسرے نوڈ تک سفر کرنا کتنا کاسٹ کرتا ہے۔ یہ AI کے لئے بھی استعمال کیا جا سکتا ہے تاکہ اس راہ کا تعین کرسکیں کہ جو، مثال کے طور پر سڑکوں کو ریگولر ٹیرن پر ترجیح دینا (جو سڑ کیں  بنانے کی لاگت یعنی کا سٹ کو ٹیرن سے کم کرتا ہے)۔

جمپ پوائنٹ سرچ خاص طور پر آٹھ طرفہ گرڈ کی بنیاد پر نقشہ کی نمائندگی (map representation) کے لئے ڈیزائن کیا گیا ہے تو اس لئے ہم اسے استعمال کریں گے۔ اس کے علاوہ، یہ اپنی ونیلا شکل (vanilla form) میں بھاری Maps کو سپورٹ نہیں کرتا ہے۔ (آخری حصے میں، میں اس کا تدارک کرنے کے لئے ایک ممکنہ طریقہ پر بحث کروں گا۔)


*A پاتھ فائنڈنگ ری فریشر (A* Pathfinding Refresher) 

اب ہمارے پاس ایک دنیا کی نمائندگی (world representation) موجود ہے چلیں اب ہم *A کے عمل درآمد پر ایک فوری نظر ڈالتے ہیں۔ یہ ایک بھاری گراف سرچ الگورتھم ہے جو heuristics (چھوٹی ’’ ہنٹس‘‘) کا استعمال اس لئے کرتا ہے کہ کس طرح  شروع کی نوڈ سے لے کر آخری نوڈ تک کے ایریا کواچھے طریقے سے سرچ کرنا ہے۔

میں انتہائی مشورہ دیتا ہوں کہ آپ pathfinding الگورتھم کے اس تصور (وژولائی زیشن) کو دیکھیں:
PathFinding.js - visual. اس کے ساتھ کام کرنا آپ کےوجدان کو بڑھا سکتا ہے یہ کہ الگورتھم اصل میں کیا کر رہا ہے۔ اس کے علاوہ یہ مزے کا ہے!

rectangular گرڈز میں *A کا استعمال کرتے ہوئے pathfinding کے لئے ہم درج ذیل  کام کرتے ہیں:

heuristics  یعنی چھوٹی ہنٹس بنیادی طور پر ایک چانس پر یہ اندازہ  کر رہی ہیں کہ جس نوڈ (node) کا تعین کیا جا رہا وہ مقصد (goal) کی قیادت کرے گی۔ pathfinding algorithms کی کارکردگی میں heuristics ایک بڑا فرق ڈال سکتا ہے کیونکہ یہ نوڈز کی تعداد کو کہ جنہیں وزٹ کرنے کی ضرورت ہوتی ہے محدود کر دیتا ہیں۔ ہم اپنے مقاصد کے لئے مین ہیٹن ڈسٹنس (Manhattan distance) کا استعمال کرنے جا رہے ہیں (مطلب یہ ہے کہ نوڈز جو گول کے قریب  ہونگی انکی تعداد تھوڑی ہوگی):

یہ کم یا زیادہ ہے۔ جب ہم goal node (گول نوڈ) کو تلاش کر لیتے ہیں تو تب ہم الگورتھم کو روک دیتے ہیں، اور پھر node کے parent variable  کا استعمال کرتے ہوئے ٹریک پر واپس جاتے ہیں تاکہ پاتھ کو دوبارہ بناسکیں۔

سرچ الگورتھمز دوسری چیزوں کے لئے بھی استعمال کیے جا سکتے ہیں۔ *A ایک عام بھاری گراف سرچ الگورتھم ہے، اور یہ اسی طرح کے کسی بھی گراف پر استعمال کیا جا سکتا ہے۔ یہ AI میں دیگر شعبوں کا احاطہ کر سکتا ہے، جیسا کہ مخصوص مقاصد کے حصول کے لیے زیادہ سے زیادہ اقدامات کی تلاش: ایک بم پھینکیں یا پناہ گاہ کے لئے بھاگیں اور دشمن کے پیچھے چپکنے کی کوشش کریں؟

گیم ڈولپمنٹ میں ہمیں تیزی سے چیزوں کو کرنے کی ضرورت  ہوتی ہے، جب ہم اپنی گیمز کو60 فریمز پر سیکنڈ پر اپ ڈیٹ کر رہے ہوتے ہیں تو  ہر millisecond بھی کاؤنٹ ہو رہا ہوتا ہے۔ اگرچہ *A استعمال میں بہت معقول طور پر کام انجام دیتا ہے پر اسیے تیز بنانے یا اس میں کم میموری استعمال کرنے (والی خصوصیت ڈالنے ) کی ضرورت موجود ہے۔


 اوپٹیمائیزیشن (Optimizations) یعنی کارکردگی 

نمائندگی کا انتخاب پہلی چیز ہے جو pathfinding کی کارکردگی اور آپ کی پسند کے pathfinding الگورتھم پر اثرانداز ہوگی۔ گراف کا سائز جو سرچ کیا جا رہا ہے (اس کا) ایک بڑا باہمی تعلق ہوگا کہ کس طرح آپ کی pathfinding کام کرتی ہے، (جو سمجھ میں آتا ہے کہ،  ایک بڑے شہر کے مقابلے میں اپنے  کمرے میں اپنا راستہ تلاش کرنا آسان ہے)۔

پھر آپ اعلی سطح کی اصلاحات (higher level optimizations) پر غور کریں گے جن میں عام طور پر چھوٹے علاقوں کو جھنڈ (clustering) کے ڈیٹا میں شامل کرنا اور پھر جب آپ پاتھ کو ریفائن کر رہے ہوں گے تو سفر کیے ہوئے چھوٹے چھوٹے علاقوں میں ان کو تلاش کرنا ہے۔  مثال کے طور پر، اگر آپ ایک ہمسایہ شہر میں ایک ریستوران میں جانا چاہتے ہیں،  سب سے پہلے آپ  نے یہ غور کرنا ہے کہ آپ نے کس طرح اپنے شہر سے اس شہر تک جانا ہے، اور جب آپ ایک بار اس شہر میں داخل ہوجائیں گے تو آپ اپنی ’’تلاش‘‘ کو محدود کر دینا  ہے اس ایریا تک کہ جہاں پر ریستوران واقع ہے، باقی سب کو  نظر انداز  کردینا ہے۔ اس میں اس طرح کی چیزیں شامل ہوں گی جیسے کہ، swamps اس کے علاوہ dead end elimination، اور *HPA۔

سب سے (lowest level) آخری سطح پر آپ کو سرچنگ کرنی ہو گی۔ آپ کو اپنے ڈیٹا کی نمائندگی (data representation) اور ممکنہ رکاوٹ کا انتخاب کرنا ہے، اور پھر انہیں ایک الگورتھم میں پلگ کرنا ہے جو نوڈز کو باہر نکالے گا، مقصد کی تلاش کے لئے یہاں اور وہاں کا سفرکریں۔ یہ الگورتھم ممکنہ ترمیم کے ساتھ عام طور پر *A سرچنگ الگورتھم پر مبنی ہیں۔ آسان صورتوں (cases) میں آپ براہ راست *A  کا استعمال کرتے ہوئے آگے نکل جاتے ہیں جو آپ کو آسانی فراہم کرتا ہے۔ میں نے سورس کے ڈاؤن لوڈ (source download) میں، ایک گرڈ کی بنیاد پر عمل درآمد فراہم کیا ہے۔


جمپ پوائنٹ سرچ (Jump Point Search) 

چونکہ یہ ٹیوٹوریل جمپ پوئنٹ سرچ کےعمل درآمد کے بارے میں ہے، تو pathfinding گراف کو ایک گرڈ کے ساتھ ظاہر کیا جائے گا۔ اور اسے خاص طور پر آٹھ سمتوں کی گرڈ ( eight-way grid) ہونے کی ضرورت ہے کیونکہ الگورتھم اسے براہ راست استعمال کرتا ہے۔

جمپ پوائنٹ سرچ واقعی میں کیا کرتی ہے کہ یہ کچھ قسم کے گرڈ کے مجموعوں میں بہت ساری انٹرمیڈیٹ نوڈز کو ختم کر دیتی ہے۔    یہ بہت سارے ایسے گروپس کو سکپ کر دیتی ہے کہ جنہیں آپ open list اور closed list میں شامل کریں گے، اور دیگر اور حساب کتاب بھی، کچھ مزید پروسیسنگ کے حق میں جب اگلی نوڈ اٹھائیں گے۔

جیسا کہ *A کے ساتھ، جس کو ہم نے سب سے کم F سکور کے ساتھ open scene سے منتخب کیا ہے۔  لیکن یہ وہ جگہ ہے کہ جہاں پر چیزیں دلچسپ ہونا شروع ہوتی ہیں۔ adjacent nodes کو منتخب کرنے کی بجائے ہم اس فنکشن کو کہیں گے کہ وہ ہمارے لئے یہ کام کر دے۔

کیا یہ کرتا ہے کہ جو نوڈز ہمارے راستے کے لئے دلچسپ نہیں ہیں ان کو ختم کر دیتا ہے۔ اس کے لئے ہم مرکزی رہنمائی کے اصول کے طور پر پیرنٹ (parent) کی ہدایت کا استعمال کریں گے۔ یہاں پر نوڈز کی کٹائی (pruning the nodes) کی مثالیں ہیں جنہیں ہم افقی (horizontal) اور عمودی (vertical) سمتوں میں نظر انداز کریں گے۔

horizontal pruning کی ایک حالت کی مثال۔

ان حالات کی جانچ پڑتال کے لئے، اس کوڈ میں، یہ if statements کی سیریز میں ختم کی جائے گا۔ آپ یہاں پر مثال دیکھ سکتے ہیں، جس میں تصویر کے اندر صحیح صورت بیان کی گئی ہے:


diagonal pruning کے حالات کی مثال

جب ہم نیبر( neighbor) کو منتخب کر لیتے ہیں پھر ہم جمپ پوائنٹ سرچ کو تلاش کرنے کی کوشش کریں گے، جو ایک نوڈ ہے جس میں موجودہ کے زریعے سے پہنچا جا سکتا ہے، لیکن ضروری نہیں کہ صرف ایک ہی راستے سے۔ زیادہ باضابطہ طور پر کرنے کے لئے،  JPS کیا کرتا ہے کہ وہ راستوں کے درمیان توازن (symmetry ) کو ختم کرتا ہے- ہر ایک کی ایک جیسی چالوں کی مختلف ترتیبیں ہیں:


پاتھ کے توازن (symmetry) کی مثال۔

تو بڑی کھلی جگہوں کے لئے ہم بڑی جیت حاصل کر سکتے ہیں۔ یہاں پر ہے کہ جمپ میتھڈ (jump method) کیسے کام کرتا ہے۔

میں نے if statements سے forced neighbor چیکس کو ختم کر دیا ہے کیونکہ یہ بہت بڑے ہیں۔  یہ بنیادی طور پر ان  چیکس پر مشتمل ہوتے ہیں کہ جو ان سے مل جلتے ہوتے ہیں کہ جب ہم پہلی بار neighbors کو ایک نئی نوڈ (new node ) کے لئے منتخب کرتے ہیں (بہت سارے چیکس دیکھنے پڑتے ہیں کہ اگر سیلز (cells)  بلاک  ہوں)۔ جب ہمیں توازن پر اپنے مفروضات (assumptions on symmetry) لگانے کی اجازت مل جاتی ہے تو یہ کھوج لگانے یا ڈی ٹیکٹ کرنے کے مقصد کا کام کرتے ہیں۔


جمپ فنکشن بیہیویر (jump function behavior) کی مثال۔

diagonal case بہت سپیشل ہے اور ہمیں صرف ڈائیگنل سمتوں میں forced neighbors کو نہیں دیکھنا، بلکہ اس کے ساتھ ساتھ افقی (horizontal ) اور عمودی (vertical) سمتوں میں بھی دیکھنا ہے، اور اگر ان میں سے کوئی بھی ناکام رہتا ہے تو ہم نے ایک forced node جمپ پوائنٹ کے طور پر ڈالنی ہوگی۔ ہمیں goal node کے سپیشل کیس پر بھی غور کرنا ہے، جہاں پر جمپ میتھڈ  ختم (terminate) ہو جاتا ہے۔ 

ہر بار ہم سرچ نوڈ کو تلاش نہیں کرتے بلکہ ہم مخصوص سمت میں جمپ فنکشن کو کِسی ضابطے میں پکارتے ہیں۔  ڈیمو میں، میں نے اصل میں یہ ضابطے کی کا ل (recursive call) کو کھولا ہے کیونکہ یہ بار بار استعمال کی جائے گی۔ (میری ٹیسٹنگ میں،  یہ کارکردگی کو دو کے فیکٹر سے بڑھاتا ہے۔)

یہ وہ ہے کہ جو JPS کرتا ہے؛ حتمی نتیجہ ایک نئی نوڈ ہے *A کے چیک کرنے کے لئے اور الگورتھم کے ساتھ آگے بڑھنےکے لئے۔ جب گول نوڈ (goal node) مل جائے گی ہم راستےکو نئے سرے سے تعمیرکریں گے اور اس کو واپس کریں گے۔


خصوصیات

سرچ کرتےہوئے JPS  بہت سی nodes کو چھوڑ سکتا ہے، جو اچھی رفتار میں بہتری دے سکتا ہے (میرے پروجیکٹ میں یہ *30x over A کے ارد گرد ہوتا ہے)، لیکن یہ ایک کاسٹ (قیمت) کے ساتھ آتا ہے۔

یہ ایک یونیفام گرڈ پر بہترین کام کرتا ہے، لیکن اضافی tweaking کے استعمال کرنے سے غیر یونیفارم (گرڈ)  کے ساتھ بھی کام کرنے لائیک بنایا جا سکتا ہے، فورس سے neighbors کو مارک کرنا (نشان لگانا) جہاں پر ایک ایک نوڈ کو عبور کرنے کی مختلف لاگت ہو (مختلف اخراجات کا استعمال کرنے کے لئے بہترین ہے)۔

 میں ایک گیم پر کام کر رہا ہوں، گریڈ بالکل برابر ہے سوائے سڑکوں کے، جو ریگولر ٹیرن (قطعہ زمین) پر چلنے کی بجائے بہت کم لاگت لگاتی ہے۔  (جب کریکٹر اس کا حوالہ کرتے ہیں تو یہ زیادہ بہتر لگتا ہے۔) آخر میں، میں نےسڑک کی پوزیشنوں کی کچھ ویلیوز (values) کی precomputing کر کے اسے حل کر لیا تھا۔ جب pathfinding شروع کیا جاتا ہے، تو الگورتھم شروع اور آخری نوڈز کے درمیان سے قریب ترین ممکنہ پوائنٹ تلاش کرتا ہے، اور پھر سڑکوں کی ایک خاص اعلی سطح  کےگراف یعنی high level graph کو تلاش کرتا ہے (جو پریکومپوٹید (precomputed) ہے)، اور پھر ان ٹیرن والے ایریا کو تلاش کرنے کے لئے JPS کا استعمال کرتے ہیں۔


ڈی بگینگ (Debugging)

ڈیبگینگ کرنے کے بارے میں ایک فوری نوٹ۔ اس قسم کے الگورتھم کو ٹھیک کرنا (Debugging) بہت مشکل بھی ہو سکتا ہے، اور یہ بھی تقریبا ممکن ہے کہ سب سے پہلے نفاذ میں بگ ڈھوندنے میں مشکلات پیش ہوں۔ آپ خود کی مدد کریں فعل تصور (وژولائزشن) بنائیں اور اسکی ڈرائنگ بنائیں کہ جب  الگورتھم چلتا ہے تو کیا ہوتا ہے۔

اگر آپ کو ایک بگ مل جائے تو آپ ڈومین کو (گرڈ سائز کو) کم سے کم کر دیں یہ آپ کے مسئلے کو دوبارہ پیش کرتا ہے اور وہاں سے ٹیسٹ کرنے کی اجازت دیتا ہے۔ آپ شاید اندازہ لگا سکتے ہیں، کہ JPS کی میری پہلی نفاذ نے اسی وقت کام نہیں کیا تھا!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.