幅優先探索を利用して２次元探索空間を自動生成するアルゴリズムを作成します。二次元探索空間の単純な例は迷路です。
目次
Cellクラス
このクラスには二次元配列の各要素の情報を保持しておきます。
public class Cell {
private boolean isVisited;
private boolean hasRight;
private boolean hasBottom;
public Cell(){
isVisited = false;
hasRight = true;
hasBottom = true;
}
public void setToVisited(){
this.isVisited = true;
}
public void setToNotVisited(){
this.isVisited = false;
}
public void setRight(boolean hasRight){
this.hasRight = hasRight;
}
public void setBottom(boolean hasBottom){
this.hasBottom = true;
}
public boolean getVisited(){
return isVisited;
}
public boolean getHasRight(){
return hasRight;
}
public boolean getHasBottom(){
return hasBottom;
}
}Searchクラス
import java.util.ArrayDeque;
import java.util.Random;
public class Search{
Cell[][] searchSpace;
int[] startPoint;
int r;
int c;
...
}このクラスにメインとなるメソッドを書いていきます。
コンストラクタ
全ての座標についてCellクラスのインスタンスを生成します。
public Search(int r, int c){
searchSpace = new Cell[r][c];
this.r = r;
this.c = c;
for (int i = 0;i < r;i++){
for (int j = 0;j < c;j++){
searchSpace[i][j] = new Cell();
}
}
}探索空間生成メソッド
指定された行と列をもつ二次元探索空間を生成するStaticメソッドを作っていきます。
開始座標を[0][0]としてランダムに隣接座標へ移動していき、スタックに移動情報を随時追加していきます。
この情報をもとに、探索不能に陥った場合に探索可能箇所へトレースバックして探索を続行することができるはずです。
終了条件を全域探索完了、つまりスタックの要素がなくなった場合に設定します。
public static Search generateSearchSpace(int r, int c){
Search s = new Search(r, c);
s.searchSpace[0][0].setToVisited();
ArrayDeque<int[]> stack = new ArrayDeque<int[]>();
stack.push(new int[] {0, 0});
Random rand = new Random();
int[] top = stack.getFirst();
int i = top[0];
int j = top[1];
while(!stack.isEmpty()){
i = top[0];
j = top[1];
int[][] coords = new int[][]{
{i - 1, j },
{i + 1, j },
{i , j - 1},
{i , j + 1},
};
int[][] coordsVal = new int[4][2];
int idxV = 0;
for (int[] cd:coords){
int iPrime = cd[0];
int jPrime = cd[1];
if (iPrime >= 0 && jPrime >= 0 && iPrime < r && jPrime < c){
if(s.searchSpace[iPrime][jPrime].getVisited()) {
}else{
coordsVal[idxV] = new int[]{iPrime,jPrime};
idxV ++;
}
}else{
}
}
if (idxV == 0){
top = stack.poll();
}else{
int[] randN = coordsVal[rand.nextInt(0,idxV)];
s.searchSpace[randN[0]][randN[1]].setToVisited();
int deltai = randN[0] - i;
int deltaj = randN[1] - j;
if (deltai == -1){
s.searchSpace[i-1][j].setBottom(false);
}else if(deltai == 1){
s.searchSpace[i][j].setBottom(false);
}else if (deltaj == -1 ){
s.searchSpace[i][j-1].setRight(false);
}else if (deltaj == 1 ){
s.searchSpace[i][j].setRight(false);
}
stack.push(randN);
top = stack.getFirst();
}
}
return s;
}おそらくこれで[0][0]から[c][r]までの経路を探索できたと思います。
toString
探索結果を可視化するために、迷路風に結果を出力するメソッドを書いていきます。
基本的には全座標にアクセスして情報をもとに組み立てていく感じです。
public String toString(){
String result = "|";
for (int k =0;k<searchSpace[0].length;k++){
result += "---|";
}
for (int i = 0;i<searchSpace.length;i++){
if (i!=0){
result += "\n|";
}else{
result += "\n ";
}
for (int j = 0;j<searchSpace[0].length;j++){
if (searchSpace[i][j].getVisited() || true){
if (searchSpace[i][j].getHasRight()){
if (j == searchSpace[0].length-1 && i == 0 || !searchSpace[i][j].getHasRight()){
if(searchSpace[i][j].getVisited()){
result += " * ";
}else{
result += " ";
}
}else{
if(searchSpace[i][j].getVisited()){
result += " * |";
}else{
result += " |";
}
}
}else if(!searchSpace[i][j].getHasRight()) {
if(searchSpace[i][j].getVisited()){
result += " * ";
}else{
result += " ";
}
}
}else if(!searchSpace[i][j].getVisited()) {
result += " |";
}
}
result += "\n";
result += "|";
for (int k = 0;k<searchSpace[0].length;k++){
if (searchSpace[i][k].getHasBottom()){
result += "---|";
}else{
result += " |";
}
}
}
return result;
}
幅優先探索
実は探索空間を生成したときは幅優先探索を使用しながら経路を探索しました。そのため、同じような方法を使用して探索メソッドを書いていきます。
public void BFS(){
ArrayDeque<int[]> queue = new ArrayDeque<int[]>();
queue.push(new int[]{0, 0});
boolean isDone = false;
while(queue.size() >0 && !isDone){
int[] tmp = queue.pollLast();
searchSpace[tmp[0]][tmp[1]].setToVisited();
if (searchSpace[0].length>tmp[1]+1){
if (!searchSpace[tmp[0]][tmp[1]+1].getVisited() && !searchSpace[tmp[0]][tmp[1]].getHasRight()){
if (tmp[0] == 0 && tmp[1]+1 == searchSpace[0].length-1){
searchSpace[tmp[0]][tmp[1]+1].setToVisited();
return;
}
queue.push(new int[] {tmp[0], tmp[1]+1});
}
}
if (tmp[1] - 1 >= 0){
if (!searchSpace[tmp[0]][tmp[1]-1].getVisited() && !searchSpace[tmp[0]][tmp[1]-1].getHasRight()){
if (tmp[0] == 0 && tmp[1]-1 == searchSpace[0].length-1){
searchSpace[tmp[0]][tmp[1]-1].setToVisited();;
return;
}
queue.add(new int[] {tmp[0], tmp[1]-1});
}
}
if (searchSpace.length> tmp[0]+1){
if (!searchSpace[tmp[0]+1][tmp[1]].getVisited() && !searchSpace[tmp[0]][tmp[1]].getHasBottom()){
if (tmp[0]+1 == 0 && tmp[1] == searchSpace[0].length-1){
searchSpace[tmp[0]+1][tmp[1]].setToVisited();;
return;
}
queue.add(new int[] {tmp[0]+1, tmp[1]});
}
}
if (tmp[0]-1>=0){
if (!searchSpace[tmp[0]-1][tmp[1]].getVisited() && !searchSpace[tmp[0]-1][tmp[1]].getHasBottom()){
if (tmp[0]-1 == 0 && tmp[1] == searchSpace[0].length-1){
searchSpace[tmp[0]-1][tmp[1]].setToVisited();;
return;
}
queue.add(new int[] {tmp[0]-1, tmp[1]});
}
}
}
}実行結果
以下のようにして探索空間を生成します。
public static void main(String[] args) {
Search a = generateSearchSpace(10,10);
for (int i = 0;i<10;i++){
for (int j = 0;j<10;j++){
a.searchSpace[i][j].setToNotVisited();
}
}
System.out.println(a);
a.BFS();
System.out.println(a);
}実行結果
|---|---|---|---|---|---|---|---|---|---|
| |
|---|---| |---| | |---| |---| |
| | | | | |
| | |---| | | |---|---|---|---|
| | | | | |
| |---|---|---| |---| | |---| |
| | | | | | |
| |---| | |---| | | | |---|
| | | | | | |
|---| | |---| |---|---| |---| |
| | | | | | |
| | |---|---|---| | |---|---| |
| | | | |
| |---| |---| | |---|---|---| |
| | | | | |
|---|---|---| |---| |---| |---| |
| | | | |
| | |---|---| |---| | |---|---|
| | | |
|---|---|---|---|---|---|---|---|---|---|
|---|---|---|---|---|---|---|---|---|---|
* * * | * * * * * | *
|---|---| |---| | |---| |---| |
| * * | * * | * | * | * * * * |
| | |---| | | |---|---|---|---|
| * | * * * | * | * * | * * * |
| |---|---|---| |---| | |---| |
| * | * * * | * * | * | * | * * |
| |---| | |---| | | | |---|
| * * | * | * | * * | * * | * * |
|---| | |---| |---|---| |---| |
| * | * | * * * | * * | * * | * |
| | |---|---|---| | |---|---| |
| * * | * * * | * | * * * * |
| |---| |---| | |---|---|---| |
| * * * | * * | * | * * * | * |
|---|---|---| |---| |---| |---| |
| * * * | * * | * * | * * * |
| | |---|---| |---| | |---|---|
| * | * * * * * * | * * * |
|---|---|---|---|---|---|---|---|---|---|うまく探索できていることがわかります。
