Map Generator - Perlin Noise

Perlin Noise 1-D và 2-D, dùng để sinh địa hình ngẫu nhiên nhưng mượt cho map generator.

1-D Perlin Noise

Về cơ bản, mục tiêu của Perlin Noise là từ đầu vào ngẫu nhiên cho ra một kết quả smooth (mượt).

Xét một dãy số có giá trị thực từ 0 đến dưới 1, gọi $Y = y_{0}, ..., y_{n}$ là dãy số ngẫu nhiên này và $X = 0, ..., n$ .

Áp dụng piecewise linear interpolation (phép nội suy tuyến tính từng phần), giúp ta có thể tìm kiếm một giá trị bất kỳ trong khoảng rời rạc của 2 giá trị:

f_{l} (x) = lerp (y_{i}, y_{i} + 1, α) = (1 - α) * y_{i} + α * y_{i} + 1

(trong đó $i$ là phần nguyên của $x$ , $α$ là phần thập phân của $x$ )

x =

i = alpha = f(x) =

Lúc này thì ta đã thấy ra dáng rồi nhưng chưa được mượt lắm, bởi vậy ta thay $α$ bằng một hàm $cos$ .

f t = \frac{1 - cos ( α π )}{2}

f_{c} (x) = lerp (y_{i}, y_{i} + 1, f t) = (1 - f t) * y_{i} + f t * y_{i} + 1

x =

i = alpha = f(x) =

Ta có thể mở rộng hàm noise ra bên ngoài khoảng $n$ bằng cách:

noise (t) = f (t mod n)

2-D Perlin Noise

Ta có lưới đơn vị $n \times n$ . Với mỗi đơn vị $[i, j]$ ta sinh ra một điểm ngẫu nhiên $z [i, j] = (x, y)$ .

Từ đó ta suy ra các điểm góc là $(x_{0}, y_{0})$ , $(x_{1}, y_{0})$ , $(x_{0}, y_{1})$ , $(x_{1}, y_{1})$ , trong đó:

$x_{0}$ là phần nguyên của $x$
$x_{1}$ là $(x_{0} + 1) mod n$
$y_{0}$ là phần nguyên của $y$
$y_{1}$ là $(y_{0} + 1) mod n$

Cho hàm số liên tục $f (x)$ , ta tìm được đạo hàm $\frac{df}{d x}$ cho ta hệ số góc tiếp tuyến tại điểm $(x, f (x))$ của hàm.

Thay vì nghĩ về một hàm số $f (x, y)$ hai tham số, ta chỉ cần tưởng tượng hàm giá trị $(x, y, f (x, y))$ là độ cao của điểm trong không gian 2 chiều. Nếu $f$ smooth, thì những điểm trong địa hình đều có thể liên hệ với mặt phẳng tiếp tuyến.

"Độ dốc" của mặt phẳng tiếp tuyến đi qua một điểm như vậy được xác định bởi các đạo hàm riêng của hàm $\frac{\partial f}{\partial x}$ và $\frac{\partial f}{\partial y}$ .

Vector $(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y})$ là vector của mặt phẳng mà các điểm đi lên dốc nhất của hàm $f$ . Vector này thay đổi từng điểm, phụ thuộc vào $f$ . Gọi là gradient của $f$ và được ký hiệu bằng $\nabla f$ .

$g [0, 0]$ , $g [0, 1]$ , $g [1, 0]$ , $g [1, 1]$ là các gradient vector ngẫu nhiên ở từng góc.

Với mỗi $(x, y)$ , ta tìm được vector từ các góc đến điểm $(x, y)$ này:

$v [0, 0]$ , $v [0, 1]$ , $v [1, 0]$ , $v [1, 1]$

Tham khảo

CMSC425 - Lecture 12, 13