経路探索のアルゴリズムを改善したい
実際は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);
}
}
}
}
お礼
noias さん、ありがとうございます。 EVAアニメータキッズには QuickTime movie への書き出し機能はあるのですが、swfに書き出す機能は残念ながらありません。 ＞単純な図形であれば、使いなれたツールで作成し、凝ったものを使いたいのであれば面倒でもflashの描画機能を使わざるをえないと思います。 やはりそうなんでしょうね…。
補足
noias さん、どうもありがとうございました。 タブレットの導入を検討してみます。