Content
Where is located on the same row or column
Where to go horizontally, vertical within the rectangle
Consider extending horizontally, along
Code of main content

Update: 13/06/2014: Game Pokemon completed, you see here.

Before writing this article I had to find references for articles on the algorithm of the big game on google but could not find a clear any article or read but I do not understand =)) (cũng có thể trình độ tìm kiếm và đọc hiểu thuật toán còn quá gà 🙂 ). This article will introduce you to the way they think. They refer to some ideas and build, write code if an error occurs so we're looking for comments, Feedback left for us to build more. Currently tested and found stability in the matrix, are mounted and put on the interface.

The whole of our pokemon are arranged in the matrix model. Here we will consider temporarily on square matrix offline. Perform on cosole which can then be posted on the main interface of the game.

To implement the algorithm of the game I will split the cases from the simple to the complex to find your way (lines that can eat) 2 with pokemon, overall there 3 The TH TH and each will have 2 Small branches are horizontal review, lengthwise. Have you noticed that TH can fully share their pooled, but its not included in the code because I found it to be included in the complex with the if statement eles too much to sort returned the small case like this.

Where is located on the same row or column

TH1: Consider two points on the same line (straight line in the x)
TH2: Two at the same point of a column (y-axis line)
With 2 TH basic, we only need to use a for loop from the beginning to the end of the line and check that there is no communication with each other. If you are then considered complete, if not we will use the TH extended horizontal or vertical to continue. To comment 2 TH we use 2 function is checkLineX(int y1, int y2, int x) and checkLineY(int x1, int x2, int y) respectively in terms of rows and columns terms. The function returns true if the travel is between 2 point, false otherwise go.

Consider and approve the way horizontally, vertical within the rectangle

With 2 point misalignment, column first, then we will consider the extent rectangle that 2 that create, TH is at Z-shaped path.
TH3: Consider and approve the way horizontally within the rectangle

We build content checkRectX(Point p1, Point p2), (check within the rectangle horizontally by 2 p1 and p2 points generated). First we will find out what point coordinates column (and) less (pMinY), larger point (pMaxY). Next we care your son to run large (from left to right), with each column (and) respectively we will consider how 3 small folding lines have not seamlessly using checkLineX function and built checkLineY. If there exists a column y that makes 3 This information demonstrates another way we have traveled between 2 point and we will return the value y is the column. Otherwise returns -1.

TH4: Consider and approve the way vertically
Develop content checkRectY(Point p1, Point p2) TH3 are similar but did consider vertical.

Consider extending horizontally, along

Finally, 2 TH consider expanding if 4 TH on failed. That is, we must consider the way the case U-shaped or L.

TH5: Consider extending horizontally

TH In this we will consider extending horizontally to the left or right by function checkMoreLineX(Point p1, Point p2, int type) In that p1, p2 is 2 Points to check, find your way, type is the type of, will receive the value type is 1 (go to) or -1 (go to the left). First we find out the location column (and) lesser (pMinY), there is a larger point y (pMaxY). Because when considered within the rectangle or on the straight line 2 points are not to be together, so we expanded it out by looking at the left of the column pMaxY.y (column contains the location of the larger column) and to the right of the column pMinY. And any increase or decrease over the column index 2 point (pMinY.x, and) and (pMaxY.x, and) not obstacles. If that is the value of y that makes vertical (green) be proved to have found the way. When this function returns the y value is found, otherwise returns -1. However, before we consider each column so we need to consider the period from pMinY pMaxY (splitter green) there was no information.

TH6: Consider extending vertically
Perform functions checkMoreLineY(Point p1, Point p2, int type) same as above but the browser on each row.

Have you noticed that we absolutely can merge together because it TH3,4,5,6 similar, but here I did not do so because, as mentioned above is required too much if, else to split it out like this TH.

Another thing is that TH 5, 6 can completely contain the TH1,2,3,4 but I still separated for reasons that considering the previous TH1,2,3,4 we will find a fast and shortest path between 2 point (if there), even if combined, we did not find the shortest path if there is a U-shaped path satisfies the previous review.

Finally, we will write the function checkTwoPoint(Point p1, Point p2) to test and find your way around its middle 2 points p1, p2 any. The function returns the object is composed MyLine 2 p1 and p2 points. In line between TH 2 points p1, p2 be the return p1 and p2 MyLine include, in TH path is folded, it returns MyLine include 2 points in the bends.

Code of the main functions built

The following is the code for the function of the algorithm described in the Java language (you can completely switch to another language if understood). A number of other functions such as read function matrix from file, function in the matrix, … then the code you see in complete at the end of post.

Ham and checkLineY checkLineX

// 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;
}

Ham and checkLineY checkLineX

// 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;
}

Ham and checkMoreLineY checkMoreLineX

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;
}

Ham 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;
	}
}

The following project structure (create interface elements are not finished hehe).
The input file with the following contents (number 5 The first is the number of rows, column of the matrix, number 0 is going, 1 the need to travel, 2 obstacles such as, there used to limit the contour path, not too out):
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