递归暴力迷宫求解器Java

为了编写一个powershell迷宫来解决C程序，我首先编写了这个java程序来测试一个想法。 我是C的新手，打算在java中获得这个权利之后转换它。 结果，我试图远离arraylists，花式库等，以便更容易转换为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  4) { //array grid is a 5 by 5 //System.out.println("found row end returning false"); return false; } if (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是一个坏主意，因为这两种语言实际上并不相同，而且你不会给自己任何好处，因为如果你依赖任何function，你将遇到严重的问题移植它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 } 

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