trajectory optimizations
[aversive.git] / projects / microb2010 / mainboard / strat_avoid.c
1 /*
2  *  Copyright Droids, Microb Technology (2010)
3  *
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.
8  *
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.
13  *
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
17  *
18  *  Revision : $Id: strat.c,v 1.6 2009-11-08 17:24:33 zer0 Exp $
19  *
20  *  Olivier MATZ <zer0@droids-corp.org>
21  */
22
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <stdint.h>
27 #include <math.h>
28
29 #include <aversive.h>
30 #include <aversive/pgmspace.h>
31 #include <aversive/error.h>
32
33 #include <ax12.h>
34 #include <uart.h>
35 #include <pwm_ng.h>
36 #include <clock_time.h>
37 #include <spi.h>
38
39 #include <pid.h>
40 #include <quadramp.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>
46 #include <lines.h>
47 #include <polygon.h>
48 #include <obstacle_avoidance.h>
49 #include <blocking_detection_manager.h>
50 #include <robot_system.h>
51 #include <position_manager.h>
52
53 #include <diagnostic.h>
54
55 #include <rdline.h>
56 #include <parse.h>
57
58 #include "../common/i2c_commands.h"
59 #include "i2c_protocol.h"
60 #include "main.h"
61 #include "strat.h"
62 #include "strat_db.h"
63 #include "strat_base.h"
64 #include "strat_corn.h"
65 #include "strat_avoid.h"
66 #include "strat_utils.h"
67 #include "sensor.h"
68 #include "actuator.h"
69
70
71 const struct wp_coord circuit1[] = {
72         { .i = 11, .j = 6, .end = 0, },
73         { .i = 10, .j = 6, .end = 0, },
74         { .i = 9, .j = 5, .end = 0, },
75         { .i = 8, .j = 5, .end = 0, },
76         { .i = 7, .j = 4, .end = 0, },
77         { .i = 6, .j = 4, .end = 0, },
78         { .i = 5, .j = 4, .end = 0, },
79         { .i = 4, .j = 5, .end = 0, },
80         { .i = 3, .j = 5, .end = 0, },
81         { .i = 2, .j = 6, .end = 0, },
82         { .i = 1, .j = 6, .end = 0, },
83         { .i = 1, .j = 5, .end = 0, },
84         { .i = 1, .j = 4, .end = 0, },
85         { .i = 1, .j = 3, .end = 0, },
86         { .i = 1, .j = 2, .end = 0, },
87         { .i = 1, .j = 1, .end = 0, },
88         { .i = 2, .j = 2, .end = 0, },
89         { .i = 3, .j = 2, .end = 0, },
90         { .i = 4, .j = 3, .end = 0, },
91         { .i = 5, .j = 3, .end = 0, },
92         { .i = 6, .j = 4, .end = 0, },
93         { .i = 7, .j = 3, .end = 0, },
94         { .i = 8, .j = 3, .end = 0, },
95         { .i = 9, .j = 2, .end = 0, },
96         { .i = 10, .j = 2, .end = 0, },
97         { .i = 11, .j = 1, .end = 0, },
98         { .i = 11, .j = 2, .end = 0, },
99         { .i = 11, .j = 3, .end = 0, },
100         { .i = 11, .j = 4, .end = 0, },
101         { .i = 11, .j = 5, .end = 0, },
102         { .i = 11, .j = 6, .end = 1, },
103 };
104
105 const struct wp_coord circuit2[] = {
106         { .i = 11, .j = 6, .end = 0, },
107         { .i = 10, .j = 6, .end = 0, },
108         { .i = 9, .j = 5, .end = 0, },
109         { .i = 9, .j = 4, .end = 0, },
110         { .i = 9, .j = 3, .end = 0, },
111         { .i = 10, .j = 4, .end = 0, },
112         { .i = 11, .j = 4, .end = 0, },
113         { .i = 11, .j = 5, .end = 0, },
114         { .i = 11, .j = 6, .end = 1, },
115 };
116
117 /* list of all possible circuits */
118 const struct wp_coord *circuits[] = {
119         circuit1,
120         circuit2,
121         NULL,
122 };
123
124 /* symetric neighbor position */
125 static inline uint8_t opposite_position(uint8_t pos)
126 {
127         pos += 3;
128         if (pos > LINE_L_UP)
129                 pos -= 6;
130         return pos;
131 }
132
133 static uint8_t cc;
134 uint8_t xget_cob_count(void)
135 {
136         return cc;
137 }
138
139 static uint8_t bc;
140 uint8_t xget_ball_count(void)
141 {
142         return bc;
143 }
144
145 static uint32_t ts;
146 uint8_t xtime_get_s(void)
147 {
148         return ts;
149 }
150
151
152 /* get the neighbour of the point at specified position, return -1 if
153  * there is no neighbor */
154 static int8_t get_neigh(uint8_t i, uint8_t j,
155                         uint8_t *ni, uint8_t *nj,
156                         uint8_t position)
157 {
158         switch (position) {
159         case LINE_UP:
160                 j++;
161                 break;
162         case LINE_R_UP:
163                 if (!(i & 1)) j++;
164                 i++;
165                 break;
166         case LINE_R_DOWN:
167                 if (i & 1) j--;
168                 i++;
169                 break;
170         case LINE_DOWN:
171                 j--;
172                 break;
173         case LINE_L_DOWN:
174                 if (i & 1) j--;
175                 i--;
176                 break;
177         case LINE_L_UP:
178                 if (!(i & 1)) j++;
179                 i--;
180                 break;
181         default:
182                 return -1;
183         }
184         if (i >= WAYPOINTS_NBX || j >= WAYPOINTS_NBY)
185                 return -1;
186
187         *ni = i;
188         *nj = j;
189         return 0;
190 }
191
192 static uint8_t get_line_num(int8_t i, int8_t j, uint8_t dir)
193 {
194         switch (dir) {
195         case LINE_UP:
196         case LINE_DOWN:
197                 return i/2;
198         case LINE_R_UP:
199         case LINE_L_DOWN:
200                 i &= 0xfe;
201                 j -= i/2;
202                 return (5-j)/2;
203         case LINE_R_DOWN:
204         case LINE_L_UP:
205                 i &= 0xfe;
206                 j += i/2;
207                 return (11-j)/2;
208         default:
209                 return -1;
210         }
211 }
212
213 static uint8_t get_dir(uint8_t prev_i, uint8_t prev_j,
214                        uint8_t i, uint8_t j)
215 {
216         int8_t diff_i, diff_j;
217
218         diff_i = i - prev_i;
219         diff_j = j - prev_j;
220
221         if (diff_i == 0 && diff_j == 1)
222                 return LINE_UP;
223         if (diff_i == 0 && diff_j == -1)
224                 return LINE_DOWN;
225
226         if ((prev_i & 1) == 0) {
227                 if (diff_i == 1 && diff_j == 0)
228                         return LINE_R_UP;
229                 if (diff_i == 1 && diff_j == -1)
230                         return LINE_R_DOWN;
231                 if (diff_i == -1 && diff_j == 0)
232                         return LINE_L_UP;
233                 if (diff_i == -1 && diff_j == -1)
234                         return LINE_L_DOWN;
235         }
236         else {
237                 if (diff_i == 1 && diff_j == 1)
238                         return LINE_R_UP;
239                 if (diff_i == 1 && diff_j == 0)
240                         return LINE_R_DOWN;
241                 if (diff_i == -1 && diff_j == 1)
242                         return LINE_L_UP;
243                 if (diff_i == -1 && diff_j == 0)
244                         return LINE_L_DOWN;
245         }
246
247         /* invalid value */
248         return 0xFF;
249 }
250
251
252 int8_t get_path(const struct wp_coord *circuit,
253                 uint8_t starti, uint8_t startj, uint8_t faceA,
254                 struct wp_line *circuit_wpline)
255 {
256         const struct wp_coord *curcircuit;
257         uint8_t prev_i, prev_j;
258         uint8_t dir, prev_dir = 0xFF;
259         uint8_t found = 0, i = 0, j = 0;
260         uint8_t linenum;
261         int8_t step = faceA ? 1 : -1;
262         int8_t skipfirst=0;
263         int8_t path_len = 0;
264
265         printf_P(PSTR("face: %d\r\n"), faceA);
266         if ( !faceA && circuit->i == 11 && circuit->j == 6)
267                 skipfirst=1;
268
269         /* check that the point is present in the circuit */
270         for (curcircuit = circuit + skipfirst; curcircuit->end == 0; curcircuit ++) {
271                 if (curcircuit->i == starti && curcircuit->j == startj) {
272                         found = 1;
273                         break;
274                 }
275         }
276
277         if ( !faceA && curcircuit->i == 11 && curcircuit->j == 6)
278                 found = 1;
279         if (found == 0)
280                 return -1;
281
282         /* XXX len must be >= 1 */
283         /* XXX start = 11,6 */
284
285         prev_i = starti;
286         prev_j = startj;
287
288         curcircuit = curcircuit;
289         while (1) {
290                 if (faceA && curcircuit->end)
291                         break;
292                 else if (!faceA && curcircuit == circuit)
293                         break;
294                 i = curcircuit->i;
295                 j = curcircuit->j;
296
297                 dir = get_dir(prev_i, prev_j, i, j);
298
299                 if (prev_dir != dir) {
300                         linenum = get_line_num(prev_i, prev_j, dir);
301                         /* printf_P(PSTR("COIN %d, %d, dir=%d linenum=%d\r\n"), */
302                         /*                               prev_i, prev_j, dir, linenum); */
303                         circuit_wpline[path_len].line_num = linenum;
304                         circuit_wpline[path_len].dir = dir;
305                         path_len++;
306                 }
307                 prev_dir = dir;
308                 prev_i = i;
309                 prev_j = j;
310                 curcircuit += step;
311         }
312
313 /*      printf_P(PSTR("COIN %d, %d\r\n"), curcircuit->i, curcircuit->j); */
314
315         return path_len; /* XXX */
316 }
317
318 int16_t get_score(uint32_t wcorn_retrieved, uint32_t ucorn_retrieved,
319                   uint16_t tomato_retrieved, uint8_t len)
320 {
321         int16_t score = 0;
322         uint8_t i;
323         uint32_t mask = 1;
324         uint8_t n;
325
326         /* score with corn */
327         n = xget_cob_count() * 2;
328         for (i = 0; i<CORN_NB; i++) {
329                 if (n >= 10)
330                         break;
331                 if (wcorn_retrieved & mask) {
332                         score += 250;
333                         n += 2;
334                 }
335                 if (n >= 10)
336                         break;
337                 if (ucorn_retrieved & mask) {
338                         score += 125;
339                         n += 1;
340                 }
341                 mask <<= 1UL;
342         }
343
344         printf_P(PSTR("get score: cob %d \r\n"), n);
345         /* score with tomato */
346         n = xget_ball_count();
347         mask = 1;
348         for (i = 0; i<TOMATO_NB; i++) {
349                 if (n >= 4)
350                         break;
351                 if (tomato_retrieved & mask) {
352                         score += 150;
353                         n += 1;
354                 }
355                 mask <<= 1UL;
356         }
357
358         printf_P(PSTR("get score: ball %d \r\n"), n);
359         /* malus for long circuits */
360         score -= (len * 20);
361
362         /* double malus for long circuits if we don't have much
363          * time */
364 #define WP_SPEED 1
365         if (len * WP_SPEED > (MATCH_TIME - xtime_get_s())) {
366                 uint16_t extra;
367                 extra = (len * WP_SPEED) - (MATCH_TIME - xtime_get_s());
368                 score -= (200 * extra);
369         }
370
371         /* XXX use direction of robot */
372
373         return score;
374 }
375
376 /* i,j: starting position */
377 int8_t browse_one_circuit(const struct wp_coord *circuit,
378                           uint8_t starti, uint8_t startj,
379                           int16_t *scoreA, int16_t *scoreB)
380 {
381         const struct wp_coord *curcircuit;
382         uint32_t wcorn_retrieved = 0; /* bit mask */
383         uint32_t ucorn_retrieved = 0; /* bit mask */
384         uint16_t tomato_retrieved = 0; /* bit mask */
385         uint8_t len = 0, found = 0, i, j;
386         uint8_t ni = 0, nj = 0, pos, color;
387
388         /* check that the point is present in the circuit */
389         for (curcircuit = circuit; curcircuit->end == 0; curcircuit ++) {
390                 if (curcircuit->i == starti && curcircuit->j == startj) {
391                         found = 1;
392                         break;
393                 }
394         }
395
396         if (found == 0)
397                 return -1;
398
399         for (curcircuit = circuit; curcircuit->end == 0; curcircuit ++, len ++) {
400                 i = curcircuit->i;
401                 j = curcircuit->j;
402
403 /*              printf("cur:%d,%d %x %x %x %d\n", i, j, */
404 /*                     wcorn_retrieved, ucorn_retrieved, tomato_retrieved, len); */
405
406                 /* face A completed */
407                 if (i == starti && j == startj) {
408                         *scoreA = get_score(wcorn_retrieved, ucorn_retrieved,
409                                            tomato_retrieved, len);
410                         wcorn_retrieved = 0; /* bit mask */
411                         ucorn_retrieved = 0; /* bit mask */
412                         tomato_retrieved = 0; /* bit mask */
413                         len = 0;
414                 }
415
416                 /* is there a tomato ? */
417                 if (strat_db.wp_table[i][j].type == WP_TYPE_TOMATO &&
418                     strat_db.wp_table[i][j].present) {
419                         tomato_retrieved |= (1UL << strat_db.wp_table[i][j].tomato.idx);
420                 }
421
422                 /* browse all neighbours to see if there is cobs */
423                 for (pos = LINE_UP; pos <= LINE_R_DOWN; pos++) {
424                         if (get_neigh(i, j, &ni, &nj, pos) < 0)
425                                 continue;
426
427                         /* is there a corn cob ? */
428                         if (strat_db.wp_table[ni][nj].type == WP_TYPE_CORN &&
429                             strat_db.wp_table[ni][nj].present) {
430                                 color = strat_db.wp_table[ni][nj].corn.color;
431                                 if (color == I2C_COB_WHITE)
432                                         wcorn_retrieved |= (1UL << strat_db.wp_table[ni][nj].corn.idx);
433                                 else if (color == I2C_COB_UNKNOWN)
434                                         ucorn_retrieved |= (1UL << strat_db.wp_table[ni][nj].corn.idx);
435                         }
436                 }
437         };
438
439         *scoreB = get_score(wcorn_retrieved, ucorn_retrieved,
440                             tomato_retrieved, len);
441         if (circuit->i == starti && circuit->j == startj)
442                 *scoreA = *scoreB;
443
444         return 0;
445 }
446
447 /* i,j starting position */
448 int8_t browse_circuits(uint8_t i, uint8_t j,
449                        const struct wp_coord **selected_circuit,
450                        int8_t *selected_face)
451 {
452         const struct wp_coord **circuit;
453         int16_t scoreA, scoreB;
454         int16_t selected_score = 0x8000; /* ~-int_max */
455         int8_t found = -1;
456
457         *selected_face = 0;
458         *selected_circuit = circuits[0] ;
459         for (circuit = &circuits[0]; *circuit; circuit++) {
460                 if (browse_one_circuit(*circuit, i, j, &scoreA, &scoreB) < 0)
461                         continue;
462                 found = 0;
463                 printf_P(PSTR("Circuit: %d %d\r\n"), scoreA, scoreB);
464                 if (scoreA > selected_score) {
465                         *selected_circuit = *circuit;
466                         selected_score = scoreA;
467                         *selected_face = 0;
468                 }
469                 if (scoreB > selected_score) {
470                         *selected_circuit = *circuit;
471                         selected_score = scoreB;
472                         *selected_face = 1;
473                 }
474         }
475         return found;
476 }
477
478 static void dump_circuit_wp(struct wp_line *circuit_wpline, int8_t len)
479 {
480         int8_t i;
481         if (len <= 0)
482                 return;
483         for (i = 0; i < len; i ++) {
484                 printf_P(PSTR("linenum %d dir %d\r\n"), circuit_wpline[i].line_num,
485                        circuit_wpline[i].dir);
486         }
487
488 }
489
490 uint8_t strat_harvest_circuit(void)
491 {
492         const struct wp_coord *selected_circuit;
493         int8_t selected_face;
494         struct wp_line circuit_wpline[MAX_CIRCUIT_WPLINE];
495         int8_t len;
496         uint8_t i, j, idx;
497         int16_t x, y;
498         uint8_t linenum, prev_linenum;
499         uint8_t dir, prev_dir;
500         uint8_t err;
501
502         x = position_get_x_s16(&mainboard.pos);
503         y = position_get_y_s16(&mainboard.pos);
504
505         if (xycoord_to_ijcoord(&x, &y, &i, &j) < 0) {
506                 DEBUG(E_USER_STRAT, "%s(): cannot find waypoint at %d,%d",
507                       __FUNCTION__, x, y);
508                 return END_ERROR;
509         }
510
511         browse_circuits(i, j, &selected_circuit, &selected_face);
512         len = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
513         if (len < 0) {
514                 DEBUG(E_USER_STRAT, "%s(): cannot find a path",
515                       __FUNCTION__);
516                 return END_ERROR;
517         }
518
519         dump_circuit_wp(circuit_wpline, len);
520
521         prev_linenum = circuit_wpline[0].line_num;
522         prev_dir = circuit_wpline[0].dir;
523         for (idx = 1; idx < len; idx ++) {
524         retry:
525                 if (get_cob_count() >= 5)
526                         strat_set_speed(600, SPEED_ANGLE_FAST);
527
528                 linenum = circuit_wpline[idx].line_num;
529                 dir = circuit_wpline[idx].dir;
530
531                 /* XXX basic opponent management */
532                 DEBUG(E_USER_STRAT, "%s(): line %d dir %d -> line %d dir %d",
533                       __FUNCTION__, prev_linenum, prev_dir, linenum, dir);
534                 err = line2line(prev_linenum, prev_dir, linenum, dir);
535                 if (!TRAJ_SUCCESS(err)) {
536                         strat_hardstop();
537                         time_wait_ms(2000);
538                         goto retry;
539                 }
540
541                 prev_linenum = linenum;
542                 prev_dir = dir;
543         }
544
545         return END_TRAJ; // XXX
546 }
547
548 void test_strat_avoid(void)
549 {
550 #if 0
551         uint8_t i, j;
552         const struct wp_coord *selected_circuit;
553         int8_t selected_face;
554         struct wp_line circuit_wpline[MAX_CIRCUIT_WPLINE];
555         int8_t ret;
556
557         i = 1; j = 1;
558         printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
559
560         ts = 0; bc = 0; cc = 0;
561         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
562         browse_circuits(i, j, &selected_circuit, &selected_face);
563         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
564         dump_circuit_wp(circuit_wpline, ret);
565
566         ts = 0; bc = 3; cc = 0;
567         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
568         browse_circuits(i, j, &selected_circuit, &selected_face);
569         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
570         dump_circuit_wp(circuit_wpline, ret);
571
572         ts = 0; bc = 4; cc = 0;
573         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
574         browse_circuits(i, j, &selected_circuit, &selected_face);
575         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
576         dump_circuit_wp(circuit_wpline, ret);
577
578         ts = 0; bc = 3; cc = 5;
579         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
580         browse_circuits(i, j, &selected_circuit, &selected_face);
581         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
582         dump_circuit_wp(circuit_wpline, ret);
583
584         ts = 0; bc = 4; cc = 5;
585         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
586         browse_circuits(i, j, &selected_circuit, &selected_face);
587         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
588         dump_circuit_wp(circuit_wpline, ret);
589
590         ts = 80; bc = 0; cc = 0;
591         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
592         browse_circuits(i, j, &selected_circuit, &selected_face);
593         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
594         dump_circuit_wp(circuit_wpline, ret);
595
596         i = 4; j = 3;
597         printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
598
599         ts = 0; bc = 0; cc = 0;
600         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
601         browse_circuits(i, j, &selected_circuit, &selected_face);
602         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
603         dump_circuit_wp(circuit_wpline, ret);
604
605         ts = 0; bc = 3; cc = 0;
606         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
607         browse_circuits(i, j, &selected_circuit, &selected_face);
608         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
609         dump_circuit_wp(circuit_wpline, ret);
610
611         ts = 80; bc = 0; cc = 0;
612         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
613         browse_circuits(i, j, &selected_circuit, &selected_face);
614         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
615         dump_circuit_wp(circuit_wpline, ret);
616
617         i = 11; j = 6;
618         printf_P(PSTR("========= i=%d, j=%d\r\n"), i, j);
619
620         ts = 0; bc = 0; cc = 0;
621         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
622         browse_circuits(i, j, &selected_circuit, &selected_face);
623         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
624         dump_circuit_wp(circuit_wpline, ret);
625
626         ts = 0; bc = 3; cc = 0;
627         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
628         browse_circuits(i, j, &selected_circuit, &selected_face);
629         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
630         dump_circuit_wp(circuit_wpline, ret);
631
632         ts = 80; bc = 0; cc = 0;
633         printf_P(PSTR("=== time=%"PRIu32", ball=%d, corn=%d\r\n"), ts, bc, cc);
634         browse_circuits(i, j, &selected_circuit, &selected_face);
635         ret = get_path(selected_circuit, i, j, selected_face, circuit_wpline);
636         dump_circuit_wp(circuit_wpline, ret);
637 #endif
638 }