假设我们有描绘整数（3×3）的阵列如下：如何选择C中整数数组中的（有效）随机相邻点？
+-+-+-+
| |1| |
+-+-+-+
|0|x|1|
+-+-+-+
| |0| |
+-+-+-+
（0,1）上面被设置为1和（1,0）为0等
现在假设我发现自己在（1,1）（at x）时，对于我来说我可以拿出所有的方向（比如说所有的值都是0）最简单的方法是什么，然后再选择一个方向？
我遇到麻烦实际上是选择所有有效方向然后在其中进行选择的步骤。我可以很简单地单独完成这两个步骤，但我没有一个将两者结合在一起的感觉优雅的解决方案。
E.g.我可以将每个单元格的值乘以表示1,2,4和8的值，或者将它们全部放在一起。这会给我我可以采取的方向，但是如何在它们之间进行选择？此外，我可以很容易地随机选择1到4之间的数字来选择方向，但是如果该方向被“取走”，那么我必须再次随机化，但排除失败的方向。
任何想法？
最快的解决方案可能是您发布的最后一个解决方案 - 随机选择路线，重复，直到您获得有效路线。这最多需要四次尝试（最糟糕的情况是只有一个有效邻居）。一些更优雅是通过所有可能的方向迭代，每个有效的邻居随机更新变量，像这样的伪代码：
c = 1
r = invalid
for i in neighbors:
if (valid[i]):
if (rand() <= 1./c): r = i
++c
，然后r是答案（c是迄今发现的有效邻的数量） 。
下面是伪代码一个非常巧妙的方法
在本月底“发现号”，你将会有一个有效的方向（如果没有找到，则为零）。如果有多个有效的方向，它们将以相等的概率被选择。
一个性能稍微做作的方式可能是这（伪代码）：
使用位掩码为索引的数组：
struct RandomData
{
size_t num_directions;
struct { signed int dx, dy; } deltas[4];
} random_data[16];
其中num_directions是打开邻居的数量，以及deltas[]告诉你怎么去每个邻居。
这有很多繁琐的数据，但它消除了循环和分支。
更新：好吧，出于某种原因，我有问题让这个想法去。我在工作中责备关于“数据驱动编程”的一定程度的灌输，因为这个非常简单的问题使我“认识到”数据驱动性更好一些。这总是很好。
不管怎么说，这是一个完整的，经过测试和使用工作实施随机步进功能的上述思路：
/* 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;
}
一些解释可能是为了，上面是非常不透明的，直到你“搞定”它，我猜：
max_x”和“max_y”，以便在检查当前位置是否在边框上时保存一些常量减法。dirs设置为“打开”方向的位掩码。对于空网格，除非您位于边框上，否则这总是为0x0f。当然，这可以通过测试地图来处理墙壁。step_info阵列收集有关哪些步骤可以从16种可能的开放方向组合中的每一种获取的信息。当读取每个struct的初始化值（每行一个）时，请考虑二进制的结构索引，并将其转换为dirs中的位。STEP_NORTH宏（和朋友）减少了打字，并使其更清晰地发生了什么。random_walk()的“肉”如何只是四个几乎清晰的表达式，它令人耳目一新，看不到一个单一的if。在我的2.4 GHz x86_64系统上使用gcc（Ubuntu/Linaro 4.4.4-14ubuntu5）4.4.5进行编译时，使用优化级别-O3，性能似乎仅为每秒3600万步。阅读程序集的核心逻辑是无分支的。当然有一个rand()的电话，我不想一路走下来，并实施一个本地随机数发生器已经内联。
注意：这并没有解决问的确切问题，但我觉得这项技术值得扩展。
假设：
每个位置都有有效的目标位置的设定数量（一些位置可具有更少的有效目标，放置在拐角比在板的中间时，当国际象棋骑士具有较少的有效目标）
你想从所有可用的有效移动中选择一个随机目标。
算法：
创建一个比特阵列与一个一比特表示每个有效的目标。 （在原始示例中，您将创建一个四位数组。）
对于每个有效的目标确定位置是空的;如果为空，则将位阵列中的相应位设置为1。
如果位阵列> 0，那么NUMBER_OF_TARGETS = SUM（位阵列），否则返回（没有有效的移动）。
选择1和number_of_targets之间的随机数。
回报（与位阵列中的第n个组的位相关联的位置）
实施例使用原来的问题：
X具有四个有效移动。我们创建一个4位数组，并为每个空位置填入'1';上面开始与细胞直接和在我们最终有沿顺时针方向移动：0：0：1：1：
位的总和告诉我们，我们有两个地方我们可以移动。我们的随机选择将选择'1'或'2'。我们在位阵列中移动，直到找到第n个位集合并移动到该位置。
该算法将与任意数量的有效目标（不限于2-d）任何系统中工作。您可以用递归返回最佳移动（MIN-MAX算法）的函数替换随机数字选择器。
感谢您的快速回答:) – 2011-01-21 13:29:03
从技术上讲，随机方向方法可能需要无限次数的尝试，只有一个有效的方向....你可能非常不走运！ – mikera 2011-01-21 13:31:24
是的，我同意它可以采取无限数量的尝试（只要有任何无效的方向，它就可以），但平均数量为四，尝试次数不可能非常高。 – 2011-01-21 13:33:03