DEV Community

Nuttapon-Sartmanee
Nuttapon-Sartmanee

Posted on

เครื่องมือการสร้างแผนที่ในเกมโดยใช้ Random Walk Algorithm

#javascript #algorithms #ai #gamedev

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

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

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

  1. Dimensions (ความกว้างและความสูงของแผนที่)
  2. MaxTunnels (จำนวนรอบสูงสุดที่อัลกอริทึมสามารถทำได้ขณะสร้างแผนที่)
  3. MaxLength (ความยาวสูงสุดของแต่ละอุโมงค์ที่อัลกอริทึมจะเลือกก่อนทำการเลี้ยวในแนวนอนหรือแนวตั้ง)

การทำงานของ Algorithm จะมีดังนี้

  1. สร้างแผนที่สองมิติในรูปแบบของ Grid
  2. เลือกจุดเริ่มต้นแบบสุ่มบนแผนที่
  3. จำนวนอุโมงค์ต้องไม่เป็นศูนย์
  4. สุ่มความยาวจากความยาวสูงสุดที่ผู้ใช้กำหนด
  5. สุ่มทิศทางการเลี้ยว (ขวา, ซ้าย, ขึ้น, ลง)
  6. วาดอุโมงค์ในทิศทางนั้นโดยหลีกเลี่ยงขอบของแผนที่
  7. ลดจำนวน tunnels และทำวนซ้ำไปเรื่อย ๆ
  8. ส่งข้อมูลแผนที่ที่สร้างเสร็จแล้วกลับไป

เนื่องจากแผนที่ประกอบด้วยอุโมงค์และกำแพง จึงสามารถอธิบายเป็น 0 และ 1 ในอาร์เรย์สองมิติดังต่อไปนี้ (1 หมายถึง "กำแพง" , 0 หมายถึง "อุโมงค์")

map = [[1,1,1,1,0], [1,0,0,0,0], [1,0,1,1,1], [1,0,0,0,1], [1,1,1,0,1]]
Enter fullscreen mode Exit fullscreen mode

เราสามารถเข้าถึงค่าของมันได้โดยการใช้แถวและคอลัมน์ เช่น map [row] [column]

ก่อนเขียนอัลกอริทึม ต้องมีฟังก์ชันตัวช่วยในการสร้างอาร์เรย์สองมิติ คือ

createArray(num, dimensions) { var array = []; for (var i = 0; i < dimensions; i++) { array.push([]); for (var j = 0; j < dimensions; j++) { array[i].push(num); } } return array; }
Enter fullscreen mode Exit fullscreen mode

สร้างตัวแปรต่าง ๆ เพื่อเตรียมกำหนดค่าให้กับ Random Walk Algorithm

createMap(){ let dimensions = 5, maxTunnels = 3, maxLength = 3;
Enter fullscreen mode Exit fullscreen mode

สร้างอาร์เรย์สองมิติโดยใช้ฟังก์ชันตัวช่วยในการสร้างอาร์เรย์สองมิติ ที่กำหนดไว้ล่วงหน้า

let map = createArray(1, dimensions);
Enter fullscreen mode Exit fullscreen mode

สุ่มแถวและคอลัมน์ เพื่อเป็นจุดเริ่มต้นบนแผนที่

let currentRow = Math.floor(Math.random() * dimensions), currentColumn = Math.floor(Math.random() * dimensions);
Enter fullscreen mode Exit fullscreen mode

สร้างทิศทางการเคลื่อนที่ทั้งหมดที่ทำได้ ตัวอย่างเช่น หากต้องการไปที่จุดรอบ ๆ จุด [2][2] สามารถทำได้โดยวิธีต่อไปนี้

  • หากต้องการขึ้น ให้ลบ 1 ออกจากแถว คือไปที่จุด [1][2]
  • หากต้องการลงไป ให้เพิ่ม 1 ในแถว คือไปที่จุด [3][2]
  • หากต้องการไปทางขวา เพิ่ม 1 ในคอลัมน์ คือไปที่จุด [2][3]
  • หากต้องการไปทางซ้าย ให้ลบ 1 ออกจากคอลัมน์ คือไปที่จุด [2][1] Image description จะได้ทิศทางทั้งหมดเป็น 
let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
Enter fullscreen mode Exit fullscreen mode

สร้างตัวแปรเพื่อเก็บค่าสุ่มจาก การสุ่มทิศทางการเคลื่อนที่ และสร้างตัวแปรเพื่อเก็บ ทิศทางที่เคยเดินแล้ว โดยเริ่มต้นจะเป็น empty

let lastDirection = [], randomDirection;
Enter fullscreen mode Exit fullscreen mode

สร้างเงื่อนไขที่ไม่ทำให้เกิดการเดินซ้ำที่เดิม

do { randomDirection = directions[Math.floor(Math.random() * directions.length)]; } while ((randomDirection[0] === -lastDirection[0] && randomDirection[1] === -lastDirection[1]) || (randomDirection[0] === lastDirection[0] && randomDirection[1] === lastDirection[1]));
Enter fullscreen mode Exit fullscreen mode

สร้างตัวแปรเพิ่มสุ่มความยาวจาก maxLength และใส่ค่าให้ tunnelLength เป็น 0

let randomLength = Math.ceil(Math.random() * maxLength), tunnelLength = 0;
Enter fullscreen mode Exit fullscreen mode

สร้างอุโมงค์โดยเปลี่ยนค่าของช่องนั้นจากหนึ่งเป็นศูนย์โดยที่ tunnelLength น้อยกว่า randomLength และถ้าอุโมงค์ชนขอบแผนที่ จะหยุดการทำงาน

while (tunnelLength < randomLength) { if(((currentRow === 0) && (randomDirection[0] === -1))|| ((currentColumn === 0) && (randomDirection[1] === -1))|| ((currentRow === dimensions — 1) && (randomDirection[0] ===1))|| ((currentColumn === dimensions — 1) && (randomDirection[1] === 1))) { break; }
Enter fullscreen mode Exit fullscreen mode 
else{ map[currentRow][currentColumn] = 0; currentRow += randomDirection[0]; currentColumn += randomDirection[1]; tunnelLength++; } }
Enter fullscreen mode Exit fullscreen mode

หากอุโมงค์เกิดการชนขอบ จะเช็คว่าทิศทางนั้นมีความยาวอย่างน้อยหนึ่งหรือไม่ ถ้าใช่ ให้เปลี่ยนค่า LastDirection เป็น RandomDirection และลดค่า maxTunnels แล้วกลับไปสร้างอุโมงค์ใหม่ด้วยทิศทางสุ่มอื่น

if (tunnelLength) { lastDirection = randomDirection; maxTunnels--; }
Enter fullscreen mode Exit fullscreen mode

เมื่อเสร็จสิ้นการวาดอุโมงค์และ maxTunnels เป็นศูนย์ จะส่งข้อมูลแผนที่
ผลลัพธ์พร้อมทางเลี้ยวและอุโมงค์ทั้งหมดกลับไป

} return map; };
Enter fullscreen mode Exit fullscreen mode

ตัวอย่างผลที่ได้จาก Code

Image description

สรุปผล

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

References: https://www.freecodecamp.org/news/how-to-make-your-own-procedural-dungeon-map-generator-using-the-random-walk-algorithm-e0085c8aa9a/

Top comments (0)