دليل جودو خوارزمية البحث عن المسار في بيئة ألعاب ثنائية الأبعاد

سنوضّح في هذا المقال كيفية إعداد خوارزمية للبحث عن المسار للسماح بالتنقل في بيئة قائمة على الشبكة Grid، حيث يوفّر محرّك الألعاب جودو Godot عددًا من الطرق لتحديد المسار، ولكننا سنستخدم في هذا المقال خوارزمية A*‎، التي لها استخدام واسع في العثور على أقصر مسار بين نقطتين، ويمكن استخدامها في أيّ هيكل بيانات قائمٍ على الرسم البياني Graph، وليس في بيئة شبكية فقط.

يُعَد الصنف AStarGrid2D نسخةً متخصصةً من الصنف AStar2D الأعم في جودو، لذا يُعَد إعداده أسرع وأسهل، نظرًا لأنه متخصص للاستخدام مع الشبكة، إذ لسنا مضطرين لإضافة جميع خلايا الشبكة الفردية واتصالاتها يدويًا.

إعداد الشبكة

يُعَد ضبط حجم الخلايا والشبكة أهم خطوة، حيث سنستخدم الحجم ‎(64, 64)‎ في مثالنا، وسنستخدم حجم النافذة لتحديد عدد الخلايا الملائمة للشاشة، ولكن كل شيء سيعمل بالطريقة نفسها بغض النظر عن حجم الخلية.

سنضيف الآن الشيفرة البرمجية التالية إلى العقدة Node2D:

extends Node2D

@export var cell_size = Vector2i(64, 64)

var astar_grid = AStarGrid2D.new()
var grid_size

func _ready():
    initialize_grid()

func initialize_grid():
    grid_size = Vector2i(get_viewport_rect().size) / cell_size
    astar_grid.size = grid_size
    astar_grid.cell_size = cell_size
    astar_grid.offset = cell_size / 2
    astar_grid.update()

نقسم حجمَ الشاشة على حجم الخلية cell_size في هذه الشيفرة البرمجية لحساب حجم الشبكة بالكامل، مما يتيح ضبط الخاصية size الخاصة بالصنف AStarGrid2D.

تُستخدَم خاصية الإزاحة offset عندما نطلب مسارًا بين نقطتين، ويمثّل استخدام cell_size / 2 حساب المسار من مركز كل خلية بدلًا من زواياها، ويجب استدعاء الدالة update()‎ بعد ضبط أو تغيير خاصيات الصنف AStarGrid2D.

رسم الشبكة

سنرسم الشبكة على الشاشة في الشيفرة البرمجية للتوضيح، ولكن قد تكون لدينا عقدة TileMap أو أيّ تمثيل مرئي آخر لعالمنا في تطبيق اللعبة. يمكن رسم الشبكة باستخدام الشيفرة البرمجية التالية:

func _draw():
    draw_grid()

func draw_grid():
    for x in grid_size.x + 1:
        draw_line(Vector2(x * cell_size.x, 0),
            Vector2(x * cell_size.x, grid_size.y * cell_size.y),
            Color.DARK_GRAY, 2.0)
    for y in grid_size.y + 1:
        draw_line(Vector2(0, y * cell_size.y),
            Vector2(grid_size.x * cell_size.x, y * cell_size.y),
            Color.DARK_GRAY, 2.0)

وسنحصل على الشبكة التالية:

رسم المسار

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

var start = Vector2i.ZERO
var end = Vector2i(5, 5)

بعد ذلك نضيف الأسطر التالية في الدالة ‎_draw()‎ لإظهار هذه النقاط:

    draw_rect(Rect2(start * cell_size, cell_size), Color.GREEN_YELLOW)
    draw_rect(Rect2(end * cell_size, cell_size), Color.ORANGE_RED)

يمكننا الآن العثور على المسار بين النقطتين باستخدام التابع get_point_path()‎، ولكننا نحتاج أيضًا إلى إظهاره، لذا من المهم استخدام العقدة Line2D وإضافة إلى المشهد، حيث يمكن الحصول على المسار وإضافة النقاط الناتجة إلى العقدة Line2D كما يلي:

func update_path():
    $Line2D.points = PackedVector2Array(astar_grid.get_point_path(start, end))

وسنحصل على النتيجة التالية:

وكما نلاحظ، لدينا خطًا قطريًا بين النقطتين لأن المسار يستخدم الخطوط القطرية افتراضيًا، ويمكن تعديل ذلك من خلال تغيير الخاصية diagonal_mode باستخدام القيم التالية:

• DIAGONAL_MODE_ALWAYS: القيمة الافتراضية، وتستخدم الخطوط القطرية
• DIAGONAL_MODE_NEVER: تكون الحركة عمودية
• DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE: تسمح هذه القيمة بالخطوط القطرية، ولكنها تمنع المسار من المرور بين العوائق الموضوعة قطريًا
• DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE: تسمح بالخطوط القطرية في المناطق المفتوحة فقط، وليس بالقرب من العوائق

قد يؤدي تعديل هذه الخاصية إلى إعطاء نتائج مختلفة جدًا، لذا تأكد من التجربة بناءً على الإعداد الذي تستخدمه، لذا يجب إضافة ما يلي في الدالة initialize_grid()‎:

astar_grid.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_NEVER

وأصبح لدينا الآن الحركات المتعامدة فقط كما يلي:

إضافة العوائق

يمكننا أيضًا إضافة العوائق إلى الشبكة، حيث لن يتضمن المسار خليةً ما من خلال وضع علامة عليها بوصفها صلبة Solid، ويمكن التبديل بين القيمتين صلبة وغير صلبة للخلية باستخدام الدالة set_point_solid()‎.

سنضيف الشيفرة البرمجية التالية لرسم الجدران (إن وُجدت) من خلال العثور على الخلايا الصلبة وتلوينها:

func fill_walls():
    for x in grid_size.x:
        for y in grid_size.y:
            if astar_grid.is_point_solid(Vector2i(x, y)):
                draw_rect(Rect2(x * cell_size.x, y * cell_size.y, cell_size.x, cell_size.y), Color.DARK_GRAY)

سنستدعي الآن هذه الدالة في الدالة ‎_draw()‎، ويمكن بعد ذلك استخدام الفأرة للنقر على الخلايا وتبديل حالتها كما يلي:

func _input(event):
    if event is InputEventMouseButton:
        # إضافة أو إزالة حائط
        if event.button_index == MOUSE_BUTTON_LEFT and event.pressed:
            var pos = Vector2i(event.position) / cell_size
            if astar_grid.is_in_boundsv(pos):
                astar_grid.set_point_solid(pos, not astar_grid.is_point_solid(pos))
            update_path()
            queue_redraw()

يمكن ملاحظة أننا نستخدم التابع is_in_boundsv()‎ أولًا، مما يمنع حدوث أخطاء إذا نقرنا خارج حدود الشبكة.

يمكننا الآن رؤية تأثير العوائق على المسار كما يلي:

الاختيار الاستكشافي أو التجريبي Heuristic

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

تستخدم المسافة الإقليدية مثلًا نظرية فيثاغورس لتقدير المسار الذي يجب تجربته كما يلي:

بينما تأخذ مسافة مانهاتن في حساباتها المسافة في اتجاهات الشمال/الجنوب أو الشرق/الغرب فقط كما يلي:

وتعطي طريقة التجزيء الاستكشافية Octile Heuristic المسار التالي:

يمكن استخدام الاختيار الاستكشافي باستخدام الخاصية التالية:

astar_grid.default_estimate_heuristic = AStarGrid2D.HEURISTIC_OCTILE

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

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

ترجمة -وبتصرّف- للقسم Pathfinding on a 2D Grid من توثيقات Kidscancode.

اقرأ أيضًا

• المقال السابق: مفهوم Coyote Time وكيفية إعداد منصة متحركة في مشهد اللعبة
• إطلاق المقذوفات وترتيب عرض الكائنات في الألعاب ثنائية الأبعاد
• إنشاء شخصية وتحريكها في ألعاب المنصات ثنائية الأبعاد