#include <stdio.h>
#include <stdlib.h> /* random */
#include <time.h>
#include <locale.h>
#include <ncurses.h>
static WINDOW *masterwin;
static WINDOW *golfwin;
static WINDOW *textwin;
#define UNK_REL (-1)
#define LT 0
#define GT 1
#define LE 2
#define GE 3
#define EQ 4
#define NE 5
#define UNK_TILE -2
#define WALL -1
#define NO_OBJ 0
typedef struct bot { /* Can store both reality, and our bot's view of reality */
int sunk; /* Internal variable. When sunk == 30, we're done. */
int seed;
int turn, view, ball, success; /* exported to user. Rest should be private. */
int x, y, direction, dir_x, dir_y;
int max_x, min_x, max_y, min_y;
int map[33][33]; /* unused extra space to simplify code */
} ENVIRONMENT;
ENVIRONMENT controller, bot;
/* convert compass to delta-xy */
int xdir(int dir) {return (dir&1)-(dir==3?2:0);}
int ydir(int dir) {return (1-(dir&1))-(dir==2?2:0);}
/* Ground Truth Movements */
void master_view(void) {
int steps; /* number of squares in the direction you are facing */
controller.success = 1; controller.view = 0;
for (steps = 1; !controller.view; steps++) { /* Facing a wall? > 15? or < 0? Return with view = 0 */
if ((((controller.x+controller.dir_x*steps) | (controller.y+controller.dir_y*steps)) >> 4)&1) return;
controller.view = controller.map[controller.x+controller.dir_x*steps][controller.y+controller.dir_y*steps];
}
}
void master_move(void) {
controller.turn += 1;
master_view();
if (((((controller.x+controller.dir_x) | (controller.y+controller.dir_y)) >> 4)&1) ||
(controller.map[controller.x+controller.dir_x][controller.y+controller.dir_y])) {
controller.success = 0; return; /* Facing a wall? > 15? or < 0?, or square not empty? */
}
controller.x += controller.dir_x; controller.y += controller.dir_y;
master_view();
}
void master_turn_to(int direction) {
controller.turn += 1;
controller.direction = direction%4; controller.dir_x = xdir(controller.direction); controller.dir_y = ydir(controller.direction);
master_view();
}
#define master_left() master_turn_to(controller.direction+3)
#define master_right() master_turn_to(controller.direction+1)
void master_interact(void) {
int obj=controller.map[controller.x+controller.dir_x][controller.y+controller.dir_y];
controller.turn += 1;
controller.success = 0;
if ((((controller.x+controller.dir_x) | (controller.y+controller.dir_y)) >> 4)&1) return; /* Facing a wall? > 15? or < 0? */
if (controller.ball != 0) { /* we are holding a ball */
if (obj == 0) { /* nothing in front of me */
controller.map[controller.x+controller.dir_x][controller.y+controller.dir_y] = controller.ball;
controller.ball = 0;
master_view();
return; /* place ball on ground */
} else if (obj == (controller.ball+4)) { /* correct hole? */
controller.sunk |= 1<<controller.ball; controller.ball = 0;
controller.success = 1; return; /* sink ball */
}
} else if ((1 <= obj) && (obj <= 4)) {
controller.ball = obj; /* pick up ball */
controller.map[controller.x+controller.dir_x][controller.y+controller.dir_y] = NO_OBJ; /* remove from board */
master_view();
} /* otherwise object is not a ball */
}
void initialise_controller(int seed) {
int location = seed%256, objtype = seed%15, i;
controller.seed = seed; controller.sunk = 0;
controller.turn = 0; controller.ball = 0;
controller.min_x = controller.min_y = 0;
controller.max_x = controller.max_y = 15;
for (controller.y = 0; controller.y <= 15; controller.y++)
for (controller.x = 0; controller.x <= 15; controller.x++)
controller.map[controller.x][controller.y] = NO_OBJ;
for (i = 1; i <= 15; i++) {
location = (location*93+19)%256; objtype = (objtype*106+17)%15;
if (objtype == 14) {
controller.x = location%16; controller.y = location/16;
controller.direction = location%4; controller.dir_x = xdir(controller.direction); controller.dir_y = ydir(controller.direction);
} else controller.map[location%16][location/16] = objtype+1;
}
master_view(); /* awaiting clarification from Martin */
}
#define initialise_controller_proc(procname, win, size, name) void procname(void) { \
int x, y; \
for (y = 0; y <= size; y++) \
for (x = 0; x <= size; x++) { \
wmove(win, size-y,x); \
wprintw(win, "%c", (name.x == x && name.y == y ? "^>v<"[name.direction] : (name.map[x][y] == 0 ? '_' : name.map[x][y]+'A'-1))); \
} \
wrefresh(win); \
}
initialise_controller_proc(draw_controller, masterwin, 15, controller)
initialise_controller_proc(draw_inference_map, golfwin, 32, bot)
int VC[2][14][16]; /* Variable REL Constant */
int VV[2][14][14]; /* Variable REL Variable */
#define X 0
#define Y 1
void reset_VC(void) {
int xy, var, value;
for (xy = X; xy <= Y; xy++)
for (var = 0; var <= 13; var++)
for (value = 0; value <= 15; value++)
VC[xy][var][value] = 1; /* everything is allowed until eliminated */
}
void reset_VV(void) {
int xy, var1, var2;
for (xy = X; xy <= Y; xy++)
for (var1 = 0; var1 <= 13; var1++)
for (var2 = 0; var2 <= 13; var2++)
VV[xy][var1][var2] = UNK_REL; /* A.x REL B.x */
}
void relate_vc(int VARindex, int xy, int REL, int val) {
/* Eliminate constants using A.x REL const.
It may be wrong to do these on the fly - perhaps the
relationship should be recorded and then the eliminations
done in a loop at the end, until no more eliminations
can be performed? It would be much better to use a
proper graph algorithm. Or even a good matrix algorithm
such as Warshall's.
*/
int num;
switch (REL) {
case LT: for (;;) {VC[xy][VARindex][val] = 0; val += 1; if (val > 15) break;} break;
case LE: for (;;) {val += 1; if (val > 15) break; VC[xy][VARindex][val] = 0;} break;
case GT: for (;;) {VC[xy][VARindex][val] = 0; val -= 1; if (val < 0) break;} break;
case GE: for (;;) {val -= 1; if (val < 0) break; VC[xy][VARindex][val] = 0;} break;
case EQ: for (num = 0; num <= 15; num++) {if (num != val) VC[xy][VARindex][num] = 0;} break;
case NE: VC[xy][VARindex][val] = 0; break;
}
}
void relate_vv(int VARindex1, int xy, int REL, int VARindex2) {
/* careful! A <= B might be followed by A != B, in which case
the relationship has to be updated to A < B.
There are other combinations of relationship which will
also need to be updated. However for any given column (which
is all that really matters) we know that X != Y as two items
cannot share the same space. */
VV[xy][VARindex1][VARindex2] = REL;
VV[xy][VARindex2][VARindex1] = REL^(REL < 4 ? 1/* symmetric */ : 0/* reversed */);
}
void report(int VARindex) {
int num;
wprintw(textwin, "%c.x = ", VARindex+'A');
for (num = 0; num <= 15; num++) {
if (VC[X][VARindex][num]) wprintw(textwin, "%d, ", num);
}
(void) waddstr(textwin, "\n");
wprintw(textwin, "%c.y = ", VARindex+'A');
for (num = 0; num <= 15; num++) {
if (VC[Y][VARindex][num]) wprintw(textwin, "%d, ", num);
}
(void) waddstr(textwin, "\n");
}
void propogate(int var1, int var2) {
/* recurse: if A < D and D < B then make a note that A < B */
}
void propogate_all_vv(void) {
int var1, var2;
/* vv relations are examined after all vc relationships are done */
/* Be careful: A -> D and D -> B and B -> C requires multiple passes until no changes made.
- what I have below is not sufficient. Also this will be a crude implementation of a graph alg. */
for (var1 = 0; var1 <= 13; var1++) {
for(var2 = 0; var2 <= 13; var2++) {
propogate(var1, var2);
}
}
}
void apply_all_vv_constraints(void) {
/* now apply constraint graph info.
If A.x can be one of 4,5,6,7 and D.x can be 3,4,5,6
and A.x < D.x, then ...
A.x < D.x is encoded by calling relate(A, x, LT, 6) because 6 is the highest value of D.x
conversely,
D.x > A.x is encoded by calling relate(D, x, GT, 4) because 4 is the lowest value of A.x
After this pass, A.x can be one of 4,5 and D.x can be 5,6
(Meaning that either A.x is 4 and D.x is 5 or 6, or A.x = 5 and D.x = 6...)
*/
}
/* User Movements in bot view space */
void step(void) {
int i;
master_move();
if (controller.success) {
bot.x += bot.dir_x; bot.y += bot.dir_y;
} else {
if (controller.view == 0) { /* walked into a wall */
if (bot.dir_x > 0) {
bot.max_x = bot.x; bot.min_x = bot.max_x-15;
for (i = 0; i <= 32; i++) {bot.map[bot.max_x+1][i] = WALL; bot.map[bot.min_x-1][i] = WALL;}
} else if (bot.dir_x < 0) {
bot.min_x = bot.x; bot.max_x = bot.min_x+15;
for (i = 0; i <= 32; i++) {bot.map[bot.max_x+1][i] = WALL; bot.map[bot.min_x-1][i] = WALL;}
} else if (bot.dir_y > 0) {
bot.max_y = bot.y; bot.min_y = bot.max_y-15;
for (i = 0; i <= 32; i++) {bot.map[i][bot.max_y+1] = WALL; bot.map[i][bot.min_y-1] = WALL;}
} else if (bot.dir_y < 0) {
bot.min_y = bot.y; bot.max_y = bot.min_y+15;
for (i = 0; i <= 32; i++) {bot.map[i][bot.max_y+1] = WALL; bot.map[i][bot.min_y-1] = WALL;}
}
}
}
}
void left(void) {
master_left(); bot.direction = (bot.direction+3)%4; bot.dir_x = xdir(bot.direction); bot.dir_y = ydir(bot.direction);
}
void right(void) {
master_right(); bot.direction = (bot.direction+1)%4; bot.dir_x = xdir(bot.direction); bot.dir_y = ydir(bot.direction);
}
void interact(void) {
master_interact();
}
void random_move(void) {
switch (random()%10) {
case 0: left(); return;
case 1: right(); return;
case 2:
case 3: interact(); return;
default: step(); return;
}
}
int main(int argc, char **argv)
{
/* We use numerical methods to satisfy constraints within a very limited range,
and then we propogate graph constraints between variables to reduce the sets
further. I think this will work, though it would be nice to run it pas one
of my old university chums who stayed awake during the graph theory lectures.
*/
/* Because of the way that we find information, we either know nothing at all
about an object, or we know its x but not its y; or we know its y but not its x.
Hence we don't need to store a 2D range for every object - we can handle x and
y orthogonally.
*/
/* This skeleton is not yet sufficient for the golf game. It records the ranges
of objects that have been seen, but there are hidden squares behind objects that
we have no idea what may be in them, and for those squares we are not yet
recording the cases where the squares are known to be empty. We need to add
a new primitive which says 'all squares in this row or col between <object>, and
where the bot is currently located, are known to be empty'. At the point when
<object> becomes fixed, those squares should be converted from unknown to empty.
*/
int i;
unsigned int seed = (unsigned int)time(NULL);
srandom(seed);
seed = ((int)random())%(256*15);
setlocale(LC_ALL, "");
initscr(); cbreak(); noecho();
/* height width starty startx */
masterwin = newwin(16, 16, 0, 0);
golfwin = newwin(33, 33, 0, 20);
textwin = newwin(12, 17, 19, 0);
keypad(golfwin, TRUE);
scrollok(textwin, TRUE);
move(0,0);
wmove(textwin, 0,0);
initialise_controller(seed);
/* Now our view of the map. */
for (bot.y = 0; bot.y <= 32; bot.y++)
for (bot.x = 0; bot.x <= 32; bot.x++)
bot.map[bot.x][bot.y] = (bot.x&31)*(bot.y&31) == 0 ? WALL : NO_OBJ; /* 0, or 32 */
bot.min_x = bot.min_y = bot.max_x = bot.max_y = bot.x = bot.y = 16;
bot.direction = 0; bot.dir_x = xdir(bot.direction); bot.dir_y = ydir(bot.direction);
for (i = 0; controller.sunk!=30; i++) {
draw_controller();
draw_inference_map();
wmove(textwin,0,0);
wprintw(textwin, "Seed: %d\nTurn: %d\nSuccess: %d\nView: %d\n",
controller.seed, controller.turn, controller.success, controller.view);
wclrtobot(textwin);
wrefresh(textwin);
if (i < 1000) random_move(); else switch (wgetch(golfwin)) {
case KEY_UP: step(); break;
case KEY_LEFT: left(); break;
case KEY_RIGHT: right(); break;
case ' ': interact(); break;
case 'q':
case 'Q':
delwin(masterwin); delwin(golfwin); delwin(textwin); endwin();
exit(1);
break;
default: break;
}
}
delwin(masterwin); delwin(golfwin); delwin(textwin); endwin();
exit(0);
return(0);
}