void RoomGenerator::find_path()

in procgen/src/roomgen.cpp [71:124]

• 42 lines of code
• 15 McCabe index (conditional complexity)

void RoomGenerator::find_path(int src, int dst, std::vector<int> &path) {
    std::set<int> covered;
    std::vector<int> expanded;
    std::vector<int> parents;

    if (game->get_obj(src) != SPACE)
        return;

    expanded.push_back(src);
    parents.push_back(-1);

    int search_idx = 0;

    while (search_idx < int(expanded.size())) {
        int curr_idx = expanded[search_idx];

        if (curr_idx == dst)
            break;
        if (game->get_obj(curr_idx) != SPACE)
            continue;

        int x, y;
        game->to_grid_xy(curr_idx, &x, &y);

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if ((i == 0 || j == 0) && (i + j != 0)) {
                    int next_idx = game->to_grid_idx(x + i, y + j);

                    if (!set_contains(covered, next_idx) && game->get_obj(next_idx) == SPACE) {
                        expanded.push_back(next_idx);
                        parents.push_back(search_idx);
                        covered.insert(next_idx);
                    }
                }
            }
        }

        search_idx++;
    }

    if (expanded[search_idx] == dst) {
        std::vector<int> tmp;

        while (search_idx >= 0) {
            tmp.push_back(expanded[search_idx]);
            search_idx = parents[search_idx];
        }

        for (int j = (int)(tmp.size()) - 1; j >= 0; j--) {
            path.push_back(tmp[j]);
        }
    }
}