Most memory efficient algorithm for finding a path on a grid

Question

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.

Answer 1

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.

^{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 a breadth-first search which doesn't use 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 minimum of 664 up to a maximum of 1152 bytes of allocated memory (depending on path length) 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 640 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 (zeros)
    (*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};                             // 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 + dx[3 - i];        // coordinates of neighbouring cell
            if (nx >= 0 && nx < 32 && ny >= 0 && ny < 16    // coordinates 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 0-3
            x1 -= dx[d]; y1 -= dx[3 - 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 = NULL;
    short int steps = findPath(grid, x1, y1, x2, y2, &path);
    // do stuff
    free(path);                                             // discard path array

    return 0;
}

Answer 2

This is an unfinished idea for an algorithm which may fit into 2048 bytes, that I came up with while trying to find a non-recursive flood-fill variant.

The first step is to create an additional 32×16 array of 8-bit values; this uses 512 bytes. You then iterate over the grid horizontally, and number the runs of adjacent reachable squares as in the image below:

For a 32×16 grid, the maximum number of runs is 256 (e.g. with a checkerboard pattern, or vertical stripes), so this numbering fits into 8-bit values.

The second step is to iterate over the grid vertically, and group the runs that are adjacent:

After checking vertical line 1:
{0A,11,1A}
{2E}
{44,50,5C}
{72}
{87,8F,98}

After checking vertical line 2:
{0A,11,1A,00,24}
{2E}
{44,50,5C,37,69}
{72}
{87,8F,98,7C}

After checking vertical line 2:
{0A,11,1A,00,24,12,2F}
{2E}
{44,50,5C,37,69,51,73}
{72}
{87,8F,98,7C,90}

... and so on, merging groups if they are linked by adjacent runs. If, at the end, the number of the start and target squares are in the same group, that means there is a path.

Now, if you store the groups as simple lists, like in the example above, this doesn't really give you a path; it just tells you which squares are reachable from the start and target squares, but a path may not need to cross all these squares.

If you stored the groups in a data structure where you know which runs are connected to each other, then it becomes a "shortest path through graph" problem in a smaller space. I'm not sure which data structure would best fit into the remaining 1536 bytes.

(Anyone is welcome to try and take this idea further.)

---

This method could be used to simplify the grid before running another algorithm. Firstly, the grouping of the runs identifies unreachable parts of the grid; these could be marked as walls in the original grid or a copy of it. Secondly, it identifies dead ends; runs which are only connected to one other run (and which don't contain the start or target square) are unnecessary detours and can also be marked as such. (This should be repeated: removing a singly-connected run may reveal another run to be singly-connected.)

^{Grid simplified by removing unreachable and singly-linked runs}

Running the algorithm again, but with vertical runs and horizontal grouping, could remove additional dead ends.

---

The JavaScript snippet below is a simple code example for the first part of the algorithm: using the example grid in the images, it numbers the runs, assigns them to groups, merges groups when necessary, and then checks whether the start and target square are in the same group, i.e. whether there is a path.

The grouping method may not be the most efficient, especially when merging groups, but it uses a fixed-size array of maximum 256 bytes (number of runs × 8-bit values), which is probably best in a limited-memory situation.

function gridPath(grid, x1, y1, x2, y2) {
    var runs = [], rcount = 0;
    for (var i = 0; i < 16; i++) {           // number runs
        var start = true; runs[i] = [];
        for (var j = 0; j < 32; ++j) {
            if (grid[i][j] == 0) {           // found empty cell
                if (start) ++rcount;         // start of new run
                runs[i][j] = rcount - 1;
                start = false;
            }
            else start = true;               // found blocked cell
        }
    }
    var groups = [], gcount = 0;
    for (var i = 0; i < rcount; i++) groups[i] = 0xFF;

    for (var j = 0; j < 32; ++j) {           // assign runs to groups
        var g = [];
        for (var i = 0; i < 16; ++i) {
            if (grid[i][j] == 0) g.push(runs[i][j]);
            if ((grid[i][j] == 1 || i == 15) && g.length > 0) {
                insertGroup(g);
                g = [];
            }
        }
    }     
    return groups[runs[y1][x1]] == groups[runs[y2][x2]];

    function insertGroup(g) {
        var matches = [];
        for (var i = 0; i < g.length; i++) { // check if runs are already in group
            if (groups[g[i]] != 0xFF && matches.indexOf(groups[g[i]]) < 0) {
                matches.push(groups[g[i]]);
            }
        }
        if (matches.length == 0) matches.push(gcount++); // start new group
        for (var i = 0; i < g.length; i++) { // add runs to group
            groups[g[i]] = matches[0];
        }
        if (matches.length > 1) {            // merge groups
            for (var i = 0; i < rcount; i++) {
                if (matches.indexOf(groups[i]) > 0) groups[i] = matches[0];
            }
        }
    }
}

var grid = [[1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0],
            [0,0,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0],
            [0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,1],
            [1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0],
            [0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0,0,1,0,1],
            [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,0],
            [0,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0],
            [0,1,0,0,0,1,0,0,0,1,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0],
            [0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0],
            [1,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0],
            [1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1],
            [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0],
            [0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0],
            [0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0]];
document.write(gridPath(grid, 0, 15, 15, 7));

Answer 3

If you only want to find the target, but do not care about remembering the path that was taken, then random search is pretty much optimal memory wise. It does not need to remember anything about previous states, so the memory use is constant. (Time complexity on the other hand is unbounded, which is not great, but isn't excluded by your requirements)

If you do need to remember the taken path, then you cannot go below linear space complexity with an algorithm that is complete - i.e always finds a path if it exists. Both breadth and depth first searches have linear space complexity, so they would be asymptotically in the same class as the optimal complete algorithm.

Since the memory is very limited, you might prefer to use a memory bounded algorithm, that gives you constant upper bound for memory use, but is not guaranteed to find a path that might exist. I recommend Simplified Memory Bounded A*.