内容
例都在同一行或列
去哪儿水平, 在矩形内的垂直
考虑水平延伸, 纵
主要功能代码

更新: 13/06/2014: 口袋妖怪游戏完成, 你在这里看到.

在写这篇文章我必须找到他的算法，对大型游戏谷歌文章引用，但找不到一个明确的文章都还是有，但我读不懂=)) (cũng có thể trình độ tìm kiếm và đọc hiểu thuật toán còn quá gà 🙂 ). 本文将介绍给大家，我认为出路. 他们提到的一些想法和构建, 编写代码，所以如果我们正在寻找的建议出现错误, 回应我们，并建立更多. 在基体中目前测试，发现故障, 连接并张贴在接口上.

我们整个口袋妖怪排列在矩阵模型. 在这里，我们会暂时考虑方阵NHE. 执行在控制台上，并从那里可以采取了游戏的主接口.

为了实现他的比赛的算法将分成情况下，从简单到复杂的找到自己的方式 (糖可以吃) 2 CON口袋妖怪, 概述有 3 TH TH自己的，每个都会有 2 小树枝是横向审查, 纵. 你有没有注意到你的TH可以充分分享汇集, 但是我不总值，因为在他的代码视为归入它变得复杂了太多的ELES if语句进行排序返回小的情况下这样的.

例都在同一行或列

TH1: 两个在相同的点在一行 (在x直线)
TH2: 两个在同一点的列 (y轴线)
同 2 TH此基础上，我们只需要使用一个循环从开始到结束，检查通信线路一起不. 如果他们认为完成, 如果没有，我们将用TH扩展水平或垂直下一步. 审查 2 我们使用TH 2 功能是 checkLineX(INT Y1, INT Y2, INT x) 和 checkLineY(INT X1, INT X2, INTÿ) 分别在货物的术语和在列方面. 如果行程之间的函数返回true 2 点, 否则为false去.

批准的方式水平, 在矩形内的垂直

同 2 点错位, 第一列，我们将看看在矩形内的 2 创建, TH是在Z形路径.
TH3: 的方式批准水平的矩形范围内

我们建立下巴 checkRectX(点P1, 点P2), (检查横长方形的程度，这 2 生成p1和p2点). 首先，我们将找出点坐标列 (和) 少 (PMI), 稍大点 (pMaxY). 接下来，我们给予极大的关心运行婴儿死亡 (从左至右), 每列 (和) 分别为，我们将考虑如何 3 小折叠线都没有无缝使用checkLineX功能和内置checkLineY. 如果存在医疗列，不知怎的，使 3 连接这种方式，我们可以证明是之间的路 2 我将返回点和y是该列的值. 否则返回 -1.

TH4: 审批垂直路径
建设下巴 checkRectY(点P1, 点P2) TH3相似，但没有发表评论，垂直.

考虑水平延伸, 纵

最后， 2 TH考虑是否扩大 4 TH上失败. 也就是说，我们必须考虑到这样的情况下，U形或L.

TH5: 考虑水平延伸

，在这种情况下，我们会考虑向左或向右功能水平延伸 checkMoreLineX(点P1, 点P2, 整型) 在这种P1, P2是 2 检查点, 找到你的方式, 型是类型, 将获得的值类型 1 (去到) 或 -1 (向左走). 首先，我们找出与列点 (和) 但小 (PMI), 有较大的点y (pMaxY). 因为当矩形内或上的直线被认为 2 点不在一起, 因此，我们扩展它通过查看列pMaxY.y的左侧 (列包含较大的列的位置) 和对从柱pMinY右. 同时，任何增加或减少列索引时 2 点 (pMinY.x, 和) 和 (pMaxY.x, 和) 不是障碍. 如果您遇到任何医用价值，使垂直 (绿) 如何证明查找方式. 当该函数返回y中列的值, 否则返回 -1. 但是，你考虑每列此之前，我们需要考虑pMinY pMaxY期 (绿色分配器) 尚未通知.

TH6: 在垂直延伸
履行职能 checkMoreLineY(点P1, 点P2, 整型) 与上述相同，但浏览每个行.

你有没有注意到，我们可以完全融合在一起，因为它TH3,4,5,6相似, 但在这里我没有这样做，因为如上所述是必要的，如果过多, 否则分裂出来这样TH.

另一种是TH 5, 6 绝对可以同时包含TH1,2,3,4但我还是分开的，因为当TH1,2,3,4检讨在此之前，我们会发现快之间的最短路线 2 点 (如果有), 即使合并，我们没有发现的最短路径，如果有一个U形通道满足一次审​​查.

最后，我们将编写一个函数checkTwoPoint(点P1, 点P2) 测试并发现原来的你的方式 2 点P1, P2任. 该函数将返回的对象是MYLINE包括 2 p1和p2点. 在这两者之间TH线 2 点P1, P2可以在收益包括P1和P2 MYLINE, 在TH路径折叠，则返回MYLINE包括 2 点弯.

守则主要功能内置

这里将在Java语言中提到的算法代码的主要功能 (你绝对可以切换到不同的语言，如果理解). 从文件中读取一些其它功能矩阵功能, 打印功能矩阵, … 那么你在代码完成看到帖子的结尾.

火腿checkLineX和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;
}

火腿checkLineX和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;
}

火腿checkMoreLineX和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;
}

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

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

项目结构如下： (界面元素创建未完嘿嘿).
输入文件具有以下内容 (号码 5 首先是行数, 矩阵列, 号码 0 是去, 1 是需要旅游, 2 如障碍, 在这里可以使用选框限制道路, 没有被发送出去):
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

代码类算法中的口袋妖怪游戏