遞歸蠻力迷宮求解器Java

Question

在試圖編寫一個蠻力迷宮解決C程序時，我首先編寫了這個Java程序來測試一個想法。我對C很陌生，打算在java中獲得這個權利後將其轉換。因此，我試圖從數組列表，花哨的圖書館等方面進行操作，以便將其轉換爲C.該程序需要生成一條寬度最短的路徑來解決迷宮問題。我認爲我的問題可能在於分割通過每個遞歸的路徑存儲數組。感謝您看這個。 -Joe

maze: 

1 3 3 3 3 
3 3 3 3 3 
3 0 0 0 3 
3 0 3 3 3 
0 3 3 3 2 


Same maze solved by this program: 
4 4 4 4 4 
4 4 4 4 4 
4 0 0 0 4 
3 0 3 3 4 
0 3 3 3 2 

數字符號在代碼

public class javamaze { 

static storage[] best_path; 
static int best_count; 
static storage[] path; 

//the maze - 1 = start; 2 = finish; 3 = open path 
static int maze[][] = {{1, 3, 3, 3, 3}, 
    {3, 3, 3, 3, 3}, 
    {0, 0, 0, 0, 3}, 
    {0, 0, 3, 3, 3}, 
    {3, 3, 3, 3, 2}}; 

public static void main(String[] args) { 

    int count1; 
    int count2; 

    //declares variables used in the solve method 
    best_count = 0; 
    storage[] path = new storage[10000]; 
    best_path = new storage[10000]; 
    int path_count = 0; 


    System.out.println("Here is the maze:"); 
    for(count1 = 0; count1 < 5; count1++) { 
     for(count2 = 0; count2 < 5; count2++) { 
      System.out.print(maze[count1][count2] + " "); 
     }      
     System.out.println("");   
    }      

    //solves the maze 
    solve(findStart()/5, findStart()%5, path, path_count); 

    //assigns an int 4 path to the maze to visually represent the shortest path 
    for(int count = 0; count <= best_path.length - 1; count++) 
     if (best_path[count] != null) 
      maze[best_path[count].getx()][best_path[count].gety()] = 4; 

    System.out.print("Here is the solved maze\n"); 

    //prints the solved maze 
    for(count1 = 0; count1 < 5; count1++) { 
     for(count2 = 0; count2 < 5; count2++){ 
      System.out.print(maze[count1][count2] + " "); 
     } 
     System.out.print("\n"); 
    } 
} 

//finds maze start marked by int 1 - this works perfectly and isn't related to the problem 
public static int findStart() { 
    int count1, count2; 
    for(count1 = 0; count1 < 5; count1++) { 
     for(count2 = 0; count2 < 5; count2++) { 
      if (maze[count1][count2] == 1) 
       return (count1 * 5 + count2); 
     } 
    } 
    return -1; 
} 

//saves path coordinate values into a new array 
public static void save_storage(storage[] old_storage) { 
    int count; 
    for(count = 0; count < old_storage.length; count++) { 
     best_path[count] = old_storage[count]; 
    } 
} 

//solves the maze 
public static Boolean solve(int x, int y, storage[] path, int path_count) { 

    //checks to see if grid squares are valid (3 = open path; 0 = wall 
    if (x < 0 || x > 4) { //array grid is a 5 by 5 
     //System.out.println("found row end returning false"); 
     return false; 
    } 
    if (y < 0 || y > 4) { 
     //System.out.println("Found col end returning false"); 
     return false; 
    } 

    //when finding finish - records the number of moves in static int best_count 
    if (maze[x][y] == 2) { 
     if (best_count == 0 || best_count > path_count) { 
      System.out.println("Found end with this many moves: " + path_count); 
      best_count = path_count; 
      save_storage(path); //copies path counting array into a new static array 
     } 
    } 
    //returns false if it hits a wall 
    if (maze[x][y] == 0) 
     return false; 

    //checks with previously crossed paths to prevent an unnecessary repeat in steps 
    for(storage i: path) 
     if (i != null) 
      if (i.getx() == x && i.gety() == y) 
       return false; 

    //saves current recursive x, y (row, col) coordinates into a storage object which is then added to an array. 
    //this array is supposed to fragment per each recursion which doesn't seem to - this may be the issue 
    storage storespoints = new storage(x, y); 
    path[path_count] = storespoints; 

    //recurses up, down, right, left 
    if (solve((x-1), y, path, path_count++) == true || solve((x+1), y, path, path_count++) == true || 
      solve(x, (y+1), path, path_count++) == true || solve(x, (y-1), path, path_count++) == true) { 
     return true; 
    } 

    return false; 
} 
} 

//stores (x, y) aka row, col coordinate points 
class storage { 

private int x; 
private int y; 

public storage(int x, int y) { 
    this.x = x; 
    this.y = y; 
} 
public int getx() { 
    return x; 
} 
public int gety() { 
    return y; 
} 
public String toString() { 
    return ("storage coordinate: " + x + ", " + y + "-------"); 
} 

} 

Answer 1

這種解釋不是本來是一個答案，但它有點演變成一個。老實說，我認爲從Java開始並轉向C是一個壞主意，因爲這兩種語言真的沒什麼兩樣，你不會對自己有任何好處，因爲如果你依賴於任何功能，你將遇到嚴重的問題移植它有C沒有（即他們大多數）

這就是說，我會略圖一些算法C的東西。

支持結構

typedef 
struct Node 
{ 
    int x, y; 
    // x and y are array indices 
} 
Node; 

typedef 
struct Path 
{ 
    int maxlen, head; 
    Node * path; 
    // maxlen is size of path, head is the index of the current node 
    // path is the pointer to the node array 
} 
Path; 

int node_compare(Node * n1, Node * n2); // returns true if nodes are equal, else false 

void path_setup(Path * p, Node * n); // allocates Path.path and sets first node 
void path_embiggen(Path * p);  // use realloc to make path bigger in case it fills up 
int path_toosmall(Path * p);  // returns true if the path needs to be reallocated to add more nodes 
Node * path_head(Path * p);   // returns the head node of the path 
void path_push(Path * p, Node * n); // pushes a new head node onto the path 
void path_pop(Path * p);    // pops a node from path 

你可能改變你的迷宮格式轉換成鄰接表之類的事情。您可以將每個節點存儲爲一個掩碼，詳細說明您可以從節點前往哪些節點。

迷宮格式

const int // these constants indicate which directions of travel are possible from a node 
N = (1 << 0),  // travel NORTH from node is possible 
S = (1 << 1),  // travel SOUTH from node is possible 
E = (1 << 2),  // travel EAST from node is possible 
W = (1 << 3),  // travel WEST from node is possible 
NUM_DIRECTIONS = 4; // number of directions (might not be 4. no reason it has to be) 

const int 
START = (1 << 4), // starting node 
FINISH = (1 << 5); // finishing node 

const int 
MAZE_X = 4,   // maze dimensions 
MAZE_Y = 4; 

int maze[MAZE_X][MAZE_Y] = 
{ 
    {E,  S|E|W, S|E|W, S|W  }, 
    {S|FINISH, N|S,  N|START, N|S  }, 
    {N|S,  N|E,  S|E|W, N|S|W  }, 
    {N|E,  E|W,  N|W,  N   } 
}; 

Node start = {1, 2}; // position of start node 
Node finish = {1, 0}; // position of end node 

我的迷宮和你不一樣：這兩種格式不太相互映射1：1。例如，您的格式允許更精細的移動，但我的允許單向路徑。

請注意，您的格式顯式定位牆。根據我的格式，牆壁在概念上位於任何路徑不可能的地方。我創建的迷宮有3個水平牆和5個垂直牆（也是封閉的，即圍繞着整個迷宮有一個連續牆）

對於你的蠻力穿越，我會使用深度優先搜索。您可以通過多種方式將標誌映射到方向，如下面的說明。由於無論如何你都循環訪問每一個，訪問時間是無關緊要的，所以一個數組而不是某種更快的關聯容器就足夠了。

數據格式爲偏移映射

// map directions to array offsets 
// format is [flag], [x offset], [y offset] 
int mappings[][] = 
{ 
    {N, -1, 0}, 
    {S, 1, 0}, 
    {E, 0, 1}, 
    {W, 0, -1} 
} 

最後，你的搜索。你可以迭代或遞歸地實現它。我的例子使用遞歸。

搜索算法僞

int search_for_path(int ** maze, char ** visited, Path * path) 
{ 
    Node * head = path_head(path); 
    Node temp; 
    int i; 

    if (node_compare(head, &finish)) return 1; // found finish 
    if (visited[head->x][head->y]) return 0; // don't traverse again, that's pointless 

    visited[head->x][head->y] = 1; 
    if (path_toosmall(path)) path_embiggen(path); 

    for (i = 0; i < NUM_DIRECTIONS; ++i) 
    { 
     if (maze[head->x][head->y] & mappings[i][0]) // path in this direction 
     { 
      temp = {head->x + mappings[i][1], head->y + mappings[i][2]}; 
      path_push(path, &temp); 
      if (search_for_path(maze, visited, path)) return 1; // something found end 
      path_pop(path); 
     } 
    } 
    return 0; // unable to find path from any unvisited neighbor 
} 

調用這個函數，你應該設置好一切是這樣的：

調用規劃求解

// we already have the maze 
// int maze[MAZE_X][MAZE_Y] = {...}; 

// make a visited list, set to all 0 (unvisited) 
int visited[MAZE_X][MAZE_Y] = 
{ 
    {0,0,0,0}, 
    {0,0,0,0}, 
    {0,0,0,0}, 
    {0,0,0,0} 
}; 

// setup the path 
Path p; 
path_setup(&p, &start); 

if (search_for_path(maze, visited, &path)) 
{ 
    // succeeded, path contains the list of nodes containing coordinates from start to end 
} 
else 
{ 
    // maze was impossible 
} 

值得一提的是，由於我在編輯框中編寫了這一切，我還沒有測試過它。它可能不會在第一次嘗試時工作，並可能需要一些小小的擺弄。例如，除非全局聲明開始和結束，否則將會出現一些問題。將目標節點傳遞給搜索函數而不是使用全局變量會更好。