Случайное блуждание по сетке

// generate a random "walk" of letters from A to Z in a 2D grid, assuming a 
// character set with contiguous values of uppercase letters (e.g. ASCII); 
// stops if the "walker" gets stuck
// example of a successful walk:

//  A  .  .  .  I  J  K  .  .  . 
//  B  C  F  G  H  .  L  .  .  .
//  .  D  E  .  .  .  M  .  .  .
//  .  .  .  .  .  O  N  .  .  .
//  .  .  .  .  .  P  .  .  .  .
//  .  .  .  .  .  Q  .  .  .  .
//  .  .  .  .  .  R  S  .  .  .
//  .  .  .  .  .  .  T  U  .  . 
//  .  .  .  .  .  .  .  V  W  Z
//  .  .  .  .  .  .  .  .  X  Y

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>

#define GRID_SIZE 10

// movement directions
#define DIR_NUM 4

#define UP      0
#define LEFT    1
#define DOWN    2
#define RIGHT   3
#define ANY     (-1)

bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid[rows][cols]);
void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols]);
void print_array(size_t rows, size_t cols, char grid[rows][cols]);

int main(void)
{
    char grid[GRID_SIZE][GRID_SIZE] = { 0 };

    generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
    print_array(GRID_SIZE, GRID_SIZE, grid);

    return 0;
}

void print_array(size_t rows, size_t cols, char grid[rows][cols])
{
    for (size_t r = 0; r < rows; ++r) {
        for (size_t c = 0; c < cols; ++c) {
            char grid_c = grid[r][c];
            printf(" %c ", isalpha(grid_c) ? grid_c : '.');
        }
        putchar('n');
    }
}

// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid[rows][cols])
{
    bool cangoup    = (rpos > 0) && grid[rpos - 1][cpos] == 0;
    bool cangoleft  = (cpos > 0) && grid[rpos][cpos - 1] == 0;
    bool cangodown  = (rpos < rows - 1) && grid[rpos + 1][cpos]  == 0;
    bool cangoright = (cpos < cols - 1) && grid[rpos][cpos + 1]  == 0;

    switch (dir) {
    case UP:    return cangoup;
    case LEFT:  return cangoleft;
    case DOWN:  return cangodown;
    case RIGHT: return cangoright;
    default:    return cangoup || cangoleft || cangodown || cangoright; // ANY
    }
}

void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
    size_t rpos, cpos;

    srand((unsigned int) time(NULL));

    rpos = cpos = 0;
    grid[0][0] = 'A';
    for (char c="B"; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
        // move in a random direction
        for (int dir;;) {
            dir = rand() % DIR_NUM;
            if (can_move(dir, rpos, cpos, rows, cols, grid)) {
                switch (dir) {
                case UP:    --rpos; break;
                case LEFT:  --cpos; break;
                case DOWN:  ++rpos; break;
                case RIGHT: ++cpos; break;
                default:
                    printf("Impossible movement direction.n");
                    exit(EXIT_FAILURE);
                }
                break; // break out of the loop
            }
        }

        // leave a trail
        grid[rpos][cpos] = c;
    }
}

Подводя итог, эта программа печатает сетку со случайным блужданием заглавных букв по порядку. Если «шагающий» не может двигаться в любом направлении из-за недостатка пространства вокруг него (вверх, вниз, влево и вправо), ходьба прекращается.

Помимо общих советов относительно моего кода, которые вы можете мне дать, меня интересуют две вещи:

  1. Я читал, что функции обычно не должны принимать более 2–3 параметров; Как вы думаете, мои функции действительно «страдают» от приема более трех параметров, и если да, как мне это смягчить?

  2. Должен ли я использовать size_t при переходе по массиву или подобному, или я должен использовать int вместо? Я прочитал здесь, на Stack Exchange, различные мнения по этому поводу: некоторые люди говорят size_t всегда следует использовать, поскольку это, по сути, неопределенное поведение, если размер массива больше, чем MAX_INTи т. д., в то время как другие говорят, что неподписанные и подписанные типы не следует смешивать (и мне обычно приходится использовать их в выражениях, которые подвергаются обычным арифметическим преобразованиям), и это основной источник ошибок. С прагматической точки зрения, я считаю, что мне следует использовать обычный int. Я заметил еще одну вещь: если мне действительно нужно использовать эти счетчики для выполнения некоторых вычислений: в этих случаях у меня действительно нет выхода, и то, что я в конечном итоге делаю, просто кастинг и молитва, надеясь, что массив имеет разумный размер (т. е. что мой size_t счетчик, или результат выражения не выходит за пределы представимого диапазона для int). Я думаю, это даже хуже, чем использовать int с самого начала, так как интерфейс что size_t Тип предоставляет не соответствует, поэтому мой код «лжет» и себе, и читателю.

Обратите внимание, что я бы использовал enum вместо #define определения направлений, но моя книга еще не дошла до них, поэтому я думаю, что нам не следует сосредотачиваться на этом. Кроме того, в том же упражнении я рассмотрел и другие вопросы, но представленный там код / ​​подход несколько отличается.

1 ответ
1

Ответы на ваши вопросы

Я читал, что функции обычно не должны принимать более 2–3 параметров.

Я бы не стал слишком об этом беспокоиться. Однако, если у вас есть много параметров, вам следует подумать, действительно ли они необходимы, и, возможно, есть ли способ сгруппировать их в struct, и передавать ли это по значению или по указателю. Например, вашему коду может быть полезно создать struct для хранения координат, например:

typedef struct {
    size_t row;
    size_t col;
} vec2;

Затем вы можете уменьшить количество передаваемых параметров:

bool can_move(int dir, vec2 pos, vec2 size, char grid[size.row][size.col])

Это не должно изменить сгенерированный машинный код, но сделает его более читаемым.

Должен ли я использовать size_t при переходе по массиву или подобному, или я должен использовать int вместо?

Я бы рекомендовал использовать size_t. В частности, size_t гарантированно будет достаточно большим, чтобы вместить размер любого массива, и поэтому вы должны также использовать его для индекса массива. Он также беззнаковый, что упрощает проверку границ. Смешивание size_t а также int это, конечно, плохо, убедитесь, что у вас включены предупреждения компилятора, чтобы компилятор мог предупредить вас о таких проблемах и исправить все предупреждения, которые вы видите.

то, что я в конечном итоге делаю, это просто молюсь и молюсь,

Не делай этого! Используйте типы последовательно и избегайте ненужных приведений. Похоже, вы все еще изучаете C, вы, вероятно, выучите все подробности в какой-то момент, и тогда вместо этого вы будете рассуждать об этих вещах. Если вам все еще нужно где-то провести кастинг, и вы не уверены, что это безопасно, спросите Переполнение стека.

Избегайте ненужных предварительных деклараций

Если вы измените порядок, в котором функция появляется в исходном файле, вам больше не нужны форвардные объявления. Это позволяет избежать повторения, а также позволяет избежать потенциальных ошибок.

Использовать enum или же static const переменные

Обратите внимание, что я бы использовал enum вместо #define определения направлений,

Правильно, используя enum здесь было бы намного лучше.

но моя книга до них еще не дошла, так что я думаю, нам не стоит заострять внимание на этом.

Мы должны, поскольку другие люди также могут прочитать ваш вопрос здесь, и они не могут быть ограничены тем, насколько далеко они находятся в конкретной книге! Но это нормально, если вы хотите проигнорировать это на данном этапе. Но помимо enums, еще одна возможность избежать использования #define использовать static const переменные:

static const int UP = 0;
static const int LEFT = 1;
...
static const int ANY = -1;

Преимущество этого состоит в том, что эти константы теперь имеют правильный тип, и вам не нужно беспокоиться о том, как работает макро-подстановка, поэтому меньше шансов забыть круглые скобки, как если бы вы правильно добавили к ANY.

Вам все еще нужно использовать #define для GRID_SIZE хотя, к сожалению, const переменная недостаточно хороша для C, поскольку размер при объявлении множество (если это не VLA).

Приятнее for-заявления

Реализация случайного блуждания выглядит неплохо. Тем не менее forпетли в generate_random_walk() для меня это выглядит немного странно. Внешний for-loop начинается в B вместо A. Я бы лучше написал так, чтобы это выглядело так:

for (char c="A"; c <= 'Z'; c++) {
    ...
}

Потому что в этом случае четко указано, что вы хотите выполнить цикл из 'A' к 'Z' в одной строке. Внутренний for-statement тоже странный, он ничего не делает, кроме delcare переменной. По сути, это бесконечный цикл и более идеальный способ записи, использующий while (true). Я бы структурировал это примерно так:

for (char c="A"; c <= 'Z'; c++) {
    grid[rpos][cpos] = c;

    if (!can_move(ANY, ...)) {
        break;
    }

    while (true) {
        int dir = rand() % DIR_NUM;
        ...
    }
}

Другой вариант — изменить can_move() поэтому он попытается сделать случайный ход и вернется true в случае успеха или false если бы он больше не мог двигаться. Затем его также следует переименовать, например, в try_random_move()и используйте указатели для rpos а также cpos поэтому они могут быть изменены:

bool try_random_move(size_t *rpos, size_t *cpos, ...) {
    bool cangoup    = (*rpos > 0) && grid[*rpos - 1][*cpos] == 0;
    bool cangoleft  = (*cpos > 0) && grid[*rpos][*cpos - 1] == 0;
    bool cangodown  = (*rpos < rows - 1) && grid[*rpos + 1][*cpos] == 0;
    bool cangoright = (*cpos < cols - 1) && grid[*rpos][*cpos + 1] == 0;

    if (!(cangoup || cangoleft || cangodown || cangoright)) {
        return false;
    }

    while (true) {
        int dir = rand() % DIR_NUM;
        ...
    }
}

потом generate_random_walk() упрощается до:

void generate_random_walk(size_t rows, size_t cols, char grid[rows][cols])
{
    size_t rpos = 0;
    size_t cpos = 0;

    for (char c="A"; c <= 'Z'; c++) {
        grid[rpos][cpos] = c;

        if (!try_random_move(&rpos, &cpos, rows, cols, grid)) {
            break;
        }
    }
}

Как избежать «бесконечного» цикла

Вы выбираете случайное направление, а затем проверяете, возможно ли движение в этом направлении. Если нет, вы пробуете другое случайное направление. Проблема в том, что для выбора правильного направления может потребоваться много попыток, так как со случайными числами никогда не знаешь. Возможный способ избежать повторения случайных попыток — просто попробовать все оставшиеся возможности. Однако вы должны быть осторожны, чтобы не вводить случайная предвзятость в вашем алгоритме.

  • Большое спасибо за каждую мелочь. У меня есть несколько дополнительных вопросов по поводу некоторых советов: 1. «Если вы измените порядок, в котором функция появляется в исходном файле, вам больше не нужны форвардные объявления». В чем заключается реальный недостаток форвардных деклараций? Прямо сейчас они очень полезны, потому что мне даже не нужно думать о порядке объявления функций — зачем мне вообще? Вы думаете, что эти функции чрезмерно «загрязняют» пространство имен?

    — JCC

  • 2. Причина for цикл начинается с 'B' потому что если я начну с 'A', Идентификатор всегда необходимо проверить в цикле, c == 'A', потому что обычно вы не можете попасть в позицию (0, 0) (ты уже там). Вы думаете, что это лишняя лишняя проверка каждый итерация цикла не имеет значения? (Я знаю, что использовал эти 4 bools в той другой функции, которая всегда оцените около 8 сравнений, что также является ненужным вычислением.) В качестве общего принципа приемлем ли этот шаблон: for (int i = 0; ...) { if (i == 0) dosomething(); /*rest of the loop*/ }?

    — JCC

  • 3. Не вопрос, а комментарий к try_random_move: это именно то, что я сделал бы, просто мы еще не сделали указатели, но хорошо, что вы включили это, чтобы люди это знали. На самом деле у меня есть вопрос: я не уверен, почему мне следует избегать таких вещей, как for (int dir;;) потому что здесь я проясняю декларация что я буду использовать только dir внутри этого for цикл, сохраняя при этом бесконечный цикл. Я думаю, что это очень удобно, потому что это одно объявление, которое не повторяется снова и снова (что является своего рода раздражением).

    — JCC

  • 1

    1. Вы можете сделать опечатку в форвардном объявлении. Дело не в загрязнении пространства имен, используйте static для этого. 2. Если вы начинаете цикл с c = 'A', первое, что вы делаете в теле, это безоговорочно пишете c в текущую позицию в сетке, поэтому нет необходимости в явной проверке. 3. Объявление переменной внутри тела for-loop не «повторяется снова и снова». Место в стеке резервируется для него только один раз, даже без включенной оптимизации компилятора (см. godbolt.org/z/ea7fcP667 для примера).

    — Г. Сон

  • 1. Итак, вы говорите, что возможное несоответствие между объявлением в прототипе функции и определением может привести к ошибкам? Это то, что ты имеешь в виду?

    — JCC

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *