递归蛮力迷宫求解器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 
} 

值得一提的是，由于我在编辑框中编写了这一切，我还没有测试过它。它可能不会在第一次尝试时工作，并可能需要一些小小的摆弄。例如，除非全局声明开始和结束，否则将会出现一些问题。将目标节点传递给搜索函数而不是使用全局变量会更好。