ผลต่างระหว่างรุ่นของ "418587 ภาคปลาย 2552/การบ้าน 3"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 17: แถว 17:
 
* หลังจากนั้นจะต้อง
 
* หลังจากนั้นจะต้อง
 
*# คำนวณทางเดิน (ซึ่งหมายถึงลำดับของช่องในแผนที่) ที่สั้นที่สุดจาก startPoint ไปยัง endPoint
 
*# คำนวณทางเดิน (ซึ่งหมายถึงลำดับของช่องในแผนที่) ที่สั้นที่สุดจาก startPoint ไปยัง endPoint
*# คำนวณช่องที่ผีจะต้องเดิืนต่อไปในทางที่สั้นที่สุดนั้น
+
*# คำนวณช่องที่ผีจะต้องเดิืนต่อจาก startPoint ในทางที่สั้นที่สุดนั้น
 
*# คำนวณทิศทางที่ผีจะต้องเดืนเพื่อที่จะไปช่องในข้อ 2
 
*# คำนวณทิศทางที่ผีจะต้องเดืนเพื่อที่จะไปช่องในข้อ 2
 
*# คืนทิศทางในข้อ 3 มา
 
*# คืนทิศทางในข้อ 3 มา
แถว 24: แถว 24:
  
 
ในการคำนวณนี้อาจมีบางกรณีที่ผีไม่สามารถเดินไปถึงช่องที่กำหนดได้ ในกรณีนั้นให้คุณคืน currentDirection มาเป็นคำตอบ
 
ในการคำนวณนี้อาจมีบางกรณีที่ผีไม่สามารถเดินไปถึงช่องที่กำหนดได้ ในกรณีนั้นให้คุณคืน currentDirection มาเป็นคำตอบ
 +
 +
เมื่อเขียนฟังก์ชันนี้เสร็จแล้ว โปรแกรม Pacman ของคุณควรจะมีพฤติกรรมคล้ายๆ กับเกม Pacman ที่สมบูรณ์แล้วที่ให้ไป
 +
 +
'''ใบ้:''' คุณควรจะเขียนโปรแกรมหาทางที่สั้นที่สุดโดยใช้ [http://en.wikipedia.org/wiki/Breadth-first_search Breadth First Search]

รุ่นแก้ไขเมื่อ 11:33, 22 กุมภาพันธ์ 2553

ให้ไว้ ณ วันจันทร์ที่ 22 ก.พ. 2553 ส่งวันจันทร์ 1 ม.ค. 2553 เวลา 23.59 น. โดย zip ไฟล์ในไดเรกทอรี Pacman ส่งมาที่ pramook at gmail dot com

เริ่มต้น

งานของคุณ

เกมที่คุณได้รับใน Pacman_Starter.zip เป็นเกมแพคแมนที่สามารถเล่นได้เกือบสมบูรณ์แล้ว เพียงแต่ว่าผีในเกมยังไม่สามารถเดินไปจับตัว Pacman เท่านั้น

ที่เป็นเช่นนี้เนื่องจากผีทุกตัวมีการใช้เมธอดของคลาส PathFinder (ดูในไฟล์ PacmanLib/AI/PathFinder) ที่ชื่อ WhichWayToMove แต่ในโค้ดตั้งต้น เราให้เมธอดนี้คืนค่าืิทิศทางขึ้นบน (Direction.Up) เท่านั้น

จงเติมเมธอด WhichWaytoMove ให้สมบูรณ์ โดยที่เมธอดนี้

  • รับข้อมูล 3 ตัว ดังนี้
    • startPoint คือ คู่ลำดับ x, y ของช่องที่ผีอยู่
    • endPoint คือ คู่ลำดับ x, y ที่ผีต้องการไป
    • currentDirection คือ ทิศทางที่ผีกำลังเคลื่อนที่อยู่ในตอนนั้น
  • หลังจากนั้นจะต้อง
    1. คำนวณทางเดิน (ซึ่งหมายถึงลำดับของช่องในแผนที่) ที่สั้นที่สุดจาก startPoint ไปยัง endPoint
    2. คำนวณช่องที่ผีจะต้องเดิืนต่อจาก startPoint ในทางที่สั้นที่สุดนั้น
    3. คำนวณทิศทางที่ผีจะต้องเดืนเพื่อที่จะไปช่องในข้อ 2
    4. คืนทิศทางในข้อ 3 มา

เส้นทางที่ผีจะเดินไปจะต้องไม่มีสิ่งกีดขวาง (คุณสามารถตรวจสอบดูว่าช่อง p มีสิ่งกีดขวางหรือไม่ด้วยการเช็คว่า map.Walkability[p.x, p.y] มีค่าเท่ากับ Map.Walkabilities.Walkable หรือ Map.Walkabilities.EnemyWalkable หรือไม่

ในการคำนวณนี้อาจมีบางกรณีที่ผีไม่สามารถเดินไปถึงช่องที่กำหนดได้ ในกรณีนั้นให้คุณคืน currentDirection มาเป็นคำตอบ

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

ใบ้: คุณควรจะเขียนโปรแกรมหาทางที่สั้นที่สุดโดยใช้ Breadth First Search