ตัวสร้างเขาวงกตต้นไม้ที่เติบโต

อัลกอริทึม Growing Tree นั้นน่าสนใจ เพราะสามารถเลียนแบบพฤติกรรมของอัลกอริทึมอื่นๆ ได้หลายตัว ขึ้นอยู่กับว่าเซลล์ถัดไปถูกเลือกอย่างไรในระหว่างการสร้าง การใช้งานในหน้านี้ใช้วิธีการที่เหมือนคิวที่เน้นความกว้างก่อน

เขาวงกตที่สมบูรณ์แบบคือเขาวงกตที่มีเส้นทางเดียวจากจุดใดก็ได้ในเขาวงกตไปยังจุดใดก็ได้ นั่นหมายความว่าคุณไม่สามารถวนไปวนมาได้ แต่บ่อยครั้งที่คุณจะเจอทางตัน ซึ่งบังคับให้คุณต้องหันหลังกลับและเดินกลับไป

แผนที่เขาวงกตที่สร้างขึ้นที่นี่มีเวอร์ชันเริ่มต้นโดยไม่มีตำแหน่งเริ่มต้นและจุดสิ้นสุด ดังนั้นคุณจึงตัดสินใจเองได้: จะมีทางออกจากจุดใดก็ได้ในเขาวงกตไปยังจุดอื่นๆ หากคุณต้องการแรงบันดาลใจ คุณสามารถเปิดใช้งานตำแหน่งเริ่มต้นและจุดสิ้นสุดที่แนะนำได้ และดูทางออกระหว่างทั้งสองตำแหน่งได้ด้วย

เกี่ยวกับอัลกอริทึมต้นไม้ที่กําลังเติบโต

อัลกอริทึม Growing Tree เป็นวิธีที่ยืดหยุ่นและทรงพลังในการสร้างเขาวงกตที่สมบูรณ์แบบ อัลกอริทึมนี้น่าสนใจเพราะสามารถเลียนแบบพฤติกรรมของอัลกอริธึมการสร้างเขาวงกตอื่นๆ เช่น อัลกอริทึมของ Prim การย้อนกลับแบบเรียกซ้ํา และการแบ่งแบบเรียกซ้ํา ขึ้นอยู่กับว่าคุณเลือกเซลล์ถัดไปที่จะประมวลผลอย่างไร

อัลกอริทึมต้นไม้ที่กําลังเติบโตทํางานอย่างไร

ขั้นตอนที่ 1: การเริ่มต้น

• เริ่มต้นด้วยตารางของเซลล์ที่ยังไม่ได้เยี่ยมชม
• เลือกเซลล์เริ่มต้นแบบสุ่มและเพิ่มลงในรายการ

ขั้นตอนที่ 2: Maze Generation Loop

• ในขณะที่รายการเซลล์ไม่ว่างเปล่า:
  • เลือกเซลล์จากรายการตามกลยุทธ์เฉพาะ (อธิบายด้านล่าง)
  • แกะสลักทางเดินจากเซลล์ที่เลือกไปยังเพื่อนบ้านที่ยังไม่ได้เยี่ยมชม (เลือกแบบสุ่ม)
  • เพิ่มเพื่อนบ้านในรายการเนื่องจากตอนนี้เป็นส่วนหนึ่งของเขาวงกต
  • ถ้าเซลล์ที่เลือกไม่มีเพื่อนบ้านที่ยังไม่ได้เยี่ยมชม ให้ลบเซลล์นั้นออกจากรายการ

ขั้นตอนที่ 3: การยกเลิก

• อัลกอริทึมจะเสร็จสิ้นเมื่อไม่มีเซลล์อีกต่อไปในรายการ ซึ่งหมายความว่าเขาวงกตทั้งหมดถูกแกะสลักแล้ว

กลยุทธ์การเลือกเซลล์ (ความยืดหยุ่นของอัลกอริทึม)

คุณลักษณะที่กําหนดของอัลกอริทึม Growing Tree คือวิธีที่คุณเลือกเซลล์ที่จะประมวลผลต่อไป ตัวเลือกนี้ส่งผลต่อรูปลักษณ์ของเขาวงกตอย่างมาก:

เซลล์ใหม่ล่าสุด (พฤติกรรมเหมือนสแต็ก) – Recursive Backtracker:

• เลือกเซลล์ที่เพิ่มล่าสุดเสมอ
• สร้างทางเดินที่ยาวและคดเคี้ยวที่มีทางตันมากมาย (เช่น เขาวงกตการค้นหาที่เน้นความลึกเป็นอันดับแรก)
• เขาวงกตมักจะมีทางเดินยาวและแก้ง่าย

เซลล์สุ่ม (อัลกอริทึมของ Random Prim):

• เลือกเซลล์แบบสุ่มจากรายการในแต่ละครั้ง
• สร้างเขาวงกตที่กระจายอย่างสม่ําเสมอมากขึ้นด้วยเส้นทางที่ซับซ้อนและพันกัน
• ทางเดินยาวน้อยลงและแตกแขนงมากขึ้น

เซลล์ที่เก่าที่สุด (พฤติกรรมเหมือนคิว):

• เลือกเซลล์ที่เก่าที่สุดในรายการเสมอ
• สร้างเขาวงกตที่มีการแพร่กระจายที่สม่ําเสมอมากขึ้น เช่น รูปแบบการค้นหาที่เน้นความกว้างเป็นอันดับแรก
• ทางเดินสั้นและเป็นพุ่มพร้อมการเชื่อมต่อที่หนาแน่น
• (นี่คือเวอร์ชันที่นําไปใช้ที่นี่)

แนวทางไฮบริด:

รวมกลยุทธ์สําหรับลักษณะเขาวงกตที่หลากหลาย เช่น:

• ใหม่ที่สุด 90%, สุ่ม 10%: ส่วนใหญ่ดูเหมือนเขาวงกตย้อนกลับแบบเรียกซ้ํา แต่มีกิ่งก้านเป็นครั้งคราวที่แยกทางเดินยาว
• ใหม่ที่สุด 50%, เก่าที่สุด 50%: สร้างสมดุลระหว่างทางเดินยาวกับการเจริญเติบโตเป็นพุ่มไม้