StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A slighly contrived way might be this (pseudo-code):</p> <ol> <li>Build the bit-mask as you describe, based on which neighbors are open.</li> <li><p>Use that bit-mask as the index into an array of:</p> <p><code> struct RandomData<br> {<br> size_t num_directions;<br> struct { signed int dx, dy; } deltas[4];<br> } random_data[16];</code></p> <p>where num_directions is the number of open neighbors, and <code>deltas[]</code> tells you how to get to each neighbor.</p></li> </ol> <p>This has a lot of fiddly data, but it does away with the looping and branching.</p> <p><strong>UPDATE:</strong> Okay, for some reason I had problems letting this idea go. I blame a certain amount of indoctrination about "data-driven programming" at work, since this very simple problem made me "get" the thought of data-driven-ness a bit better. Which is always nice.</p> <p>Anyway, here's a complete, tested and working implementation of the random-stepping function using the above ideas:</p> <pre><code>/* Directions are ordered from north and going clockwise, and assigned to bits: * * 3 2 1 0 * WEST | SOUTH | EAST | NORTH * 8 4 2 1 */ static void random_walk(unsigned int *px, unsigned int *py, unsigned max_x, unsigned int max_y) { const unsigned int x = *px, y = *py; const unsigned int dirs = ((x > 0) << 3) | ((y < max_y) << 2) | ((x < max_x) << 1) | (y > 0); static const struct { size_t num_dirs; struct { int dx, dy; } deltas[4]; } step_info[] = { #define STEP_NORTH { 0, -1 } #define STEP_EAST { 1, 0 } #define STEP_SOUTH { 0, 1 } #define STEP_WEST { -1, 0 } { 0 }, { 1, { STEP_NORTH } }, { 1, { STEP_EAST } }, { 2, { STEP_NORTH, STEP_EAST } }, { 1, { STEP_SOUTH } }, { 2, { STEP_NORTH, STEP_SOUTH } }, { 2, { STEP_EAST, STEP_SOUTH } }, { 3, { STEP_NORTH, STEP_EAST, STEP_SOUTH } }, { 1, { STEP_WEST } }, { 2, { STEP_NORTH, STEP_WEST } }, { 2, { STEP_EAST, STEP_WEST } }, { 3, { STEP_NORTH, STEP_EAST, STEP_WEST } }, { 2, { STEP_SOUTH, STEP_WEST } }, { 3, { STEP_NORTH, STEP_SOUTH, STEP_WEST } }, { 3, { STEP_EAST, STEP_SOUTH, STEP_WEST } }, { 4, { STEP_NORTH, STEP_EAST, STEP_SOUTH, STEP_WEST } } }; const unsigned int step = rand() % step_info[dirs].num_dirs; *px = x + step_info[dirs].deltas[step].dx; *py = y + step_info[dirs].deltas[step].dy; } int main(void) { unsigned int w = 16, h = 16, x = w / 2, y = h / 2, i; struct timeval t1, t2; double seconds; srand(time(NULL)); gettimeofday(&t1, NULL); for(i = 0; i < 100000000; i++) { random_walk(&x, &y, w - 1, h - 1); } gettimeofday(&t2, NULL); seconds = (t2.tv_sec - t1.tv_sec) + 1e-6 * (t2.tv_usec - t1.tv_usec); printf("Took %u steps, final position is (%u,%u) after %.2g seconds => %.1f Msteps/second\n", i, x, y, seconds, (i / 1e6) / seconds); return EXIT_SUCCESS; } </code></pre> <p>Some explanations might be in order, the above is pretty opaque until you "get" it, I guess:</p> <ul> <li>The interface to the function itself should be clear. Note that width and height of the grid are represented as "<code>max_x</code>" and "<code>max_y</code>", to save on some constant-subtractions when checking if the current position is on the border or not.</li> <li>The variable <code>dirs</code> is set to a bit-mask of the "open" directions to walk in. For an empty grid, this is always 0x0f unless you're on a border. This could be made to handle walls by testing the map, of course.</li> <li>The <code>step_info</code> array collects information about which steps are available to take from each of the 16 possible combinations of open directions. When reading the initializations (one per line) of each <code>struct</code>, think of that struct's index in binary, and convert that to bits in <code>dirs</code>.</li> <li>The <code>STEP_NORTH</code> macro (and friends) cut down on the typing, and make it way clearer what's going on.</li> <li>I like how the "meat" of <code>random_walk()</code> is just four almost-clear expressions, it's refreshing to not see a single <code>if</code> in there.</li> </ul> <p>When compiled with gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 on my 2.4 GHz x86_64 system, using optimization level -O3, the performance seems to be just short of 36 million steps per second. Reading the assembly the core logic is branch-free. Of course there's a call to <code>rand()</code>, I didn't feel like going all the way and implementing a local random number generator to have inlined.</p> <p><strong>NOTE</strong>: This doesn't solve the exact question asked, but I felt the technique was worth expanding on.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload