Sokoban/C: Difference between revisions

Content added Content deleted
m (replace asserts)
(added some easy deadlock checks)
Line 11: Line 11:
int w, h, n_boxes;
int w, h, n_boxes;
int offset[4] = {0, 0, 1, -1};
int offset[4] = {0, 0, 1, -1};
uint8_t *board, *goals, *live;
uint8_t *board, *goals, *live, *tmpmap;
int *dist;
int *dist;


Line 94: Line 94:
w = x, h = y;
w = x, h = y;
ensure( board = calloc(w * h, sizeof(uint8_t)) );
ensure( board = calloc(w * h, sizeof(uint8_t)) );
ensure( tmpmap= calloc(w * h, sizeof(uint8_t)) );
ensure( goals = calloc(w * h, sizeof(uint8_t)) );
ensure( goals = calloc(w * h, sizeof(uint8_t)) );
ensure( live = calloc(w * h, sizeof(uint8_t)) );
ensure( live = calloc(w * h, sizeof(uint8_t)) );
Line 134: Line 135:
}
}


memcpy(tmpmap, board, sizeof(uint8_t) * w * h);
return state;
return state;
}
}
Line 233: Line 235:
buckets[i] = s;
buckets[i] = s;
return s;
return s;
⚫
}

inline void sort_state(state_t *n)
{
⚫
// leet bubble sort: boxes are indistinguishable
⚫
cidx_t *p = n->c;
⚫
for (int i = n_boxes; --i; ) {
⚫
cidx_t t = 0;
⚫
for (int j = 1; j < i; j++) {
⚫
if (p[j] > p[j + 1])
⚫
t = p[j], p[j] = p[j+1], p[j+1] = t;
⚫
}
⚫
if (!t) break;
}
}
}


Line 245: Line 261:
{
{
for (int i = 1; i <= n_boxes; i++)
for (int i = 1; i <= n_boxes; i++)
if (!live[s->c[i]])
if (!live[s->c[i]]) return 1;

⚫
return 1;
sort_state(s);
return 0;

int ret = 0;
for (int i = 1; i <= n_boxes; i++)
tmpmap[s->c[i]] = box;

/* check if two boxes are next to each other and sitting along a wall
or some such */
for (int i = 1; i < n_boxes; i++) {
int x = s->c[i];
int y = s->c[i + 1];
if (y == x + 1 && !(goals[x] && goals[y])) {
if ((tmpmap[x - w] >= wall && tmpmap[y - w] >= wall) ||
(tmpmap[x + w] >= wall && tmpmap[y + w] >= wall))
{
ret = 1;
goto bail;
}
if ((tmpmap[x - w] == wall || tmpmap[x + w] == wall) &&
(tmpmap[y - w] == wall || tmpmap[y + w] == wall))
{
ret = 1;
goto bail;
}
}
for (int j = i + 1; j <= n_boxes; j++) {
y = s->c[j];

if (y == x + w) {
if (goals[x] && goals[y]) continue;
if ((tmpmap[x - 1] >= wall && tmpmap[y - 1] >= wall) ||
(tmpmap[x + 1] >= wall && tmpmap[y + 1] >= wall))
{
ret = 1;
goto bail;
}
if ((tmpmap[x - 1] == wall || tmpmap[x + 1] == wall) &&
(tmpmap[y - 1] == wall || tmpmap[y + 1] == wall))
{
ret = 1;
goto bail;
}
}
}
}
bail: for(int i = 1; i <= n_boxes; i++)
tmpmap[s->c[i]] = space;

⚫
return ret;
}
}


Line 315: Line 379:
n->c[i] = (s->c[i] == c1) ? c2 : s->c[i];
n->c[i] = (s->c[i] == c1) ? c2 : s->c[i];
n->c[0] = c1;
n->c[0] = c1;

⚫
cidx_t *p = n->c;

⚫
// leet bubble sort: boxes are indistinguishable
⚫
for (int i = n_boxes; --i; ) {
⚫
cidx_t t = 0;
⚫
for (int j = 1; j < i; j++) {
⚫
if (p[j] > p[j + 1])
⚫
t = p[j], p[j] = p[j+1], p[j+1] = t;
⚫
}
⚫
if (!t) break;
⚫
}

return n;
return n;
}
}
Line 505: Line 556:
" ##### "
" ##### "
" # # "
" # # "
" # # "
" #$ # "
" ### $## "
" ### $## "
" # $ $ # "
" # $ $ # "
"### # ## # ######"
"### # ## # ######"
"# # ## ##### ..#"
"# # ## ##### ..#"
"# $ $ .#"
"# $ $ ..#"
"##### ### #@## ..#"
"##### ### #@## ..#"
" # #########"
" # #########"
Line 537: Line 588:
for (int d = 1; d < known_moves; d++) {
for (int d = 1; d < known_moves; d++) {
state_t *s = queue[d];
state_t *s = queue[d];
printf("depth %d (mem: %dM)\r", d, alloced * state_size / (1 << 20));
printf("depth %d (%d records, mem: %d/%dM)\r", d, filled,
filled * state_size / (1 << 20),
alloced * state_size / (1 << 20));
fflush(stdout);
fflush(stdout);


Line 553: Line 606:
free(buckets);
free(buckets);
free(board);
free(board);
free(tmpmap);
free(goals);
free(goals);
free(live);
free(live);
Retrieved from "https://rosettacode.org/wiki/Sokoban/C"