حل الـ Maze باستخدام الـ DFS و الـ BFS

المقدمة

بعد أن شرحنا الـ LinkedList والـ Stack والـ Queue والـ Hash Table والـ Graph
اليوم سنتحدث عن تطبيق عملي ومثير للاهتمام وهو حل الـ Maze أو المتاهة

الـ Maze هو مشكلة كلاسيكية في علوم الحاسوب وله تطبيقات عملية كثيرة
مثل الألعاب والروبوتات والذكاء الاصطناعي
وحل الـ Maze يتطلب استخدام مفاهيم هياكل البيانات والخوارزميات التي تعلمناها سابقًا مثل الـ Graph Traversal وخصوصًا خوارزمية الـ Depth First Search و Breadth First Search

لكن السؤال ... كيف يمكننا حل المتاهة برمجيًا ؟
سأجيب عن هذا السؤال بسؤال آخر ... هل تعرف كيف تحل المتاهة بنفسك ؟

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

وهذا بالضبط ما سنقوم ببرمجته اليوم !

ما هو الـ Maze ؟

الـ Maze أو المتاهة هي شبكة من المسارات والجدران
حيث يجب أن تجد طريقًا من نقطة البداية إلى نقطة النهاية
بدون المرور عبر الجدران

في البرمجة، نمثل الـ Maze عادة كـ 2D Array أو Grid
حيث كل خانة تمثل إما:

• 0 أو ' ' (فراغ) = مسار يمكن المرور عليه
• 1 أو # (جدار) = عائق لا يمكن المرور عليه
• S = نقطة البداية (Start)
• E = نقطة النهاية (End)

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

مثال على متاهة بسيطة:

S 0 1 0 0
0 0 1 0 1
1 0 0 0 1
1 1 0 1 0
0 0 0 0 E

في هذه المتاهة:

• S هي نقطة البداية في الزاوية العلوية اليسرى
• E هي نقطة النهاية في الزاوية السفلية اليمنى
• 0 مسارات يمكن المرور عليها
• 1 جدران لا يمكن المرور عليها

الهدف: إيجاد مسار من S إلى E بدون المرور عبر الجدران

تمثيل الـ Maze كـ 2D Array

كما ذكرنا فنحن نستطيع استخدام 2D Array لتمثيل الـ Maze
أو يمكننا أيضًا تمثيله كـ Graph

لكن سنركز في هذه المقالة على تمثيله كـ 2D Array ونحله باستخدام خوارزمية الـ DFS أو BFS
لأن هذا هو الأكثر شيوعًا في التطبيقات العملية

الآن دعنا نبدأ بتمثيل المتاهة كـ 2D Array

S 0 1
0 0 1
1 0 E

لدينا الآن متاهة بسيطة مكونة من 3 صفوف و 3 أعمدة
دعنا نبدأ بتمثيلتها كـ 2D Array

const maze: string[][] = [
  ['S', '0', '1'],
  ['0', '0', '1'],
  ['1', '0', 'E'],
];

الآن مثلنا المتاهة في أراي ثنائية الأبعاد
ولدينا S كنقطة بداية ومكانها في maze[0][0]
وE كنقطة نهاية ومكانها في maze[2][2]

نحتاج الآن إلى كود يستطيع حل هذه المتاهة واعطاءنا المسار من S إلى E
والأمر يتطلب استخدام خوارزمية DFS أو BFS وهو ما شرحناه في مقالة بداية دخولك في عالم الجراف | Graph Theory
وبالطبع يوجد طرق أخرى لحل المتاهة مثل A* أو Dijkstra's Algorithm لكن هنا سنركز على DFS و BFS

لكننا هنا بدلًا من أن نستخدم الـ DFS أو الـ BFS على الـ Graph
هنا سنستخدمها على الـ 2D Array الذي تمثل المتاهة
والأمر ليس صعبًا كما يبدو وهو يطبق نفس المفاهيم التي تعلمناها سابقًا
لكن بتطبيق مختلف قليلًا

لذلك من المهم أن تفهم دائمًا المفاهيم والمبادئ الأساسية والتطبيقات مجرد تفاصيل أو طرق مختلفة لتطبيق هذه المبادئ

كيفية التحرك في المتاهة برمجيًا

حسنًا، قبل أن نبدأ في حل المتاهة
علينا أن نعرف كيف نتحرك في المتاهة بشكل برمجي
المتاهة التي لدينا هي 2D Array وكل خانة فيها لها index خاص بها
لذلك يمكننا التحرك في المتاهة باستخدام index الصف والعمود

فمثلاً، إذا أردنا التحرك من خانة S التى هي maze[0][0] إلى اليمين أي إلى maze[0][1] فنحن سنضيف 1 إلى index العمود
وإذا أردنا الانتقال إلى اليسار نطرح 1 من index العمود
ولو أردنا الانتقال إلى الأسفل نضيف 1 إلى index الصف
إذا أردنا الانتقال إلى الأعلى نطرح 1 من index الصف
وهكذا

بالتالي نسطيع إنشاء متغير أخر يمثل الاتجاهات الأربعة التي يمكننا التحرك فيها

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

هكذا قمنا متغير يدعى directions يحتوي على الاتجاهات الأربعة التي يمكننا التحرك فيها
كل index فيه يمثل اتجاهًا معينًا ويحتوي على row و col يمثلان التغير في الصف والعمود عند التحرك في هذا الاتجاه
هكذا directions[0] يمثل التحرك لليمين
و directions[1] يمثل التحرك لليسار
و directions[2] يمثل التحرك لأعلى
و directions[3] يمثل التحرك لأسفل

وطريقة التحرك في المتاهة ستكون كالتالي:

const currentPosition = { row: 0, col: 0 };

// التحرك لليمين
currentPosition.row += directions[0].row; // لا يتغير الصف
currentPosition.col += directions[0].col; // يزيد العمود بواحد
// currentPosition = { row: 0, col: 1 };

// التحرك للأسفل
currentPosition.row += directions[3].row; // يزيد الصف بواحد
currentPosition.col += directions[3].col; // لا يتغير العمود
// currentPosition = { row: 1, col: 1 };

أو يمكننا استخدام الـ enum لتسهيل الأمر أكثر:

enum Direction {
  Right = 'Right',
  Left = 'Left',
  Up = 'Up',
  Down = 'Down',
}

const directions = {
  [Direction.Right]: { row: 0, col: 1 },
  [Direction.Left]: { row: 0, col: -1 },
  [Direction.Up]: { row: -1, col: 0 },
  [Direction.Down]: { row: 1, col: 0 },
};

هكذا قمنا بإنشاء enum يمثل الاتجاهات الأربعة واستخدمناها كـ key في المتغير directions
هكذا directions[Direction.Right] يمثل التحرك لليمين
و directions[Direction.Left] يمثل التحرك لليسار
و directions[Direction.Up] يمثل التحرك لأعلى
و directions[Direction.Down] يمثل التحرك لأسفل

وطريقة التحرك في المتاهة ستكون كالتالي:

const currentPosition = { row: 0, col: 0 };

// التحرك لليمين
currentPosition.row += directions[Direction.Right].row; // لا يتغير الصف
currentPosition.col += directions[Direction.Right].col; // يزيد العمود بواحد
// currentPosition = { row: 0, col: 1 };

// التحرك للأسفل
currentPosition.row += directions[Direction.Down].row; // يزيد الصف بواحد
currentPosition.col += directions[Direction.Down].col; // لا يتغير العمود
// currentPosition = { row: 1, col: 1 };

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

حل الـ Maze باستخدام BFS

الآن بعد أن فهمنا كيفية التحرك في المتاهة
دعنا نبدأ في حل المتاهة باستخدام الـ BFS

أولًا لو أردت أن نفهم كيف تعمل خوارزمية الـ BFS بشكل عام وتطبيقها على الـ Graph فيمكنك مراجعة مقالة بداية دخولك في عالم الجراف | Graph Theory هو خوارزمية بحث تعتمد على مفهوم الـ Queue
والذي شرحناه في مقالة بناء الـ Queue عن طريق الـ LinkedList

الـ BFS أو Breadth First Search هي خوارزمية بحث تعتمد على استكشاف كل الجيران في المستوى الحالي قبل الانتقال إلى المستوى التالي
بمعنى لو أنا أقف في الخانة [0][0] في المتاهة، سأبحث عن كل الخانات المجاورة لها (يمين، يسار، أعلى، أسفل)
فأول مستوى من الخانات بالنسبة لي حاليًا هي [0][1] و [1][0] و [0][-1] و [-1][0]
وثاني بالنسبة لي هي الخانات المجاورة لخانات المستوى الأول وهكذا

بالتالي نحن في الـ BFS عندما نقف في الخانة [0][0] نبحث عن كل الخانات المجاورة لها أولًا
وهي [0][1] و [1][0] و [0][-1] و [-1][0] ولا نستطيع البحث في الخانات المجاورة لتلك الخانات مثل [0][2] و [2][0] و [0][-2] و [-2][0]
إلا بعد أن أنتهي من البحث في كل الخانات المجاورة لي في المستوى الحالي

لنبدأ في حل المتاهة باستخدام الـ BFS ونرى كيف يمكننا تطبيق ذلك برمجيًا بشكل مبسط لكي نفهم الفكرة

const maze: string[][] = [
  ['S', '0', '1'],
  ['0', '0', '1'],
  ['1', '0', 'E'],
];

الآن لدينا متاهة بسيطة مكونة من 3 صفوف و 3 أعمدة
نقطة البداية هي S في الخانة [0][0] ونقطة النهاية هي E في الخانة [2][2]

الآن دعنا نبدأ في حل المتاهة باستخدام الـ BFS
بمجرد النظر إلى الخانة [0][0]، سنبحث عن جميع الخانات المجاورة لها (يمين، يسار، أعلى، أسفل)
وهم كما ذكرنا سابقًا:

• [0][1] تحرك الخانة لليمين عندما نجمعها مع الخانة الحالية، بحيث نجمع 1 إلى col الحالي
• [0][-1] تحرك الخانة لليسار عندما نجمعها مع الخانة الحالية، بحيث نجمع -1 إلى col الحالي
• [1][0] تحرك الخانة لأسفل عندما نجمعها مع الخانة الحالية، بحيث نجمع 1 إلى row الحالي
• [-1][0] تحرك الخانة لأعلى عندما نجمعها مع الخانة الحالية، بحيث نجمع -1 إلى row الحالي

ثم نظيفهم في الـ Queue للبحث فيهم لاحقًا بترتيب دخولهم
ولاحظ أن الـ Queue بسبب فهو سيبحث في الخانات بالترتيب الذي أضفناها به
بالتالي نستطيع اضافة خانات المستوى الأول في الـ Queue ثم خانات المستوى الثاني وهكذا
والـ Queue سيضمن لنا أننا نبحث في الخانات بالترتيب الصحيح
لأن الـ Queue يعتمد على مفهوم الـ FIFO (First In First Out) بالتالي ما يدخل أولًا يخرج أولًا وهذا ما نحتاجه في الـ BFS
لأننا سندخل خانات المستوى الأول في الـ Queue أولًا ثم نبحث فيهم ثم ندخل خانات المستوى الثاني وهكذا

والكود سيكون كالتالي:

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

const currentPosition = { row: 0, col: 0 }; // نقطة البداية
const queue: Queue<{ row: number; col: number }> = new Queue();
queue.push(currentPosition); // نضيف نقطة البداية

// الاتجاهات الأربعة التي يمكننا التحرك فيها
for (const direction of directions) {
  const newRow = currentPosition.row + direction.row;
  const newCol = currentPosition.col + direction.col;
  queue.push({ row: newRow, col: newCol });
}

تذكر أن directions هو المتغير الذي يحتوي على الاتجاهات الأربعة التي يمكننا التحرك فيها
فهنا نحن نقف في الخانة [0][0] ونبحث عن كل الخانات المجاورة لها
لذا قمنا بعمل حلقة for على directions
ثم قمنا بحساب newRow و newCol لكل اتجاه
ثم أضفنا الخانة الجديدة إلى الـ Queue

لكن ستلاحظ أن بعض هذه الخانات قد تكون خارج حدود المتاهة أو عبارة عن جدران أو حواجز
مثل الخانة [0][-1] (يسار) و [-1][0] (أعلى) فهما خارج حدود المتاهة
لذلك، يجب علينا التحقق من صحة كل خانة قبل إضافتها إلى قائمة البحث

لذلك سنقوم بإنشاء دالة للتحقق من صحة الخانة:

function isValidMove(maze: string[][], row: number, col: number): boolean {
  // التحقق من أن الخانة داخل حدود المتاهة
  if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length) {
    return false;
  }

  // التحقق من أن الخانة ليست جدارًا
  if (maze[row][col] === '1') {
    return false;
  }

  return true;
}

هذه الدالة تتحقق من هل الخانة داخل حدود المتاهة و هل هي عبارة عن جدار أم لا

الآن دعنا نستخدم هذه الدالة في الكود السابق للتحقق من صحة الخانات قبل إضافتها إلى الـ Queue:

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

const currentPosition = { row: 0, col: 0 }; // نقطة البداية
const queue: Queue<{ row: number; col: number }> = new Queue();
queue.push(currentPosition); // نضيف نقطة البداية

// الاتجاهات الأربعة التي يمكننا التحرك فيها
for (const direction of directions) {
  const newRow = currentPosition.row + direction.row;
  const newCol = currentPosition.col + direction.col;

  // التحقق من صحة الخانة قبل إضافتها
  if (isValidMove(maze, newRow, newCol)) {
    queue.push({ row: newRow, col: newCol });
  }
}

الآن نحن نتحقق من صحة كل خانة قبل إضافتها إلى الـ Queue
وبهذا الشكل نكون قد بدأنا في حل المتاهة باستخدام الـ BFS

ستلاحظ أن هذه الخطوات هي مجرد بداية
لأننا لم نصل بعد إلى نقطة النهاية E، نحن فقط أضفنا الخانات المجاورة لنقطة البداية إلى الـ Queue
الآن بعد ما أضفنا الخانات المجاورة لنقطة البداية إلى الـ Queue
نحتاج إلى التوسيع في البحث عن الخانات المجاورة لكل خانة أضفناها في الـ Queue بالتالي نبحث في خانات المستوى الأول ثم المستوى الثاني وهكذا

لذلك سنقوم بعمل while loop يستمر في التوسع واضافة الخانات في الـ Queue

while (queue.length > 0) {
  const current = queue.pop();

  // إذا وصلنا إلى نقطة النهاية
  if (maze[current.row][current.col] === 'E') {
    console.log('تم إيجاد المسار!');
    break;
  }

  // الاتجاهات الأربعة التي يمكننا التحرك فيها
  for (const direction of directions) {
    const newRow = current.row + direction.row;
    const newCol = current.col + direction.col;

    // التحقق من صحة الخانة قبل إضافتها
    if (isValidMove(maze, newRow, newCol)) {
      queue.push({ row: newRow, col: newCol });
    }
  }
}

الآن لدينا while تستمر في البحث طالما أن هناك خانات في الـ Queue
إذا وجدنا نقطة النهاية E، نطبع رسالة تفيد بأننا وجدنا المسار
وإذا لم نجد نقطة النهاية نستمر في البحث عن الخانات المجاورة لكل خانة في الـ Queue

لكن هنا يجب أن نأخذ في الاعتبار أننا لا نريد زيارة نفس الخانة أكثر من مرة
لذلك سنقوم بإنشاء أراي أخرى سنسميها visited لتتبع الخانات التي زرناها بالفعل
لكي لا نضيفها مرة أخرى إلى الـ Queue ونقع في مشكلة infinite loop

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

// الأراي التي تتبع الخانات التي زرناها
const visited: boolean[][] = Array.from({ length: maze.length }, () =>
  Array(maze[0].length).fill(false)
);

const currentPosition = { row: 0, col: 0 }; // نقطة البداية
const queue: Queue<{ row: number; col: number }> = new Queue();
queue.push(currentPosition); // نضيف نقطة البداية

// نعلم أن نقطة البداية قد زارناها بالفعل
visited[currentPosition.row][currentPosition.col] = true;

while (queue.length > 0) {
  const current = queue.pop();

  // إذا وصلنا إلى نقطة النهاية
  if (maze[current.row][current.col] === 'E') {
    console.log('تم إيجاد المسار!');
    break;
  }

  // الاتجاهات الأربعة التي يمكننا التحرك فيها
  for (const direction of directions) {
    const newRow = current.row + direction.row;
    const newCol = current.col + direction.col;

    // التحقق من صحة الخانة قبل إضافتها
    if (isValidMove(maze, newRow, newCol) && !visited[newRow][newCol]) {
      queue.push({ row: newRow, col: newCol });
      visited[newRow][newCol] = true; // نعلم أننا زرنا هذه الخانة
    }
  }
}

الآن نحن نتحقق من صحة الخانة قبل إضافتها إلى الـ Queue وأيضًا نتأكد من أننا لم نزورها من قبل

لقد انتهينا من حل المتاهة باستخدام الـ BFS
لقد استخدما خوارزمية BFS لحل المتاهة وإذا نظرت إلى الكود ستجده مشابهًا جدًا لما كتبناه سابقًا في مقالة بداية دخولك في عالم الجراف | Graph Theory
لكننا هنا طبقناها على 2D Array يمثل المتاهة

تتبع خوارزمية الـ BFS خطوة بخطوة

ما رأيك في تتبع الخوارزمية خطوة بخطوة ؟ ونرى كيف تعمل ؟

const maze: string[][] = [
  ['S', '0', '1'],
  ['0', '0', '1'],
  ['1', '0', 'E'],
];

لنطبق الكود الذي كتبناه سابقًا خطوة بخطوة على هذه المتاهة البسيطة
أريد أن تحضر ورقة وقلب وتتبع معي الخطوات التالية خطوة بخطوة

ويمكنك تخيل المتاهة التي لدينا كالتالي:

     0    1    2
 0 ['S', '0', '1'],
 1 ['0', '0', '1'],
 2 ['1', '0', 'E'],

بحيث تعرف الـ index لكل خانة في المتاهة

أولًا، سنبدأ من نقطة البداية S في الخانة [0][0]
لذا سنضعها في الـ Queue ونجعلها visited:

const currentPosition = { row: 0, col: 0 }; // نقطة البداية
const queue: Queue<{ row: number; col: number }> = new Queue();
queue.push(currentPosition); // نضيف نقطة البداية

// نعلم أن نقطة البداية قد زارناها بالفعل
visited[currentPosition.row][currentPosition.col] = true;

الآن لدينا queue تحتوي على { row: 0, col: 0 } والـ visited تحتوي على true في الخانة [0][0] مما يعني أننا زرناها بالفعل

Queue: [{ row: 0, col: 0 }]
Visited: [
  [true, false, false],
  [false, false, false],
  [false, false, false]
]

هنا من أجل التوضيح سنتخيل قيم الـ Queue و visited
ستلاحظ أن Queue تحتوي على الخانة الحالية التي نحن فيها وهي { row: 0, col: 0 }
والـ visited تحتوي على true في الخانة [0][0] مما يعني أننا زرناها بالفعل

الآن دعنا ندخل في حلقة while التي تستمر طالما أن هناك خانات في الـ Queue:

while (queue.length > 0) {
  const current = queue.pop();

  // إذا وصلنا إلى نقطة النهاية
  if (maze[current.row][current.col] === 'E') {
    console.log('تم إيجاد المسار!');
    break;
  }

  // ...
}

هنا الـ while ستستمر طالما أن هناك خانات في الـ Queue وبما أننا لدينا { row: 0, col: 0 } في الـ Queue
فسندخل في اللفة الأولى من الـ while ونأخذ الخانة الحالية من الـ Queue:

const current = queue.pop(); // current = { row: 0, col: 0 }

الآن لدينا current تحتوي على { row: 0, col: 0 } الخطوة التالية هي التحقق إذا وصلنا إلى نقطة النهاية E:

if (maze[current.row][current.col] === 'E') {
  console.log('تم إيجاد المسار!');
  break;
}

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

الآن دعنا نبحث عن الخانات المجاورة للخانة الحالية [0][0] باستخدام الاتجاهات الأربعة:

// الاتجاهات الأربعة التي يمكننا التحرك فيها
for (const direction of directions) {
  const newRow = current.row + direction.row;
  const newCol = current.col + direction.col;

  // التحقق من صحة الخانة قبل إضافتها
  if (isValidMove(maze, newRow, newCol) && !visited[newRow][newCol]) {
    queue.push({ row: newRow, col: newCol });
    visited[newRow][newCol] = true; // نعلم أننا زرنا هذه الخانة
  }
}

حسنًا نحن نعرف أن directions تحتوي على الاتجاهات الأربعة التي يمكننا التحرك فيها

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

بالتالي الـ for of ستقوم بالبحث في كل اتجاه من الاتجاهات الأربعة
كل لفة من الـ for ستقوم بحساب newRow و newCol للخانة الجديدة التي سنبحث فيها
أول لفة ستحسب الخانة التي على اليمين من الخانة الحالية [0][0] و ستكون [0][1]
وثاني لفة ستحسب الخانة التي على اليسار من الخانة الحالية [0][0] و ستكون [0][-1]
وثالث لفة ستحسب الخانة التي أعلى من الخانة الحالية [0][0] و ستكون [-1][0]
ورابع لفة ستحسب الخانة التي أسفل من الخانة الحالية [0][0] و ستكون [1][0]

const newRow = current.row + direction.row; // يحسب الصف الجديد
const newCol = current.col + direction.col; // يحسب العمود الجديد

ومع كل لفة من الـ for سنقوم بالتحقق من صحة الخانة الجديدة باستخدام الدالة isValidMove:

if (isValidMove(maze, newRow, newCol) && !visited[newRow][newCol]) {
  queue.push({ row: newRow, col: newCol });
  visited[newRow][newCol] = true; // نعلم أننا زرنا هذه الخانة
}

وأيضًا سنتأكد من أننا لم نزور هذه الخانة من قبل باستخدام visited
هنا الخانات الجديدة التي سنبحث فيها هي: [0][1], [0][-1], [-1][0], [1][0]
ودالة isValidMove ستتحقق من صحة كل خانة جديدة قبل إضافتها إلى الـ Queue
بالتالي سيتم استبعاد الخانات التي خارج حدود المتاهة أو التي عبارة عن جدران وهي [0][-1] و [-1][0]
وسيتبقى لدينا الخانة [0][1] و [1][0] وهي خانات لم نزرها من قبل
لذا سنقوم بإضافتها إلى الـ Queue لمتابعة البحث ونضع علامة true في visited لتتبع أننا زرناها بالفعل

Queue: [{ row: 0, col: 1 }, { row: 1, col: 0 }]
Visited: [
  [true, true, false],
  [true, false, false],
  [false, false, false]
]

حسنا الآن لدينا Queue تحتوي على الخانات المجاورة للخانة الحالية [0][0] وهي { row: 0, col: 1 } و { row: 1, col: 0 }
والـ visited تحتوي على true في الخانات التي زرناها بالفعل وهي [0][0], [0][1], و [1][0]

ماذا سيحدث الآن ؟ سيتم إعادة تنفيذ الـ while مرة أخرى طالما أن هناك خانات في الـ Queue
ثم سنأخذ الخانة التي عليها الدور من الـ Queue وهي { row: 0, col: 1 }
ثم سنتحقق إذا وصلنا إلى نقطة النهاية E أم لا
ثم سنبحث عن الخانات المجاورة للخانة الحالية [0][1] وستكون الخانات المجاورة هي [0][2] (يمين) و [0][0] (يسار) و [-1][1] (أعلى) و [1][1] (أسفل)
ثم نممرهم على دالة isValidMove للتحقق من صحتهم وعلى visited للتأكد من أننا لم نزورهم من قبل
وبالتالي سيتم استبعاد الخانة [0][2] لأنها جدار، والخانة [0][0] لأننا زرناها من قبل، والخانة [-1][1] لأنها خارج حدود المتاهة وبالتالي ستتبقى لدينا الخانة [1][1] وهي خانة لم نزورها من قبل وسنضيفها إلى الـ Queue
ونضع علامة true في visited لتتبع أننا زرناها بالفعل

Queue: [{ row: 1, col: 0 }, { row: 1, col: 1 }]
Visited: [
  [true, true, false],
  [true, true, false],
  [false, false, false]
]

ويمكنك تذكر شكل المتاهة التي نعمل عليها:

const maze: string[][] = [
  //        0    1    2
  /* 0 */ ['S', '0', '1'],
  /* 1 */ ['0', '0', '1'],
  /* 2 */ ['1', '0', 'E'],
];

الآن لدينا Queue تحتوي على الخانة { row: 1, col: 0 } والخانة { row: 1, col: 1 } والـ visited تحتوي على true في الخانات التي زرناها بالفعل وهي [0][0], [0][1], [1][0], و [1][1]
الآن دعنا ندخل في حلقة while مرة أخرى طالما أن هناك خانات في الـ Queue
وسنأخذ الخانة التي عليها الدور من الـ Queue وهي { row: 1, col: 0 }
ثم سنتحقق إذا وصلنا إلى نقطة النهاية E أم لا
ثم سنبحث عن الخانات المجاورة للخانة الحالية [1][0] وهى [1][1] (يمين) و [1][-1] (يسار) و [0][0] (أعلى) و [2][0] (أسفل)
ثم نممرهم على دالة isValidMove للتحقق من صحتهم وعلى visited للتأكد من أننا لم نزورهم من قبل
وبالتالي سيتم استبعاد الخانة [1][1]و [0][0] لأننا زرناهم من قبل، والخانة [1][-1] لأنها خارج حدود المتاهة، والخانة [2][0] لأنها جدار
وبالتالي لن يتبقى لدينا أي خانات جديدة لنضيفها إلى الـ Queue

Queue: [{ row: 1, col: 1 }]
Visited: [
  [true, true, false],
  [true, true, false],
  [false, false, false]
]

الآن لدينا Queue تحتوي على الخانة { row: 1, col: 1 }
والـ visited تحتوي على true في الخانات التي زرناها بالفعل وهي [0][0], [0][1], [1][0], و [1][1]
الآن دعنا ندخل في حلقة while مرة أخرى طالما أن هناك خانات في الـ Queue
وسنأخذ الخانة التي عليها الدور من الـ Queue وهي { row: 1, col: 1 }
ثم سنتحقق إذا وصلنا إلى نقطة النهاية E أم لا
ثم سنبحث عن الخانات المجاورة للخانة الحالية [1][1] وهى [1][2] (يمين) و [1][0] (يسار) و [0][1] (أعلى) و [2][1] (أسفل)
ثم نممرهم على دالة isValidMove للتحقق من صحتهم وعلى visited للتأكد من أننا لم نزورهم من قبل وبالتالي سيتم استبعاد الخانة [1][2] لأنها جدار، والخانة [1][0] و [0][1]
سيتبقى لدينا الخانة [2][1] وهي خانة لم نزورها من قبل ولذالك سنضيفها إلى الـ Queue
ونضع علامة true في visited لتتبع أننا زرناها بالفعل

Queue: [{ row: 2, col: 1 }]
Visited: [
  [true, true, false],
  [true, true, false],
  [false, true, false]
]

الآن لدينا Queue تحتوي على الخانة { row: 2, col: 1 }
والـ visited تحتوي على true في الخانات التي زرناها بالفعل وهي [0][0], [0][1], [1][0], [1][1], و [2][1]
الآن دعنا ندخل في حلقة while مرة أخرى طالما أن هناك خانات في الـ Queue
وسنأخذ الخانة التي عليها الدور من الـ Queue وهي { row: 2, col: 1 }
ثم سنتحقق إذا وصلنا إلى نقطة النهاية E أم لا
ثم سنبحث عن الخانات المجاورة للخانة الحالية [2][1] وهى [2][2] (يمين) و [2][0] (يسار) و [1][1] (أعلى) و [3][1] (أسفل)
ثم نممرهم على دالة isValidMove للتحقق من صحتهم وعلى visited للتأكد من أننا لم نزورهم من قبل
وبالتالي سيتم استبعاد الخانة [2][0] لأنها جدار، والخانة [1][1] لأننا زرناها من قبل، والخانة [3][1] لأنها خارج حدود المتاهة
وبالتالي ستتبقى لدينا الخانة [2][2] وهي خانة لم نزورها من قبل وسنضيفها إلى الـ Queue
ونضع علامة true في visited لتتبع أننا زرناها بالفعل

Queue: [{ row: 2, col: 2 }]
Visited: [
  [true, true, false],
  [true, true, false],
  [false, true, true]
]

الآن لدينا Queue تحتوي على الخانة { row: 2, col: 2 }
والـ visited تحتوي على true في الخانات التي زرناها بالفعل وهي [0][0], [0][1], [1][0], [1][1], [2][1], و [2][2]
الآن دعنا ندخل في حلقة while مرة أخرى طالما أن هناك خانات في الـ Queue
وسنأخذ الخانة التي عليها الدور من الـ Queue وهي { row: 2, col: 2 }
ثم سنتحقق إذا وصلنا إلى نقطة النهاية E أم لا
و ... لقد وصلنا إلى نقطة النهاية E في الخانة [2][2]
لذا سنقوم بطباعة رسالة تفيد بأننا وصلنا إلى نقطة النهاية وننهي البحث

حل المتاهة باستخدام DFS

الآن بعد أن فهمنا كيفية حل المتاهة باستخدام الـ BFS
دعنا نرى كيف يمكننا حل المتاهة باستخدام الـ DFS أو Depth First Search

الـ DFS على عكس الـ BFS يعتمد على مفهوم الـ Stack
وهو يختلف قليلاً في طريقة البحث عن الـ BFS
حيث أننا في الـ BFS كنا نبحث في كل الخانات المجاورة للخانة الحالية أولاً
ثم ننتقل إلى المستوى التالي من الخانات المجاورة
بينما في الـ DFS نحن نبحث في العمق أولاً بمعنى أننا نبحث في خانة الحالية ثم ننتقل مباشرة لأول خانة مجاورة لها ثم نمسك الخانة الجديدة ونبحث في أول خانة مجاورة لها وهكذا
وهو على عكس الـ BFS الذي يبحث في كل الخانات المجاورة للخانة الحالية أولاً ثم بعدها ينتقل إلى المستوى التالي من الخانات المجاورة

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

لقد شرحنا الـ DFS بشكل مفصل في مقالة بداية دخولك في عالم الجراف | Graph Theory

لنرى نبذة عن كيفية حل المتاهة باستخدام الـ DFS

     0    1    2
 0 ['S', '0', '1'],
 1 ['0', '0', '1'],
 2 ['1', '0', 'E'],

لنفترض أننا نقف في الخانة [0][0] في المتاهة ونريد أن نطبق خوارزمية الـ DFS
أول شيء سيفعله هو البحث في الخانة المجاورة لها لذا سنبحث في الخانة [0][1] (يمين) ثم يقف ويمسك الخانة [0][1] ويبحث في أول خانة متاحة مجاورة لها وهي [0][2] (يمين) ثم يقف ويمسك الخانة [0][2] ويبحث في أول خانة متاحة مجاورة لها وهي [0][3] (يمين) وهكذا حتى يصل إلى طريق مسدود أو يصل إلى نقطة النهاية E
لنفترض أننا وصلنا إلى [0][2] وهي جدار، في هذه الحالة سيقوم الـ DFS بالرجوع للخلف إلى الخانة السابقة
بالتالي سيرجع إلى [0][1] ثم ينتقل إلى إتجاه آخر وهو [1][1] (أسفل) ثم يمسك الخانة [1][1] ويبحث في أول خانة متاحة مجاورة لها وهي [1][2] (يمين) ثم يقف ويمسك الخانة [1][2] ويبحث في أول خانة متاحة مجاورة لها لكنه سيجد أنها جدار
لذا سيقوم بالرجوع للخلف إلى الخانة السابقة وهي [1][1] ثم ينتقل إلى إتجاه آخر وهو [2][1] (أسفل) ثم يمسك الخانة [2][1] ويبحث في أول خانة متاحة مجاورة لها وهي [2][2] (يمين) ثم يقف ويمسك الخانة [2][2] ويجد أنها نقطة النهاية E

هكذا نكون قد وجدنا نقطة النهاية E باستخدام خوارزمية الـ DFS

طبعًا، هذا مجرد شرح مبسط لفهم الفكرة وحتى الكود حين تراه ستجده هو نفسه الكودالخاص بالـ BFS لكننا سنستخدم Stack بدلاً من Queue

const directions = [
  { row: 0, col: 1 }, // لليمين
  { row: 0, col: -1 }, // لليسار
  { row: -1, col: 0 }, // لأعلى
  { row: 1, col: 0 }, // لأسفل
];

// الأراي التي تتبع الخانات التي زرناها
const visited: boolean[][] = Array.from({ length: maze.length }, () =>
  Array(maze[0].length).fill(false)
);

const currentPosition = { row: 0, col: 0 }; // نقطة البداية
const stack: Stack<{ row: number; col: number }> = new Stack();
stack.push(currentPosition); // نضيف نقطة البداية

// نعلم أن نقطة البداية قد زارناها بالفعل
visited[currentPosition.row][currentPosition.col] = true;

while (stack.length > 0) {
  const current = stack.pop();

  // إذا وصلنا إلى نقطة النهاية
  if (maze[current.row][current.col] === 'E') {
    console.log('تم إيجاد المسار!');
    break;
  }

  // الاتجاهات الأربعة التي يمكننا التحرك فيها
  for (const direction of directions) {
    const newRow = current.row + direction.row;
    const newCol = current.col + direction.col;

    // التحقق من صحة الخانة قبل إضافتها
    if (isValidMove(maze, newRow, newCol) && !visited[newRow][newCol]) {
      stack.push({ row: newRow, col: newCol });
      visited[newRow][newCol] = true; // نعلم أننا زرنا هذه الخانة
    }
  }
}

حسنا، الآن لدينا خوارزمية DFS لحل المتاهة
وهي مشابهة جدًا للـ BFS لكننا استخدمنا Stack بدلاً من Queue

ولا داعي لأن اشرح الكود مرة أخرى لأنه مشابه جدًا لما كتبناه في الـ BFS لكن مع اختلاف وهو الاختلاف ما بين Stack و Queue
وهو أن Stack يعتمد على مفهوم الـ LIFO (Last In First Out) وهو يعني أن العنصر الذي يدخل آخرًا هو الذي يخرج أولًا
وهو ما يجعل الـ DFS يبحث في العمق أولًا لأنه أخر شيء يدخل في الـ Stack هى الخانة التي سيبحث فيها أولًا

عرض المسار في المتاهة

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

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

أولًا لنضيف أراي تسمى previous لتتبع الخانة الأصل لكل خانة في المسار

// أراي لتتبع الخانة السابقة لكل خانة
const previous: ({ row: number; col: number } | null)[][] = Array.from(
  { length: maze.length },
  () => Array(maze[0].length).fill(null)
);

هذه الأراي سيساعدنا في تتبع المسار من نقطة البداية إلى نقطة النهاية

الآن دعنا نعدل كود الـ BFS لتتبع المسار:

// الأراي التي تتبع الخانات التي زرناها
const visited: boolean[][] = Array.from({ length: maze.length }, () =>
  Array(maze[0].length).fill(false)
);

// أراي لتتبع الخانة السابقة لكل خانة
const previous: ({ row: number; col: number } | null)[][] = Array.from(
  { length: maze.length },
  () => Array(maze[0].length).fill(null)
);

const currentPosition = { row: 0, col: 0 }; // نقطة البداية

const queue: Queue<{ row: number; col: number }> = new Queue();
queue.push(currentPosition);
visited[currentPosition.row][currentPosition.col] = true;

while (queue.length > 0) {
  const current = queue.pop();

  // إذا وصلنا إلى نقطة النهاية
  if (maze[current.row][current.col] === 'E') {
    console.log('تم إيجاد المسار!');
    break;
  }

  // البحث في الاتجاهات الأربعة
  for (const direction of directions) {
    const newRow = current.row + direction.row;
    const newCol = current.col + direction.col;

    if (isValidMove(maze, newRow, newCol) && !visited[newRow][newCol]) {
      queue.push({ row: newRow, col: newCol });
      visited[newRow][newCol] = true;
      previous[newRow][newCol] = current; // تتبع الخانة السابقة
    }
  }
}

هنا نفس الكود السابق لكننا أضفنا previous لتتبع الخانة السابقة لكل خانة بعد إضافتها إلى الـ Queue

previous[newRow][newCol] = current; // تتبع الخانة السابقة

ميزة هذه الخطوة هي أننا الآن نستطيع تتبع المسار من نقطة النهاية إلى نقطة البداية باستخدام الأراي previous
شكل الـ previous سيكون كالتالي:

              0                   1                   2
 0 [        null,        { row: 0, col: 0 },        null        ],
 1 [ { row: 0, col: 0 }, { row: 1, col: 0 },        null        ],
 2 [        null,        { row: 1, col: 1 }, { row: 2, col: 1 } ],

الآن بالنظر على ترى الخانة [2][2] (نقطة النهاية E) الخانة السابقة لها هي [2][1]
والخانة السابقة للخانة [2][1] هي [1][1]
والخانة السابقة للخانة [1][1] هي [1][0]
والخانة السابقة للخانة [1][0] هي [0][0] (نقطة البداية S)

لذا يمكننا تتبع المسار من نقطة النهاية إلى نقطة البداية باستخدام الأراي previous
ويمكنك عمل أراي بسيطة لتخزين المسار

const path: { row: number; col: number }[] = [];
let endPosition = { row: 2, col: 2 }; // نقطة النهاية
while (endPosition) {
  path.push(endPosition);
  endPosition = previous[endPosition.row][endPosition.col];
}

// عكس المسار لأننا تتبعناه من النهاية إلى البداية
path.reverse();

الآن لدينا path تحتوي على المسار من نقطة البداية إلى نقطة النهاية
وبما أننا استخدمنا BFS، فإن هذا المسار هو أقصر مسار من نقطة البداية إلى نقطة النهاية

دعنا نعرض المسار في المتاهة باستخدام دالة:

{ row: 0, col: 0 } -> { row: 0, col: 1 } -> { row: 1, col: 1 } -> { row: 2, col: 1 } -> { row: 2, col: 2 }

الخاتمة

وهكذا نكون قد تعلمنا كيفية حل المتاهة باستخدام خوارزميات البحث المختلفة مثل BFS و DFS
وتمثيل المتاهة باستخدام 2D Array
وأيضًا كيفية تتبع المسار الذي وجدناه باستخدام الأراي previous

أتمنى أن تكون هذه المقالة مفيدة لك في فهم حل المتاهة باستخدام خوارزميات البحث