• 69k
• 3
• 74
• 180

• 69k
• 3
• 74
• 180

Avoid unnecessary type conversions

kDIRECTIONS is a 2D array of std::int_fast8_t. However, these values will be added to other variables of type std::int_fast16_t. If these two types have a different size, then the compiler might have to add instructions to convert between the two, and despite having "fast" in the name, this will be slow.

Avoid overusing std::array

std::array has its uses, but here you can just use a simply C-style array:

static constexpr size_type kDIRECTIONS[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};

That is much easier to read than nested std::arrays, and will work just as well in the rest of your code without needing any modifications.

Avoid overusing std::size()

Instead of writing std::size(grid), you can write grid.size(). It avoids having to type the std::, and reads a bit more natural. Also, don't use std::size() or .size() to check if a container has members, instead use !something.empty(), like:

while (!player_box_q.empty()) {
 ...
}

The reason is that counting the number of elements can be expensive for containers that do not keep an explicit count in memory, but have to traverse the whole container to derive that number.

Use structured bindings where appropriate

Since you are writing C++17 code, you can use structured bindings, which makes code using std::pair much nicer. For example:

while (qlen--) {
 const auto [box_pos, player_pos] = player_box_q.front();
 ...

Avoid encoding things to string

I can see your reasoning: "an unordered_set<> is faster than a set<>. But the standard library doesn't know how to hash a std::pair, so I can't use an unordered_set<std::pair<size_type, size_type>. But it does allow std::string... I know, let's encode the pair to a string!" However, encoding two ints to a string is in itself quite expensive.

The proper solution is to create a custom hash function for the box/player coordinate pairs, and tell std::unordered_set to use it. There are several ways to do this, the way I will show here is to create a functor class and pass it as a template argument:

struct player_box_hash {
 std::size_t operator()(const std::pair<size_type, size_type> &key) const {
 return key.first << 16 | key.second;
 }
};
std::unordered_set<std::pair<size_type, size_type>, player_box_hash> box_player_visited;

And now you can use it as follows:

auto box_player_encode = std::make_pair(box, next_x_player * col_len + next_y_player);
if (box_player_visited.count(box_player_encode)) {
 continue;
}
if (isAccessible(grid, player, next_x_player * col_len + next_y_player, box)) {
 player_box_q.push({next_x_box * col_len + next_y_box, box});
 box_player_visited.insert(box_player_encode);
}

Create a function to check whether a position is valid

You have duplicated the code to check whether the box's position and player's position is valid. Create a member function for it:

static bool isValidPosition(size_type x, size_type y) {
 return x >= 0 && x < row_len && ...;
}

And then use it like so:

for (const auto &direction: kDIRECTIONS) {
 ...
 if (!isValidPosition(next_x_box, next_y_box) || !isValidPosition(next_x_player, next_y_player)) {
 continue;
 }
 ...
}