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

Nuttapon-Sartmanee — Wed, 29 Mar 2023 15:05:02 +0000

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

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

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

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

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

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

เนื่องจากแผนที่ประกอบด้วยอุโมงค์และกำแพง จึงสามารถอธิบายเป็น 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]]

เราสามารถเข้าถึงค่าของมันได้โดยการใช้แถวและคอลัมน์ เช่น 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;  
}

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

createMap(){
 let dimensions = 5,     
 maxTunnels = 3, 
 maxLength = 3;

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

let map = createArray(1, dimensions);

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

let currentRow = Math.floor(Math.random() * dimensions),       
    currentColumn = Math.floor(Math.random() * dimensions);

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

หากต้องการขึ้น ให้ลบ 1 ออกจากแถว คือไปที่จุด [1][2]
หากต้องการลงไป ให้เพิ่ม 1 ในแถว คือไปที่จุด [3][2]
หากต้องการไปทางขวา เพิ่ม 1 ในคอลัมน์ คือไปที่จุด [2][3]
หากต้องการไปทางซ้าย ให้ลบ 1 ออกจากคอลัมน์ คือไปที่จุด [2][1] จะได้ทิศทางทั้งหมดเป็น

let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

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

let lastDirection = [], 
    randomDirection;

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

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]));

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

let randomLength = Math.ceil(Math.random() * maxLength),       
    tunnelLength = 0;

สร้างอุโมงค์โดยเปลี่ยนค่าของช่องนั้นจากหนึ่งเป็นศูนย์โดยที่ 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; }

else{ 
  map[currentRow][currentColumn] = 0; 
  currentRow += randomDirection[0];
  currentColumn += randomDirection[1]; 
  tunnelLength++; 
 } 
}

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

if (tunnelLength) { 
 lastDirection = randomDirection; 
 maxTunnels--; 
}

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

}
 return map;
};

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

สรุปผล

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

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

DEV Community: Nuttapon-Sartmanee

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

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

สรุปผล