WSP-Navigate: An Optimal Calculation of Diagonal and Orthogonal Navigation Steps in 2-Dimensional Grids With Fewer CPU Cycles on Average
William Stafford Parsons developed a grid step navigation calculation algorithm as a substantial improvement to all similar algorithms for navigating rectangular grids in a 2D plane.
Library
Source
struct wsp_navigate_s {
unsigned long grid_width;
unsigned long grid_height;
unsigned long source;
unsigned long destination;
long source_step;
unsigned long source_x;
unsigned long source_y;
unsigned long destination_x;
unsigned long destination_y;
char source_x_step;
char source_y_step;
unsigned long repetitions_count;
unsigned char has_source_coordinates;
unsigned char has_destination_coordinates;
};
void wsp_navigate(struct wsp_navigate_s *s) {
if (s->repetitions_count == 0) {
if (s->has_source_coordinates == 0) {
s->source_y = s->source / s->grid_width;
s->source_x = s->source - (s->grid_width * s->source_y);
s->has_source_coordinates = 1;
}
if (s->has_destination_coordinates == 0) {
s->destination_y = s->destination / s->grid_width;
s->destination_x = s->destination - (s->grid_width * s->destination_y);
s->has_destination_coordinates = 1;
}
if (s->source_x == s->destination_x) {
s->source_x_step = 0;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width;
s->source_y_step = 1;
s->repetitions_count = s->destination_y - s->source_y;
} else {
if (s->source_y > s->destination_y) {
s->source_step = -s->grid_width;
s->source_y_step = -1;
s->repetitions_count = s->source_y - s->destination_y;
} else {
s->source_step = 0;
s->source_y_step = 0;
s->repetitions_count = 0;
}
}
} else {
if (s->source_y == s->destination_y) {
s->source_y_step = 0;
if (s->source_x < s->destination_x) {
s->source_step = 1;
s->source_x_step = 1;
s->repetitions_count = s->destination_x - s->source_x;
} else {
s->source_step = -1;
s->source_x_step = -1;
s->repetitions_count = s->source_x - s->destination_x;
}
} else {
if (s->source_x < s->destination_x) {
s->repetitions_count = s->destination_x - s->source_x;
s->source_x_step = 1;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width + 1;
s->source_y_step = 1;
if ((s->destination_y - s->source_y) < s->repetitions_count) {
s->repetitions_count = s->destination_y - s->source_y;
}
} else {
s->source_step = -s->grid_width + 1;
s->source_y_step = -1;
if ((s->source_y - s->destination_y) < s->repetitions_count) {
s->repetitions_count = s->source_y - s->destination_y;
}
}
} else {
s->repetitions_count = s->source_x - s->destination_x;
s->source_x_step = -1;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width - 1;
s->source_y_step = 1;
if ((s->destination_y - s->source_y) < s->repetitions_count) {
s->repetitions_count = s->destination_y - s->source_y;
}
} else {
s->source_step = -s->grid_width - 1;
s->source_y_step = -1;
if ((s->source_y - s->destination_y) < s->repetitions_count) {
s->repetitions_count = s->source_y - s->destination_y;
}
}
}
}
}
}
s->source += s->source_step;
s->source_x += s->source_x_step;
s->source_y += s->source_y_step;
s->repetitions_count--;
}Reference
wsp_navigate() is the step navigation function that accepts the following argument.
s is the struct wsp_navigate_s pointer.
The following elements in s must be initialized.
struct wsp_navigate_s s = {
.grid_width = 10,
.grid_height = 10,
.source = 0,
.destination = 95,
.source_step = 0,
.repetitions_count = 0,
.has_source_coordinates = 0,
.has_destination_coordinates = 0
};s.grid_width is the width of the rectangular grid.
s.grid_height is the height of the rectangular grid.
s.source is the starting position as an index in a grid array with s.grid_width * s.grid_height elements.
s.destination is the ending position as an index in a grid array with s.grid_width * s.grid_height elements.
The return value data type is void.
Requirements
C compiler with C89 (ISO/IEC 9899:1990) standard compatibility.
Explanation
WSP-Navigate is designed to calculate the next step in 1 of 8 possible directions within the bounds of a rectangular grid by only knowing the grid width, grid height, source index position and destination index position.
It's portable for both 32-bit and 64-bit systems.
It meets strict compliance, portability and code security requirements.
For example, the following grid array uses a source 1 at index position 0 and a destination 2 at index position 95.
unsigned char grid[100] = {
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, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 2, 0, 0, 0, 0
};The next step forward towards the destination 2 from the source 1 is at index position 11.
In this case, the wsp_navigate() function increments s.source to advance to this position.
This is applied recursively until s.source reaches s.destination as demonstrated in the following code example.
int main(void) {
struct wsp_navigate_s s = {
.grid_width = 10,
.grid_height = 10,
.source = 0,
.destination = 95,
.source_step = 0,
.repetitions_count = 0,
.has_source_coordinates = 0,
.has_destination_coordinates = 0
};
unsigned char grid[100] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
unsigned char i = 0;
grid[s.source] = 1;
wsp_navigate(&s);
while (s.source != s.destination) {
wsp_navigate(&s);
grid[s.source] = 3;
}
grid[s.destination] = 2;
i = 0;
while (i != 100) {
printf("%u ", grid[i]);
if (((i + 1) % 10) == 0) {
printf("\n");
}
i++;
}
return 0;
}The following grid output is the traversal from the source to the destination with each step marked as 3.
1 0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 2 0 0 0 0This simple calculation could be processed billions of times per minute, so it's necessary to micro-optimize wherever possible.
There are plenty of ways to do this wrong by calculating steps incorrectly and wasting CPU cycles and memory.
For example, the following code is the first attempt at creating this algorithm without optimization.
long bad_navigate(const unsigned long grid_width,
const unsigned long grid_height, const unsigned long source,
const unsigned long destination) {
long map[10] = {0, 0, 0, 0, 0, 0, 1, 0, 0, 0};
const unsigned long source_x = source % grid_width;
const unsigned long source_y = source / grid_width;
const unsigned long destination_x = destination % grid_width;
const unsigned long destination_y = destination / grid_width;
unsigned char i = source_y < destination_y;
map[0] = -(grid_width + 1);
map[1] = grid_width - 1;
map[2] = -1;
map[3] = 0;
map[4] = -(grid_width - 1);
map[5] = grid_width + 1;
map[8] = -grid_width;
map[9] = grid_width;
if (source_y == destination_y) {
i += 2;
}
if (source_x < destination_x) {
i += 4;
}
if (source_x == destination_x) {
i += 8;
}
return map[i];
}Although the aforementioned solution works, map isn't required and wastes 40–80 bytes of memory per instance.
In addition to the 4 required conditional statements, map uses 8 dereferences, 8 assignments and 7 arithmetic operations.
These 4 conditional statements can be optimized further by nesting conditional statements and using = operations instead of += operations.
The following code is a second attempt without mapping the traversal steps.
long bad_navigate(const unsigned long grid_width,
const unsigned long grid_height, const unsigned long source,
const unsigned long destination) {
const unsigned long source_x = source % grid_width;
const unsigned long source_y = source / grid_width;
const unsigned long destination_x = destination % grid_width;
const unsigned long destination_y = destination / grid_width;
long step = 0;
if (source != destination) {
if (source_x == destination_x) {
if (source_y < destination_y) {
step = grid_width;
} else {
step = -grid_width;
}
} else {
if (source_y == destination_y) {
if (source_x < destination_x) {
step = 1;
} else {
step = -1;
}
} else {
if (source_x < destination_x) {
if (source_y < destination_y) {
step = grid_width + 1;
} else {
step = -grid_width + 1;
}
} else {
if (source_y < destination_y) {
step = grid_width - 1;
} else {
step = -grid_width - 1;
}
}
}
}
}
return step;
}The aforementioned code is passable, but still not optimal.
The initialized value for step is overwritten in a majority of cases and the % operator uses too many CPU cycles.
Arithmetic division with the / operator is necessary to calculate both source_y and destination_y, but source_x and destination_x can use cheaper operations with arithmetic * and - instead of %.
The following code tests the processing time of % operations in a loop without compiler optimization enabled.
#include <stdio.h>
int main(void) {
unsigned short a = 11111;
unsigned long b = 0;
unsigned short c = 0;
while (b != 111111111) {
c += a % 111;
a += c;
b++;
}
return 0;
}Arithmetic * and - were more efficient by a few seconds when testing against both / and % with more than 100m iterations as shown in the following table.
Operators Expression Average Time
* - c += c - (a * 111); 0m6.105s
/ c += a / 111; 0m6.780s
% c += a % 111; 0m8.282sThe following code is the optimal result with a usage example.
#include <stdio.h>
struct wsp_navigate_s {
unsigned long grid_width;
unsigned long grid_height;
unsigned long source;
unsigned long destination;
long source_step;
unsigned long source_x;
unsigned long source_y;
unsigned long destination_x;
unsigned long destination_y;
char source_x_step;
char source_y_step;
unsigned long repetitions_count;
unsigned char has_source_coordinates;
unsigned char has_destination_coordinates;
};
void wsp_navigate(struct wsp_navigate_s *s) {
if (s->repetitions_count == 0) {
if (s->has_source_coordinates == 0) {
s->source_y = s->source / s->grid_width;
s->source_x = s->source - (s->grid_width * s->source_y);
s->has_source_coordinates = 1;
}
if (s->has_destination_coordinates == 0) {
s->destination_y = s->destination / s->grid_width;
s->destination_x = s->destination - (s->grid_width * s->destination_y);
s->has_destination_coordinates = 1;
}
if (s->source_x == s->destination_x) {
s->source_x_step = 0;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width;
s->source_y_step = 1;
s->repetitions_count = s->destination_y - s->source_y;
} else {
if (s->source_y > s->destination_y) {
s->source_step = -s->grid_width;
s->source_y_step = -1;
s->repetitions_count = s->source_y - s->destination_y;
} else {
s->source_step = 0;
s->source_y_step = 0;
s->repetitions_count = 0;
}
}
} else {
if (s->source_y == s->destination_y) {
s->source_y_step = 0;
if (s->source_x < s->destination_x) {
s->source_step = 1;
s->source_x_step = 1;
s->repetitions_count = s->destination_x - s->source_x;
} else {
s->source_step = -1;
s->source_x_step = -1;
s->repetitions_count = s->source_x - s->destination_x;
}
} else {
if (s->source_x < s->destination_x) {
s->repetitions_count = s->destination_x - s->source_x;
s->source_x_step = 1;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width + 1;
s->source_y_step = 1;
if ((s->destination_y - s->source_y) < s->repetitions_count) {
s->repetitions_count = s->destination_y - s->source_y;
}
} else {
s->source_step = -s->grid_width + 1;
s->source_y_step = -1;
if ((s->source_y - s->destination_y) < s->repetitions_count) {
s->repetitions_count = s->source_y - s->destination_y;
}
}
} else {
s->repetitions_count = s->source_x - s->destination_x;
s->source_x_step = -1;
if (s->source_y < s->destination_y) {
s->source_step = s->grid_width - 1;
s->source_y_step = 1;
if ((s->destination_y - s->source_y) < s->repetitions_count) {
s->repetitions_count = s->destination_y - s->source_y;
}
} else {
s->source_step = -s->grid_width - 1;
s->source_y_step = -1;
if ((s->source_y - s->destination_y) < s->repetitions_count) {
s->repetitions_count = s->source_y - s->destination_y;
}
}
}
}
}
}
s->source += s->source_step;
s->source_x += s->source_x_step;
s->source_y += s->source_y_step;
s->repetitions_count--;
}
int main(void) {
struct wsp_navigate_s s = {
.grid_width = 10,
.grid_height = 10,
.source = 0,
.destination = 95,
.source_step = 0,
.repetitions_count = 0,
.has_source_coordinates = 0,
.has_destination_coordinates = 0
};
unsigned char grid[100] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
unsigned char i = 0;
grid[s.source] = 1;
wsp_navigate(&s);
while (s.source != s.destination) {
wsp_navigate(&s);
grid[s.source] = 3;
}
grid[s.destination] = 2;
i = 0;
while (i != 100) {
printf("%u ", grid[i]);
if (((i + 1) % 10) == 0) {
printf("\n");
}
i++;
}
return 0;
}In addition to saving CPU time and memory, the required conditional statements are nested properly to minimize conditional checks for each navigational direction, as shown in the following table.
Case Conditional Checks Conditional Checks
Before Optimization After Optimization
0 1 3
1 3 2
2 3 3
3 4 3
4 4 3
5 5 4
6 5 4
7 5 4
8 5 4
__________ __________
35 30The minority case when the source is the same as the destination requires more conditional checks to decrease the overall count from 35 to 30 and the average count from 3.89 to 3.33.
Furthermore, it'd be wasteful to calculate x and y coordinates for each space traversal instead of calculating repetitions in the same direction, so the directional calculations for each turn are separate from iterative, incremental space traversals in wsp_navigate().
The x and y coordinates are saved after the first calculation and they're either incremented or decremented after each navigation step.
The wsp_navigate() function is iterative to allow flexibility with using the changed source index position for each step.
To navigate to a new destination after reaching the current destination, s.destination must be set to the new index position and s.has_destination_coordinates must be set to 0.
Although it may be unsafe if done incorrectly, navigating can be optimized further by defining s.source_x, s.source_y, s.destination_x, s.destination_y, s.has_destination_coordinates and s.has_destination_coordinates in the struct if the x and y grid coordinates are already known.
4-directional navigation is omitted because it's a trivial adjustment from the 8-directional result and it's dependent on the position of obstacles.
For example, the 8-directional calculation from position 21 to 32 in the following grid with obstacles marked as 4 doesn't need to consider adjacent obstacles, but the 4-directional adjustment considers a possible obstacle at either position 22 or 31.
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 4 3 0 0 0 0 0 0 0
0 0 4 3 0 0 0 0 0 0
0 0 4 3 0 0 0 0 0 0
0 0 4 3 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0In this case, a 4-directional implementation should adjust the calculation step from 11 to 1 instead of 10 based on the obstacle at position 31.
Games
Contrivity
Spawn into the hostile quantum laboratory and destroy wave after wave of oscillations.