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

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 2

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*.