経路探索のアルゴリズムを改善したい
実際はFlashで書いていましたが、アルゴリズムに関してなので、
多種方面の方にご教示・助言を頂きたいと思い、
わかる範囲での C# に書き換えこちらのカテゴリーで質問しています。
■ ２次元配列に格納されているマップ情報を使い、特定の場所からの最短経路を全て出す
・マップに格納されている情報は、通行 可/不可 のみ
・経路の探索進行方向は縦横左右のみ
・障害物がないマス全てへの最短経路を求める
・障害物により辿りつけないマスは求める内容から除外
上記の目的・条件をもとに下記のようになりました。
C#だとほんの一瞬ですが、マップをこれより少し広くして行うと、Flash上では反復回数制御により強制的に止まってしまうため、探索用関数を改善したいと思っています。
同じ結果が得られれば全く違う内容でも構いません、何か良い案がありましたら、よろしくお願いします。
（ここでは静的なマップ内容ですが、実際は障害物の有無が動的に変わります）
using System;
namespace ConsoleApplication1 {
class Program {
static int count;
static int[][] chMap;//歩数格納用配列
static bool[][] myMap;//マップ格納用配列
const int mx = 10;
static void Main(string[] args) {
int[] stP = { 1, 2 };//探索開始位置{Y,X}
chMap = new int[mx][];
for (int i = 0; i < chMap.Length; chMap[i++] = new int[mx]) ;
bool o = true;//障害物なし 通行可能
bool x = false;//障害物あり 通行不可能
myMap = new bool[mx][];
myMap[0] = new bool[mx] { o, o, o, o, o, o, o, o, o, o };
myMap[1] = new bool[mx] { o, o, o, o, o, o, o, x, o, o };
myMap[2] = new bool[mx] { o, o, o, o, o, o, o, x, o, o };
myMap[3] = new bool[mx] { o, o, o, o, o, o, o, x, o, o };
myMap[4] = new bool[mx] { o, o, o, o, o, o, o, x, o, o };
myMap[5] = new bool[mx] { x, x, x, o, o, o, o, x, o, o };
myMap[6] = new bool[mx] { o, o, o, o, o, x, x, x, o, o };
myMap[7] = new bool[mx] { o, o, o, o, o, x, o, o, o, o };
myMap[8] = new bool[mx] { o, o, o, o, o, x, o, o, o, o };
myMap[9] = new bool[mx] { o, o, o, o, o, x, o, o, o, o };
Write:
count = 0;
for (int Y = 0; Y < myMap.Length; Y++) {
for (int X = 0; X < myMap[Y].Length; X++) {
Console.Write(myMap[Y][X] ? "□ " : "■ ");
chMap[Y][X] = myMap[Y][X] ? myMap.Length * myMap.Length : -1;
}
Console.WriteLine();
}
Console.WriteLine();
G2P(stP[0], stP[1], 0);
for (int Y = 0; Y < chMap.Length; Y++) {
for (int X = 0; X < chMap[Y].Length; X++) {
Console.Write(chMap[Y][X] == 0 ? "★ " : chMap[Y][X] == -1 ? "■ " : chMap[Y][X] == myMap.Length * myMap.Length ? "-- " : chMap[Y][X].ToString("00 "));
}
Console.WriteLine();
}
Console.WriteLine("\n探索用関数を " + count.ToString() + " 回 通りました");
Console.ReadKey();
goto Write;
}
//探索用関数
static void G2P(int y, int x, int n) {
++count;
if (y < 0 || x < 0 || y >= myMap.Length || x >= myMap.Length) return;
chMap[y][x] = n;
if (x + 1 < mx && chMap[y][x + 1] > n + 1 && myMap[y][x + 1]) {
G2P(y, x + 1, n + 1);
}
if (x - 1 >= 0 && chMap[y][x - 1] > n + 1 && myMap[y][x - 1]) {
G2P(y, x - 1, n + 1);
}
if (y + 1 < mx && chMap[y + 1][x] > n + 1 && myMap[y + 1][x]) {
G2P(y + 1, x, n + 1);
}
if (y - 1 >= 0 && chMap[y - 1][x] > n + 1 && myMap[y - 1][x]) {
G2P(y - 1, x, n + 1);
}
}
}
}
お礼
返事が遅れて申し訳ありません。度々御意見をいただき恐縮です。入力引数、出力引数を指定したところ、当初目的としていた結果を得ることができました。一般的に見れば簡単なことかもしれませんが、自分一人ではこんなに早く解決できる問題ではなかったと思います。御助言ありがとうございました。