From 263fa4fa5472cd013f2ac2993e6cee0f8d73a2fb Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Sat, 2 Jun 2012 00:17:44 +0200 Subject: digital/io-hub/src/guybrush: use faster algorithms for decision --- digital/io-hub/src/guybrush/path.c | 23 ++++++++++---- digital/io-hub/src/guybrush/path.h | 5 +++- digital/io-hub/src/guybrush/strat.c | 60 ++++++++++++++++++++++++------------- 3 files changed, 60 insertions(+), 28 deletions(-) (limited to 'digital') diff --git a/digital/io-hub/src/guybrush/path.c b/digital/io-hub/src/guybrush/path.c index 639e9472..a1bc94e1 100644 --- a/digital/io-hub/src/guybrush/path.c +++ b/digital/io-hub/src/guybrush/path.c @@ -486,13 +486,23 @@ path_get_next (vect_t *p) return 0; } +void +path_prepare_score (void) +{ + path_blocked_update (); + astar_dijkstra_prepare (path.astar_nodes, PATH_NODES_NB, + PATH_SRC_NODE_INDEX, PATH_DST_NODE_INDEX); + path.escape_factor = 0; +} + uint16_t -path_get_score () +path_get_score (void) { - if (path.found) - return path.astar_nodes[PATH_SRC_NODE_INDEX].score; - else - return (uint16_t) -1; + uint16_t score; + score = astar_dijkstra_finish (path.astar_nodes, PATH_NODES_NB, + PATH_DST_NODE_INDEX); + path.escape_factor = 0; + return score; } /** Neighbors callback for nodes in grid. */ @@ -582,7 +592,8 @@ path_astar_neighbor_callback_other (uint8_t node, } } /* Check if direct path OK. */ - if (!path_blocking (node, PATH_SRC_NODE_INDEX, &d)) + if (node != PATH_SRC_NODE_INDEX + && !path_blocking (node, PATH_SRC_NODE_INDEX, &d)) { /* Add this neighbor. */ neighbors[neighbors_nb].node = PATH_SRC_NODE_INDEX; diff --git a/digital/io-hub/src/guybrush/path.h b/digital/io-hub/src/guybrush/path.h index cd580c87..a07d50ea 100644 --- a/digital/io-hub/src/guybrush/path.h +++ b/digital/io-hub/src/guybrush/path.h @@ -73,8 +73,11 @@ path_update (void); uint8_t path_get_next (vect_t *p); +void +path_prepare_score (void); + uint16_t -path_get_score (); +path_get_score (void); #if AC_PATH_REPORT diff --git a/digital/io-hub/src/guybrush/strat.c b/digital/io-hub/src/guybrush/strat.c index fe029f4d..47f9c4bc 100644 --- a/digital/io-hub/src/guybrush/strat.c +++ b/digital/io-hub/src/guybrush/strat.c @@ -133,6 +133,7 @@ strat_init (void) { uint8_t i; strat.last_decision = -1; + strat.prepared = 0; for (i = 0; i < STRAT_PLACE_NB; i++) strat.place[i].valid = 1; if (team_color) @@ -151,40 +152,55 @@ strat_init (void) } } -/** Compute score for a path to the given position. */ -static int32_t -strat_position_score (const vect_t *pos) +/** Compute all path scores for valid places. */ +static void +strat_path_score_prepare (uint16_t *score) { - uint16_t path_score; - /* Find a path to position. */ + uint8_t i, escape = 0; position_t current_pos; asserv_get_position (¤t_pos); - path_endpoints (current_pos.v, *pos); - path_update (); - path_score = path_get_score (); - if (path_score != (uint16_t) -1) - return path_score; - else + /* First pass, without escaping. */ + path_endpoints (current_pos.v, current_pos.v); + path_prepare_score (); + for (i = 0; i < STRAT_PLACE_NB; i++) { - path_escape (8); - path_update (); - path_score = path_get_score (); - if (path_score != (uint16_t) -1) - return 4 * path_score; + if (!strat.place[i].valid) + score[i] = (uint16_t) -1; else - return -1; + { + path_endpoints (current_pos.v, strat_place[i].pos); + score[i] = path_get_score (); + if (score[i] == (uint16_t) -1) + escape = 1; + } + } + /* Second pass if needed with escaping. */ + if (escape) + { + path_escape (8); + path_endpoints (current_pos.v, current_pos.v); + path_prepare_score (); + for (i = 0; i < STRAT_PLACE_NB; i++) + { + if (strat.place[i].valid && score[i] == (uint16_t) -1) + { + path_escape (8); + path_endpoints (current_pos.v, strat_place[i].pos); + score[i] = path_get_score (); + } + } } } /** Compute score for a given place. */ static int32_t -strat_place_score (uint8_t i) +strat_place_score (uint16_t path_score, uint8_t i) { if (!strat.place[i].valid) return -1; - int32_t position_score = strat_position_score (&strat_place[i].pos); - if (position_score == -1) + if (path_score == (uint16_t) -1) return -1; + int32_t position_score = path_score; int32_t score = 10000ll - position_score + strat_place[i].score - 100ll * strat.place[i].fail_nb; if (team_color) @@ -234,9 +250,11 @@ strat_decision (vect_t *pos) return strat.last_decision; } /* Else compute the best decision. */ + uint16_t path_score[STRAT_PLACE_NB]; + strat_path_score_prepare (path_score); for (i = 0; i < STRAT_PLACE_NB; i++) { - int32_t score = strat_place_score (i); + int32_t score = strat_place_score (path_score[i], i); if (score > best_score) { best_score = score; -- cgit v1.2.3