Maze Generating Algorithm

A maze solving system comparing the efficiency of Breadth-First Search (BFS) and A* Search.
Using Manhattan Distance as a heuristic, tested on randomly generated 60x60 mazes across various scenarios. เป็นการทำระบบแก้เขาวงกตเพื่อเปรียบเทียบประสิทธิภาพของ Breadth-First Search (BFS) และ A* Search
โดยใช้ Manhattan Distance เป็น heuristic ทดสอบกับเขาวงกตขนาด 60×60 ที่สุ่มสร้างขึ้นในหลายสถานการณ์

Information

GitHub

Core Concepts

BFS (Breadth-First Search) is an Uninformed Search that expands nodes from near to far in all directions, without using any target location data.

A* Search is an Informed Search that uses a heuristic (Manhattan Distance) along with a priority queue (heapq) to prioritize exploring nodes that are likely closer to the target. BFS หรือ Breadth-First Search เป็น Uninformed Search จะขยาย Node จากใกล้ไปไกลแบบรอบตัว ไม่ใช้ข้อมูลของตำแหน่งเป้าหมายเลย

ส่วน A* Search เป็น Informed Search ใช้ heuristic คือ Manhattan Distance ร่วมกับ heapq เพื่อจัดลำดับการค้นหา ทำให้เลือกสำรวจ Node ที่มีแนวโน้มเข้าใกล้เป้าหมายก่อน

Maze Example

This example shows a maze with walls broken down to create an "Open Zone". The red line represents the shortest path found by backtracking from the destination to the start point. ในงานนี้เราใช้เขาวงกตเป็นตัวอย่าง ภาพที่เห็นคือเขาวงกตหลังจากทุบกำแพงเพิ่ม ซึ่งเราเรียกว่า Open Zone เส้นสีแดงที่เห็น คือเส้นทางที่สั้นที่สุด ซึ่งได้มาจากการ backtracking จากจุดหมายกลับไปยังจุดเริ่มต้น

Result Table

- Scenario 1: A* beats BFS every time, but the node count difference is small (approx. 0-18%).
- Scenario 2 (Open Zone): A* clearly outperforms BFS, reducing node count by approx. 40-84%, showing significant efficiency gains. -สถานการณ์ที่ 1 A* ชนะ BFS ทุกครั้งแต่จำนวน Node ที่ต่างกันยังไม่มากอยู่ประมาณ 0-18 เปอร์เซ็นต์
-สถานการณ์ที่ 2 หลัง Open Zone A* ชนะอย่างชัดเจนทุกครั้งลดจำนวน Node ได้ประมาณ 40-84 เปอร์เซ็นต์จะแสดงให้เห็นถึงความแตกต่างด้านประสิทธิภาพอย่างชัดเจน

Analysis

In a normal maze, walls force the path. Even if A* knows the direction, it must follow the same turns as BFS, leading to similar results.
However, in an Open Zone, the heuristic can guide accurately. A* moves directly towards the target, while BFS still searches in a wide circle. ในเขาวงกตปกติเส้นทางถูกกำแพงบังคับแม้ A* จะรู้ว่าเป้าหมายอยู่ทิศไหนแต่ถ้าต้องเลี้ยวซ้ายก็ต้องเลี้ยวเหมือน BFS ทำให้ผลลัพธ์ใกล้เคียงกัน
แต่ใน Open Zone พื้นที่เปิดกว้าง heuristic สามารถชี้ทางได้แม่น A* จึงพุ่งเข้าใกล้เป้าหมายได้จริงขณะที่ BFS ยังต้องกระจายค้นหาเป็นวงกว้าง

Conclusion

- A* visits fewer nodes than BFS in all cases.
- Open Zones allow A* to fully utilize its heuristic.
- BFS is suitable for simple problems or when no heuristic is available.
- A* is better for open areas or multiple path options.
- Both algorithms can find the correct path equally well. -A* ใช้ Node น้อยกว่า BFS ทุกกรณี
-Open Zone ทำให้ A* ใช้ heuristic ได้เต็มประสิทธิภาพ
-BFS เหมาะกับปัญหาที่ไม่ซับซ้อนหรือไม่มี heuristic
-A* เหมาะกับพื้นที่เปิดหรือมีหลายเส้นทาง
-ทั้งสองอัลกอริทึมสามารถหาเส้นทางที่ถูกต้องได้เหมือนกัน