这最初并不是为了成为一个答案,但它后来演变成了一个答案。老实说,我认为从 Java 开始转向 C 是一个坏主意,因为这两种语言实际上完全不同,而且你不会给自己带来任何好处,因为如果你依赖 java 的任何功能,移植它时你会遇到严重的问题。 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
我的迷宫与你的不同:这两种格式并不完全一一对应。例如,您的格式允许更精细的移动,但我的格式允许单向路径。
请注意,您的格式明确定位了墙壁。按照我的格式,墙在概念上位于不可能有路径的任何地方。我创建的迷宫有 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
}
值得注意的是,因为我把这些都写在编辑框中,所以我没有测试任何内容。第一次尝试可能不会成功,并且可能需要一些调整。例如,除非全局声明开始和结束,否则将会出现一些问题。最好将目标节点传递给搜索函数,而不是使用全局变量。