2 * Copyright Droids, Microb Technology (2010)
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 * Revision : $Id: strat.c,v 1.6 2009-11-08 17:24:33 zer0 Exp $
20 * Olivier MATZ <zer0@droids-corp.org>
30 #include <aversive/pgmspace.h>
31 #include <aversive/error.h>
36 #include <clock_time.h>
41 #include <control_system_manager.h>
42 #include <trajectory_manager.h>
43 #include <trajectory_manager_utils.h>
44 #include <trajectory_manager_core.h>
45 #include <vect_base.h>
48 #include <obstacle_avoidance.h>
49 #include <blocking_detection_manager.h>
50 #include <robot_system.h>
51 #include <position_manager.h>
53 #include <diagnostic.h>
58 #include "../common/i2c_commands.h"
59 #include "i2c_protocol.h"
63 #include "strat_base.h"
64 #include "strat_corn.h"
65 #include "strat_avoid.h"
66 #include "strat_utils.h"
73 #define DPR(fmt, ...) printf_P(PSTR(fmt), ##__VA_ARGS__)
75 #define DPR(args...) do {} while (0)
81 const struct wp_coord *path;
84 const struct wp_coord butterfly_tab[] = {
109 { .i = 10, .j = 2, },
110 { .i = 11, .j = 1, },
111 { .i = 11, .j = 2, },
112 { .i = 11, .j = 3, },
113 { .i = 11, .j = 4, },
114 { .i = 11, .j = 5, },
115 { .i = 11, .j = 6, },
118 const struct circuit butterfly_circuit = {
120 .len = sizeof(butterfly_tab)/sizeof(struct wp_coord),
121 .path = butterfly_tab,
124 const struct wp_coord losange_tab[] = {
125 { .i = 11, .j = 6, },
126 { .i = 10, .j = 6, },
130 { .i = 10, .j = 4, },
131 { .i = 11, .j = 4, },
132 { .i = 11, .j = 5, },
133 { .i = 11, .j = 6, },
136 const struct circuit losange_circuit = {
138 .len = sizeof(losange_tab)/sizeof(struct wp_coord),
142 const struct wp_coord triangle_tab[] = {
143 { .i = 11, .j = 6, },
144 { .i = 10, .j = 6, },
152 { .i = 10, .j = 2, },
153 { .i = 11, .j = 1, },
154 { .i = 11, .j = 2, },
155 { .i = 11, .j = 3, },
156 { .i = 11, .j = 4, },
157 { .i = 11, .j = 5, },
158 { .i = 11, .j = 6, },
161 const struct circuit triangle_circuit = {
163 .len = sizeof(triangle_tab)/sizeof(struct wp_coord),
164 .path = triangle_tab,
167 const struct wp_coord answer_d_tab[] = {
168 { .i = 11, .j = 6, },
169 { .i = 11, .j = 5, },
170 { .i = 11, .j = 4, },
171 { .i = 11, .j = 3, },
172 { .i = 11, .j = 2, },
173 { .i = 11, .j = 1, },
174 { .i = 10, .j = 2, },
178 { .i = 10, .j = 4, },
179 { .i = 11, .j = 4, },
180 { .i = 11, .j = 5, },
181 { .i = 11, .j = 6, },
184 const struct circuit answer_d_circuit = {
186 .len = sizeof(answer_d_tab)/sizeof(struct wp_coord),
187 .path = answer_d_tab,
190 const struct wp_coord h_lambda_tab[] = {
191 { .i = 11, .j = 6, },
192 { .i = 10, .j = 6, },
205 { .i = 10, .j = 6, },
206 { .i = 11, .j = 6, },
209 const struct circuit h_lambda_circuit = {
211 .len = sizeof(h_lambda_tab)/sizeof(struct wp_coord),
212 .path = h_lambda_tab,
215 const struct wp_coord asym_butterfly_tab[] = {
216 { .i = 11, .j = 6, },
217 { .i = 10, .j = 6, },
234 { .i = 10, .j = 2, },
235 { .i = 11, .j = 1, },
236 { .i = 11, .j = 2, },
237 { .i = 11, .j = 3, },
238 { .i = 11, .j = 4, },
239 { .i = 11, .j = 5, },
240 { .i = 11, .j = 6, },
243 const struct circuit asym_butterfly_circuit = {
244 .name = "asym_butterfly",
245 .len = sizeof(asym_butterfly_tab)/sizeof(struct wp_coord),
246 .path = asym_butterfly_tab,
249 const struct wp_coord big_h_lambda_tab[] = {
250 { .i = 11, .j = 6, },
251 { .i = 10, .j = 6, },
274 { .i = 10, .j = 6, },
275 { .i = 11, .j = 6, },
278 const struct circuit big_h_lambda_circuit = {
279 .name = "big_h_lambda",
280 .len = sizeof(big_h_lambda_tab)/sizeof(struct wp_coord),
281 .path = big_h_lambda_tab,
284 /* list of all possible circuits */
285 const struct circuit *circuits[] = {
291 &asym_butterfly_circuit,
292 &big_h_lambda_circuit,
296 /* symetric neighbor position */
297 static inline uint8_t opposite_position(uint8_t pos)
306 //#define TEST_STRAT_AVOID
309 #ifdef TEST_STRAT_AVOID
311 uint8_t xget_cob_count(void)
317 uint8_t xget_ball_count(void)
323 uint8_t xtime_get_s(void)
328 #define xget_cob_count() get_cob_count()
329 #define xget_ball_count() get_ball_count()
330 #define xtime_get_s() time_get_s()
333 /* return true if turn is at 60 deg */
334 uint8_t is_60deg(uint8_t dir1, uint8_t dir2)
348 /* return true if turn is at 60 deg */
349 uint8_t is_120deg(uint8_t dir1, uint8_t dir2)
363 /* get the neighbour of the point at specified dir, return -1 if
364 * there is no neighbor */
365 int8_t wp_get_neigh(uint8_t i, uint8_t j, uint8_t *ni, uint8_t *nj,
394 if (i >= WAYPOINTS_NBX || j >= WAYPOINTS_NBY)
402 static uint8_t get_line_num(int8_t i, int8_t j, uint8_t dir)
423 static uint8_t get_dir(uint8_t prev_i, uint8_t prev_j,
424 uint8_t i, uint8_t j)
426 int8_t diff_i, diff_j;
431 if (diff_i == 0 && diff_j == 1)
433 if (diff_i == 0 && diff_j == -1)
436 if ((prev_i & 1) == 0) {
437 if (diff_i == 1 && diff_j == 0)
439 if (diff_i == 1 && diff_j == -1)
441 if (diff_i == -1 && diff_j == 0)
443 if (diff_i == -1 && diff_j == -1)
447 if (diff_i == 1 && diff_j == 1)
449 if (diff_i == 1 && diff_j == 0)
451 if (diff_i == -1 && diff_j == 1)
453 if (diff_i == -1 && diff_j == 0)
461 /* return true if a waypoint belongs to a line */
462 uint8_t wp_belongs_to_line(uint8_t i, uint8_t j, uint8_t linenum, uint8_t dir)
465 ln = get_line_num(i, j, dir);
471 /* count the number of non-black corns which are neighbors of
473 uint8_t corn_count_neigh(uint8_t i, uint8_t j)
478 for (dir = LINE_UP; dir <= LINE_R_UP; dir++) {
479 if (wp_get_neigh(i, j, &ni, &nj, dir) < 0)
482 /* is there a corn cob ? */
483 if (strat_db.wp_table[ni][nj].type == WP_TYPE_CORN &&
484 strat_db.wp_table[ni][nj].present &&
485 strat_db.wp_table[ni][nj].corn.color != I2C_COB_BLACK)
493 /* fill circuit_wpline table with waypoints from circuit starting at
494 * i,j and using selected face */
495 static int8_t get_path(const struct circuit *circuit,
496 uint8_t starti, uint8_t startj, uint8_t faceA,
497 struct wp_line *circuit_wpline)
499 const struct wp_coord *curcircuit;
500 const struct wp_coord *start;
501 const struct wp_coord *end;
502 uint8_t prev_i, prev_j;
503 uint8_t dir, prev_dir = 0xFF;
504 uint8_t found = 0, i = 0, j = 0;
506 int8_t step = faceA ? 1 : -1;
509 /* start and end of circuit */
511 start = &circuit->path[0];
512 end = start + circuit->len - 1;
515 end = &circuit->path[0];
516 start = end + circuit->len - 1;
519 DPR("face: %s %d\r\n", circuit->name, faceA);
521 /* check that the point is present in the circuit */
522 for (curcircuit = start; curcircuit != end; curcircuit += step) {
523 if (curcircuit->i == starti && curcircuit->j == startj) {
532 /* browse the circuit from starti, startj in the specified
533 * direction, and fill the table when direction changes */
536 for ( ; curcircuit != end;
537 curcircuit += step, prev_dir = dir, prev_i = i, prev_j = j) {
542 dir = get_dir(prev_i, prev_j, i, j);
544 if (prev_dir != dir) {
545 linenum = get_line_num(prev_i, prev_j, dir);
546 circuit_wpline[path_len].line_num = linenum;
547 circuit_wpline[path_len].dir = dir;
555 /* process score from retrieved objects number, and circuit len */
556 static int16_t get_score(uint32_t wcorn_retrieved,
557 uint32_t ucorn_retrieved,
558 uint16_t tomato_retrieved,
559 uint8_t len, uint8_t opp_on_path)
566 /* score with corn */
567 n = xget_cob_count() * 2;
568 for (i = 0; i<CORN_NB; i++) {
571 if (wcorn_retrieved & mask) {
577 if (ucorn_retrieved & mask) {
584 DPR("get score: cob %d (->%d)\r\n", n, n/2);
586 /* score with tomato */
587 n = xget_ball_count();
589 for (i = 0; i<TOMATO_NB; i++) {
592 if (tomato_retrieved & mask) {
599 DPR("get score: ball %d\r\n", n);
601 /* malus for long circuits */
603 DPR("malus for length: %d\r\n", len * 20);
605 /* double malus for long circuits if we don't have much
608 if (len * WP_SPEED > (MATCH_TIME - xtime_get_s())) {
610 extra = (len * WP_SPEED) - (MATCH_TIME - xtime_get_s());
611 extra = (200 * extra);
612 if (extra < 0) /* should not happen */
617 DPR("malus for length + time: %d\r\n", extra);
620 /* malus if there is opponent on the path */
622 DPR("malus for opponent: 1000\r\n");
629 /* return the corn type of specified coords: I2C_COB_WHITE,
630 * I2C_COB_UNKNOWN, or I2C_COB_NONE if it is black or not present */
631 static uint8_t get_corn_type(uint8_t i, uint8_t j)
634 /* is there a corn cob ? */
635 if (strat_db.wp_table[i][j].type == WP_TYPE_CORN &&
636 strat_db.wp_table[i][j].present) {
637 color = strat_db.wp_table[i][j].corn.color;
638 if (color == I2C_COB_WHITE)
639 return I2C_COB_WHITE;
640 else if (color == I2C_COB_UNKNOWN)
641 return I2C_COB_UNKNOWN;
646 /* i,j: starting position */
647 static int8_t evaluate_one_face(const struct circuit *circuit,
648 uint8_t starti, uint8_t startj,
649 uint8_t faceA, int16_t *score)
651 const struct wp_coord *curcircuit;
652 const struct wp_coord *start;
653 const struct wp_coord *end;
654 uint32_t wcorn_retrieved = 0; /* bit mask */
655 uint32_t ucorn_retrieved = 0; /* bit mask */
656 uint16_t tomato_retrieved = 0; /* bit mask */
657 uint8_t opponent_on_path = 0;
658 uint8_t len = 0, found = 0;
659 uint8_t i, j, prev_i, prev_j;
660 uint8_t ni = 0, nj = 0;
661 uint8_t dir, color, idx;
662 int8_t step = faceA ? 1 : -1;
666 *score = 0x8000; /* -int_max */
668 /* start and end of circuit */
670 start = &circuit->path[0];
671 end = start + circuit->len - 1;
674 end = &circuit->path[0];
675 start = end + circuit->len - 1;
678 DPR("%s() face: %s %d\r\n", __FUNCTION__, circuit->name, faceA);
680 /* check that the point is present in the circuit */
681 for (curcircuit = start; curcircuit != end; curcircuit += step) {
682 if (curcircuit->i == starti && curcircuit->j == startj) {
690 /* get opponent coords */
691 if (get_opponent_xy(&oppx, &oppy) < 0)
692 oppx = I2C_OPPONENT_NOT_THERE;
694 /* silent the compiler */
698 /* browse all points and calculate the score */
699 for (curcircuit = start;
701 curcircuit += step, len ++, prev_i = i, prev_j = j) {
705 /* is opponent near the point ? */
706 ijcoord_to_xycoord(i, j, &x, &y);
707 if (oppx != I2C_OPPONENT_NOT_THERE) {
708 d = distance_between(oppx, oppy, x, y);
710 opponent_on_path = 1;
713 /* don't try to look cobs/tomato for first point */
714 if (curcircuit == start)
717 /* get current direction, we wil check cobs behind us
718 * on left and right */
719 dir = get_dir(prev_i, prev_j, i, j);
721 DPR("%d %d -> %d %d (%d)\n", prev_i, prev_j, i, j, dir);
723 /* is there a tomato ? */
724 if (strat_db.wp_table[i][j].type == WP_TYPE_TOMATO &&
725 strat_db.wp_table[i][j].present) {
727 tomato_retrieved |= (1UL << strat_db.wp_table[i][j].tomato.idx);
731 if (wp_get_neigh(i, j, &ni, &nj, (dir + 2) % 6) == 0) {
732 color = get_corn_type(ni, nj);
733 idx = strat_db.wp_table[ni][nj].corn.idx;
734 if (color == I2C_COB_WHITE) {
735 DPR(" LEFT WCORN (%d)\n", idx);
736 wcorn_retrieved |= (1UL << idx);
738 else if (color == I2C_COB_UNKNOWN) {
739 DPR(" LEFT UCORN (%d)\n", idx);
740 ucorn_retrieved |= (1UL << idx);
745 if (wp_get_neigh(i, j, &ni, &nj, (dir + 4) % 6) == 0) {
746 color = get_corn_type(ni, nj);
747 idx = strat_db.wp_table[ni][nj].corn.idx;
748 if (color == I2C_COB_WHITE) {
749 DPR(" RIGHT WCORN (%d)\n", idx);
750 wcorn_retrieved |= (1UL << idx);
752 else if (color == I2C_COB_UNKNOWN) {
753 DPR(" RIGHT UCORN (%d)\n", idx);
754 ucorn_retrieved |= (1UL << idx);
758 /* prev_i, prev_j, len and curcircuit are updated in
762 /* write score and exit */
763 *score = get_score(wcorn_retrieved, ucorn_retrieved,
764 tomato_retrieved, len, opponent_on_path);
768 /* i,j: starting position */
769 static int8_t evaluate_one_circuit(const struct circuit *circuit,
770 uint8_t starti, uint8_t startj,
771 int16_t *scoreA, int16_t *scoreB)
773 if (evaluate_one_face(circuit, starti, startj, 1, scoreA) < 0)
776 /* we are on eject point, scoreB is the same */
777 if (starti == 11 && startj == 6) {
782 if (evaluate_one_face(circuit, starti, startj, 0, scoreB) < 0)
787 /* i,j starting position */
788 int8_t find_best_circuit(uint8_t i, uint8_t j,
789 const struct circuit **selected_circuit,
790 int8_t *selected_face)
792 const struct circuit **circuit;
793 int16_t scoreA, scoreB;
794 int16_t selected_score = 0x8000; /* ~-int_max */
798 *selected_circuit = circuits[0] ;
799 for (circuit = &circuits[0]; *circuit; circuit++) {
800 if (evaluate_one_circuit(*circuit, i, j, &scoreA, &scoreB) < 0)
803 DEBUG(E_USER_STRAT, "Scores for %s are: faceA=%d, faceB=%d",
804 (*circuit)->name, scoreA, scoreB);
805 if (scoreA > selected_score) {
806 *selected_circuit = *circuit;
807 selected_score = scoreA;
810 if (scoreB > selected_score) {
811 *selected_circuit = *circuit;
812 selected_score = scoreB;
818 DEBUG(E_USER_STRAT, "no circuit found");
820 DEBUG(E_USER_STRAT, "circuit found: %s, %s",
821 (*selected_circuit)->name,
822 (*selected_face) ? "faceA":"faceB");
826 static void dump_circuit_wp(struct wp_line *circuit_wpline, int8_t len)
831 for (i = 0; i < len; i ++) {
832 DEBUG(E_USER_STRAT, "linenum %d dir %d",
833 circuit_wpline[i].line_num,
834 circuit_wpline[i].dir);
839 /* choose a circuit, then harvest on this circuit */
840 uint8_t strat_harvest_circuit(void)
842 const struct circuit *selected_circuit;
843 int8_t selected_face;
844 struct wp_line circuit_wpline[MAX_CIRCUIT_WPLINE];
848 uint8_t linenum, prev_linenum;
849 uint8_t dir, prev_dir;
852 x = position_get_x_s16(&mainboard.pos);
853 y = position_get_y_s16(&mainboard.pos);
855 if (xycoord_to_ijcoord(&x, &y, &i, &j) < 0) {
856 DEBUG(E_USER_STRAT, "%s(): cannot find waypoint at %d,%d",
861 if (find_best_circuit(i, j, &selected_circuit, &selected_face) < 0) {
862 DEBUG(E_USER_STRAT, "%s(): cannot find a good circuit",
867 len = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
869 DEBUG(E_USER_STRAT, "%s(): cannot find a path",
874 dump_circuit_wp(circuit_wpline, len);
876 prev_linenum = circuit_wpline[0].line_num;
877 prev_dir = circuit_wpline[0].dir;
878 for (idx = 1; idx < len; idx ++) {
880 linenum = circuit_wpline[idx].line_num;
881 dir = circuit_wpline[idx].dir;
883 /* XXX basic opponent management */
884 DEBUG(E_USER_STRAT, "%s(): line %d dir %d -> line %d dir %d",
885 __FUNCTION__, prev_linenum, prev_dir, linenum, dir);
886 err = line2line(prev_linenum, prev_dir, linenum, dir,
888 if (!TRAJ_SUCCESS(err)) {
894 prev_linenum = linenum;
898 return END_TRAJ; // XXX
901 uint8_t strat_unblock(void)
906 void test_strat_avoid(void)
908 #ifdef TEST_STRAT_AVOID
910 const struct circuit *selected_circuit;
911 int8_t selected_face;
912 struct wp_line circuit_wpline[MAX_CIRCUIT_WPLINE];
916 printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
918 ts = 0; bc = 0; cc = 0;
919 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
920 find_best_circuit(i, j, &selected_circuit, &selected_face);
921 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
922 dump_circuit_wp(circuit_wpline, ret);
924 ts = 0; bc = 3; cc = 0;
925 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
926 find_best_circuit(i, j, &selected_circuit, &selected_face);
927 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
928 dump_circuit_wp(circuit_wpline, ret);
930 ts = 0; bc = 4; cc = 0;
931 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
932 find_best_circuit(i, j, &selected_circuit, &selected_face);
933 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
934 dump_circuit_wp(circuit_wpline, ret);
936 ts = 0; bc = 3; cc = 5;
937 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
938 find_best_circuit(i, j, &selected_circuit, &selected_face);
939 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
940 dump_circuit_wp(circuit_wpline, ret);
942 ts = 0; bc = 4; cc = 5;
943 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
944 find_best_circuit(i, j, &selected_circuit, &selected_face);
945 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
946 dump_circuit_wp(circuit_wpline, ret);
948 ts = 80; bc = 0; cc = 0;
949 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
950 find_best_circuit(i, j, &selected_circuit, &selected_face);
951 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
952 dump_circuit_wp(circuit_wpline, ret);
955 printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
957 ts = 0; bc = 0; cc = 0;
958 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
959 find_best_circuit(i, j, &selected_circuit, &selected_face);
960 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
961 dump_circuit_wp(circuit_wpline, ret);
963 ts = 0; bc = 3; cc = 0;
964 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
965 find_best_circuit(i, j, &selected_circuit, &selected_face);
966 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
967 dump_circuit_wp(circuit_wpline, ret);
969 ts = 80; bc = 0; cc = 0;
970 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
971 find_best_circuit(i, j, &selected_circuit, &selected_face);
972 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
973 dump_circuit_wp(circuit_wpline, ret);
976 printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
978 ts = 0; bc = 0; cc = 0;
979 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
980 find_best_circuit(i, j, &selected_circuit, &selected_face);
981 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
982 dump_circuit_wp(circuit_wpline, ret);
984 ts = 0; bc = 3; cc = 0;
985 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
986 find_best_circuit(i, j, &selected_circuit, &selected_face);
987 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
988 dump_circuit_wp(circuit_wpline, ret);
990 ts = 80; bc = 0; cc = 0;
991 printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
992 find_best_circuit(i, j, &selected_circuit, &selected_face);
993 ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
994 dump_circuit_wp(circuit_wpline, ret);