Thuật toán của game Lines98 (P.3)

Phần 3. Kiểm tra các viên bi ăn điểm

Có 3 kiểu ăn điểm trong game này:

  1. Kiểu Line: các viên bi cùng màu với số lượng từ 5 trở lên, nằm liên tiếp nhau, thằng hàng hoặc cột hoặc đường chéo.
  2. Kiểu Square: các viên bi cùng màu nằm kề cạnh nhau tạo thành 1 hình chữ nhật đặc có kích thước 2×2 hoặc 2×3.
  3. Kiểu Block: các viên bi cùng màu nằm kề cạnh nhau với số lượng từ 7 trở lên, tạo thành hình dạng bất kì.

Chúng ta sẽ xem xét lần lượt cả 3 kiểu trên:

1. Line: Dễ thấy là ta chỉ cần kiểm tra tất cả các viên bi, với mỗi viên bi B, xét theo 4 phương, xem có phương nào xét được hơn 5 viên cùng màu (kể cả viên B). Hàm kiểm tra có vẻ như nguyên mẫu là: PointList checkLines(int** a); checkLines sẽ trả về một danh sách tọa độ các viên bi ăn điểm, nếu danh sách rỗng (độ dài bằng 0) tức là ko có ăn điểm. Tuy nhiên, có một chi tiết giúp ta tiết kiệm thời gian cho hàm checkLines. Đó là, khi người chơi di chuyển 1 viên bi từ ô (i1, j1) đến (i2, j2) thì chắc chắn danh sách các viên bi ăn điểm (nếu có) sẽ chứa (i2, j2). Vậy nên, ta chỉ cần xét tại viên bi (i2, j2) và các ô kề nó theo 4 phương.

#define EAT_BALL_LINE_NUM 5

PointList checkLines(int** a, int iCenter, int jCenter)
{
	PointList lines;

	int u[] = {0, 1, 1, 1};
	int v[] = {1, 0, -1, 1};
	int i, j, k, t, count;
	count = 0;

	for (t = 0; t < 4; t++)
	{
		k = 0;
		i = iCenter;
		j = jCenter;
		while (1)
		{
			i += u[t];
			j += v[t];
			if (!isInside(i, j))
				break;
			if (a[i][j] != a[iCenter][jCenter])
				break;
			k++;
		}
		i = iCenter;
		j = jCenter;
		while (1)
		{
			i -= u[t];
			j -= v[t];
			if (!isInside(i, j))
				break;
			if (a[i][j] != a[iCenter][jCenter])
				break;
			k++;
		}
		k++;
		if (k >= EAT_BALL_LINE_NUM)
		{
			while (k-- > 0)
			{
				i += u[t];
				j += v[t];
				if (i != iCenter || j != jCenter)
				{
					lines.point[count].x = i;
					lines.point[count].y = j;
					count++;
				}
			}
		}
	}

	if (count > 0)
	{
		lines.point[count].x = iCenter;
		lines.point[count].y = jCenter;
		lines.len = count + 1;
	}
	else
	{
		lines.len = 0;
	}
	return lines;
}

2. Square: Cũng giống như checkLines, ta sẽ có 1 ô trung tâm mà chắc chắn danh sách ăn điểm chứa ô đó. Xem hình dưới đây:

Ô trung tâm đánh dấu X, 8 ô xung quanh được đánh số. Dễ thấy danh sách các ô có thể ăn điểm là:

{X, 1, 2, 3, 4, 5}, {X, 3, 4, 5, 6, 7}, {X, 5, 6, 7, 0, 1}, {X, 7, 0, 1, 2, 3}, {X, 1, 2, 3}, {X, 3, 4, 5}, {X, 5, 6, 7}, {X, 7, 0, 1}

Từ đó có code sau:

PointList checkSquares(int** a, int iCenter, int jCenter)
{
	PointList squares;

	int u[] = {-1, 0, 1, 1, 1, 0, -1, -1};
	int v[] = {-1, -1, -1, 0, 1, 1, 1, 0};
	int mark[] = {0, 0, 0, 0, 0, 0, 0, 0};
	int eatRect[][5] =
	{
		{1, 2, 3,  4,  5},
		{3, 4, 5,  6,  7},
		{5, 6, 7,  0,  1},
		{7, 0, 1,  2,  3},
		{1, 2, 3, -1, -1},
		{3, 4, 5, -1, -1},
		{5, 6, 7, -1, -1},
		{7, 0, 1, -1, -1},
	};
	int color = a[iCenter][jCenter];
	int x, y, k, i, j;

	squares.len = 0;

	for (k = 0; k < 8; k++)
	{
		x = iCenter + u[k];
		y = jCenter + v[k];
		if (isInside(x, y) && a[x][y] == color)
		{
			mark[k] = 1;
		}
	}

	for (k = 0; k < 8; k++)
	{
		x = k <= 3 ? 5 : 3;
		j = 1;
		for (i = 0; i < 5; i++)
		{
			if (!mark[eatRect[k][i]])
			{
				j = 0;
				break;
			}
		}
		if (j)
		{
			squares.len = 1;
			squares.point[0].x = iCenter;
			squares.point[0].y = jCenter;
			for (i = 0; i < x; i++)
			{
				squares.point[squares.len].x = iCenter + u[eatRect[k][i]];
				squares.point[squares.len].y = jCenter + v[eatRect[k][i]];
				squares.len++;
			}
			return squares;
		}
	}

	return squares;
}

3. Block: Nếu đã biết cách loang (theo chiều rộng hoặc sâu) thì quá đơn giản. Ở đây, tôi chọn loang theo chiều rộng:

#define EAT_BALL_BLOCK_NUM 7

PointList checkBlocks(int** a, int iCenter, int jCenter)
{
	PointList blocks;

	int queuei[BOARD_COL * BOARD_ROW];
	int queuej[BOARD_COL * BOARD_ROW];

	int mark[BOARD_COL][BOARD_ROW];

	int u[] = {1, 0, -1, 0};
	int v[] = {0, 1, 0, -1};

	int i, j, color, x, y, xx, yy, k;
	int fist = 0, last = 0;

	for (i = 0; i < BOARD_COL; i++)
		for (j = 0; j < BOARD_ROW; j++)
			mark[i][j] = 1;

	mark[iCenter][jCenter] = 0;
	color = a[iCenter][jCenter];

	queuei[fist] = iCenter;
	queuej[fist] = jCenter;

	blocks.len = 1;

	blocks.point[0].x = iCenter;
	blocks.point[0].y = jCenter;

	while (fist <= last)
	{
		x = queuei[fist];
		y = queuej[fist];
		fist++;
		for (k = 0; k < 4; k++)
		{
			xx = x + u[k];
			yy = y + v[k];
			if (!isInside(xx, yy)) continue;
			if (mark[xx][yy] && a[xx][yy] == color)
			{
				last++;
				queuei[last] = xx;
				queuej[last] = yy;
				mark[xx][yy] = 0;
				blocks.point[blocks.len].x = xx;
				blocks.point[blocks.len].y = yy;
				blocks.len++;
			}
		}
	}

	if (blocks.len < EAT_BALL_BLOCK_NUM)
	{
		blocks.len = 0;
	}

	return blocks;
}
Advertisements

4 thoughts on “Thuật toán của game Lines98 (P.3)

  1. Anh ơi, anh có mã nguồn đầy đủ của trò Lines98 viết trên C++ không ạh ? Hiện em rất cần mã nguồn đầy đủ của trò này vì có liên quan đến đồ án tốt nghiệp. Chân thành cảm ơn anh !

    Like

  2. Anh ơi cho em hỏi ở checklines, vòng while có 2 cái if. Cái if đầu tiên hàm isinside(i,j) là xet cái gì vậy anh. Còn cái if còn lại là xét cái gì vậy anh. Thanks

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s