Nội dung
Trường hợp cùng nằm trên một hàng hoặc cột
Trường hợp đi theo chiều ngang, dọc trong phạm vi hình chữ nhật
Xét mở rộng theo chiều ngang, dọc
Code các hàm chính

Update: 13/06/2014: Game pokemon đã hoàn thành, các bạn xem tại đây.

Trước khi viết bài viết này mình đã có tìm tham khảo các bài viết về thuật toán của game trên ông lớn google nhưng không tìm thấy một bài viết rõ ràng nào cả hoặc có nhưng mình đọc không hiểu =)) (cũng có thể trình độ tìm kiếm và đọc hiểu thuật toán còn quá gà 🙂 ). Bài viết này sẽ giới thiệu tới các bạn cách mà mình nghĩ ra. Do mình tham khảo một số ý tưởng và tự xây dựng, viết code nên nếu có lỗi xảy ra rất mong các bạn góp ý, phản hồi lại để chúng ta cùng xây dựng thêm. Hiện tại đã test và thấy ổn trên ma trận, đang gắn và đưa lên giao diện.

Toàn bộ các pokemon của chúng ta được sắp xếp theo mô hình của ma trận. Ở đây tạm thời chúng ta sẽ xét trên ma trận vuông nhé. Thực hiện trên cosole rồi từ đó có thể đưa lên giao diện chính của game.

Để thực hiện giải thuật của game mình sẽ chia làm các trường hợp từ đơn giản đến phức tạp để tìm đường đi (đường mà có thể ăn) 2 con pokemon, tổng quan thì có 3 TH chính và mỗi TH sẽ có 2 nhánh nhỏ là xét theo chiều ngang, chiều đọc. Các bạn chú ý là các TH mình chia hoàn toàn có thể gộp lại, tuy nhiên mình không gộp vì trong quá trình code mình thấy khi gộp vào nó trở nên phức tạp với những lệnh if eles quá nhiều để phân loại trở về các trường hợp nhỏ như thế này.

Trường hợp cùng nằm trên một hàng hoặc cột

TH1: Hai điểm xét cùng thuộc một hàng (đường thẳng theo trục x)
TH2: Hai điểm xét cùng thuộc một cột (đường thẳng theo trục y)
Với 2 TH cơ bản này thì chúng ta chỉ cần dùng vòng lặp for từ điểm đầu đến điểm cuối và kiểm tra xem đường thẳng đó có thông với nhau được không. Nếu được thì coi như xong, nếu không được ta sẽ sử dụng các TH mở rộng theo chiều ngang hoặc dọc để làm tiếp. Để xét 2 TH này chúng ta sử dụng 2 hàm là checkLineX(int y1, int y2, int x) và checkLineY(int x1, int x2, int y) tương ứng là xét theo hàng và xét theo cột. Hàm trả về true nếu đi được giữa 2 điểm, false nếu không đi được.

Xét duyệt các đường đi theo chiều ngang, dọc trong phạm vi hình chữ nhật

Với 2 điểm không thẳng hàng, cột thì trước tiên ta sẽ xét trong phạm vi hình chữ nhật mà 2 điểm đó tạo ra, đây là TH xét đường đi hình chữ Z.
TH3: Xét duyệt các đường đi theo chiều ngang trong phạm vi hình chữ nhật

Ta xây dựng hàm checkRectX(Point p1, Point p2), (kiểm tra trong phạm vi hình chữ nhật theo chiều ngang mà 2 điểm p1 và p2 tạo ra). Trước tiên chúng ta sẽ tìm xem điểm nào có tọa độ cột (y) nhỏ hơn (pMinY), điểm nào lớn hơn (pMaxY). Tiếp theo chúng ta cho y chạy tử bé đến lớn (từ trái sang phải), với mỗi cột (y) tương ứng chúng ta sẽ xét xem 3 đường thẳng nhỏ gấp khúc có liền mạch không bằng cách sử dụng hàm checkLineX và checkLineY đã xây dựng. Nếu tồn tại một cột y nào đó mà làm cho 3 đường này thông nhau chứng tỏ chúng ta có đường đi được giữa 2 điểm và ta sẽ trả về giá trị y là cột đó. Nếu không thì trả về -1.

TH4: Xét duyệt các đường đi theo chiều dọc
Xây dựng hàm checkRectY(Point p1, Point p2) tuơng tự như TH3 đã làm nhưng xét theo chiều dọc.

Xét mở rộng theo chiều ngang, dọc

Cuối cùng là 2 TH xét mở rộng ra nếu 4 TH trên đều thất bại. Tức là chúng ta phải xét đến trường hợp đường đi có hình dạng chữ U hoặc chữ L.

TH5: Xét mở rộng theo chiều ngang

Trong TH này chúng ta sẽ xét mở rộng chiều ngang về phía bên trái hoặc bên phải bằng hàm checkMoreLineX(Point p1, Point p2, int type) Trong đó p1, p2 là 2 điểm cần kiểm tra, tìm đường đi, type là loại, type sẽ nhận giá trị là 1 (đi về phải) hoặc -1 (đi về trái). Trước tiên chúng ta cũng tìm xem điểm có cột (y) nào nhỏ hơn (pMinY), điểm nào có y lớn hơn (pMaxY). Vì khi xét trong phạm vi hình chữ nhật hoặc trên đường thẳng thì 2 điểm đều không đến được với nhau, do đó chúng ta mở rộng nó ra bằng cách xét về bên trái từ cột pMaxY.y (cột của điểm chứa cột lớn hơn) và về bên phải từ cột pMinY. Và cứ tăng hoặc giảm dần chỉ số cột lên khi 2 điểm (pMinY.x, y) và (pMaxY.x, y) không phải chướng ngại vật. Nếu gặp giá trị y nào mà làm cho đường thẳng đứng (màu xanh lục) được thông thì chứng tỏ đã tìm thấy đường đi. Khi đó hàm trả về giá trị là cột y tìm được, nếu không thì trả về -1. Tuy nhiên trước khi xét từng cột như vậy chúng ta cần xét đoạn từ pMinY đến pMaxY (doạn màu xanh lá) có thông không đã.

TH6: Xét mở rộng theo chiều dọc
Thực hiện hàm checkMoreLineY(Point p1, Point p2, int type) tương tự như trên nhưng duyệt theo từng hàng.

Các bạn chú ý là ta hoàn toàn có thể ghép các TH3,4,5,6 vào với nhau vì nó tương tự nhau, nhưng ở đây mình không làm vậy vì như nói ở trên là cần quá nhiều if, else để phân nhỏ nó ra các TH như thế này.

Một điều nữa là TH 5, 6 hoàn toàn có thể chứa đựng cả TH1,2,3,4 nhưng mình vẫn tách ra vì lý do là khi xét các TH1,2,3,4 trước thì chúng ta sẽ tìm được đường đi nhanh và ngắn nhất giữa 2 điểm (nếu có), còn nếu gộp lại thì chúng ta lại không tìm được đường đi ngắn nhất nếu có đường hình chữ U thoả mãn được xét trước.

Cuối cùng chúng ta sẽ viết hàm checkTwoPoint(Point p1, Point p2) để kiểm tra và tìm đường đi gữa 2 điểm p1, p2 bất kỳ. Hàm sẽ trả về đối tượng là MyLine gồm 2 điểm p1 và p2. Trong TH đường thẳng giữa 2 điểm p1, p2 được thông thì trả về MyLine gồm p1 và p2, trong TH đường đi là gấp khúc thì trả về MyLine gồm 2 điểm ở đoạn gấp khúc.

Code các hàm chính đã xây dựng

Dưới đây sẽ là code các hàm chính đã nêu của thuật toán trên ngôn ngữ Java (các bạn hoàn toàn có thể chuyển sang ngôn ngữ khác nếu đã hiểu). Một số hàm khác như hàm đọc ma trận từ file, hàm in ma trận, … thì các bạn xem thêm tại code hoàn chỉ ở phía cuối bài.

Hàm checkLineX và checkLineY

// check with line x, from column y1 to y2
private boolean checkLineX(int y1, int y2, int x) {
	// find point have column max and min
	int min = Math.min(y1, y2);
	int max = Math.max(y1, y2);
	// run column
	for (int y = min; y <= max; y++) {
		if (matrix[x][y] == barrier) { // if see barrier then die
			System.out.println("die: " + x + "" + y);
			return false;
		}
		System.out.println("ok: " + x + "" + y);
	}
	// not die -> success
	return true;
}

private boolean checkLineY(int x1, int x2, int y) {
	int min = Math.min(x1, x2);
	int max = Math.max(x1, x2);
	for (int x = min; x <= max; x++) {
		if (matrix[x][y] == barrier) {
			System.out.println("die: " + x + "" + y);
			return false;
		}
		System.out.println("ok: " + x + "" + y);
	}
	return true;
}

Hàm checkLineX và checkLineY

// check in rectangle
private int checkRectX(Point p1, Point p2) {
	// find point have y min and max
	Point pMinY = p1, pMaxY = p2;
	if (p1.y > p2.y) {
		pMinY = p2;
		pMaxY = p1;
	}
	for (int y = pMinY.y + 1; y < pMaxY.y; y++) {
		// check three line
		if (checkLineX(pMinY.y, y, pMinY.x)
				&& checkLineY(pMinY.x, pMaxY.x, y)
				&& checkLineX(y, pMaxY.y, pMaxY.x)) {

			System.out.println("Rect x");
			System.out.println("(" + pMinY.x + "," + pMinY.y + ") -> ("
					+ pMinY.x + "," + y + ") -> (" + pMaxY.x + "," + y
					+ ") -> (" + pMaxY.x + "," + pMaxY.y + ")");
			// if three line is true return column y
			return y;
		}
	}
	// have a line in three line not true then return -1
	return -1;
}

private int checkRectY(Point p1, Point p2) {
	// find point have y min
	Point pMinX = p1, pMaxX = p2;
	if (p1.x > p2.x) {
		pMinX = p2;
		pMaxX = p1;
	}
	// find line and y begin
	for (int x = pMinX.x + 1; x < pMaxX.x; x++) {
		if (checkLineY(pMinX.x, x, pMinX.y)
				&& checkLineX(pMinX.y, pMaxX.y, x)
				&& checkLineY(x, pMaxX.x, pMaxX.y)) {
			
			System.out.println("Rect y");
			System.out.println("(" + pMinX.x + "," + pMinX.y + ") -> (" + x
					+ "," + pMinX.y + ") -> (" + x + "," + pMaxX.y
					+ ") -> (" + pMaxX.x + "," + pMaxX.y + ")");
			return x;
		}
	}
	return -1;
}

Hàm checkMoreLineX và checkMoreLineY

private int checkMoreLineX(Point p1, Point p2, int type) {
	// find point have y min
	Point pMinY = p1, pMaxY = p2;
	if (p1.y > p2.y) {
		pMinY = p2;
		pMaxY = p1;
	}
	// find line and y begin
	int y = pMaxY.y;
	int row = pMinY.x;
	if (type == -1) {
		y = pMinY.y;
		row = pMaxY.x;
	}
	// check more
	if (checkLineX(pMinY.y, pMaxY.y, row)) {
		while (matrix[pMinY.x][y] != barrier
				&& matrix[pMaxY.x][y] != barrier) {
			if (checkLineY(pMinY.x, pMaxY.x, y)) {
				
				System.out.println("TH X " + type);
				System.out.println("(" + pMinY.x + "," + pMinY.y + ") -> ("
						+ pMinY.x + "," + y + ") -> (" + pMaxY.x + "," + y
						+ ") -> (" + pMaxY.x + "," + pMaxY.y + ")");
				return y;
			}
			y += type;
		}
	}
	return -1;
}

private int checkMoreLineY(Point p1, Point p2, int type) {
	Point pMinX = p1, pMaxX = p2;
	if (p1.x > p2.x) {
		pMinX = p2;
		pMaxX = p1;
	}
	int x = pMaxX.x;
	int col = pMinX.y;
	if (type == -1) {
		x = pMinX.x;
		col = pMaxX.y;
	}
	if (checkLineY(pMinX.x, pMaxX.x, col)) {
		while (matrix[x][pMinX.y] != barrier
				&& matrix[x][pMaxX.x] != barrier) {
			if (checkLineX(pMinX.y, pMaxX.y, x)) {
				System.out.println("TH Y " + type);
				System.out.println("(" + pMinX.x + "," + pMinX.y + ") -> ("
						+ x + "," + pMinX.y + ") -> (" + x + "," + pMaxX.y
						+ ") -> (" + pMaxX.x + "," + pMaxX.y + ")");
				return x;
			}
			x += type;
		}
	}
	return -1;
}

Hàm checkTwoPoint

private MyLine checkTwoPoint(Point p1, Point p2) {
	// check line with x
	if (p1.x == p2.x) {
		if (checkLineX(p1.y, p2.y, p1.x)) {
			return new MyLine(p1, p2);
		}
	}
	// check line with y
	if (p1.y == p2.y) {
		if (checkLineY(p1.x, p2.x, p1.y)) {
			return new MyLine(p1, p2);
		}
	}

	int t = -1; // t is column find

	// check in rectangle with x
	if ((t = checkRectX(p1, p2)) != -1) {
		return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
	}

	// check in rectangle with y
	if ((t = checkRectY(p1, p2)) != -1) {
		return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
	}
	// check more right
	if ((t = checkMoreLineX(p1, p2, 1)) != -1) {
		return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
	}
	// check more left
	if ((t = checkMoreLineX(p1, p2, -1)) != -1) {
		return new MyLine(new Point(p1.x, t), new Point(p2.x, t));
	}
	// check more down
	if ((t = checkMoreLineY(p1, p2, 1)) != -1) {
		return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
	}
	// check more up
	if ((t = checkMoreLineY(p1, p2, -1)) != -1) {
		return new MyLine(new Point(t, p1.y), new Point(t, p2.y));
	}
	return null;
}

Class MyLine

package nguyenvanquan7826;
import java.awt.Point;
public class MyLine {
	public Point p1;
	public Point p2;

	public MyLine(Point p1, Point p2) {
		super();
		this.p1 = p1;
		this.p2 = p2;
	}

	public String toString() {
		String string = "(" + p1.x + "," + p1.y + ") and (" + p2.x + "," + p2.y + ")";
		return string;
	}
}

Cấu trúc project như sau (phần giao diện đang tạo chưa xong hehe).
File input có nội dung như sau (số 5 đầu tiên là số hàng, số cột ma trận, số 0 là được đi, 1 là cần đi và đến, 2 là chưóng ngại vậy, ở đây có sử dụng đường bao quanh để giới hạn đường đi, không bị đi quá ra ngoài):
5
2 2 2 2 2 2 2

2 0 0 0 0 0 2
2 0 1 0 0 0 2
2 0 2 2 0 0 2
2 0 0 0 1 0 2
2 0 0 0 0 2 2

2 2 2 2 2 2 2

Code Class Algorithm in pokemon game