#include #include #include #include #include #include #include "pie/dib24.h" #include "pie/emu.h" #include "bitmap.h" #include "position.h" #include "xtools.h" #include "pill.h" #include "level.h" #include "debug.h" /* Find first pill on a picture */ static position_t find_first_pill(Dib24 *xi, position_t entry, pixel_t pillcolor) { int x, y; position_t first_pill = {-1, -1}; for(y=entry.y; ygetHeight(); y++) { for(x=entry.x; xgetWidth(); x++) { entry.x = 0; pixel_t pix = xi->getPixel(x, y); if ( pix == pillcolor ) { first_pill.x = x; first_pill.y = y; return first_pill; } } } return first_pill; } /** * Evaluate the distance between two pills * * Since the first pill if found by scanning * from up to down and left to right, we can * only have next pill at right or bottom. * * To find the next pill, we first try to * guess the pill size (in pixels) then we * go on until the color matches. */ static int eval_pill_step(Dib24 *xi, position_t first_pill, pixel_t color) { int x, y; x = first_pill.x; y = first_pill.y; /* Pill on right side ? */ /* Go to the right outer edge of the pill */ while ( xi->getFastPixel(x, y) == color ) x++; /* Go on until we find a pill */ while ( xi->getFastPixel(x, y) != color ) { x++; if ( x >= xi->getWidth() ) break; } /* Something was found */ if ( x < xi->getWidth() ) return (x - first_pill.x); /* Do the same shit for down direction */ assert("NYI"); return -1; } /** * Send a beam towards "dir" * * FIXME: considers black as background */ beam_result_t send_beam(Dib24 *xi, position_t from, direction_t dir) { pixel_t got; beam_result_t res; res.dst = 0; res.pixel = 0; res.pos = from; do { res.dst++; switch( dir ) { case DIR_UP: case DIR_DOWN: res.pos.y = move_safe(xi, res.pos.y, dir, 1); break; case DIR_LEFT: case DIR_RIGHT: res.pos.x = move_safe(xi, res.pos.x, dir, 1); break; } //printf("(%d, %d) beaming : (%d, %d)\n", from.x, from.y, res.pos.x, res.pos.y); res.pixel = xi->getFastPixel(res.pos.x, res.pos.y); } while ( res.pixel == 0x0 /* Black */ ); return res; } /** * Go to the edge of a pill */ position_t pill_goto_edge(Dib24 *xi, position_t pos, direction_t dir) { pixel_t pix = xi->getFastPixel(pos.x, pos.y); position_t prec; beam_result_t beam; beam.pos = pos; do { prec = beam.pos; beam = send_beam(xi, beam.pos, dir); } while ( beam.dst == 1 && beam.pixel == pix ); return prec; } /** * Try to guess pill center */ position_t pill_goto_center(Dib24 *xi, position_t pos) { position_t left, right, up, down; left = pill_goto_edge(xi, pos, DIR_LEFT); right = pill_goto_edge(xi, pos, DIR_RIGHT); pos.x = left.x + (right.x - left.x) / 2; up = pill_goto_edge(xi, pos, DIR_UP); down = pill_goto_edge(xi, pos, DIR_DOWN); pos.y = up.y + (down.y - up.y) / 2; return pos; } /** * Move to the edge of the pill then send a beam * (it enables us to have a pill of any size) */ static beam_result_t send_beam_from_pill(Dib24 *xi, position_t from, direction_t dir) { position_t beam_from; beam_from = pill_goto_edge(xi, from, dir); return send_beam(xi, beam_from, dir); } /** * Check if a desired pixel is found in the * neighbourhood int the specified radius */ static int check_neighbours(Dib24 *xi, position_t pos, pixel_t want, unsigned int radius) { int x, y; /* Clamp to picture size */ int left = pos.x - radius; if ( left < 0 ) left = 0; int right = pos.x + radius; if ( right >= xi->getWidth() ) right = xi->getWidth() - 1; for(y=pos.y - radius; ygetFastPixel(x, y) == want ) return 1; } return 0; } static direction_t find_possible_moves(Dib24 *xi, position_t pos, unsigned int pill_step, pixel_t pill_color, pixel_t wall_color) { /* Check where we can try to go */ direction_t dirs = DIR_NONE; /* Possible next directions */ /* For each direction, check if possible */ direction_t d; foreach_direction(d) { beam_result_t beam = send_beam_from_pill(xi, pos, d); /* We have "Blank" space -> maybe a corridor ? */ if ( beam.dst > (pill_step * 1.5) ) { /* Move to supposed next point */ position_t next_pos = beam.pos; switch ( d ) { case DIR_LEFT: case DIR_RIGHT: next_pos.x = move_safe(xi, pos.x, d, pill_step); break; case DIR_UP: case DIR_DOWN: next_pos.y = move_safe(xi, pos.y, d, pill_step); } /* Check if this is really a possible move */ if (! check_neighbours(xi, next_pos, wall_color, pill_step/2) ) { DEBUG("(%d, %d) checking neighbours : ok \n", next_pos.x, next_pos.y); dirs |= d; } } /* Pill spotted ! */ else if ( beam.pixel == pill_color ) { //printf("(%d, %d) : GOT Pill here with dst = %d\n", beam.pos.x, beam.pos.y, beam.dst); dirs |= d; } } return dirs; } /* A comparator for positions */ static int position_comparator(node_t *node, void *data) { position_t *want = (position_t*)data; position_t *has = (position_t*)node->data; return (has->x == want->x/8 && has->y == want->y/8); } /* A comparator for two edges */ static int edges_comparator(edge_t *e, void *data) { edge_t *want = (edge_t*)data; return (e->n1 == want->n1 && e->n2 == want->n2) || (e->n1 == want->n2 && e->n2 == want->n1); } static void discover_corridors(graph_t *g, Dib24 *xi, pixel_t pill_color, pixel_t wall_color, int pill_step, position_t pos, direction_t from, edge_t *edge_to_connect) { /* Reference nodes by their center, so adjust to it */ pos = pill_goto_center(xi, pos); DEBUG("(%d, %d) Entering from ", pos.x, pos.y); FDEBUG(print_dirs(from)); /* Find possible moves (directions) */ direction_t dirs = find_possible_moves(xi, pos, pill_step, pill_color, wall_color); /* Remove incoming direction */ dirs &= ~from; /* Resolve our position to a node, if exists */ node_t *me = graph_node_find(g, &pos, position_comparator); /* Add only if we are at an intersection * Having only our reversed direction means * we are in a corridor, not an intersection */ if ( dirs != dir_invert(from) ) { /* * If we don't have this node, add it * Otherwise, return and ignore the call */ if ( me == NULL ) { DEBUG("(%d, %d) Adding node\n", pos.x, pos.y); node_data_t *nd = (node_data_t*)malloc(sizeof(node_data_t)); //memcpy(&nd->pos, &pos, sizeof(position_t)); // normalize position nd->pos.x = pos.x / 8; nd->pos.y = pos.y / 8; me = graph_node_add(g, nd); } else { DEBUG("(%d, %d) SKIPPING\n", pos.x, pos.y); /* Set dirs to DIR_NONE, so that no directions are explorated */ dirs = DIR_NONE; } /* Connect the pending edge to us (= node) */ if ( edge_to_connect != NULL ) { edge_to_connect->n2 = me; /* Check if we don't have it yet */ if ( graph_edge_find(g, edge_to_connect, edges_comparator) ) { /* If so, drop it */ free(edge_to_connect->data); graph_edge_free(edge_to_connect); } else graph_edge_add(g, edge_to_connect); } } /* Then explore possible directions */ DEBUG("(%d, %d) Can go ", pos.x, pos.y); FDEBUG(print_dirs(dirs)); direction_t d; foreach_direction(d) { if ( dirs & d ) { /* * If we are a node, then create and edge which is * connected to us and will be connected to antother later */ if ( me != NULL ) { edge_data_t *data = (edge_data_t*)malloc(sizeof(edge_data_t)); data->type = CORR_NORMAL; edge_to_connect = graph_edge_new(me, NULL, data); } /* Send a beam to possible direction */ beam_result_t beam = send_beam_from_pill(xi, pos, d); position_t next_pos = beam.pos; /* If we have a corridor, not a pill */ if ( beam.dst > (pill_step * 1.5) ) { /* Move to next point */ switch ( d ) { case DIR_LEFT: if ( pos.x - pill_step < 0 ) ((edge_data_t*)edge_to_connect->data)->type = CORR_TUNNEL; case DIR_RIGHT: if ( pos.x + pill_step > xi->getWidth() ) ((edge_data_t*)edge_to_connect->data)->type = CORR_TUNNEL; next_pos.x = move_safe(xi, pos.x, d, pill_step); break; case DIR_UP: case DIR_DOWN: next_pos.y = move_safe(xi, pos.y, d, pill_step); break; } } /* Explore ! */ DEBUG("(%d, %d) Exploring (%d, %d) ", pos.x, pos.y, next_pos.x, next_pos.y); FDEBUG(print_dirs(d)); discover_corridors(g, xi, pill_color, wall_color, pill_step, next_pos, dir_invert(d), edge_to_connect); } } } /** * Remove part of picture that prevent * level_create from working correctly */ static void clear_rectangle(Dib24 *xi, position_t tl, position_t br) { int x, y; for(y=tl.y; ysetFastPixel(x, y, 0); } static void cleanup_picture(Dib24 *xi) { /* Remove the player X or ghost */ position_t play_tl = {70, 108}; position_t play_br = {153, 123}; clear_rectangle(xi, play_tl, play_br); /* Remove the ready banner */ position_t ready_tl = {68, 156}; position_t ready_br = {154, 171}; clear_rectangle(xi, ready_tl, ready_br); /* Remove the pacman */ position_t pacman_tl = {102, 204}; position_t pacman_br = {121, 219}; clear_rectangle(xi, pacman_tl, pacman_br); } /** * Find color of walls */ pixel_t find_wall_color(Dib24 *xi) { position_t from = {0, 0}; beam_result_t r = send_beam(xi, from, DIR_DOWN); return r.pixel; } /** * Find color of pills * It assumes there's always a pill at the bottom right of the screen */ pixel_t find_pill_color(Dib24 *xi) { return xi->getFastPixel(211, 260); } /** * Guess a level from a picture * * xi : the picutre * pillcolor : the color of the pill * entry : where to start to scan from */ level_t *level_create(Dib24 *xi, position_t entry) { int pill_step; position_t first_pill; /* Remove non interesting parts */ cleanup_picture(xi); /* Find first pill */ pixel_t pill_color = find_pill_color(xi); first_pill = find_first_pill(xi, entry, pill_color); /* If we are unable to find the pill, we can't do more */ if ( first_pill.x < 0 ) { DEBUG("Unable to find first pill!\n", "p") return NULL; } DEBUG("Found first pill at (%d, %d)\n", first_pill.x, first_pill.y); /* Guess step */ pill_step = eval_pill_step(xi, first_pill, pill_color); if ( pill_step < 0 ) { DEBUG("Unable to guess pill step\n", "p"); return NULL; } DEBUG("Pill step = %d\n", pill_step); /* Now, try to discover corridors */ pixel_t wall_color = find_wall_color(xi); level_t *lev = (level_t*)malloc(sizeof(level_t)); lev->graph = graph_new(); discover_corridors(lev->graph, xi, pill_color, wall_color, pill_step, first_pill, DIR_UP, NULL); return lev; } /** * Destroy a level and its ressources */ void level_destroy(level_t *l) { /* FIXME: Destroy node/edge data TOO */ graph_free(l->graph); free(l); }