การสำรวจและการทำแผนที่

หุ่นยนต์ที่เดินไปมาแบบสุ่มจะทำคะแนนได้ไม่มาก หน้านี้แสดงวิธีเปลี่ยนจากการเดินสุ่มไปเป็นการสำรวจอย่างเป็นระบบ สิ่งเหล่านี้เป็นแนวคิดให้นำไปต่อยอด ไม่ใช่วิธีแก้ที่สมบูรณ์

รู้ว่าตัวเองอยู่ที่ใด

ช่องกว้าง 12 ซม. ดังนั้นตำแหน่งจาก GPS บอกได้ว่าอยู่ช่องใด ตำแหน่งของจุดเริ่มต้นแตกต่างกันในแต่ละโลก จึงควรวัดทุกอย่างเทียบจากจุดนั้น:

TILE = 0.12
startX, _, startZ = gps.getValues() # At the start of the game

def currentTile():
    x, _, z = gps.getValues()
    return round((x - startX) / TILE), round((z - startZ) / TILE)

หมายเหตุ

หากไม่มี GPS คุณประมาณตำแหน่งได้ด้วยเอนโค้ดเดอร์ล้อและไจโร แต่ความคลาดเคลื่อนจะสะสมขึ้น

จดจำสิ่งที่เห็น

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

tiles = {}
tiles[(0, 0)] = {"walls": {"N": False, "E": True, "S": False, "W": True}, "floor": "start", "visited": True}

ในพื้นที่ 2 และ 3 ช่องไม่ได้บอกทุกอย่าง เพราะผนังอาจอยู่บนช่องย่อยหนึ่งในสี่ (quarter tile) การเก็บแผนที่ด้วยความละเอียดระดับช่องย่อยหนึ่งในสี่ หรือการใช้กลุ่มจุด (point cloud) ของ Lidar จะช่วยให้คุณพร้อมรับมือกับพื้นที่เหล่านี้

ตัดสินใจว่าจะไปที่ใด

อย่าเดินตามผนังเพียงอย่างเดียว: วิธีนั้นจะไปไม่ถึงช่องลอย (floating tiles) ซึ่งสัญลักษณ์ในช่องเหล่านั้นมีคะแนนสูงกว่า วิธีที่นิยมใช้คือ:

1. จากช่องปัจจุบัน ให้หาช่องข้างเคียงทั้งหมดที่ไม่มีผนังกั้น
2. ไปยังช่องที่ยังไม่เคยไป ถ้ามี
3. หากไม่มี ให้หาช่องที่ใกล้ที่สุดซึ่งมีช่องข้างเคียงที่ยังไม่เคยไป ด้วยการค้นหาแบบกว้างก่อน (breadth-first search) แล้วไปที่นั่น
4. เมื่อไม่เหลือช่องแบบนั้นแล้ว หรือเวลาใกล้หมด ให้กลับไปยังจุดเริ่มต้นด้วยวิธีเดียวกัน

ให้ถือว่าหลุมเป็นผนัง หนองน้ำทำให้เสียเวลา และเสียมากขึ้นทุกครั้งที่เข้าหนองน้ำเดิม ดังนั้นให้เข้าไปเฉพาะเมื่อคุ้มค่า

รับมือกับสิ่งที่ไม่คาดคิด

• การไม่มีความคืบหน้า (lack of progress): หุ่นยนต์จะถูกย้ายไปยังจุดตรวจล่าสุด รอรับข้อความ L แล้วอัปเดตตำแหน่งของคุณ
• เวลา: ขอดูเวลาที่เหลือด้วย G เหลือเวลาไว้ให้พอสำหรับส่งแผนที่และกลับไปยังจุดเริ่มต้น
• สัญญาณรบกวน: เซนเซอร์มีสัญญาณรบกวน ดังนั้นให้เปรียบเทียบค่าที่อ่านได้หลายครั้งก่อนเชื่อว่ามีผนังหรือสัญลักษณ์

จากช่องไปเป็นเมทริกซ์แผนที่

เมทริกซ์แผนที่ มี 4 เซลล์ต่อช่อง บวกอีกหนึ่ง สำหรับช่องในแถว r และคอลัมน์ c ของแผนที่ของคุณ:

องค์ประกอบ	ตำแหน่งในเมทริกซ์ (แถว, คอลัมน์)
เครื่องหมายบนพื้น เช่น 4 หรือ 5	แถว 4r + 1 และ 4r + 3, คอลัมน์ 4c + 1 และ 4c + 3
ผนังทิศเหนือ	แถว 4r, คอลัมน์ 4c ถึง 4c + 4
ผนังทิศตะวันตก	คอลัมน์ 4c, แถว 4r ถึง 4r + 4

แผนที่ของคุณเริ่มที่ใดก็ได้: Erebus จัดแนวเมทริกซ์ โดยใช้ช่องเริ่มต้น และลองหมุนทั้งสี่ทิศทาง กติกาการทำแผนที่ อธิบายทุกค่าของเมทริกซ์ จากนั้นส่งแผนที่

ทดสอบด้วยโลกตัวอย่าง ซึ่งมีคำตอบที่ถูกต้องอยู่ในกติกาการทำแผนที่ ผลลัพธ์จะแสดงเป็น Map Correctness ในประวัติของหน้าต่างควบคุม