المقالات العلمية

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

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

يمكنك قراءة المقالة الأصلية باللغة الإنجليزية هنا...

مقدمة

آليات الحالة المحدودة Finite State Machines (FSMs) هي طريقة بسيطة وفعالة لتنفيذ العديد من مزايا اللعبة، ويمكن أن تكون جزءاً من الحل أو تكون هي في مجملها الحل لعديد من المشاكل التي تواجه برمجة الألعاب، كالذكاء الاصطناعي والتعامل مع الدخل والتعامل مع اللاعب وواجهة المستخدم والتقدم في مراحل اللعبة. ويمكن أن تمثل بشكل بياني باستخدام أسلوب الرسم البياني القياسي والذي يسمى بالرسم البياني الموجه (directed graph)، وهو سهل القراءة والفهم، حتى بالنسبة لغير المبرمجين. وعمية تحويل الرسم البياني الموجه إلى جداول حالة تعتبر عملية بسيطة والعكس صحيح أيضاً. وكذلك من السهل تحسين أداء الـ FSM لتتشكل من أقل عدد من الحالات.

في هذه المقالة سنشرح كيف ننشئ نظاماً يتيح لنا تصميم مخططات FSM بشكل مرئي ويقوم بتصديرها بصيغة يمكن تنفيذها في اللعبة.

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

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

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

إنشاء النظام

عناصر نظامنا تبدأ بـبرنامج مايكروسوفت فيزيو (Microsoft Visio) والتي تمثل الواجهة المرئية التي سيتم عرض المخططات البيانية لآلية الحالة عليها. نبدأ بمكتبة وحداتFSM تدعى "مرسام" أو "قوالب" أو stencil في عالم فيزيو هي وثيقة برمجية ينشئها ويتابعها المبرمج لتعريف الأشكال البيانية الأساسية (الوحدات) التي سيبني منها المصممين مخططاتهم البيانية. حالما ينتهي المصمم من رسم مخطط الـ FSM يحفظه على شكل ملف XML. هذا الملف يشكل جزءاً من مصدر اللعبة.

العمل الحقيقي للمبرمجين هو الأدوات المستخدمة لكي تحلل وتفسر المخطط بصيغته الـ XML . الأداة الأولى هي أداة كونسول لتقرأ ملف الـ XML وتحوله إلى جدول ببيانات الحالة. بعد ذلك يأتي دور محلل الـ XML، والذي يشكل الجزء الأكبر من عمل الأداة. أخيراً، الصنف (class) التنفيذي للـ FSMs في اللعبة وهو الكود البرمجي الذي ينفذ البيانات في جدول الـ FSM ضمن اللعبة.

يمكن الحصول على الوثائق المرجعية والكود المصدري المشروح هنا من الرابط

نظام الذكاء الاصطناعي البسيط المقدم هنا يصف المنطق والبيانات المطلوبة لصنع شخصية تقوم بالمشي إلى الأمام والخلف على طول المحور X، مشابهة لـجومبا (Goomba)وهي شخصية من لعبة سوبر ماريو بروس (Super Mario Bros) ( عادةً, يشار إليهم بالدوريات [ Patrollers ] ).

 
يأتي برنامج فيزيو بدرازن من القوالب لإنشاء مخططات بيانية دقيقة لعديد من المعايير المختلفة. ويمكن للمستخدمين إنشاء قوالب (الوحدات أو المرسام كما ذكرنا في بداية المقالة) . القالب يمكن له أن يعرف شكل وصِفـَة الأشكال والروابط التي يمكن أن تـُستخدم مجتمعة في تشكيل المخطط البياني. فبرنامج فيزيو يشكل واجهة استخدام مثالية لنظام FSM، ويزيل الحاجة لأي أداة إظهار رسومية أخرى.

القوالب والمخططات يمكن أن تحفظ أو تحول إلى العديد من الصيغ المختلفة. في هذا النظام اعتمدنا صيغة XML (*.vsx و *.vdx للقوالب والمخططات على التوالي).

الأشكال

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

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

الصفات المخصصة

لدى كل شكل في فيزيو القدرة على أن يحوي مجموعة من الصفات القابلة للتعديل من قبل المستخدم، وتسمى بالصفات المخصصة (custom properties)، خاصية الصفات المخصصة هذه تدعم العديد من الأنواع مثل: السلاسل النصية (strings) والأعداد الصحيحة (integers) والقوائم المنسدلة (drop-lists) وغيرها الكثير. باستثناء خاصية الاسم (والتي هي من نوع السلاسل الحرفية) سوف نستخدم حصراً خاصية القوائم المنسدلة. المنطق الكامن وراء هذا الكلام سيتضح عندما نناقش كيف يقوم الكود البرمجي للعبة بتحويل هذه الصفات إلى بيانات. بالنسبة لنظام جومبا فقد قمنا بتعريف الصفات المخصصة المدرجة في الجدول 1.

الشكل 1 هو لقطة من الذكاء الاصطناعي لـجومبا في فيزيو. الدورية (patroller) تقوم بالمشي إلى الأمام والخلف بين كيانين محددين، وحينما يقوم اللاعب بإصابتها فستنهزم وتدخل في حالة نهائية. جومبا سيؤذي اللاعب إذا قام بلمسه (يتم وصف ذلك بالخاصية HitType (نوع الإصابة)، التي تحدد قيمته كيفية تصرف اللاعب مع بالشكل 1 هو لقطة من الذكاء الاصطناعي لـجومبا في فيزيو. الدورية (patroller) تقوم بالمشي إلى الأمام والخلف بين كيانين محددين، وحينما يقوم اللاعب بإصابتها فستنهزم وتدخل في حالة نهائية. جومبا سيؤذي اللاعب إذا قام بلمسه (يتم وصف ذلك بالخاصية HitType (نوع الإصابة)، التي تحدد قيمته كيفية تصرف اللاعب مع بيانات تصادم الذكاء الاصطناعي).

XML لمخطط مايكروسوفت فيزيو

بعد أن يتم إنشاء القوالب و مخطط FSM البياني للذكاء الاصطناعي، تكون المرحلة التالية هي تحويل بيانات هذا المخطط إلى جدول حالة . هذا الجدول يجب أن يكون مصفوفة ثنائية البعد تكون نموذجاً مكافئاً لآلة الحالة ومناسبة للمعالجة في الكود. بنية مخطط الـ XML في فيزيو هي بنية عميقة ومعقدة. ولحسن الحظ، في استخدامنا لتحويل XML إلى بيانات نحتاج فقط أن نهتم بالشجرة الفرعية (sub-tree) للهيكل المبين بالعناوين عريضة في [ الشكل 1 ] ومشروح في [ الجدول 2 ]. بالمرور بشكل تكراري على هذه العناوين تتمكن الأداة من أخذ كل لمعلومات اللازمة لتحويل مخطط الحالة إلى جدول حالة.

الشكل 1 : فرع من شجرة تمثل رسمة فيزيو بهيئة إكس إم إل

تحليل XML

هناك الكثير من مكتبات تحليل الـ XML المتاحة مجاناً. في مثالنا، سنستخدم الصنف XMLDataDocument (class) الخاص بـمكتبة Microsoft .Net للـ C++. وهو يتصرف كمحلل DOM الذي يقوم بتحويل واحتواء الوثيقة. ووظيفة إجراءات الوصول تجعل من تتبع العقد في الشجرة أمراً سهلاً. يوجد ملاحظة هنا وهي أن محللات DOM ليست بسرعة محللات single-pass SAX، لذلك إذا كان لديك مشروع يحوي العديد من بنى الذكاء الاصطناعي وكان زمن البناء يشكل الأولوية فعليك التفكير بحلول أخرى.

تحليل مخطط XML البياني بناءاً على المجموعات المذكورة أعلاه من مخطط فيزيو يجب أن يكون واضحاً. عينة الكود الموجودة في [ القصاصة 1 ] توضح كيف يمكن أن تقوم بالتكرار في العقد المترابطة بشكل نظيف.

الإجراء المذكور في [ القصاصة 1 ] يقوم بالتكرار خلال معرفات رئيسية في الوثيقة وذلك بتميز صفة التعريف الفريدة ID. إذا كان الدليل خارج النطاق out-of-range، سيتم إرجاع مؤشر بقيمة فارغة NULL. إجراء التكرار مفيد في تبسيط منطق توليد الكود الناتج.

   1: static XmlNode* getMaster(XmlDataDocument* xmlDoc, int ID)

   2: {   

   3:     XmlNode* pResult = NULL;

   4:     XmlNodeList* pElemList = xmlDoc->GetElementsByTagName("Master");

   5:     for (int i = 0; i < pElemList->Count; i++)

   6:     {

   7:         XmlAttributeCollection* pAttributes = pElemList->Item(i)->get_Attributes();

   8:         XmlAttribute* pAttrib = dynamic_cast(pAttributes->GetNamedItem("ID"));

   9:         if (Int32::Parse(pAttrib->Value) == ID)

  10:         {

  11:             pResult = pElemList->Item(i);

  12:             break;

  13:         }

  14:     }

  15:     return pResult;

  16: }

القصاصة 1 : إجراء لتعداد المعرفات.

الأداة

محرك اللعبة سوف يتطلب أداة تصدير كونسول لتحويل بيانات XML إلى جداول بيانات FSM كملفات C++ مصدرية أو ملفات بيانات ثنائية وذلك كجزء من عملية البناء. باستخدام محلل XML لتخزين المخطط البياني للبيانات، نستطيع أن نقوم بالتكرار خلال السمات المشروحة في القسم السابق وتجميع المعلومات التي نحتاجها. في [ القصاصة 2 ] ، سوف نقوم بتوليد كود C++ مصدري الذي سوف يُترجم ويُربط في الملف الثنائي التنفيذي.

   1: namespace AI

   2: {

   3:    // transitions

   4:    enum TransitionTestType

   5:    {

   6:       TEST_none = -1,

   7:       TEST_hitTriggerLeft = 0,

   8:       TEST_hitTriggerRight,

   9:       TEST_animationDone,

  10:       TEST_hitByPlayer,

  11:    };

  12:    struct TransitionTest

  13:    {

  14:       TransitionTestType mType;

  15:       int mValue;

  16:    };

  17:    // states

  18:    enum StateEntryActionType

  19:    {

  20:       ACTION_setAnimation,

  21:       ACTION_setXMovement,

  22:    };

  23:    enum Animation

  24:    {

  25:       ANIMATION_moveLeft,

  26:       ANIMATION_moveRight,

  27:       ANIMATION_death,

  28:       NUM_ANIMS,

  29:    };

  30:    enum XMovement

  31:    {

  32:       XMOVEMENT_left,

  33:       XMOVEMENT_right,

  34:       XMOVEMENT_death,

  35:       NUM_MOVEMENT,

  36:    };

  37:    struct StateEntryAction

  38:    {

  39:       StateEntryActionType mType;

  40:       int mValue;

  41:    };

  42:    struct State

  43:    {

  44:       const int* mTransitions;

  45:       int mNumTransitions;

  46:       const StateEntryAction* mActions;

  47:       int mNumActions;

  48:    };

  49:    // param

  50:    struct Param 

  51:    {

  52:       const TransitionTest* tests;

  53:       int numTests;

  54:       const State* states;

  55:       int numStates;

  56:       const int* stateTable;

  57:    };

  58: }

القصاصة 2 : "ai.h" – ملف رئيسي يعرف مؤشرات مصفوفة البيانات و البنى المشار إليها بالخرج المولد.

بعض التعاريف المفيدة لهيكل البيانات المذكورة في [ القصاصة 2 ] سوف يتم استخدامها في الخرج الذي قمنا بتوليده . [ القصاصة 3 ] هي الخرج المولـّد الفعلي الذي تم إنشاؤه بواسطة أداة الكونسول الخاصة بنا، في [ القصاصة 3 ] قمنا بتعديل الملف بشكل يدوي ، ولكن أداة بدائية يجب أن تستطيع توليد هذا الخرج من قالب XML مباشرة.

القائمة التالية تلخص الغرض من كل تعريف تم ذكره في [ القصاصة 2 ] :

   1: using namespace AI;

   2: // transitions

   3: const int numTransitionTests = 5;

   4: const TransitionTest transitionTests[numTransitionTests] =

   5: {

   6:    { TEST_hitTriggerRight, 0 },

   7:    { TEST_hitTriggerLeft, 0 },

   8:    { TEST_hitByPlayer, 0 },

   9:    { TEST_animationDone, 0 }, 

  10: };

  11: // states

  12: const int numStates = 3;

  13: // state 0

  14: const int numState0Transitions = 2;

  15: const int state0Transitions[numState0Transitions] = { 0, 2, };

  16: const int numState0Actions = 2;

  17: const StateEntryAction state0Actions[numState0Actions] =

  18: {

  19:    { ACTION_setXMovement, XMOVEMENT_left },

  20:    { ACTION_setAnimation, ANIMATION_moveLeft }, 

  21: };

  22: // state 1

  23: const int numState1Transitions = 2;

  24: const int state1Transitions[numState1Transitions] = { 1, 2, };

  25: const int numState1Actions = 2;

  26: const StateEntryAction state1Actions[numState1Actions] =

  27: {

  28:    { ACTION_setXMovement, XMOVEMENT_right },

  29:    { ACTION_setAnimation, ANIMATION_moveRight }, 

  30: };

  31: // state 2

  32: const int numState2Transitions = 1;

  33: const int state2Transitions[numState2Transitions] = { 3, };

  34: const int numState2Actions = 2;

  35: const StateEntryAction state2Actions[numState2Actions] =

  36: {

  37:    { ACTION_setXMovement, XMOVEMENT_death },

  38:    { ACTION_setAnimation, ANIMATION_death }, 

  39: };

  40: const State states[numStates] =

  41: {

  42:    // state 0 - start state

  43:    { 

  44:       // transitions

  45:       state0Transitions,

  46:       numState0Transitions,

  47:       // actions

  48:       state0Actions,

  49:       numState0Actions,

  50:    },

  51:    // state 1

  52:    { 

  53:       // transitions

  54:       state1Transitions,

  55:       numState1Transitions,

  56:       // actions

  57:       state1Actions,

  58:       numState1Actions,

  59:    },

  60:    // state 2

  61:    { 

  62:       // transitions

  63:       state2Transitions,

  64:       numState2Transitions,

  65:       // actions

  66:       state2Actions,

  67:       numState2Actions,

  68:    },

  69: };

  70: const int stateTable[numStates * numTransitionTests] =

  71: { 

  72:    1, 0, 2, 0,

  73:    1, 0, 2, 1,

  74:    2, 2, 2, -1,

  75: };

  76: const Param ai_ref::param =

  77: {

  78:    transitionTests,

  79:    numTransitionTests,

  80:    states,

  81:    numStates,

  82:    stateTable,

  83: };

   1: class AIObject : public VisibleGameObject

   2: {

   3:    public:

   4:    AIObject(

   5:       const AI::Param& param,

   6:       const Animation** anims,

   7:       const MoveParam2D* moves,

   8:       const Position& worldLocation

   9:       );

  10:    virtual ~AIObject();

  11:    bool receive(const Hit& hit);

  12:    void update();

  13:    protected:

  14:    void enterState(const AI::State& state);

  15:    void setAnimation(AI::Animation anim);

  16:    void setMovement(AI::XMovement move);

  17:    const AI::Param& mParam;

  18:    const Animation** mAnims;

  19:    const MoveParam2D* mMoves;

  20:    int mCurrentStateIndex;

  21:    union 

  22:    {

  23:       unsigned int mMask;

  24:       bool mHitByPlayer;

  25:       bool mHitTriggerLeft;

  26:       bool mHitTriggerRight;

  27:    } mFlags;

  28: };