Рекурсивный решатель лабиринта грубой силы Java

Изначально это не должно было быть ответом, но оно как бы превратилось в один. Честно говоря, я думаю, что начинать с 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

Мой лабиринт отличается от вашего: два формата не совсем соответствуют друг другу 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
}

Стоит отметить, что, поскольку я написал все это в поле редактирования, я ничего не проверял. Вероятно, это не сработает с первой попытки и может потребоваться небольшая возня. Например, если начало и конец не объявлены глобально, возникнет несколько проблем. Было бы лучше передать целевой узел в функцию поиска, а не использовать глобальную переменную.