コンテンツ
ケースには、同じ行または列にあります
どこに水平方向に行きます, 長方形内の垂直
水平方向に延びる考えてみましょう, 毒性
キーの機能コード

アップデート: 13/06/2014: ポケモンゲームが完成します, あなたはここを参照してください.

この記事を書く前に、私は=大物Googleで自分のアルゴリズムに関する記事の参照を見つけることがあったが、そこにすべてのまたはで明確な記事を見つけることができませんでしたが、私は理解していない読み取り)) (cũng có thể trình độ tìm kiếm và đọc hiểu thuật toán còn quá gà 🙂 ). この記事はあなたに私が考える方法をご紹介します. 彼らはいくつかのアイデアとビルドを参照してください。, コー​​ドを記述するため、エラーが発生した場合、我々は提案を探しています, 私たちに応答し、より多くを構築. 行列で現在テストされ、見つかった不具合, 取り付けられており、インターフェイス上に掲載されています.

私たちのポケモンの全体は、マトリックスモデルに配置されています. ここでは、正方行列に一時的に検討していきますNHE. コンソール上で実行し、そこからゲームのメインインターフェイスを取ることができます.

彼のゲームのアルゴリズムを実装するには自分の道を見つけるために、単純なものから複雑なものまでケースに分割されます (食べることができます砂糖) 2 コンポケモン, そこ概要 3 THは、自身のTH、それぞれが持っています 2 小さな枝は横レビューあり, 縦に. あなたのTH​​は完全にプールされた共有できることに気づきました, 彼のコードの間に見られるので、しかし、私は包摂としての文はこのように返された小さなケースをソートする場合、それはあまりにも多くのelesと複雑になるグロスはありません.

ケースには、同じ行または列にあります

TH1: 1行の同じポイントで二つ (xの直線)
TH2: 列の同じ時点での二つの (y軸線)
ととも​​に 2 THがこの基本的な、私たちは最初から最後までループするために使用し、通信回線は一緒ではないことを確認してください. 彼らは完全であると考えている場合, ない私たちは、THを使用する場合は、次の操作を行うために水平方向または垂直方向に延びています. 確認するには 2 私たちは、THを使用 2 関数であります checkLineX(int型Y1, int型Y2, int型のx) と checkLineY(int型×1, int型×2, int型のy) それぞれ、財の面でと列の観点から. 旅行の間にある場合、関数は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, int型) その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, int型) 上記と同じですが、行ごとに閲覧.

あなたはそれが同じようなTH3,4,5,6ので、我々は完全に一緒にマージすることができていることに気づきました, 上述のようにあまりにも多くの場合に必要であるため、しかし、ここで私はそうしませんでした, このTHようにそれを分割する他の.

もう一つはTHであります 5, 6 絶対に両方TH1,2,3,4を含めることができますが、私はまだTH1,2,3,4レビューは、我々は、高速の間の最短ルートを見つける前に、時ので分離し、 2 ポイント (もしそこに), 組み合わせた場合でも、U字状のパスは以前のレビューを満たすがある場合、我々は最短経路を見つけることができませんでした.

最後に、関数を書きますcheckTwoPoint(点P1, 点p2) テストして、元の間にあなたの方法を見つけるために 2 点P1, p2のいずれかの. この関数はオブジェクトを返しますマイラインなどがあり 2 P1とP2のポイント. 間の行目の 2 点P1, p2のリターンはP1とP2のマイラインを含めること, TH経路に折り畳まれ、それはマイラインとして返します 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;
}

クラスマイライン

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

ポケモンゲーム内のコードクラスアルゴリズム