# BFS and Voronoi diagrams using bit-shift operations

wlesavo
1,984 views

### Open Source Your Knowledge, Become a Contributor ## Great Escape

Lets proceed with an example, but first we need some brief introduction to general movement on grid operations.

## Coordinates and connections on a grid

A common way to store a 2-dimensional array is to put it in 1-dimensional array performing a simple transformation for coordinates

``````int pos = x + y * WIDTH;
``````

with a back transformation

``````int x = pos%WIDTH;
int y = pos/WIDTH;
``````

To move position say UP, we would have to do it the hard way

``````int x = pos%WIDTH;
int y = pos/WIDTH;
int new_x = x;
int new_y = y - 1;
// perform all necessary out of bounds checks
int new_pos = new_x + new_y * WIDTH;
``````

But there is also an equivalent unsafe method to do the same

``````int new_pos = pos - WIDTH;
``````

This is quite faster, but we have to make sure that an impossible moves will be rejected.

Lets move on. To perform a simple BFS we will store connections for each direction in a single uint128_t value. Set bit for connection would mean that it is possible to walk from current possition to a corresponding direction.

``````class State{
public:
uint128_t con = {};
int player_pos = pos;
}
``````

To set or reset bit we will use a simple well known functions

``````template <class T>
static inline void set_bit(T& val, int n){
val |= (T)1 << n;
}
template <class T>
static inline void reset_bit(T& val, int n){
val &= ~((T)1 << n);
}
``````

Preparing the state is described in the executed code example, although during the search we may simply turn on and off the connections needed, so that this connections will always be in an actualized state.

## Performing bit-shift BFS for finding the shortest path length

To perform a BFS we will need a containers to store current positions along with all visited positions. To move all current possitions in some direction (for example UP) we perform 'and' and 'shift' operations.

``````(cur&con[d])>>WIDTH;
``````

Here 'and' opperation resets all currently stored positions to 0 if the move in chosen direction is impossible, making it ready to use the 'unsafe' move, described above. This way moving simultaneously in all directions is performed by simply merging all the moves for URDL with 'or'. We also will have to keep track of all visits to not go back to visited cells. Basically we are done, a simple BFS then will look like this

``````int BFS(const State& s){
uint128_t cur = 0;
set_bit(cur, s.player_pos);
uint128_t visits = cur;
int dist = 0;
while (true) {
if (cur==0){
return dist;
}
cur = (cur&s.con)>>WIDTH | (cur&s.con)<<1 | (cur&s.con)<<WIDTH | (cur&s.con)>>1;
cur &= ~visits;
visits |= cur;
dist += 1;
}
return -1;
}
``````

The attentive reader would notice that here BFS misses win condition, so it performs a full scout until all reachable cells are visited. We will further fix this in the final executable example.

## Code example

In the executable example the connections preparation and win masks calculation are demonstrated.

Great escape shortest path calculation example
Open Source Your Knowledge: become a Contributor and help others learn.  