A * Pathfinding للمنصات المستندة إلى الشبكة 2D: جعل بوت يتبع السبيل

Arabic (العربية/عربي) translation by Basrah (you can also view the original English article)

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

عرض

يمكنك تشغيل Unity demo أو إصدار WebGL (100 ميغابايت+) لرؤية النتيجة النهائية في الإجراء. استخدم WASD لنقل الحرف ، انقر بزر الماوس الأيسر على نقطة للعثور على مسار يمكنك اتباعه للوصول إلى هناك ، انقر بزر الماوس الأيمن فوق خلية لتبديل الأرض في هذه النقطة ، انقر نقرًا مزدوجًا فوق منتصف لوضع نظام أساسي أحادي الاتجاه ، وانقر واسحب المنزلقات لتغيير قيمها.

تحديث المحرك

التعامل مع الدولة بوت

البوت له حالتان محددتان: الأول هو عدم القيام بشيء ، والثاني هو التعامل مع الحركة. في لعبتك ، على الأرجح ستحتاج إلى الكثير لتغيير سلوك البوت وفقًا للوضع.

public enum BotState
{
  None = 0,
	MoveTo,
}

ستقوم حلقة التحديث الخاصة بالبوت بأشياء مختلفة وفقًا للحالة المعيّنة حاليًا لـ mCurrentBotState:

void BotUpdate()
{
    switch (mCurrentBotState)
    {
        case BotState.None:
            /* no need to do anything */
            break;
            
        case BotState.MoveTo:
            /* bot movement update logic */
            break;
    }
    
    CharacterUpdate();
}

تقوم دالة CharacterUpdate بمعالجة جميع المدخلات وتحديث الفيزياء الخاصة بالبوت.

لتغيير الحالة ، سنستخدم وظيفة ChangeState التي تقوم بتعيين القيمة الجديدة ببساطة إلى mCurrentBotState:

1	public void ChangeState(BotState newState)
2	{
3	mCurrentBotState = newState;
4	}

السيطرة على بوت

سنقوم بالتحكم في البوت من خلال محاكاة المدخلات ، والتي سنقوم بتعيينها لمجموعة من Booleans:

1	protected bool[] mInputs;

يتم فهرسة هذا المصفوفة بواسطة التعداد KeyInput:

public enum KeyInput
{
    GoLeft = 0,
	GoRight,
	GoDown,
	Jump,
	Count
}

على سبيل المثال ، إذا أردنا محاكاة الضغط على الزر الأيسر ، فسنقوم بذلك على النحو التالي:

1	mInputs[(int)KeyInput.GoLeft] = true;

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

سنحتاج أيضًا إلى وظيفة مساعدة إضافية أو جدول بحث للحصول على عدد الإطارات التي نحتاجها للضغط على زر الانتقال من أجل القفز على عدد معين من الكتل:

int GetJumpFrameCount(int deltaY)
{
    if (deltaY <= 0)
        return 0;
    else
    {
        switch (deltaY)
        {
            case 1:
                return 1;
            case 2:
                return 2;
            case 3:
                return 5;
            case 4:
                return 8;
            case 5:
                return 14;
            case 6:
                return 21;
            default:
                return 30;
        }
    }
}

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

التحضير والحصول على مسار المتابعة

تقييد موقع الهدف

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

أولا ، دعونا ننظر إلى وظيفة TappedOnTile. يتم استدعاء هذه الوظيفة عندما يقوم اللاعب بالنقر فوق أي مكان في اللعبة؛ إن معلمة mapPos هي موضع البلاطة التي نقر عليها المشغل:

1	public void TappedOnTile(Vector2i mapPos)
2	{
3	}

نحتاج إلى تقليل موضع المربّع الذي تم النقر عليه حتى يكون على الأرض:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;
}

أخيرًا ، بمجرد وصولنا إلى بلاطة أرضية ، نعرف أين نريد نقل الشخصية إلى:

public void TappedOnTile(Vector2i mapPos)
{
    while (!(mMap.IsGround(mapPos.x, mapPos.y)))
        --mapPos.y;

    MoveTo(new Vector2i(mapPos.x, mapPos.y + 1));
}

تحديد موقع البدء

قبل أن نطلق فعليًا على وظيفة FindPath ، نحتاج إلى التأكد من أننا نمرر خلية البداية الصحيحة.

أولاً ، لنفترض أن بلاطة البداية هي الخلية اليسرى السفلية للحرف:

1	public void MoveTo(Vector2i destination)
2	{
3	Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
4	}

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

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

لنبدأ بإنشاء وظيفة تخبرنا ما إذا كان الحرف سيتناسب مع موضع مختلف ، وإذا كان كذلك ، سواء كان على الأرض في هذا المكان:

1	bool IsOnGroundAndFitsPos(Vector2i pos)
2	{
3	}

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

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }
}

يمكننا الآن معرفة ما إذا كان أي من المربعات الموجودة أسفل الحرف هي بلاطات أرضية:

bool IsOnGroundAndFitsPos(Vector2i pos)
{
    for (int y = pos.y; y < pos.y + mHeight; ++y)
    {
        for (int x = pos.x; x < pos.x + mWidth; ++x)
        {
            if (mMap.IsObstacle(x, y))
                return false;
        }
    }

    for (int x = pos.x; x < pos.x + mWidth; ++x)
    {
        if (mMap.IsGround(x, pos.y - 1))
            return true;
    }

    return false;
}

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

Vector2i startTile = mMap.GetMapTileAtPoint(mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f);
        
if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
}

نعلم أنه في هذه الحالة ، يقف الحرف إما على الحافة اليسرى أو على الحافة اليمنى من المنصة.

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

if (mOnGround && !IsOnGroundAndFitsPos(startTile))
{
    if (IsOnGroundAndFitsPos(new Vector2i(startTile.x + 1, startTile.y)))
        startTile.x += 1;
    else
        startTile.x -= 1;
}

الآن يجب أن نحصل على جميع البيانات التي نحتاج إليها لاستدعاء برنامج Pathfinder:

var path =  mMap.mPathFinder.FindPath(
            startTile, 
            destination,
            Mathf.CeilToInt(mAABB.HalfSizeX / 8.0f), 
            Mathf.CeilToInt(mAABB.HalfSizeY / 8.0f), 
            (short)mMaxJumpHeight);

الوسيطة الأولى هي بلاطة البداية.

والثاني هو الوجهة. يمكننا تمرير هذا كما هو.

الوسيطتان الثالثة والرابعة هما العرض والارتفاع اللذان يجب تقريبهما بحجم البلاط. لاحظ أننا هنا نرغب في استخدام سقف الارتفاع في البلاط؟ - على سبيل المثال ، إذا كان الارتفاع الحقيقي للحرف هو 2.3 من البلاط ، فنحن نريد أن تفكر الخوارزمية أن الحرف هو في الواقع 3 بلاطات عالية. (من الأفضل إذا كان الارتفاع الحقيقي للحرف هو في الواقع أقل قليلاً من حجمه في البلاط ، للسماح بمساحة أكبر قليلاً للأخطاء من المسار التالي لمنظمة العفو الدولية.)

وأخيرًا ، تكون الوسيطة الخامسة أعلى ارتفاع للقفزة للحرف.

النسخ الاحتياطي لأعلى قائمة عقدة

بعد تشغيل الخوارزمية ، يجب أن نتحقق مما إذا كانت النتيجة جيدة - أي إذا تم العثور على أي مسار:

1	if (path != null && path.Count > 1)
2	{
3	}

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

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);
}

كما ترون ، فنحن ننسخ النتيجة بترتيب عكسي ؛ هذا لأن النتيجة نفسها معكوسة. يعني ذلك أن العقد في قائمة mPath ستكون بترتيب أول وآخر طلب.

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

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);
        
    mCurrentNodeId = 1;
    ChangeState(BotState.MoveTo);
}

بعد تعيين عقدة الهدف الحالية ، نعين حالة bot على MoveTo ، لذا سيتم تمكين حالة مناسبة.

الحصول على السياق

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

نحن بحاجة إلى معرفة:

مواقف الوجهات السابقة والحالية والقادمة
ما إذا كانت الوجهة الحالية على الأرض أم في الجو
ما إذا كان الحرف قد وصل إلى الوجهة الحالية على المحور السيني
ما إذا كان الحرف قد وصل إلى الوجهة الحالية على المحور y

ملاحظة: الوجهات هنا ليست بالضرورة وجهة الهدف النهائي. انهم العقد في القائمة من القسم السابق.

سوف تسمح لنا هذه المعلومات بدقة بتحديد ما يجب أن يفعله البوت في أي موقف.

لنبدأ بالإعلان عن وظيفة للحصول على هذا السياق:

1	public void GetContext(out Vector2 prevDest, out Vector2 currentDest, out Vector2 nextDest, out bool destOnGround, out bool reachedX, out bool reachedY)
2	{
3	}

حساب المواقع العالمية من نقاط الوجهة

أول شيء يجب علينا القيام به في الدالة هو حساب الموقع العالمي لعقد الوجهة.

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

ترجمة هذه البرامج بسيطة للغاية: فنحن نحتاج فقط إلى مضاعفة موضع العقدة حسب حجم البلاط ، ثم تعويض المتجه المحسوب بموضع الخريطة:

1	prevDest = new Vector2(mPath[mCurrentNodeId - 1].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId - 1].y * Map.cTileSize + mMap.transform.position.y);

لاحظ أننا نبدأ بـ mCurrentNodeId يساوي 1 ، لذلك لا داعي للقلق حول محاولة الوصول إلى عقدة بفهرس بـ -1.

سنقوم بحساب موضع الوجهة الحالية بالطريقة نفسها:

1	currentDest = new Vector2(mPath[mCurrentNodeId].x * Map.cTileSize + mMap.transform.position.x,
2	mPath[mCurrentNodeId].y * Map.cTileSize + mMap.transform.position.y);

والآن بالنسبة لموقع الوجهة التالي. هنا نحتاج إلى التحقق مما إذا كان هناك أي عقد متبقية بعد الوصول إلى هدفنا الحالي ، لذا دعنا نفترض أولاً أن الوجهة التالية هي نفس الوجهة الحالية:

1	nextDest = currentDest;

الآن ، إذا كانت هناك أية نقاط متبقية ، فسنحسب الوجهة التالية بالطريقة نفسها التي اتبعناها في العقدين السابقين:

if (mPath.Count > mCurrentNodeId + 1)
{
    nextDest = new Vector2(mPath[mCurrentNodeId + 1].x * Map.cTileSize + mMap.transform.position.x,
                                  mPath[mCurrentNodeId + 1].y * Map.cTileSize + mMap.transform.position.y);
}

التحقق ما إذا كانت العقدة على الأرض

الخطوة التالية هي تحديد ما إذا كانت الوجهة الحالية على الأرض.

تذكر أنه لا يكفي فقط التحقق من المربع مباشرة تحت الهدف ؛ نحتاج للنظر في الحالات التي يكون فيها الحرف أكثر من كتلة واحدة:

لنبدأ بافتراض أن موضع الوجهة ليس على الأرض:

1	destOnGround = false;

الآن سوف ننظر من خلال البلاط أسفل الوجهة لمعرفة ما إذا كان هناك أي كتل صلبة هناك. إذا كان هناك ، يمكننا تعيين destOnGround على true:

for (int x = mPath[mCurrentNodeId].x; x < mPath[mCurrentNodeId].x + mWidth; ++x)
{
    if (mMap.IsGround(x, mPath[mCurrentNodeId].y - 1))
    {
        destOnGround = true;
        break;
    }
}

التحقق من وصول العقدة على المحور X

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

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

هذا هو الموقف الذي نحتاج إلى مطابقته مع عقد الهدف.

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

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

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x);

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

1	reachedX = (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
2	\|\| (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x);

التقط موقف الشخصية

في بعض الأحيان ، وبسبب سرعة الحرف ، فإنه يتجاوز الهدف ، مما قد يؤدي إلى عدم هبوطه على العقدة المستهدفة. انظر المثال التالي:

لإصلاح هذا ، سننقر في موضع الحرف بحيث يسقط على نقطة الهدف.

الشروط بالنسبة لنا لمفاجئة الحرف هي:

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

if (reachedX && Mathf.Abs(pathPosition.x - currentDest.x) > Constants.cBotMaxPositionError && Mathf.Abs(pathPosition.x - currentDest.x) < Constants.cBotMaxPositionError*3.0f && !mPrevInputs[(int)KeyInput.GoRight] && !mPrevInputs[(int)KeyInput.GoLeft])
{
    pathPosition.x = currentDest.x;
    mPosition.x = pathPosition.x - Map.cTileSize * 0.5f + mAABB.HalfSizeX + mAABBOffset.x;
}

يساوي cBotMaxPositionError في هذا البرنامج التعليمي 1 بكسل ؛ هذا هو المدى البعيد الذي تركنا فيه الشخصية من الوجهة بينما نسمح لها بالانتقال إلى الهدف التالي.

التحقق من وصول العقدة على المحور ص

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

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y);

وبالمثل ، إذا كانت الوجهة الحالية أقل من السابقة ، ووصل الحرف إلى الموقع y للعقدة الحالية ، فيمكننا تعيينreachedY إلى true أيضًا.

1	reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.)
2	\|\| (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y);

بغض النظر عما إذا كانت الشخصية تحتاج إلى القفز أو السقوط للوصول إلى موقع y في نقطة المقصد ، إذا كان قريبًا حقًا ، فيجب أن نحدد Yreached to true أيضًا:

reachedY = (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)

    || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)

    || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);

إذا كانت الوجهة على الأرض لكن الحرف ليس كذلك ، فعندئذ يمكننا أن نفترض أنه لم يتم الوصول إلى موقع Y للهدف الحالي:

1	if (destOnGround && !mOnGround)
2	reachedY = false;

هذا كل ما في الأمر - هذه هي جميع البيانات الأساسية التي نحتاج إلى معرفتها للنظر في نوع الحركة التي تحتاج إليها منظمة العفو الدولية.

التعامل مع حركة بوت

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

1	Vector2 prevDest, currentDest, nextDest;
2	bool destOnGround, reachedY, reachedX;
3	GetContext(out prevDest, out currentDest, out nextDest, out destOnGround, out reachedX, out reachedY);

الآن دعونا نحصل على الموقف الحالي للشخصية على طول الطريق. نحسب هذا بنفس الطريقة التي قمنا بها في وظيفة GetContext:

1	Vector2 pathPosition = mAABB.Center - mAABB.HalfSize + Vector2.one * Map.cTileSize * 0.5f;

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

1	mInputs[(int)KeyInput.GoRight] = false;
2	mInputs[(int)KeyInput.GoLeft] = false;
3	mInputs[(int)KeyInput.Jump] = false;
4	mInputs[(int)KeyInput.GoDown] = false;

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

1	if (pathPosition.y - currentDest.y > Constants.cBotMaxPositionError && mOnOneWayPlatform)
2	mInputs[(int)KeyInput.GoDown] = true;

التعامل مع القفزات

دعونا نوضح كيف يجب أن تعمل قفزاتنا. أولاً ، لا نريد الإبقاء على زر الانتقال مضغوطًا إذا كان mFramesOfJumping هو 0.

1	if (mFramesOfJumping > 0)
2	{
3	}

الشرط الثاني للتحقق هو أن الحرف ليس على الأرض.

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

1	if (mFramesOfJumping > 0 && !mOnGround)
2	{
3	}

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

لن يعمل هذا إذا كان يجب تنفيذ القفزة من الأرض ؛ للتعامل مع هذه نحتاج للتحقق من هذه الشروط:

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

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround)))
3	{
4	}

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

1	if (mFramesOfJumping > 0 &&
2	(!mOnGround \|\| (reachedX && !destOnGround) \|\| (mOnGround && destOnGround)))
3	{
4	}

الآن دعونا تفعيل القفز وتقليل إطارات القفز ، بحيث يحمل الحرف القفزة عن العدد الصحيح من الإطارات:

if (mFramesOfJumping > 0 &&
    (!mOnGround || (reachedX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

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

الانتقال إلى نقطة الوجهة التالية

لنفكر في ما يجب أن يحدث عندما نصل إلى العقدة ، أي عندما يكون كل من الوصولX إلى الحد الأقصى وصولاًY إلىtrue.

1	if (reachedX && reachedY)
2	{
3	}

أولاً ، سنزيد معرف العقدة الحالي:

1	mCurrentNodeId++;

نحتاج الآن إلى التحقق مما إذا كان هذا المعرّف أكبر من عدد العقد في مسارنا. إذا كان الأمر كذلك ، فهذا يعني أن الحرف قد وصل إلى الهدف:

if (mCurrentNodeId >= mPath.Count)
{
    mCurrentNodeId = -1;
    ChangeState(BotState.None);
    break;
}

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

1	public int GetJumpFramesForNode(int prevNodeId)
2	{
3	}

لا نريد سوى القفز إذا كانت العقدة الجديدة أعلى من العقدة السابقة وكان الحرف على الأرض:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
    }
}

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

أولاً ، دعونا نعلن ونضبط المتغير الذي يحمل قيمة القفزة:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
    }
}

الآن دعنا نكرر خلال العقد ، بدءًا من العقدة الحالية:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
        }
    }
}

إذا كانت العقدة التالية أعلى من jumpHeight ، وهي ليست على الأرض ، فلنقم بضبط ارتفاع الوثب الجديد:

public int GetJumpFramesForNode(int prevNodeId)
{
    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight && !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                    jumpHeight = mPath[i].y - mPath[prevNodeId].y;
        }
    }
}

إذا كان ارتفاع العقدة الجديدة أقل من السابق ، أو كان على الأرض ، فإننا نعيد عدد إطارات القفزة اللازمة للارتفاع الذي تم العثور عليه. (وإذا لم يكن هناك حاجة للقفز ، دعنا نعود فقط 0.)

public int GetJumpFramesForNode(int prevNodeId)
{
    int currentNodeId = prevNodeId + 1;

    if (mPath[currentNodeId].y - mPath[prevNodeId].y > 0 && mOnGround)
    {
        int jumpHeight = 1;
        for (int i = currentNodeId; i < mPath.Count; ++i)
        {
            if (mPath[i].y - mPath[prevNodeId].y >= jumpHeight)
                jumpHeight = mPath[i].y - mPath[prevNodeId].y;
            if (mPath[i].y - mPath[prevNodeId].y < jumpHeight || !mMap.IsGround(mPath[i].x, mPath[i].y - 1))
                return GetJumpFrameCount(jumpHeight);
        }
    }
    
    return 0;
}

نحن بحاجة إلى استدعاء هذه الوظيفة في مكانين.

أولها في حالة وصول الحرف إلى موضع x-و y-n للعقدة:

if (reachedX && reachedY)
{
    int prevNodeId = mCurrentNodeId;
    mCurrentNodeId++;

    if (mCurrentNodeId >= mPath.Count)
    {
        mCurrentNodeId = -1;
        ChangeState(BotState.None);
        break;
    }

    if (mOnGround)
        mFramesOfJumping = GetJumpFramesForNode(prevNodeId);
}

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

بعد تحديث الهدف ، نحتاج إلى معالجة كل شيء مرة أخرى ، بحيث يتم حساب إطار الحركة التالي على الفور. لهذا ، سنستخدم أمر goto:

1	goto case BotState.MoveTo;

المكان الثاني الذي نحتاج إليه لحساب القفزة هو وظيفة MoveTo ، لأنه قد يكون السبب أن العقدة الأولى للمسار هي عقدة قفزة:

if (path != null && path.Count > 1)
{
    for (var i = path.Count - 1; i >= 0; --i)
        mPath.Add(path[i]);

    mCurrentNodeId = 1;

    ChangeState(BotState.MoveTo);

    mFramesOfJumping = GetJumpFramesForNode(0);
}

التعامل مع الحركة للوصول إلى X-Position الخاص بالعقدة

الآن دعنا نتعامل مع الحركة للحالة التي لم يصل فيها الحرف بعد إلى موضع x للعقد المستهدف.

لا شيء معقد هنا ؛ إذا كانت الوجهة على اليمين ، نحتاج إلى محاكاة الزر الأيمن للزر. إذا كانت الوجهة إلى اليسار ، فإننا نحتاج إلى محاكاة الضغط على الزر الأيسر. نحتاج فقط إلى نقل الحرف إذا كان الفرق في الموضع أكثر من ثابت cBotMaxPositionError:

else if (!reachedX)
{
    if (currentDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - currentDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

التعامل مع الحركة للوصول إلى موقع Y للعُقدة

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

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

1	else if (!reachedY && mPath.Count > mCurrentNodeId + 1 && !destOnGround)
2	{
3
4	}

ولكن قبل أن نتحرك نحو الهدف التالي ، نحتاج إلى التحقق من أننا لن نقطع الطريق عن طريق القيام بذلك.

تجنب كسر السبل قبل الأوان

خذ بعين الاعتبار السيناريو التالي:

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

لإصلاح هذا ، نحتاج إلى التحقق مما إذا كانت هناك أي عقبات بين الشخصية والوجهة التالية ؛ إذا لم تكن هناك ، فعندئذ نحن أحرار في نقل الشخصية نحوها ؛ إذا كان هناك ، فعلينا الانتظار.

أولاً ، دعنا نرى المربعات التي سنحتاج إلى التحقق منها. إذا كان الهدف التالي هو إلى اليمين من الهدف الحالي ، فسنحتاج إلى التحقق من المربعات الموجودة على الجانب الأيمن ؛ إذا كان الأمر على اليسار ، فسنحتاج إلى التحقق من المربعات إلى اليسار. إذا كانوا في نفس موضع x ، فلا يوجد سبب لإجراء أي تحركات وقائية.

int checkedX = 0;

int tileX, tileY;
mMap.GetMapTileAtPoint(pathPosition, out tileX, out tileY);

if (mPath[mCurrentNodeId + 1].x != mPath[mCurrentNodeId].x)
{
    if (mPath[mCurrentNodeId + 1].x > mPath[mCurrentNodeId].x)
        checkedX = tileX + mWidth;
    else
        checkedX = tileX - 1;
}

كما ترى ، يعتمد إحداثي x للعقدة إلى اليمين على عرض الحرف.

الآن يمكننا التحقق مما إذا كان هناك أي مقاطع بين الحرف وموضع العقدة التالية على المحور y:

1	if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
2	{
3	}

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

وهنا تنفيذ وظيفة.

public bool AnySolidBlockInStripe(int x, int y0, int y1)
{
    int startY, endY;

    if (y0 <= y1)
    {
        startY = y0;
        endY = y1;
    }
    else
    {
        startY = y1;
        endY = y0;
    }

    for (int y = startY; y <= endY; ++y)
    {
        if (GetTile(x, y) == TileType.Block)
            return true;
    }

    return false;
}

كما ترون ، فإن الوظيفة بسيطة للغاية. فإنه يتكرر فقط من خلال البلاط في عمود ، بدءاً من العمود السفلي.

والآن بعد أن علمنا أنه يمكننا الانتقال إلى الوجهة التالية ، لنفعل ذلك:

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;
}

السماح بوت لتخطي العقد

هذا تقريبا - ولكن لا يزال هناك حل واحد للحالة. إليك مثال على ذلك:

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

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

الخطوة الأولى نحو ذلك ستكون فصل حساباتنا السابقة لـ reachedX و reachedY في وظائفهم الخاصة:

public bool ReachedNodeOnXAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.x <= currentDest.x && pathPosition.x >= currentDest.x)
        || (prevDest.x >= currentDest.x && pathPosition.x <= currentDest.x)
        || Mathf.Abs(pathPosition.x - currentDest.x) <= Constants.cBotMaxPositionError;
}

public bool ReachedNodeOnYAxis(Vector2 pathPosition, Vector2 prevDest, Vector2 currentDest)
{
    return (prevDest.y <= currentDest.y && pathPosition.y >= currentDest.y)
        || (prevDest.y >= currentDest.y && pathPosition.y <= currentDest.y)
        || (Mathf.Abs(pathPosition.y - currentDest.y) <= Constants.cBotMaxPositionError);
}

بعد ذلك ، استبدل العمليات الحسابية باستدعاء الدالة في دالة GetContext:

1	reachedX = ReachedNodeOnXAxis(pathPosition, prevDest, currentDest);
2	reachedY = ReachedNodeOnYAxis(pathPosition, prevDest, currentDest);

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

if (checkedX != 0 && !mMap.AnySolidBlockInStripe(checkedX, tileY, mPath[mCurrentNodeId + 1].y))
{
    if (nextDest.x - pathPosition.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoRight] = true;
    else if (pathPosition.x - nextDest.x > Constants.cBotMaxPositionError)
        mInputs[(int)KeyInput.GoLeft] = true;

    if (ReachedNodeOnXAxis(pathPosition, currentDest, nextDest) && ReachedNodeOnYAxis(pathPosition, currentDest, nextDest))
    {
        mCurrentNodeId += 1;
        goto case BotState.MoveTo;
    }
}

هذا كل شيء لحركة شخصية!

التعامل مع Restart الشروط

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

لذا ، دعونا نعلن عن المتغيرات التي ستحسب عدد الإطارات التي تم لصق الحرف بها وعدد الإطارات التي قد تكون عالقة على الأكثر:

1	public int mStuckFrames = 0;
2	public const int cMaxStuckFrames = 20;

نحتاج إلى إعادة ضبط هذا عندما نطلق على وظيفة MoveTo:

public void MoveTo(Vector2i destination)
{
    mStuckFrames = 0;
    /*
    ...
    */
}

وأخيرًا ، في نهاية BotState.MoveTo ، دعنا نتحقق مما إذا كان الحرف عالقًا. هنا ، نحتاج فقط للتحقق مما إذا كان موقعه الحالي مساوياً للوضع القديم. إذا كان الأمر كذلك ، فإننا نحتاج أيضًا إلى زيادة mStuckFrames والتحقق مما إذا كان الحرف عالقاً لإطارات أكثر من cMaxStuckFrames - وإذا كان كذلك ، فإننا نحتاج إلى استدعاء وظيفة MoveTo مع العقدة الأخيرة للمسار الحالي كمعلمة. بالطبع ، إذا كان الوضع مختلفًا ، فعلينا إعادة تعيين mStuckFrames إلى 0:

if (mFramesOfJumping > 0 &&
    (!mOnGround || (reachedX && !destOnGround) || (mOnGround && destOnGround)))
{
    mInputs[(int)KeyInput.Jump] = true;
    if (!mOnGround)
        --mFramesOfJumping;
}

if (mPosition == mOldPosition)
{
    ++mStuckFrames;
    if (mStuckFrames > cMaxStuckFrames)
        MoveTo(mPath[mPath.Count - 1]);
}
else
    mStuckFrames = 0;

الآن يجب على الحرف العثور على مسار بديل إذا لم يكن قادراً على الانتهاء من الأول.

خاتمة

هذا كله من البرنامج التعليمي! لقد كان الكثير من العمل ، ولكن أرجو أن تجد هذه الطريقة مفيدة. إنه ليس حلاً مثاليًا لإيجاد المسارات الخاصة بمنصة platformer ؛ إن التقريب بين منحنى القفزة للشخصية التي تحتاج الخوارزمية إلى إجرائها يكون غالبًا أمرًا صعبًا للغاية ويمكن أن يؤدي إلى سلوك غير صحيح. لا يزال من الممكن تمديد الخوارزمية ، فليس من الصعب جدًا إضافة حواف الاستدارة وغيرها من أنواع مرونة الحركة الممتدة - لكننا قمنا بتغطية ميكانيكا المنصة الأساسية. من الممكن أيضًا تحسين التعليمة البرمجية لجعلها أسرع بالإضافة إلى استخدام ذاكرة أقل؛ هذه التكرار من الخوارزمية ليست مثالية على الإطلاق عندما يتعلق الأمر بتلك الجوانب. كما أنه يعاني من تقريب ضعيف للغاية من المنحنى عند الوقوع بسرعات كبيرة.

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

شكرا للقراءة! تأكد من ترك بعض التعليقات على الطريقة واسمحوا لي أن أعرف ما إذا كنت قد قمت بإجراء أي تحسينات عليه!