1/**********************************************************************************
2 This file is part of the game 'KTron'
3
4 Copyright (C) 1998-2000 by Matthias Kiefer <matthias.kiefer@gmx.de>
5 Copyright (C) 2005 Benjamin C. Meyer <ben at meyerhome dot net>
6 Copyright (C) 2008-2009 Stas Verberkt <legolas at legolasweb dot nl>
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21
22 *******************************************************************************/
23
24#include "intelligence.h"
25
26#include "tron.h"
27#include "settings.h"
28
29#include <KgDifficulty>
30
31Intelligence::Intelligence()
32{
33 m_random.setSeed(0);
34
35 m_lookForward = 15;
36}
37
38void Intelligence::referenceTron(Tron *t)
39{
40 m_tron = t;
41}
42
43//
44// Settings
45//
46
47/** retrieves the opponentSkill */
48int Intelligence::opponentSkill() {
49 switch (Kg::difficultyLevel()) {
50 case KgDifficultyLevel::VeryEasy:
51 return 1;
52 default:
53 case KgDifficultyLevel::Easy:
54 return 1;
55 case KgDifficultyLevel::Medium:
56 return 2;
57 case KgDifficultyLevel::Hard:
58 return 3;
59 case KgDifficultyLevel::VeryHard:
60 return 3;
61 }
62}
63
64//
65// Algorithm helper function
66//
67
68void Intelligence::changeDirection(int playerNr,int dis_right,int dis_left)
69{
70 PlayerDirections::Direction currentDir = m_tron->getPlayer(playerNr)->getDirection();
71 PlayerDirections::Direction sides[2];
72 sides[0] = PlayerDirections::None;
73 sides[1] = PlayerDirections::None;
74
75 switch (currentDir)
76 {
77 case PlayerDirections::Left:
78 //turns to either side
79 sides[0] = PlayerDirections::Down;
80 sides[1] = PlayerDirections::Up;
81 break;
82 case PlayerDirections::Right:
83 sides[0] = PlayerDirections::Up;
84 sides[1] = PlayerDirections::Down;
85 break;
86 case PlayerDirections::Up:
87 sides[0] = PlayerDirections::Left;
88 sides[1] = PlayerDirections::Right;
89 break;
90 case PlayerDirections::Down:
91 sides[0] = PlayerDirections::Right;
92 sides[1] = PlayerDirections::Left;
93 break;
94 default:
95 break;
96
97 }
98
99 if(!(dis_left == 1 && dis_right == 1))
100 {
101 // change direction
102 if ((int)m_random.getLong(100) <= (100*dis_left)/(dis_left+dis_right))
103 {
104 if (dis_left != 1)
105 // turn to the left
106 m_tron->getPlayer(playerNr)->setDirection(sides[0]);
107 else
108 // turn to the right
109 m_tron->getPlayer(playerNr)->setDirection(sides[1]);
110 }
111 else
112 {
113 if (dis_right != 1)
114 // turn to the right
115 m_tron->getPlayer(playerNr)->setDirection(sides[1]);
116 else
117 // turn to the left
118 m_tron->getPlayer(playerNr)->setDirection(sides[0]);
119 }
120 }
121}
122
123// This part is partly ported from
124// xtron-1.1 by Rhett D. Jacobs <rhett@hotel.canberra.edu.au>
125void Intelligence::think(int playerNr)
126{
127 if (opponentSkill() != 1)
128 {
129 int opponent=(playerNr==1)? 0 : 1;
130
131 // determines left and right side
132 PlayerDirections::Direction sides[2];
133 sides[0] = PlayerDirections::None;
134 sides[1] = PlayerDirections::None;
135 // increments for moving to the different sides
136 int flags[6]={0,0,0,0,0,0};
137 int index[2];
138 // distances to barrier
139 int dis_forward, dis_left, dis_right;
140
141 dis_forward = dis_left = dis_right = 1;
142
143 switch (m_tron->getPlayer(playerNr)->getDirection())
144 {
145 case PlayerDirections::Left:
146 //forward flags
147 flags[0] = -1;
148 flags[1] = 0;
149
150 //left flags
151 flags[2] = 0;
152 flags[3] = 1;
153
154 // right flags
155 flags[4] = 0;
156 flags[5] = -1;
157
158 //turns to either side
159 sides[0] = PlayerDirections::Down;
160 sides[1] = PlayerDirections::Up;
161 break;
162 case PlayerDirections::Right:
163 flags[0] = 1;
164 flags[1] = 0;
165 flags[2] = 0;
166 flags[3] = -1;
167 flags[4] = 0;
168 flags[5] = 1;
169 sides[0] = PlayerDirections::Up;
170 sides[1] = PlayerDirections::Down;
171 break;
172 case PlayerDirections::Up:
173 flags[0] = 0;
174 flags[1] = -1;
175 flags[2] = -1;
176 flags[3] = 0;
177 flags[4] = 1;
178 flags[5] = 0;
179 sides[0] = PlayerDirections::Left;
180 sides[1] = PlayerDirections::Right;
181 break;
182 case PlayerDirections::Down:
183 flags[0] = 0;
184 flags[1] = 1;
185 flags[2] = 1;
186 flags[3] = 0;
187 flags[4] = -1;
188 flags[5] = 0;
189 sides[0] = PlayerDirections::Right;
190 sides[1] = PlayerDirections::Left;
191 break;
192 default:
193 break;
194 }
195
196 // check forward
197 index[0] = m_tron->getPlayer(playerNr)->getX()+flags[0];
198 index[1] = m_tron->getPlayer(playerNr)->getY()+flags[1];
199 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object)
200 {
201 dis_forward++;
202 index[0] += flags[0];
203 index[1] += flags[1];
204 }
205
206 // check left
207 index[0] = m_tron->getPlayer(playerNr)->getX()+flags[2];
208 index[1] = m_tron->getPlayer(playerNr)->getY()+flags[3];
209 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object)
210 {
211 dis_left++;
212 index[0] += flags[2];
213 index[1] += flags[3];
214 }
215
216 // check right
217 index[0] = m_tron->getPlayer(playerNr)->getX()+flags[4];
218 index[1] = m_tron->getPlayer(playerNr)->getY()+flags[5];
219 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object)
220 {
221 dis_right++;
222 index[0] += flags[4];
223 index[1] += flags[5];
224 }
225
226 // distances to opponent
227 int hor_dis=0; // negative is opponent to the right
228 int vert_dis=0; // negative is opponent to the bottom
229 hor_dis = m_tron->getPlayer(playerNr)->getX() - m_tron->getPlayer(opponent)->getX();
230 vert_dis = m_tron->getPlayer(playerNr)->getY() - m_tron->getPlayer(opponent)->getY();
231
232 int opForwardDis=0; // negative is to the back
233 int opSideDis=0; // negative is to the left
234 bool opMovesOppositeDir=false;
235 bool opMovesSameDir=false;
236 bool opMovesRight=false;
237 bool opMovesLeft=false;
238
239 switch (m_tron->getPlayer(playerNr)->getDirection())
240 {
241 case PlayerDirections::Up:
242 opForwardDis=vert_dis;
243 opSideDis=-hor_dis;
244 if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Down)
245 opMovesOppositeDir=true;
246 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Up)
247 opMovesSameDir=true;
248 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Left)
249 opMovesLeft=true;
250 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Right)
251 opMovesRight=true;
252 break;
253 case PlayerDirections::Down:
254 opForwardDis=-vert_dis;
255 opSideDis=hor_dis;
256 if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Up)
257 opMovesOppositeDir=true;
258 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Down)
259 opMovesSameDir=true;
260 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Left)
261 opMovesRight=true;
262 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Right)
263 opMovesLeft=true;
264 break;
265 case PlayerDirections::Left:
266 opForwardDis=hor_dis;
267 opSideDis=vert_dis;
268 if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Right)
269 opMovesOppositeDir=true;
270 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Left)
271 opMovesSameDir=true;
272 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Down)
273 opMovesLeft=true;
274 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Up)
275 opMovesRight=true;
276 break;
277 case PlayerDirections::Right:
278 opForwardDis=-hor_dis;
279 opSideDis=-vert_dis;
280 if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Left)
281 opMovesOppositeDir=true;
282 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Right)
283 opMovesSameDir=true;
284 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Up)
285 opMovesLeft=true;
286 else if(m_tron->getPlayer(opponent)->getDirection()==PlayerDirections::Down)
287 opMovesRight=true;
288 break;
289 default:
290 break;
291 }
292
293 int doPercentage = 100;
294 switch(opponentSkill())
295 {
296 case 1:
297 // Never reached
298 break;
299 case 2:
300 doPercentage=5;
301 break;
302 case 3:
303 doPercentage=90;
304 break;
305 }
306
307 // if opponent moves the opposite direction as we
308 if(opMovesOppositeDir)
309 {
310 // if opponent is in front
311 if(opForwardDis>0)
312 {
313 // opponent is to the right and we have the chance to block the way
314 if(opSideDis>0 && opSideDis < opForwardDis && opSideDis < dis_right && opForwardDis < m_lookForward)
315 {
316 if ((int)m_random.getLong(100) <= doPercentage || dis_forward==1)
317 m_tron->getPlayer(playerNr)->setDirection(sides[1]); // turn right
318 }
319 // opponent is to the left and we have the chance to block the way
320 else if(opSideDis<0 && -opSideDis < opForwardDis && -opSideDis < dis_left && opForwardDis < m_lookForward)
321 {
322 if ((int)m_random.getLong(100) <= doPercentage || dis_forward==1)
323 m_tron->getPlayer(playerNr)->setDirection(sides[0]); // turn left
324 }
325 // if we can do nothing, go forward
326 else if(dis_forward < m_lookForward)
327 {
328 dis_forward = 100 - 100/dis_forward;
329
330 if(!(dis_left == 1 && dis_right == 1))
331 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
332 changeDirection(playerNr,dis_right,dis_left);
333 }
334 }
335 // opponent is in back of us and moves away: do nothing
336 else if(dis_forward < m_lookForward)
337 {
338 dis_forward = 100 - 100/dis_forward;
339
340 if(!(dis_left == 1 && dis_right == 1))
341 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
342 changeDirection(playerNr,dis_right,dis_left);
343 }
344 } // end if(opMovesOppositeDir)
345 else if(opMovesSameDir)
346 {
347 // if opponent is to the back
348 if(opForwardDis < 0)
349 {
350 // opponent is to the right and we have the chance to block the way
351 if(opSideDis>0 && opSideDis < -opForwardDis && opSideDis < dis_right)
352 {
353 if ((int)m_random.getLong(100) <= doPercentage || dis_forward==1)
354 m_tron->getPlayer(playerNr)->setDirection(sides[1]); // turn right
355 }
356 // opponent is to the left and we have the chance to block the way
357 else if(opSideDis<0 && -opSideDis < -opForwardDis && -opSideDis < dis_left)
358 {
359 if ((int)m_random.getLong(100) <= doPercentage || dis_forward==1)
360 m_tron->getPlayer(playerNr)->setDirection(sides[0]); // turn left
361 }
362 // if we can do nothing, go forward
363 else if(dis_forward < m_lookForward)
364 {
365 dis_forward = 100 - 100/dis_forward;
366
367 if(!(dis_left == 1 && dis_right == 1))
368 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
369 changeDirection(playerNr,dis_right,dis_left);
370 }
371 }
372 // opponent is in front of us and moves away
373 else if(dis_forward < m_lookForward)
374 {
375 dis_forward = 100 - 100/dis_forward;
376
377 if(!(dis_left == 1 && dis_right == 1))
378 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
379 changeDirection(playerNr,dis_right,dis_left);
380 }
381 } // end if(opMovesSameDir)
382 else if(opMovesRight)
383 {
384 // opponent is in front of us
385 if(opForwardDis>0)
386 {
387 // opponent is to the left
388 if(opSideDis < 0 && -opSideDis < opForwardDis && -opSideDis < dis_left)
389 {
390 if(opForwardDis < m_lookForward && dis_left > m_lookForward)
391 {
392 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
393 changeDirection(playerNr,dis_right,dis_left);
394 }
395 else if(dis_forward < m_lookForward)
396 {
397 dis_forward = 100 - 100/dis_forward;
398
399 if(!(dis_left == 1 && dis_right == 1))
400 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
401 changeDirection(playerNr,dis_right,dis_left);
402 }
403 }
404 // op is to the right and moves away, but maybe we can block him
405 else if(opSideDis>=0 && opSideDis < dis_right)
406 {
407 if(opForwardDis < m_lookForward && dis_right > m_lookForward)
408 {
409 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
410 m_tron->getPlayer(playerNr)->setDirection(sides[1]); // turn right
411 }
412 else if(dis_forward < m_lookForward)
413 {
414 dis_forward = 100 - 100/dis_forward;
415
416 if(!(dis_left == 1 && dis_right == 1))
417 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
418 changeDirection(playerNr,dis_right,dis_left);
419 }
420 }
421 else if(dis_forward < m_lookForward)
422 {
423 dis_forward = 100 - 100/dis_forward;
424
425 if(!(dis_left == 1 && dis_right == 1))
426 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
427 changeDirection(playerNr,dis_right,dis_left);
428 }
429 }
430 // opponent is in the back of us
431 else
432 {
433 // opponent is right from us and we already blocked him
434 if(opSideDis>0 && opForwardDis < m_lookForward && opSideDis < dis_right)
435 {
436 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
437 changeDirection(playerNr,dis_right,dis_left);
438 }
439 else if(dis_forward < m_lookForward)
440 {
441 dis_forward = 100 - 100/dis_forward;
442
443 if(!(dis_left == 1 && dis_right == 1))
444 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
445 changeDirection(playerNr,dis_right,dis_left);
446 }
447 }
448 } // end if(opMovesRight)
449 else if(opMovesLeft)
450 {
451 // opponent is in front of us
452 if(opForwardDis>0)
453 {
454 // opponent is to the right, moves towards us and could block us
455 if(opSideDis > 0 && opSideDis < opForwardDis && opSideDis < dis_right)
456 {
457 if(opForwardDis < m_lookForward && dis_right > m_lookForward)
458 {
459 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
460 changeDirection(playerNr,dis_right,dis_left);
461 }
462 else if(dis_forward < m_lookForward)
463 {
464 dis_forward = 100 - 100/dis_forward;
465
466 if(!(dis_left == 1 && dis_right == 1))
467 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
468 changeDirection(playerNr,dis_right,dis_left);
469 }
470 }
471 // op is to the left and moves away, but maybe we can block him
472 else if(opSideDis<=0 && opSideDis < dis_left)
473 {
474 if(opForwardDis < m_lookForward && dis_left > m_lookForward)
475 {
476 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
477 m_tron->getPlayer(playerNr)->setDirection(sides[0]); // m_turn left
478 }
479 else if(dis_forward < m_lookForward)
480 {
481 dis_forward = 100 - 100/dis_forward;
482
483 if(!(dis_left == 1 && dis_right == 1))
484 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
485 changeDirection(playerNr,dis_right,dis_left);
486 }
487
488 }
489 else if(dis_forward < m_lookForward)
490 {
491 dis_forward = 100 - 100/dis_forward;
492
493 if(!(dis_left == 1 && dis_right == 1))
494 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
495 changeDirection(playerNr,dis_right,dis_left);
496 }
497 }
498 // opponent is in the back of us
499 else //if(opForwardDis<=0)
500 {
501 // opponent is left from us and we already blocked him
502 if(opSideDis<0 && opForwardDis < m_lookForward && -opSideDis < dis_left)
503 {
504 if ((int)m_random.getLong(100) <= doPercentage/2 || dis_forward==1)
505 changeDirection(playerNr,dis_right,dis_left);
506 }
507 else if(dis_forward < m_lookForward)
508 {
509 dis_forward = 100 - 100/dis_forward;
510
511 if(!(dis_left == 1 && dis_right == 1))
512 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 1)
513 changeDirection(playerNr,dis_right,dis_left);
514 }
515 }
516 } // end if(opMovesLeft)
517
518 }
519 // This part is completely ported from
520 // xtron-1.1 by Rhett D. Jacobs <rhett@hotel.canberra.edu.au>
521 else // Settings::skill() == Settings::EnumSkill::Easy
522 {
523 PlayerDirections::Direction sides[2];
524 sides[0] = PlayerDirections::None;
525 sides[1] = PlayerDirections::None;
526 int flags[6] = {0,0,0,0,0,0};
527 int index[2];
528 int dis_forward, dis_left, dis_right;
529
530 dis_forward = dis_left = dis_right = 1;
531
532 switch (m_tron->getPlayer(playerNr)->getDirection()) {
533 case PlayerDirections::Left:
534 //forward flags
535 flags[0] = -1;
536 flags[1] = 0;
537 //left flags
538 flags[2] = 0;
539 flags[3] = 1;
540 // right flags
541 flags[4] = 0;
542 flags[5] = -1;
543 //turns to either side
544 sides[0] = PlayerDirections::Down;
545 sides[1] = PlayerDirections::Up;
546 break;
547 case PlayerDirections::Right:
548 flags[0] = 1;
549 flags[1] = 0;
550 flags[2] = 0;
551 flags[3] = -1;
552 flags[4] = 0;
553 flags[5] = 1;
554 sides[0] = PlayerDirections::Up;
555 sides[1] = PlayerDirections::Down;
556 break;
557 case PlayerDirections::Up:
558 flags[0] = 0;
559 flags[1] = -1;
560 flags[2] = -1;
561 flags[3] = 0;
562 flags[4] = 1;
563 flags[5] = 0;
564 sides[0] = PlayerDirections::Left;
565 sides[1] = PlayerDirections::Right;
566 break;
567 case PlayerDirections::Down:
568 flags[0] = 0;
569 flags[1] = 1;
570 flags[2] = 1;
571 flags[3] = 0;
572 flags[4] = -1;
573 flags[5] = 0;
574 sides[0] = PlayerDirections::Right;
575 sides[1] = PlayerDirections::Left;
576 break;
577 default:
578 break;
579 }
580
581 // check forward
582 index[0] = m_tron->getPlayer(playerNr)->getX() + flags[0];
583 index[1] = m_tron->getPlayer(playerNr)->getY() + flags[1];
584 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object) {
585 dis_forward++;
586 index[0] += flags[0];
587 index[1] += flags[1];
588 }
589
590 if (dis_forward < m_lookForward)
591 {
592 dis_forward = 100 - 100 / dis_forward;
593
594 // check left
595 index[0] = m_tron->getPlayer(playerNr)->getX() + flags[2];
596 index[1] = m_tron->getPlayer(playerNr)->getY() + flags[3];
597 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object) {
598 dis_left++;
599 index[0] += flags[2];
600 index[1] += flags[3];
601 }
602
603 // check right
604 index[0] = m_tron->getPlayer(playerNr)->getX() + flags[4];
605 index[1] = m_tron->getPlayer(playerNr)->getY() + flags[5];
606 while (index[0] < m_tron->getPlayField()->getWidth() && index[0] >= 0 && index[1] < m_tron->getPlayField()->getHeight() && index[1] >= 0 && m_tron->getPlayField()->getObjectAt(index[0], index[1])->getObjectType() == ObjectType::Object) {
607 dis_right++;
608 index[0] += flags[4];
609 index[1] += flags[5];
610 }
611 if(!(dis_left == 1 && dis_right == 1)) {
612 if ((int)m_random.getLong(100) >= dis_forward || dis_forward == 0) {
613 // change direction
614 if ((int)m_random.getLong(100) <= (100*dis_left)/(dis_left+dis_right)) {
615 if (dis_left != 1)
616 // turn to the left
617 m_tron->getPlayer(playerNr)->setDirection(sides[0]);
618 else
619 // turn to the right
620 m_tron->getPlayer(playerNr)->setDirection(sides[1]);
621 }
622 else {
623 if (dis_right != 1)
624 // turn to the right
625 m_tron->getPlayer(playerNr)->setDirection(sides[1]);
626 else
627 // turn to the left
628 m_tron->getPlayer(playerNr)->setDirection(sides[0]);
629 }
630 }
631 }
632 }
633 }
634}
635
636