Chủ Nhật, 17 tháng 11, 2013

Kĩ thuật lập trình Game – Cơ bản - part 1

I.   Vòng lặp game (Game loop) hoạt động thế  nào?
Phần cốt lõi của hầu hết các game chính là vòng lặp được dùng để cập nhật và hiển thị trạng thái của game. Trong bài viết này,  ta  sẽ minh họa các phương pháp tạo vòng lặp   game với ngôn ngữ javascript.
1.  Vòng lặp cơ bản
Một vòng lặp game cơ bản bao gồm các việc được thực hiện theo thứ tự sau:
while(gameRunning)
{
 processInput(); // keyboard, mouse,...
 updateGame();
 draw();
 // checkGameOver();
}
Minh họa:






Trong  javascript,  thay  vì  dùng  vòng  lặp,  ta  sẽ  thay  thế  bằng  setInterval()  hoặc  setTimeout(). Thông thường bạn chỉ cần xác định một giá trị interval thích hợp theo tốc độ của game.
function gameLoop()
{
 processInput();
 updateGame();
 draw();
 setTimeout(gameLoop,100); // 10 fps
}
 Hợp lý hơn khi bạn muốn xác định rõ số khung hình/giây (fps):
 const FPS = 60;
 function gameLoop()
{
 // …
}
window.setInterval(gameLoop,1000/FPS);


2.  Vòng lặp có tính toán thời gian
Tuy nhiên, không phải lúc nào công việc update và draw cũng hoà n thành trước khi lần gọi kế  tiếp được thực hiện. Như vậy tốc độ của game sẽ không đồng nhất trên các thiết bị có cấu hình khác nhau. Để  giải quyết,  ta  sẽ  sử  dụng  đến  thời  gian  hệ  thống  để  so  sánh  và  quyết  định  thời  điểm 
update/draw.
const FPS = 60;
const TICKS = 1000/FPS;
var lastUpdateTime;
function gameLoop()
{
 var now = Date.now();
 var diffTime = now - lastUpdateTime;
 if(diffTime >= TICKS)
  processInput();
 updateGame();
 lastUpdateTime = now;
}
 draw();
 var sleepTime = TICKS - diffTime;
 if(sleepTime<0)
  sleepTime = 0;
 setTimeout(gameLoop,sleepTime);
}
Phương  pháp  trên  chạy  ổn  với  giá  trị  diffTime  nhỏ  hơn  TICKS.  Nghĩa  l à  tốc  độ  của  game không vượt quá  giá  trị  TICKS cho phép. Tuy nhiên trong trường hợp diffTime l ớn, việc cập nhật sẽ  diễn ra chậm.
3.  Giải pháp cuối cùng
Giải pháp của ta l à  sẽ  thực hiện update với số  l ần dựa vào tỉ  l ệ  diffTime/TICKS trong một l ần l ặp của game. Sẽ  hiệu quả  hơ n nếu ta bỏ  qua việc draw và  thực hiện update liên tiếp vì  sẽ  giúp tăng tốc độ game để bù vào khoảng thời gian bị trì hoãn.
const FPS = 60;
const TICKS = 1000/FPS;
var lastUpdateTime;
function gameLoop()
{
 var diffTime = Date.now() - lastUpdateTime;
 var numOfUpdate = Math.floor(diffTime/TICKS);
 for(var i = 0;i < numOfUpdate;i++){
  processInput();
  updateGame();
}
 if(diffTime >= TICKS)
  draw();
 lastUpdateTime += TICKS * numOfUpdate;
 diffTime -= TICKS * numOfUpdate;
 var sleepTime = TICKS - diffTime;
 setTimeout(gameLoop,sleepTime);
}
Nếu bạn sử dụng requestAnimationFrame  cho vòng l ặp game, bạn sẽ không cần quan tâm đến việc tính toán giá trị sleepTime.
4.  Ví dụ  hoàn chỉnh
Kiểm tra ví  dụ  này và  so sánh với các phương pháp trước  đó, thực hiện một vài công việc  “quá tải” nào đó trên trình duyệt và bạn sẽ  thấy khác biệt:
const FPS = 6;
const TICKS = 1000 / FPS;
var startTime;
var expectedCounter = 0;
var lastUpdateTime;
var actualCounter = 0;
var output;
function gameLoop()
{
 var diffTime = Date.now() - lastUpdateTime;
 var numOfUpdate = Math.floor(diffTime/TICKS);
 for(var i = 0;i < numOfUpdate;i++){
 updateGame();
}
 if(diffTime >= TICKS)
  draw();
 lastUpdateTime += TICKS * numOfUpdate;
 diffTime -= TICKS * numOfUpdate;
 var sleepTime = TICKS - diffTime;
 setTimeout(gameLoop,sleepTime);
}
 function updateGame() {
 actualCounter++;
}
function draw() {
 var s = "Actual updates: "+actualCounter;
 s += "<br/>Expected updates: "+Math.floor((Date.now()-startTime)/TICKS);
 output.innerHTML = s;
}
// onLoad
output = document.getElementById("output");
startTime = Date.now();
lastUpdateTime = startTime;
gameLoop();
Output:
Actual updates: 1323
Expected updates: 1323

II.    Kiểm tra va chạm: hình tròn và chữ  nhật

Thông thường các đối tượng trong game sẽ được xác định va chạm bằng cách đưa chúng về một dạng hình học cơ bản như hình chữ nhật, hình tròn. Bài viết này sẽ giúp bạn cách tính toán để kiểm tra va chạm giữa hai loại hình học này.
1.  Giữa hai hình chữ  nhật
Phương pháp: kiểm tra từng đỉnh của hình này có nằm bên trong hình kia không.
Rect.prototype.collideWidthRect = function(rect) {
 return this.contains(rect.left,rect.top) ||
 this.contains(rect.right,rect.top) ||
 this.contains(rect.right,rect.bottom) ||
 this.contains(rect.left,rect.bottom);
}
Cách trên không phải cách nhanh nhất, vì vậy bạn có thể dùng cách sau, đơn giản và hiệu quả hơn:
Rect.prototype.collideWidthRect = function(rect) {
 return !(this.left > rect.right ||this.right < rect.left ||
 this.top > rect.bottom ||
 this.bottom < rect.top);
}
2.  Giữa hai hình tròn
Phương pháp: Bởi vì mọi điểm nằm trên đường tròn cách đều tâm, nên việc kiểm tra va chạm giữa  hai  hình tròn  sẽ  được  xác  định  dựa  vào  khoảng  cá ch  tâm  giữa  chúng.Để xác định khoảng cách giữa hai điểm, ta dựa vào định lý Pythagoras (Pythagorean theorem) . Ta coi khoảng cách giữa hai điểm là đường chéo của một tam giác vuông. Vậy độ lớn của đường 
chéo này là:
c² = a² + b²
=> c = sqrt(a² + b²)
Circle.prototype.collideWithCircle = function(circle){ var dx = this.cx - circle.cx; var dy = this.cy - circle.cy; return Math.sqrt(dx*dx + dy*dy) <= this.radius+circle.radius;}
Trong minh họa dưới đây, hai hình tròn có màu mặc định là xanh lá, khi va chạm  nhau, chúng sẽ chuyển sang màu đỏ.
3.  Giữa hình tròn và hình chữ  nhật
Phương pháp: Gọi C là tâm và R là bán kính hình tròn. Ta sẽ tìm cách xác định điểm A là điểm gần  nhất thuộc  hình  chữ  nhật  đến  tâm  C.  Sau  đó  so  sánh  độ  lớn  của  CA  với  R. 
Khoảng cách giữa tâm C hình tròn và điểm A của hình chữ nhật được minh họa như hình dưới đây. Khi tâm hình tròn nằm bên trong hình chữ nhật, thì điểm C và A sẽ trùng nhau.
Gọi rect là hình chữ nhật cần xác định va chạm. Ta có thuật toán để xác định điểm A như sau:
- B1: Gán A bằng với C.
- B2: Nếu C.X < rect.Left, đặt A.X = rect.Left. Ngược l ại nếu C.X > rect.Right, đặt A.X = rect.Right.
- B3: Nếu C.Y < rect.Top, đặt A.Y = rect.Top. Ngược l ại nếu C.Y > rect.Bottom, đặt A.Y = rect.Bottom.
Khi đã có điểm A, ta lại dùng công thức Pythagoras để so sánh với bán kính của hình tròn.
Circle.prototype.collideWithRect = function(rect){
 var px = this.cx;
 var py = this.cy;
 if(px < rect.left)
  px = rect.left;
 else if(px > rect.right)
  px = rect.right;
 if(py < rect.top)
  py = rect.top;
 else if(py > rect.bottom)
  py = rect.bottom;
 var dx = this.cx - px;
 var dy = this.cy - py;
 return (dx*dx + dy*dy) <= this.radius*this.radius;
}

III.   Kiểm tra một điể m nằm trên đoạn thẳng

Có nhiều cách để kiểm tra một điểm có thuộc đường thằng  (tương tự với đoạn thẳng) hay không: bằng cách sử dụng các công thức hình học hoặc thuật toán vẽ đường thẳng,… Ngoài những cách trên,  ta  sẽ giới thiệu một phương pháp đơn giản nhất là sử dụng phép so sánh góc để giải quyết vấn đề này.
Trong demo sau, khi  bạn di chuyển chuột ngang lên trên đoạn thẳng, bạn sẽ đoạn thẳng chuyển sang màu đỏ.
Ý tưởng : 
Ta có đoạn  thẳng AB tạo nên góc α (so với phương  ngang  hoặc phương bất kì),  và  mọi điểm thuộc AB đều tạo nên góc α so với phương ngang.
Hay nói cách khác, ta xem đoạn thẳng AB là đường chéo của một tam giác vuông ABM. Tỉ lệ 
giữa hai cạnh góc vuông của tam giác này sẽ bằng với tỉ lệ hai cạnh góc vuông tạo bởi tam giác 
vuông AXN. Minh họa như hình dưới đây:
Như vậy việc xác định một điểm X có thuộc AB hay không chỉ cần dựa vào 2 yếu tố:
(1)    X phải  nằm  trong  vùng  hình chữ nhật được tạo bởi đường chéo AB (ngoại  tiếp tam  giác 
ABM).
(2)   Góc XAN và BAM phải bằng nhau.
Ngoài ra, do việc so sánh là kiểu số thực và có thể do độ rộng của đoạn thẳng khác nhau nên ta cần chấp nhận một giá trị sai số EPSILON nào đó.  
Muốn chính xác hơn khi độ rộng của đoạn thẳng thay đổi, bạn có thể tính góc sai số cho phép bằng cách dựa vào ½ độ rộng đoạn thẳng và khoảng cách AX để tính. Tuy nhiên, điều này không quan trọng lắm và làm cho việc kiểm tra tốn thêm chi phí.
Để đơn giản, ta sẽ tính tỉ lệ (tan) thay vì tính góc α:
Line.prototype.contains = function(x, y) {
 if(   x < Math.min(this.handler1.cx,this.handler2.cx) ||
 x > Math.max(this.handler1.cx,this.handler2.cx) ||
 y < Math.min(this.handler1.cy,this.handler2.cy) ||
 y > Math.max(this.handler1.cy,this.handler2.cy))
  return false;
 var dx = this.handler1.cx-this.handler2.cx;
 var dy = this.handler1.cy-this.handler2.cy;
 var tan1 = Math.abs(dy/dx);
 var tan2 = Math.abs((y-this.handler1.cy)/(x-this.handler1.cx));
 return Math.abs(tan1 - tan2) < EPSILON;
}

IV.   Vector 2D cơ  bản

Ứng dụng của vector rất quan trọng trong lĩnh vực lập trình game và đồ họa. Thông qua vector, ta có thể mô phỏng được các chuyển động, tính toán lực, hướng di chuyển sau khi va chạm,…
1.  Khái niệm
“ …một vectơ là một phần tử trong một không gian vectơ, được xác định bởi ba yếu tố: điểm đầu (hay điểm gốc), hướng (gồm phương và chiều) và độ lớn (hay độ dài).”  (Wiki pedia)
Từ một đoạn thẳng AB ta có thể xác định được vector (mã giả):
u.root = A;
u.x = B.x - A.x;
u.y = B.y - A.y;
u.length = sqrt(u.x*u.x+u.y*u.y);  // |u|
2.  Vector đơn vị (Unit Vector, Normalized Vector)
Vector đơn vị của u là vector có chiều dài bằng 1 và kí hiệu là û. Vector u sau được gọi là vector đơn vị của v bằng cách tính (mã giả):
û = u/|u|
Như  vậy:
|û| = 1
3.  Tích vô hướ ng (Dot product, Scalar pro duct)
Phép toán tích vô hướng của hai vector được biểu diễn dấu chấm (nên được gọi dot product) và được tính như sau:
v.u = |v||u|cosθ
= v1u1 + v2u2 + … + vnun
Với θ (theta) là góc giữa v, u và n là chiều của không gian.
Từ công thức trên, ta có thể tính được θ:
cosθ = (v.u)/(|v||u|)
θ = arccos(cosθ)
4.  Phép chiếu (Projection)
Một ứng dụng khác của tích  vô hướng  là  tính phép chiếu của  một  vector  này  lên vector khác. 
Tương tự như việc chiếu một vector v thành 2 giá trị x và y lên trục Oxy. (Hình từ wikipedia)
Một vector a được gọi là vector chiếu của v lên u nếu như nó có cùng phương với u và có độ lớn:
|a| = |v|cosθ 
Tổng quát hơn với hai vector bất kì, xét biểu thức:
|a| = |v|cosθ
Với u là vector tạo với v một góc θ, từ công thức:
cosθ = (v.u)/(|v||u|)
Suy ra :
|a| = |v|(v.u)/(|v||u|) = (v.u)/|v|
Vậy ta đã tính được độ lớn của vector v chiếu trên vector u. Từ giá trị |x| này, ta có thể tính được vector x bằng cách nhân với vector đơn vị của u:
a = |a|û
5.  Hiện thực với javascript
Một đối tượng Line được biểu diễn bởi 2 điểm đầu (p1) và cuối (p2) của một đoạn thẳng. Từ hai điểm này, ta có phương thức getVector() để lấy về một đối tượng vector của đoạn thẳng.
Line.prototype.getVector = function() {
 var x = this.p2.x-this.p1.x;
 var y = this.p2.y-this.p1.y;
 return {
  x: x,
  y: y,
 root: this.p1,
 length: Math.sqrt(x*x+y*y)
 };
}
Phương thức update() sau được gọi mỗi khi một đoạn thẳng bị thay đổi:
function update(){
 var v1 = _line1.getVector();
 var v2 = _line2.getVector();
 // normalize vector v2
 v2.dx = v2.x/v2.length;
 v2.dy = v2.y/v2.length;
 // dot product
 var dp = v1.x*v2.x + v1.y*v2.y;
 // length of the projection of v1 on v2
 var length = dp/v2.length;
 // the projection vector of v1 on v2
 var v3 = { 
  x: length*v2.dx,
  y: length*v2.dy,
 };
 // the projection line
 _line3.p2.x = _line3.p1.x+v3.x;
 _line3.p2.y = _line3.p1.y+v3.y;
 // calculate the angle between v1 and v2
 // and convert it from radians into degrees
  _angle = Math.acos(dp/(v1.length*v2.length))*(180/Math.PI);
 _angle = Math.round(_angle*100)/100;
}
Trong phần demo sau,  ta  thực  hiện phép chiếu vector  màu đỏ  lên  vector  xanh  lá. Kết quả của phép chiếu là vector màu xanh lam. Bạn có thể thay đổi hướng và độ lớn của vector bằng cách nhấn nhấn và rê chuột vào đầu mũi tên.

V.  Khoảng cách từ điểm đến đoạn thẳng

Dựa vào phép chiếu từ tích vô hướng (Dot product) của hai vector,  ta có thể tính được khoảng cách từ một điểm đến một đường thẳng, đoạn thẳng.
Bài toán: Tìm khoảng cách từ điểm C đến đoạn thẳng AB.
Giải quyết:
Ta sẽ tính vector chiếu của AC lên AB và gọi là AH. Vì CH vuông góc với AB và khoảng cách từ C đến AB chính là CH. Như vậy ta tính được khoảng cách từ một điểm đến một đường thẳng chứa AB.
Để tìm khoảng cách đến đoạn thẳng, ta cần xác định H có thuộc AB hay không. 
Ta xem lại một chút về tích vô hướng của hai vector. 
Kết quả của tích vô hướng có 3 khoảng giá trị  để ta có thể ước lượng được góc giữa hai vector (bỏ qua chiều âm/dương):
Case 1 (Dot product < 0): Góc giữa hai vector lớn hơn 90 độ. Điểm H nằm ngoài AB.
Case 2 (Dot product = 0): Hai vector vuông góc với nhau (90 độ). Điểm H trùng với A.
Case 3 (Dot product > 0): Góc giữa hai vector nhỏ hơn 90 độ. Điểm H có thể nằm trong AB hoặc không. Điểm H sẽ nằm ngoài AB nếu như độ dài AH > AB
Mã nguồn:
function pointLineDistance(){
 // v1: AC
 // v2: AB
 // v3: AH
 var v1 = _line1.getVector();
 var v2 = _line2.getVector();
 // normalize vector v2
 v2.dx = v2.x/v2.length;
 v2.dy = v2.y/v2.length;
 // dot product
 var dp = v1.x*v2.x + v1.y*v2.y;
 // length of the projection of v1 on v2
 var length = dp/v2.length;
 // the projection vector of v1 on v2
 var v3 = {
  x: length*v2.dx,
  y: length*v2.dy,
 };
 v3.length = Math.sqrt(v3.x*v3.x+v3.y*v3.y);
 // the projection line
 _line3.p2.x = _line3.p1.x+v3.x;
 _line3.p2.y = _line3.p1.y+v3.y;
 var d; // distance
 // d = -1 means H does not lie on AB
 if(dp < 0)
 {
  d = -1;
 }
 else
 {
  if(v3.length > v2.length)
   d = -1;
  else
  {
   var dx = v1.x-v3.x;
   var dy = v1.y-v3.y;
   d = Math.sqrt(dx*dx+dy*dy);
  }
 }
 return d;
}

Xem tiếp: part 2

Không có nhận xét nào:

Đăng nhận xét