Random User Random User - 4 months ago 10
C Question

Most memory efficient algorithm for finding a path on a grid

What is the most memory efficient algorithm that can be used to find a path from one grid square to another? The grid may have obstacles that cannot be crossed. Being the shortest path is not necessary, but certainly, is a bonus. The algorithm is going to be coded in C (C++ is available, but I am avoiding it to reduce memory usage) and run on an ATmega328 chip with only 2048 bytes of SRAM. CPU efficiency is not of paramount importance.

EDIT: The grid is 16 by 32 squares, each represented by one bit. The total memory usage is therefore 64 bytes. The grid is stored as a 2D array of unsigned chars and all of the 2048 bytes are available. The output would be an array of integers referencing the squares that should be taken.

If there is an obstacle in a square, the array of squares would have a 1 instead of a zero. These squares should be treated like walls.

m69 m69
Answer

I looked into using Dijkstra (as suggested by Weather Vane), which would require that for each grid cell the distance to the starting point and the direction from the previous cell is stored.

Unfortunately, it is possible for paths on a 32x16 grid to have a distance greater than 255; the longest path I found has distance 319 (see image below, left). This means that the distances won't fit in 8-bits, and the distance matrix has a size of 1024 bytes.

longest path and largest queue

Left: longest path (distance=319). Right: largest number of equidistant cells (72 cells at distance 16)

However, in a square grid where all distances equal 1, you can simplify Dijkstra to not need a distance matrix; if you use a fifo queue, the cells are visited in order of distance to the starting cell, so you cannot find a shorter path to an already visited cell.

The fifo queue will contain every cell at a certain distance, then gradually transition to distance + 1, and so on. The maximum size of the queue depends on how many equidistant cells there can be; the maximum I found is 72 (see image above, right) and during the transition from the previous distance this requires a queue that can hold the coordinates of 76 cells, or 152 bytes.

The path which is returned by the algorithm is an array holding the coordinates of a maximum of 320 cells, so it has a maximum size of 640 bytes. Before constructing this array, the queue can be discarded, so only the direction grid and the path are in memory at the same time.

Below is a code example of the simplified algorithm with only a direction matrix and a fifo queue; it can probably be improved on many points, but it demonstrates the idea. The findPath() function uses a maximum of 1152 bytes of allocated memory plus around 20 bytes for additional variables.

This could be further reduced, e.g. by storing the direction matrix as 4-bit nibbles, reducing its size from 512 to 256 bytes (but requiring more calculations), or by returning the path as a sequence of up/right/down/left directions instead of cell coordinates, which would require only 2 bits per step, reducing its maximum size from 320 to 80 bytes.

#include <stdlib.h>                                         //  gcc -std=c99

short int findPath(char grid[][32], char x1, char y1, char x2, char y2, char **path) {
    char (*dir)[16][32] = calloc(512, 1);                   // allocate direction matrix: 512 bytes
    (*dir)[y2][x2] = 5;                                     // mark starting cell as visited (search backwards)
    char *queue = malloc(152);                              // allocate fifo queue: 152 bytes
    queue[0] = x2; queue[1] = y2;                           // put starting cell in queue (search backwards)
    unsigned char qRead = 0, qWrite = 2;                    // queue pointers
    char qCurSize = 1, qNextSize = 0;                       // queue size per distance
    short int distance = 0;                                 // distance to current cell
    char dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};      // up, right, down, left
    while (qRead != qWrite && !(*dir)[y1][x1]) {            // until queue empty (fail) or target reached
        char x = queue[qRead++], y = queue[qRead++];        // take oldest cell from queue
        qRead %= 152;                                       // wrap-around queue pointer
        for (char i = 0; i < 4; i++) {                      // check 4 neighbouring cells
            char nx = x + dx[i], ny = y + dy[i];            // coordinates of neighbouring cell
            if (nx >= 0 && nx < 32 && ny >= 0 && ny < 16    // neighbouring cell not off-grid
            && !grid[ny][nx] && !(*dir)[ny][nx]) {          // traversable unvisited cell
                (*dir)[ny][nx] = i + 1;                     // store direction 1-4
                queue[qWrite++] = nx; queue[qWrite++] = ny; // put cell in queue
                qWrite %= 152;                              // wrap-around queue pointer
                ++qNextSize;                                // increment queue size for next distance
            }
        }
        if (!--qCurSize || (*dir)[y1][x1]) {                // current distance done or target reached
            qCurSize = qNextSize;                           // switch to distance + 1
            qNextSize = 0;
            ++distance;
        }
    }
    free(queue);                                            // free up queue memory for path
    if (!(*dir)[y1][x1]) distance = -1;                     // no path found
    else {                                                  // path found
        *path = malloc(distance * 2 + 2);                   // allocate path array: 2 bytes per step
        (*path)[0] = x1; (*path)[1] = y1;                   // starting position (forward)
        for (short int i = 1; i <= distance; i++) {         // retrace steps
            char d = (*dir)[y1][x1] - 1;                    // direction of previous step
            x1 -= dx[d]; y1 -= dy[d];                       // go back to previous position
            (*path)[i * 2] = x1; (*path)[i * 2 + 1] = y1;   // add cell to path
        }
    }
    free(*dir);                                             // discard direction matrix
    return distance + 1;                                    // return number of cells in path
}

int main() {
    char grid[][32] = // max queue size: 76
        {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
         {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
    char x1 = 31, y1 = 0, x2 = 16, y2 = 7, *path;
    short int steps = findPath(grid, x1, y1, x2, y2, &path);
    // do stuff
    free(path);                                             // discard path array

    return 0;
}