summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNicolas Schodet2012-06-02 00:17:44 +0200
committerNicolas Schodet2012-06-02 00:17:44 +0200
commit263fa4fa5472cd013f2ac2993e6cee0f8d73a2fb (patch)
treef88ba0820df3b45ceb7081ef6d01fab04065f228
parent1ef63de6558685e4b49cf1155423f24293d0bb88 (diff)
digital/io-hub/src/guybrush: use faster algorithms for decision
-rw-r--r--digital/io-hub/src/guybrush/path.c23
-rw-r--r--digital/io-hub/src/guybrush/path.h5
-rw-r--r--digital/io-hub/src/guybrush/strat.c60
3 files changed, 60 insertions, 28 deletions
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 (&current_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;