เครื่องมือการสร้างแผนที่ในเกมโดยใช้ Random Walk Algorithm
Tags: javascript, algorithms, ai, gamedev
Published: 2023-03-29 15:05:02

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

ในวันนี้เราขอเสนอหนึ่งวิธีที่จะสามารถสร้างแผนที่ดันเจี้ยน 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]]
```
เราสามารถเข้าถึงค่าของมันได้โดยการใช้แถวและคอลัมน์ เช่น 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]
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s814s1s76kqwzi3wh9zq.png)
จะได้ทิศทางทั้งหมดเป็น
```
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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o73hy06gu32xdyvdzgi4.png)


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

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