How to choose a (valid) random adjacent point in an array of integers in C?

Assume that we have an array of integers (3x3) depicted as follows:

+-+-+-+
| |1| |
+-+-+-+
|0|x|1|
+-+-+-+
| |0| |
+-+-+-+

(0,1) above is set to 1 and (1,0) is 0 etc.

Now assume that I find myself at (1,1) (at x), what would be the easiest method for me to come up with all the directions I can take (say all that have the value 0) and then among those choose one?

What I'm having trouble with is actually the step between choosing all valid directions and then choosing among those. I can do the two steps seperately fairly easily but I don't have a solution that feels elegant which combines the two.

E.g. I can multiply the value of each cell by a value representing 1,2,4 and 8 and or them all together. this would give me what directions I can take, but how to choose between them? Also I can easily randomize a number between 1 and 4 to choose a direction but if th开发者_StackOverflow中文版at direction is "taken" then I have to randomize again but excluding the direction that failed.

Any ideas?

The fastest solution is likely the last one you posted -- choose directions randomly, repeating until you get a valid one. That will take at most four tries (the worst case is when there is only one valid neighbor). Something more elegant is to iterate through all possible directions, updating a variable randomly at each valid neighbor, such as this pseudocode:

c = 1
r = invalid
for i in neighbors:
  if (valid[i]):
    if (rand() <= 1. / c): r = i
    ++c

and then r is the answer (c is the number of valid neighbors found so far).

Here's a very neat trick in pseudocode

1. Initialise your "current result" to nil
2. Initialise a "number found" to 0
3. Loop through all the possible directions. If it is valid then:
   • increment "number found"
   • set "current result" to the direction with probability 1/"number found"

At the end of this, you will have a valid direction (or nil if not found). If there are multiple valid directions, they will all be chosen with equal probability.

Assumed:

Each location has a set number of valid target locations (some location may have fewer valid targets, a chess-knight has fewer valid targets when placed in a corner than when in the middle of the board.)

You want to pick a random target from all available, valid moves.

Algorithm:

Create a bit-array with one one bit representing each valid target. (In the original example you would create a four bit array.)

For each valid target determine if the location is empty; set the corresponding bit in the bit-array to 1 if empty.

If bit-array > 0 then number_of_targets = SUM(bit-array), else return(No Valid Moves).

Pick random number between 1 and number_of_targets.

return(the location associated with the nth set bit in the bit-array)

Example using the the original question:

X has four valid moves. We create a 4-bit array and fill it in with '1' for each empty location; starting with the cell directly above and moving in a clockwise direction we end up with :0:0:1:1:

The sum of bits tells us we have two places we can move. Our random selection will choose either '1' or '2'. We move through the bit-array until we find the nth set bit and move to that location.

This algorithm will work for any system with any number of valid targets (not limited to 2-D). You can replace the Random number selector with a function that recursively returns the best move (MIN-MAX algorithm.)

A slighly contrived way might be this (pseudo-code):

1. Build the bit-mask as you describe, based on which neighbors are open.

2. Use that bit-mask as the index into an array of:

   struct RandomData
{
size_t num_directions;
struct { signed int dx, dy; } deltas[4];
} random_data[16];

   where num_directions is the number of open neighbors, and deltas[] tells you how to get to each neighbor.

This has a lot of fiddly data, but it does away with the looping and branching.

UPDATE: 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.

Anyway, here's a complete, tested and working implementation of the random-stepping function using the above ideas:

/* 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;
}

Some explanations might be in order, the above is pretty opaque until you "get" it, I guess:

• The interface to the function itself should be clear. Note that width and height of the grid are represented as "max_x" and "max_y", to save on some constant-subtractions when checking if the current position is on the border or not.
• The variable dirs 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.
• The step_info 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 struct, think of that struct's index in binary, and convert that to bits in dirs.
• The STEP_NORTH macro (and friends) cut down on the typing, and make it way clearer what's going on.
• I like how the "meat" of random_walk() is just four almost-clear expressions, it's refreshing to not see a single if in there.

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 rand(), I didn't feel like going all the way and implementing a local random number generator to have inlined.

NOTE: This doesn't solve the exact question asked, but I felt the technique was worth expanding on.