Sokoban/C: Difference between revisions
m
Fixed syntax highlighting.
m (replace asserts) |
m (Fixed syntax highlighting.) |
||
| (One intermediate revision by one other user not shown) | |||
Line 1:
C99.
<
#include <stdlib.h>
#include <string.h>
Line 11:
int w, h, n_boxes;
int offset[4] = {0, 0, 1, -1};
uint8_t *board, *goals, *live, *tmpmap;
int *dist;
Line 94:
w = x, h = y;
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( live = calloc(w * h, sizeof(uint8_t)) );
Line 134 ⟶ 135:
}
memcpy(tmpmap, board, sizeof(uint8_t) * w * h);
return state;
}
Line 233 ⟶ 235:
buckets[i] = 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 ⟶ 261:
{
for (int i = 1; i <= n_boxes; i++)
if (!live[s->c[i]]) return 1;
return 1;▼
sort_state(s);
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;
}
Line 315 ⟶ 379:
n->c[i] = (s->c[i] == c1) ? c2 : s->c[i];
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;
}
Line 505 ⟶ 556:
" ##### "
" # # "
" #
" ### $## "
" # $ $ # "
"### # ## # ######"
"# # ## ##### ..#"
"# $ $
"##### ### #@## ..#"
" # #########"
Line 537 ⟶ 588:
for (int d = 1; d < known_moves; d++) {
state_t *s = queue[d];
printf("depth %d (%d records, mem: %d/%dM)\r", d,
filled * state_size / (1 << 20),
alloced * state_size / (1 << 20));
fflush(stdout);
Line 553 ⟶ 606:
free(buckets);
free(board);
free(tmpmap);
free(goals);
free(live);
Line 565 ⟶ 619:
return 0;
}</
| |||