Блог

Когда я запускаю свой код, он выдает ошибку сегментации, и я несколько раз пытался переписать код. Все равно безрезультатно, он даже не запускается. Ошибка сегментации возникает, как только запускается моя программа. Что он должен сделать, так это напечатать путь на экране, используя библиотеку ncurses в Linux, по заданным координатам. Вот проблемный фрагмент со строками, где gdb сказал, что произошла ошибка сегментации, также он (фрагмент) воспроизводит проблему.

ПРАВКА: Это поможет объяснить, что я пытаюсь сделать, но с использованием динамических массивов. Первый поиск по Ширине

ПРАВКА 2: Предполагается, что граница переменных отслеживает значения X и Y по определенному индексу. Функция add_neighbors предназначена для добавления всех четырех соседей (при условии, что они еще не добавлены) в массивы frontier и came_from.

граница[индекс][0] — это значение X.
граница[индекс][1] — это значение Y.

Перед первым циклом while я устанавливаю начальную позицию x1 и y1. Во время первого цикла while он увеличивает получение новых координат с границы, затем обрабатывает и добавляет в массив came_from.

Например:
(x1,y1) (x1 1,y1)
(x1,y1 1) (x1 1,y1 1)
(x1,y2) (x2,y2)

Я пытаюсь перейти от (x1,y1) к (x2,y2). Конечно, надеюсь, что это объясняет все лучше. То, что я пытаюсь реализовать, — это алгоритм поиска в ширину (BFS). Используя два массива, один-frontier (отслеживает посещенные позиции) и came_from (отслеживает X и Y путь от x1,y1 до x2,y2). Обновил код, чтобы отразить первый ответ. Плюс добавил комментарий, чтобы объяснить, где может быть ошибка, не совсем уверен, но я ее отлаживал. Похоже, что массив came_from никогда не устанавливается с помощью x и y.

Код:

 /*
 * pathfind.c - Simple Breadth First Search algorithm implementation.
 *
 * Author: Philip R. Simonson
 * Date  : 05/17/2021
 *
 ****************************************************************************
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ncurses.h>
    
#define MAXHEIGHT 24
#define MAXWIDTH 80

/* Add neighboring positions to the arrays.
 */
int add_neighbors(int **frontier, int ***came_from, int count, int x, int y)
{
    // North
    if(y > 0 amp;amp; came_from[y - 1][x][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count  ;
        came_from[y - 1][x][0] = x;
        came_from[y - 1][x][1] = y;
    }
    // South
    if(y < MAXHEIGHT-1 amp;amp; came_from[y   1][x][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count  ;
        came_from[y   1][x][0] = x;
        came_from[y   1][x][1] = y;
    }
    // West
    if(x > 0 amp;amp; came_from[y][x - 1][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count  ;
        came_from[y][x - 1][0] = x;
        came_from[y][x - 1][1] = y;
    }
    // East
    if(x < MAXWIDTH-1 amp;amp; came_from[y][x   1][0] < 0) {
        frontier[count][0] = x;
        frontier[count][1] = y;
        count  ;
        came_from[y][x   1][0] = x;
        came_from[y][x   1][1] = y;
    }
    return count; // Return counter for frontier
}
/* Simple BFS algorithm for path finding.
 */
void path_finding(int x1, int y1, int x2, int y2)
{
    int **frontier, ***came_from;
    int index, count;
    int i, j;

    index = 0;
    count = 0;

    // Initialise frontier array
    frontier = malloc(sizeof(int *) * MAXHEIGHT * MAXWIDTH);
    for(i = 0; i < (MAXHEIGHT * MAXWIDTH); i  ) {
        frontier[i] = malloc(sizeof(int) * 2);
    }

    // Create came_from array
    came_from = malloc(sizeof(int **) * MAXHEIGHT);
    for(i = 0; i < MAXHEIGHT; i  ) {
        came_from[i] = malloc(sizeof(int *) * MAXWIDTH);
        for(j = 0; j < MAXWIDTH; j  ) {
            came_from[i][j] = malloc(sizeof(int) * 2);
            came_from[i][j][0] = -1;
            came_from[i][j][1] = -1;
        }
    }

    // Add start to came_from
    came_from[y1][x1][0] = -9;
    came_from[y1][x1][1] = -9;

    // Add start to frontier
    frontier[count][0] = x1;
    frontier[count][1] = y1;
    count  ;

    while(index < count) {
        int x = frontier[index][0];
        int y = frontier[index][1];
        index  ;

        if(x == x2 amp;amp; y == y2)
            break;

        count = add_neighbors(frontier, came_from, count, x, y);
    }

    // Set temp position variables to end position
    {
        int x = x2;
        int y = y2;

        while(x != x1 || y != y1) {
            int tempy = y;
            mvprintw(y, x, "*");
            // Segmentation fault because came_from[tempy][x][1] and came_from[tempy][x][0]
            // always equals -1 which is out of bounds. Not sure how to fix it, something
            // is wrong with add_neighbors function I think.
            y = came_from[tempy][x][1];
            x = came_from[tempy][x][0];
        }
    }

    // TODO: Return came_from array!

    // Free all resources from both arrays
    for(i = 0; i < MAXHEIGHT; i  ) {
        for(j = 0; j < MAXWIDTH; j  ) {
            free(came_from[i][j]);
        }
        free(came_from[i]);
    }
    free(came_from);
    for(i = 0; i < (MAXHEIGHT * MAXWIDTH); i  ) {
        free(frontier[i]);
    }
    free(frontier);
}

int main(void)
{
    initscr();
    noecho();
    clear();

    path_finding(0, 2, 7, 8);

    refresh();
    getch();
    endwin();
    return 0;
}
 

Компиляция с помощью: cc -o test test.c -lncurses

Выход GDB:

 [philip@darkstar temp]$ gdb --batch --ex r --ex bt --ex q temp

Program received signal SIGSEGV, Segmentation fault.
                                                    0x000055555555599d in path_finding (x1=0, y1=2, x2=7, y2=8) at src/pathfind.c:117
117             y = came_from[tempy][x][1];
#0  0x000055555555599d in path_finding (x1=0, y1=2, x2=7, y2=8) at src/pathfind.c:117
#1  0x00005555555551ff in main () at src/main.c:11
A debugging session is active.

    Inferior 1 [process 65294] will be killed.

Quit anyway? (y or n) [answered Y; input not from terminal]
[philip@darkstar temp]$
 

Некоторые размеры распределения неверны:

• frontier = malloc(sizeof(frontier) * MAXHEIGHT * MAXWIDTH); должно быть

   frontier = malloc(sizeof(*frontier) * MAXHEIGHT * MAXWIDTH);
   

• frontier[i] = malloc(sizeof(*frontier) * 2); следует прочитать:

   frontier[i] = malloc(sizeof(frontier[i][0]) * 2);
   

Эти доступы не защищены должным образом:

• if(y <= MAXHEIGHT amp;amp; came_from[y 1][x][0] < 0) должно быть

    if (y < MAXHEIGHT-1 amp;amp; came_from[y   1][x][0] < 0)
   

• if(x <= MAXWIDTH amp;amp; came_from[y][x 1][0] < 0) должно быть

    if(x < MAXWIDTH-1 amp;amp; came_from[y][x   1][0] < 0)
   

• frontier массив не инициализирован. Вы должны использовать calloc() для инициализации int массивов 0 или запуска цикла инициализации.
• в while (x != x1 || y != y1) цикле, когда вы читаете y = came_from[tempy][x][1] , вы не проверяете это y >= 0 . Поскольку вы инициализировали came_from[y1][x1][0] = -9; его, он будет отрицательным и вызовет доступ за пределы во время следующей итерации, как вы установили tempy = y .
• алгоритм не очевиден из кода, возможно, вы захотите прокомментировать больше для удобства читателя.