The most 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 square of a grid to another? The net may have obstacles that cannot be crossed. Being the shortest way is not necessary, but, of course, is a bonus. The algorithm will be encoded in C (C ++ is available, but I avoid this to reduce memory usage) and run on an ATmega328 chip with only 2048 bytes of SRAM. Processor efficiency is not paramount.

EDIT: The grid consists of 16 by 32 squares, each of which is represented by one bit. Thus, the total memory usage is 64 bytes. The grid is stored as an unsigned 2D array, and all 2048 bytes are available. The result will be an array of integers referring to the squares to be taken.

If there is an obstacle in the square, the array of squares will have 1 instead of zero. These squares should be considered as walls.

Answer 1

This is an unfinished idea for an algorithm that can fit in the 2048 bytes I came up with while trying to find a non-recursive fill-fill option.

The first step is to create an additional 32-bit and 16-bit array of 8-bit values; it uses 512 bytes. Then you iterate over the grid horizontally and count the runs of the adjacent reachable squares, as shown in the figure below:

For grid 32 and times; 16, the maximum number of runs is 256 (for example, with a checkerboard pattern or vertical stripes), so this numbering corresponds to 8-bit values.

The second step is to loop through the grid vertically and group adjacent lines:

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}

... etc., combining groups if they are connected by adjacent runs. If at the end the number of starting and target squares is in the same group, this means that there is a path.

Now, if you save groups as simple lists, as in the example above, this does not give you a way; it just tells you which squares are reachable from the beginning and the target squares, but the path may not have to cross all of these squares.

If you saved groups in a data structure where you know which starts are connected to each other, then it becomes a “shortest path through a graph” problem in a smaller space. I'm not sure which data structure fits best in the remaining 1536 bytes.

(Anyone can continue this idea.)

---

This method can be used to simplify the grid before running another algorithm. First, the run grouping identifies unreachable parts of the grid; they can be marked as walls in the original grid or a copy of it. Secondly, it identifies dead ends; runs that are associated with only one run (and that do not contain a start or target square) are unnecessary walks and can also be flagged as such. (This needs to be repeated: deleting a single-user run may indicate that the other run will be simply connected.)

^{The grid is simplified by removing unreachable and simply connected runs}

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

---

The following snippet of JavaScript code is a simple code example for the first part of the algorithm: using an example grid in images, it displays runs, assigns them to groups, combines groups if necessary, and then checks whether the start and target squares are run in the same group , i.e. is there a way.

The grouping method may not be the most effective, especially when merging groups, but it uses a fixed-size array of a maximum of 256 bytes (number of runs and times; 8-bit values), which is probably a 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 largely optimal for memory. He does not need to remember anything about previous conditions, so the memory usage is permanent. (On the other hand, the complexity of time is not limited, which is not very good, but not excluded by your requirements)

If you need to remember the path traveled, then you cannot go below the linear complexity of the space with a complete algorithm - you will always find the path if it exists. And first-order width and depth searches have linear spatial complexity, so they will be asymptotically in the same class as the optimal complete algorithm.

Since memory is very limited, you can use a limited memory algorithm, which gives you a constant upper bound for memory use, but is not guaranteed to find a path that may exist. I recommend Simplified Limited Memory A *.

Answer 3

I studied 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 are maintained.

Unfortunately, paths on a 32x16 grid can have a distance greater than 255; the longest path I found has a distance of 319 (see image below, left). This means that the distances will not correspond to 8 bits, and the distance matrix is ​​1024 bytes in size.

^{Left: the longest path (distance = 319). Right: the largest number of equidistant cells (72 cells at a distance of 16)}

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

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

The path returned by the algorithm is an array containing 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 that only the direction grid and path are in memory at a time.

The following is an example of a simplified algorithm code with only a direction matrix and a fifo queue; it can probably be improved in many aspects, but it demonstrates this idea. The findPath () function uses a minimum of 664 up to a maximum of 1152 bytes of allocated memory (depending on the path length) plus about 20 bytes for additional variables.

This can be further reduced, for example. saving the direction matrix in the form of 4-bit pieces, reducing its size from 512 to 256 bytes (but requiring large computations) or returning the path as a sequence up / right / down / left, instead of the cell coordinates, which requires 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; }