Chủ nhật, ngày 11 tháng 12 năm 2016

GameDev – Áp dụng AI trong game Rắn Săn Mồi – Part 2 (end)

Ngày đăng: 4/6/2012, 8:29:47PM | Lượt xem: 1,928
Hot!

Ta đã tìm hiểu và vạch ra những việc cần làm trong phần trước. Việc còn lại là cài đặt lại trên nền Canvas với ngôn ngữ javascript, và bạn có thể sẽ thấy thích thú với thành quả của mình.

Cute_snake_cartoonTa đã tìm hiểu và vạch ra những việc cần làm trong phần trước. Việc còn lại là cài đặt lại trên nền Canvas với ngôn ngữ javascript, và bạn có thể sẽ thấy thích thú với thành quả của mình.

Demo và Sourcecode

Xem Demo.

Sourcecode.

Canvas - AI Snake Game

Xây dựng một lớp Queue dựa trên mảng

Việc sử dụng thuật toán Breadth First Search (BFS) cần phải sử dụng một cấu trúc dữ liệu kiểu hàng đợi (Queue) để làm tập Open.
Định nghĩa:
“Hàng đợi (tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước
Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao tác thêm vào và lấy một đối tượng ra khỏi hàng đợi được gọi lần lượt là ‘enqueue’ và ‘dequeue’. Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.”
(Wikipedia);
Trong javascript, ta có thể dễ dàng tạo một lớp Queue nhờ những phương thức sẵn có của mảng:

function Queue(){
	var data  = [];

	this.clear = function(){
		data.length = 0;
	}

	this.getLength = function(){
		return data.length;
	}

	this.isEmpty = function(){
		return data.length == 0;
	}

	this.enqueue = function(item){
		data.push(item);
	}

	this.dequeue = function(){
		if (data.length == 0) return undefined;
		return data.shift();
	}

	this.peek = function(){
		return (data.length > 0 ? data[0] : undefined);
	}
}

Cài đặt thuật toán Breadth First Search

Tốc độ tìm đường đi trong game này rất quan trọng vì càng lên level cao, việc di chuyển của con rắn có thể lên tới 60 ô trong một giây (tương ứng FPS = 60) hay thậm chí có thể cao hơn. Nếu tốc độ quá chậm có thể khiến game bị “đứng” mỗi khi thuật toán này được sử dụng và tệ hơn là con rắn sẽ lao đầu vào tường như một chiếc xe mất phanh.

Nếu khi test bạn thấy tốc độ chưa được ưng ý, đặc biệt trên các máy yếu, hãy thử làm chậm tốc độ game lại và tăng thêm độ phức tạp của bản đồ. Một cách khác nữa là giảm kích thước bản đồ để giảm không gian tìm kiếm. Tuy nhiên bạn không cần quá lo lắng về tốc độ tìm đường, theo thử nghiệm của tôi thì với FPS = 1000 và độ dài rắn lên tới 100, game vẫn chạy ổn và con rắn không để mất một “viên kẹo” nào.

Để cài đặt thuật toán này, trước tiên tôi tạo một lớp Node dùng để lưu giữ thông tin của một phần tử trong mảng hai chiều. Ta cần hai thuộc tính x,y để lưu lại chính vị trí dòng và cột của Node trong mảng. Như vậy ta có thể xác định được ngay vị trí của một đối tượng Node trong mảng mà không cần lặp qua mảng để tìm kiếm (do Node được lưu trong Queue).

function Node(x,y,value){
	this.x = x;
	this.y = y;
	this.value = value;
	this.visited = false;
}

Mặc dù dễ hiểu nhưng cách này sẽ khiến việc tìm được chưa đạt được tốc độ mà tôi mong muốn do phải so sánh 2 thuộc tính value và visited để xác định một Node đã được “ghé thăm” chưa. Vì vậy, tôi sẽ bỏ đi thuộc tính visited và tận dụng thuộc tính value. Ta có lớp Node mới:

var BLANK = 0;
var WALL = 1;
var SNAKE = 2;
var VISITED = 3;

function Node(x,y,value){
	this.x = x;
	this.y = y;
	this.value = value;
}

Vòng lặp chính của thuật toán:

// ...
// add the start node to queue
open.enqueue(start);
// the main loop

while(!open.isEmpty())
{
	node = open.dequeue();
	if(node)
	{
		if(node.x==goal.x && node.y==goal.y)
		{
			return getSolution(node);
		}
		genMove(node);
	}
	else
		break;
}
// ...

Phương thức sinh các nước đi tiếp theo tại vị trí đầu rắn:

// generate next states by adding neighbour nodes
function genMove(node)
{
	if (node.x < cols - 1)
		addToOpen(node.x + 1, node.y, node);
	if (node.y < rows - 1)
		addToOpen(node.x, node.y + 1, node);
	if (node.x > 0)
		addToOpen(node.x - 1, node.y, node);
	if (node.y > 0)
		addToOpen(node.x, node.y - 1, node);
}

Phương thức thêm một nước đi vào tập Open, ta chỉ cần thêm các node rỗng (BLANK). Khi thêm vào, ta đặt lại trạng thái của node là VISITED để không thêm nó vào lần thứ 2:

function addToOpen(x,y, previous)
{
	var node = nodes[x][y];

	if (node.value==BLANK)
	{
		// mark this node as visited to avoid adding it multiple times
		node.value = VISITED;
		// store the previous node
		// so that we can backtrack to find the optimum path
		// (by using the getSolution() method)
		node.previous = previous;
		open.enqueue(node);
	}
}

Phương thức dùng để lấy đường đi sau khi tìm được vị trí của node đích. Ta chỉ cần backtracking các node dựa vào thuộc tính previous của các node:

function getSolution(p)
{
	var nodes = [];
	nodes.push(p);
	while (p.previous)
	{
		nodes.push(p.previous);
		p = p.previous;
	}
	return nodes;
}

Như vậy, khi đã có đường đi đến đích, ta chỉ cần cho rắn di chuyển từng ô dựa theo đường đi này cho đến hết độ dài.

Di chuyển đối tượng theo đường đi

Trong lớp Snake, tôi tạo một biến autoMoving để xác định quyền điều khiển đối tượng thuộc về người chơi hay tự động (máy tính). Mỗi khi một viên thức ăn mới tạo ra, ta sẽ cập nhật lại đường đi mới cho con rắn. Chỉ cần thêm một dòng lệnh vào trong phương thức createFood().

function createFood() {
	var x = Math.floor(Math.random()*_cols);
	var y;
	do {
		y = Math.floor(Math.random()*_rows);
	} while(_walls[x][y] || _comSnake.contain(x, y) || _playerSnake.contain(x, y));

	_food = {x: x, y: y};
	// find new path for the com player
	_comSnake.setPath(_bfs.findPath(_comSnake.data,_comSnake.getHead(),_food));
}

Trong lớp Snake, ta cần tạo một phương thức mới giúp rắn di chuyển tự động. Bởi vì việc di chuyển của rắn dựa vào bốn hướng (do còn cho phép người chơi điều khiển), ta có thể xác định hướng di chuyển dựa vào vị trí của ô cũ và mới của đầu rắn:

// Snake
this.move = function(){
	if(this.stepIndex>0)
	{
		this.stepIndex--;
		var newPos = this.path[this.stepIndex];
		if(newPos.x<this.data[0].x)
			this.direction = LEFT;
		else if(newPos.x>this.data[0].x)
			this.direction = RIGHT;
		else if(newPos.y<this.data[0].y)
			this.direction = UP;
		else if(newPos.y>this.data[0].y)
			this.direction = DOWN;
	}
};

Vòng lặp chính của game

Phần quan trọng nhất giúp game vận hành, phần này khá đơn giản và được chú thích nên tôi cũng không cần giải thích thêm.

function update() {
	if(!_running)
		return;

	_playerSnake.handleKey(_pressedKey);
	// player has priority to eat
	var ret =_playerSnake.update(_walls,_food);
	if(ret==1) // player eated the food
	{
		_scores += _level*2;
		createFood();
	}
	else if(ret==2) // player collided with something
	{
		if(_scores>=0)
		{
			_scores -= _level*2;
			if(_scores<0)
				_scores = 0;
		}
		endGame();
		return;
	}else{
		if(!_comSnake.path)
			_comSnake.setPath(_bfs.findPath(_comSnake.data,_comSnake.getHead(),_food),_food);

		ret = _comSnake.update(_walls,_food);
		if(ret==1) // com player eated the food
			createFood();
	}
	draw();
	// Player's snake reached the maximum length
	// so the game will start the next level
	if(_playerSnake.data.length==MAX_PLAYER_LENGTH)
	{
		// go to next level
		_level++;
		_scores += _level*100;
		_running = false;
		_context.save();
		_context.fillStyle = "rgba(0,0,0,0.2)";
		_context.fillRect(0,0,WIDTH,HEIGHT);
		_context.restore();
		_context.fillStyle = "red";
		_context.textAlign = "center";
		_context.fillText("Press Enter to start the next level",WIDTH/2,HEIGHT/2);
	}else if(_comSnake.data.length==MAX_COM_LENGTH)
	{
		endGame();
		return;
	}
}

YinYangIt’s Blog

http://yinyangit.wordpress.com
 Chia sẻ qua: 
Hot!
Ý kiến bạn đọc

These items will be permanently deleted and cannot be recovered. Are you sure?

Gallery

image

Maecenas viverra rutrum pulvinar

Maecenas viverra rutrum pulvinar! Aenean vehicula nulla sit amet metus aliquam et malesuada risus aliquet. Vestibulum rhoncus, dolor sit amet venenatis porta, metus purus sagittis nisl, sodales volutpat elit lorem…

Read more

Text Links

Thiết kế logo chuyên nghiệp Insky
DAFABET
W88 w88b.com/dang-ky-tai-khoan-w88
W88
Copyright © 2011 - 2012 vietshare.vn by phamkhuong102@gmail.com doanhkisi2315@gmail.com. All rights reserved.