Слегка придуманный способ (псевдокод):
- Создайте битовую маску, как вы описываете, в зависимости от того, какие соседи открыты.
Используйте эту битовую маску в качестве индекса в массиве:
struct RandomData<br>
{<br>
size_t num_directions;<br>
struct { signed int dx, dy; } deltas[4];<br>
} 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.
При компиляции с помощью gcc (Ubuntu / Linaro 4.4.4-14ubuntu5) 4.4.5 на моей системе с частотой 2,4 ГГц x86_64 с использованием уровня оптимизации -O3 производительность, по-видимому, едва достигает 36 миллионов шагов в секунду. При чтении сборки ядро логики не имеет ветвей. Конечно, есть звонок в rand(), мне не хотелось идти до конца и реализовывать локальный генератор случайных чисел, чтобы встроить.
ПРИМЕЧАНИЕ : Это не решает точный заданный вопрос, но я чувствовал, что технику стоит расширить.