killbots/engine.cpp

   1 /*
   2  *  Copyright 2006-2009  Parker Coates <parker.coates@gmail.com>
   3  *
   4  *  This file is part of Killbots.
   5  *
   6  *  Killbots is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  Killbots is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with Killbots. If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include "engine.h"
  21
  22 #include "scene.h"
  23 #include "settings.h"
  24 #include "sprite.h"
  25
  26 #include <KDE/KDebug>
  27 #include <KDE/KLocale>
  28 #include <KDE/KRandom>
  29
  30 uint qHash( const QPoint & point )
  31 {
  32         return qHash( point.x() * 1000 + point.y() );
  33 }
  34
  35
  36 inline int sign( int num )
  37 {
  38         return (num > 0) ? 1 : (num == 0) ? 0 : -1;
  39 }
  40
  41
  42 Killbots::Engine::Engine( Scene * scene, QObject * parent )
  43   : QObject( parent ),
  44     m_scene( scene ),
  45     m_hero( 0 ),
  46     m_busyAnimating( false ),
  47     m_processFastbots( false ),
  48     m_gameOver( false ),
  49     m_newGameRequested( false ),
  50     m_repeatedAction( NoAction ),
  51     m_queuedAction( NoAction ),
  52     m_rules( 0 ),
  53     m_round( 0 ),
  54     m_score( 0 ),
  55     m_energy( 0 ),
  56     m_maxEnergy( 0.0 ),
  57     m_robotCount( 0.0 ),
  58     m_fastbotCount( 0.0 ),
  59     m_junkheapCount( 0.0 ),
  60     m_spriteMap()
  61 {
  62         connect( m_scene, SIGNAL(animationDone()), this, SLOT(animationDone()), Qt::QueuedConnection );
  63 }
  64
  65
  66 Killbots::Engine::~Engine()
  67 {
  68         delete m_rules;
  69 }
  70
  71
  72 const Killbots::Ruleset * Killbots::Engine::ruleset()
  73 {
  74         return m_rules;
  75 }
  76
  77
  78 bool Killbots::Engine::gameHasStarted()
  79 {
  80         return m_hero && m_score > 0;
  81 }
  82
  83
  84 void Killbots::Engine::requestNewGame()
  85 {
  86         if ( !m_busyAnimating || m_gameOver )
  87                 newGame();
  88         else
  89                 m_newGameRequested = true;
  90 }
  91
  92
  93 void Killbots::Engine::newGame()
  94 {
  95         if ( !m_rules || m_rules->fileName() != Settings::ruleset() )
  96         {
  97                 delete m_rules;
  98                 m_rules = 0;
  99                 m_rules = Ruleset::load( Settings::ruleset() );
 100         }
 101         if ( !m_rules )
 102                 m_rules = Ruleset::loadDefault();
 103         Q_ASSERT( m_rules != 0 );
 104
 105         // Don't show the new game message on first start.
 106         if ( m_round != 0 )
 107                  emit showNewGameMessage();
 108         emit newGame( m_rules->rows(), m_rules->columns(), m_rules->energyEnabled() );
 109         emit teleportAllowed( true );
 110         emit waitOutRoundAllowed( true );
 111         emit teleportSafelyAllowed( m_rules->safeTeleportEnabled() && m_energy >= m_rules->costOfSafeTeleport() );
 112         emit sonicScrewdriverAllowed( m_rules->sonicScrewdriverEnabled() && m_energy >= m_rules->costOfSonicScrewdriver() );
 113
 114         m_newGameRequested = false;
 115         m_gameOver = false;
 116
 117         m_round = 1;
 118         m_score = 0;
 119         m_maxEnergy = m_rules->energyEnabled() ? m_rules->maxEnergyAtGameStart() : 0;
 120         m_energy = m_rules->energyEnabled() ? m_rules->energyAtGameStart() : 0;
 121         m_robotCount = m_rules->enemiesAtGameStart();
 122         m_fastbotCount = m_rules->fastEnemiesAtGameStart();
 123         m_junkheapCount = m_rules->junkheapsAtGameStart();
 124
 125         // Code used to generate theme previews
 126         //newRound( "  r\nhjf", false );
 127
 128         newRound( false );
 129         m_busyAnimating = true;
 130         m_scene->startAnimation();
 131 }
 132
 133
 134 void Killbots::Engine::requestAction( HeroAction action )
 135 {
 136         // If the hero is doing a repeated move the new request only stops the hero.
 137         const bool cancelRepeatedMove = m_repeatedAction != WaitOutRound
 138                                         && m_repeatedAction != NoAction;
 139         if ( cancelRepeatedMove )
 140         {
 141                 m_repeatedAction = NoAction;
 142         }
 143
 144         if ( !m_busyAnimating && !m_gameOver )
 145         {
 146                 doAction( action );
 147         }
 148         else if ( !cancelRepeatedMove )
 149         {
 150                 m_queuedAction = action;
 151         }
 152 }
 153
 154
 155 // This slot is provided only for QSignalMapper compatibility.
 156 void Killbots::Engine::requestAction( int action )
 157 {
 158         requestAction( static_cast<HeroAction>( action ) );
 159 }
 160
 161
 162 void Killbots::Engine::doAction( HeroAction action )
 163 {
 164         bool actionSuccessful = false;
 165         bool boardFull = false;
 166
 167         refreshSpriteMap();
 168
 169         if ( action <= Hold )
 170         {
 171                 actionSuccessful = moveHero( action );
 172         }
 173         else if ( ( action == TeleportSafely || action == TeleportSafelyIfPossible )
 174                   && m_rules->safeTeleportEnabled()
 175                   && m_energy >= m_rules->costOfSafeTeleport()
 176                 )
 177         {
 178                 actionSuccessful = teleportHeroSafely();
 179                 boardFull = !actionSuccessful;
 180         }
 181         else if ( action == Teleport || action == TeleportSafelyIfPossible )
 182         {
 183                 actionSuccessful = teleportHero();
 184         }
 185         else if ( action == SonicScrewdriver && m_energy >= m_rules->costOfSonicScrewdriver() )
 186         {
 187                 actionSuccessful = sonicScrewdriver();
 188         }
 189         else if ( action == WaitOutRound )
 190         {
 191                 m_repeatedAction = WaitOutRound;
 192                 actionSuccessful = true;
 193         }
 194
 195         if ( actionSuccessful )
 196         {
 197                 moveRobots();
 198                 assessDamage();
 199                 if ( m_bots.isEmpty() )
 200                         emit showRoundCompleteMessage();
 201                 else
 202                         m_processFastbots = true;
 203                 m_busyAnimating = true;
 204                 m_scene->startAnimation();
 205         }
 206         else if ( boardFull )
 207         {
 208                 resetBotCounts();
 209                 m_busyAnimating = true;
 210                 m_scene->startAnimation();
 211         }
 212 }
 213
 214
 215 void Killbots::Engine::animationDone()
 216 {
 217         m_busyAnimating = false;
 218
 219         if ( m_newGameRequested )
 220         {
 221                 newGame();
 222         }
 223         else if ( m_processFastbots )
 224         {
 225                 m_processFastbots = false;
 226                 moveRobots( true );
 227                 assessDamage();
 228                 if ( m_bots.isEmpty() )
 229                         emit showRoundCompleteMessage();
 230                 m_busyAnimating = true;
 231                 m_scene->startAnimation();
 232         }
 233         else if ( m_gameOver )
 234         {
 235                 emit showGameOverMessage();
 236                 emit teleportAllowed( false );
 237                 emit waitOutRoundAllowed( false );
 238                 emit teleportSafelyAllowed( false );
 239                 emit sonicScrewdriverAllowed( false );
 240                 emit gameOver( m_score, m_round );
 241         }
 242         else if ( m_bots.isEmpty() )
 243         {
 244                 newRound();
 245                 if ( m_robotCount + m_fastbotCount + m_junkheapCount > m_rules->rows() * m_rules->columns() / 2 )
 246                         resetBotCounts();
 247                 m_busyAnimating = true;
 248                 m_scene->startAnimation();
 249         }
 250         else if ( m_repeatedAction != NoAction )
 251         {
 252                 doAction( m_repeatedAction );
 253         }
 254         else if ( m_queuedAction != NoAction )
 255         {
 256                 doAction( m_queuedAction );
 257                 m_queuedAction = NoAction;
 258         }
 259 }
 260
 261
 262 void Killbots::Engine::newRound( bool incrementRound, const QString & layout )
 263 {
 264         cleanUpRound();
 265
 266         m_processFastbots = false;
 267         m_repeatedAction = NoAction;
 268         m_queuedAction = NoAction;
 269
 270         m_scene->beginNewAnimationStage();
 271
 272         if ( incrementRound )
 273         {
 274                 ++m_round;
 275
 276                 if ( m_rules->energyEnabled() )
 277                 {
 278                         m_maxEnergy += m_rules->maxEnergyAddedEachRound();
 279                         updateEnergy( m_rules->energyAddedEachRound() );
 280                 }
 281                 m_robotCount += m_rules->enemiesAddedEachRound();
 282                 m_fastbotCount += m_rules->fastEnemiesAddedEachRound();
 283                 m_junkheapCount += m_rules->junkheapsAddedEachRound();
 284         }
 285
 286         if ( layout.isEmpty() )
 287         {
 288                 // Place the hero in the centre of the board.
 289                 const QPoint centre = QPoint( qRound( m_rules->columns() / 2 ), qRound( m_rules->rows() / 2 ) );
 290                 m_hero = m_scene->createSprite( Hero, centre );
 291
 292                 // Create and randomly place junkheaps.
 293                 for ( int i = m_junkheapCount; i > 0 ; --i )
 294                 {
 295                         const QPoint point = randomEmptyCell();
 296                         m_junkheaps << m_scene->createSprite( Junkheap, point );
 297                         m_spriteMap.insert( point, m_junkheaps.last() );
 298                 }
 299
 300                 // Create and randomly place robots.
 301                 for ( int i = m_robotCount; i > 0; --i )
 302                 {
 303                         const QPoint point = randomEmptyCell();
 304                         m_bots << m_scene->createSprite( Robot, point );
 305                         m_spriteMap.insert( point, m_bots.last() );
 306                 }
 307
 308                 // Create and randomly place fastbots.
 309                 for ( int i = m_fastbotCount; i > 0; --i )
 310                 {
 311                         const QPoint point = randomEmptyCell();
 312                         m_bots << m_scene->createSprite( Fastbot, point );
 313                         m_spriteMap.insert( point, m_bots.last() );
 314                 }
 315         }
 316         else
 317         {
 318                 const QStringList rows = layout.split('\n');
 319                 for ( int r = 0; r < rows.size(); ++r )
 320                 {
 321                         for ( int c = 0; c < rows.at( r ).size(); ++c )
 322                         {
 323                                 const QChar ch = rows.at( r ).at( c );
 324                                 const QPoint point( c, r );
 325
 326                                 if ( ch == 'h' && m_hero == 0 )
 327                                         m_hero = m_scene->createSprite( Hero, point );
 328                                 else if ( ch == 'r' )
 329                                         m_bots << m_scene->createSprite( Robot, point );
 330                                 else if ( ch == 'f' )
 331                                         m_bots << m_scene->createSprite( Fastbot, point );
 332                                 else if ( ch == 'j' )
 333                                         m_junkheaps << m_scene->createSprite( Junkheap, point );
 334                         }
 335                 }
 336         }
 337
 338         emit roundChanged( m_round );
 339         emit scoreChanged( m_score );
 340         emit enemyCountChanged( m_bots.size() );
 341         emit energyChanged( m_energy );
 342
 343         refreshSpriteMap();
 344 }
 345
 346
 347 // Returns true if the move was performed, returns false otherwise.
 348 bool Killbots::Engine::moveHero( HeroAction direction )
 349 {
 350         const QPoint newCell = m_hero->gridPos() + offsetFromDirection( direction );
 351
 352         if ( moveIsValid( newCell, direction )
 353              && ( moveIsSafe( newCell, direction )
 354                   || ( !Settings::preventUnsafeMoves()
 355                        && m_repeatedAction == NoAction
 356                      )
 357                 )
 358            )
 359         {
 360                 m_repeatedAction = direction < 0 ? direction : NoAction;
 361
 362                 if ( direction != Hold )
 363                 {
 364                         m_scene->beginNewAnimationStage();
 365
 366                         if ( spriteTypeAt( newCell ) == Junkheap )
 367                                 pushJunkheap( m_spriteMap.value( newCell ), direction );
 368
 369                         m_scene->slideSprite( m_hero, newCell );
 370                 }
 371                 return true;
 372         }
 373         else
 374         {
 375                 m_repeatedAction = NoAction;
 376                 return false;
 377         }
 378 }
 379
 380
 381 void Killbots::Engine::pushJunkheap( Sprite * junkheap, HeroAction direction )
 382 {
 383         const QPoint nextCell = junkheap->gridPos() + offsetFromDirection( direction );
 384         Sprite * currentOccupant = m_spriteMap.value( nextCell );
 385         if ( currentOccupant )
 386         {
 387                 if ( currentOccupant->spriteType() == Junkheap )
 388                 {
 389                         pushJunkheap( currentOccupant, direction );
 390                 }
 391                 else
 392                 {
 393                         destroySprite( currentOccupant );
 394                         updateScore( m_rules->squashKillPointBonus() );
 395                         updateEnergy( m_rules->squashKillEnergyBonus() );
 396                 }
 397         }
 398
 399         m_scene->slideSprite( junkheap, nextCell );
 400 }
 401
 402
 403 // Always returns true as teleports always succeed.
 404 bool Killbots::Engine::teleportHero()
 405 {
 406         const QPoint point = randomEmptyCell();
 407         m_scene->beginNewAnimationStage();
 408         m_scene->teleportSprite( m_hero, point );
 409         return true;
 410 }
 411
 412
 413 // Returns true if a safe cell was found. If no safe cell was found than
 414 // the board must be full.
 415 bool Killbots::Engine::teleportHeroSafely()
 416 {
 417         // Choose a random cell...
 418         const QPoint startPoint = QPoint( KRandom::random() % m_rules->columns(), KRandom::random() % m_rules->rows() );
 419         QPoint point = startPoint;
 420
 421         // ...and step through all the cells on the board looking for a safe cell.
 422         do
 423         {
 424                 if ( point.x() < m_rules->columns() - 1 )
 425                         point.rx()++;
 426                 else
 427                 {
 428                         point.rx() = 0;
 429                         if ( point.y() < m_rules->rows() - 1 )
 430                                 point.ry()++;
 431                         else
 432                                 point.ry() = 0;
 433                 }
 434
 435                 // Looking for an empty and safe cell.
 436                 if ( spriteTypeAt( point ) == NoSprite && point != m_hero->gridPos() && moveIsSafe( point, Teleport ) )
 437                         break;
 438         }
 439         while ( point != startPoint );
 440
 441         // If we stepped through every cell and found none that were safe, reset the robot counts.
 442         if ( point == startPoint )
 443         {
 444                 return false;
 445         }
 446         else
 447         {
 448                 m_scene->beginNewAnimationStage();
 449                 updateEnergy( -m_rules->costOfSafeTeleport() );
 450                 m_scene->teleportSprite( m_hero, point );
 451
 452                 return true;
 453         }
 454 }
 455
 456
 457 // Returns true if any enemies were within range.
 458 bool Killbots::Engine::sonicScrewdriver()
 459 {
 460         QList<Sprite *> neighbors;
 461         for ( int i = Right; i <= DownRight; ++i )
 462         {
 463                 const QPoint neighbor = m_hero->gridPos() + offsetFromDirection( i );
 464                 if ( cellIsValid( neighbor ) && ( spriteTypeAt( neighbor ) == Robot || spriteTypeAt( neighbor ) == Fastbot ) )
 465                         neighbors << m_spriteMap.value(neighbor);
 466         }
 467
 468         if ( neighbors.size() )
 469         {
 470                 m_scene->beginNewAnimationStage();
 471                 foreach ( Sprite * sprite, neighbors )
 472                         destroySprite( sprite );
 473                 updateEnergy( -m_rules->costOfSonicScrewdriver() );
 474                 return true;
 475         }
 476         else
 477         {
 478                 return false;
 479         }
 480 }
 481
 482
 483 void Killbots::Engine::moveRobots( bool justFastbots )
 484 {
 485         m_scene->beginNewAnimationStage();
 486
 487         foreach( Sprite * bot, m_bots )
 488         {
 489                 if ( bot->spriteType() == Fastbot || !justFastbots )
 490                 {
 491                         const QPoint offset( sign( m_hero->gridPos().x() - bot->gridPos().x() ), sign( m_hero->gridPos().y() - bot->gridPos().y() ) );
 492                         m_scene->slideSprite( bot, bot->gridPos() + offset );
 493                 }
 494         }
 495 }
 496
 497
 498 void Killbots::Engine::assessDamage()
 499 {
 500         refreshSpriteMap();
 501
 502         m_scene->beginNewAnimationStage();
 503
 504         if ( m_spriteMap.count( m_hero->gridPos() ) > 0 )
 505                 m_gameOver = true;
 506
 507         // Check junkheaps for dead robots
 508         foreach ( Sprite * junkheap, m_junkheaps )
 509                 destroyAllCollidingBots( junkheap, !m_gameOver );
 510
 511         // Check for robot-on-robot violence
 512         int i = 0;
 513         while ( i < m_bots.size() )
 514         {
 515                 Sprite * bot = m_bots[i];
 516                 if ( bot->gridPos() != m_hero->gridPos() && destroyAllCollidingBots( bot, !m_gameOver ) )
 517                 {
 518                         m_junkheaps << m_scene->createSprite( Junkheap, bot->gridPos() );
 519                         destroySprite( bot, !m_gameOver );
 520                 }
 521                 else
 522                 {
 523                         i++;
 524                 }
 525         }
 526 }
 527
 528
 529 void Killbots::Engine::cleanUpRound()
 530 {
 531         m_scene->beginNewAnimationStage();
 532
 533         if ( m_hero )
 534                 destroySprite( m_hero );
 535         m_hero = 0;
 536
 537         foreach( Sprite * bot, m_bots )
 538                 destroySprite( bot, false );
 539         m_bots.clear();
 540
 541         foreach( Sprite * junkheap, m_junkheaps )
 542                 destroySprite( junkheap );
 543         m_junkheaps.clear();
 544
 545         m_spriteMap.clear();
 546 }
 547
 548
 549 void Killbots::Engine::destroySprite( Sprite * sprite, bool calculatePoints )
 550 {
 551         const SpriteType type = sprite->spriteType();
 552
 553         if ( type == Robot || type == Fastbot)
 554         {
 555                 if ( calculatePoints )
 556                 {
 557                         if ( type == Robot )
 558                                 updateScore( m_rules->pointsPerEnemyKilled() );
 559                         else
 560                                 updateScore( m_rules->pointsPerFastEnemyKilled() );
 561
 562                         if ( m_repeatedAction == WaitOutRound )
 563                         {
 564                                 updateScore(  m_rules->waitKillPointBonus() );
 565                                 updateEnergy( m_rules->waitKillEnergyBonus() );
 566                         }
 567                 }
 568                 m_bots.removeOne( sprite );
 569                 emit enemyCountChanged( m_bots.size() );
 570         }
 571         else if ( type == Junkheap )
 572         {
 573                 m_junkheaps.removeOne( sprite );
 574         }
 575
 576         m_scene->destroySprite( sprite );
 577 }
 578
 579
 580 bool Killbots::Engine::destroyAllCollidingBots( const Sprite * sprite, bool calculatePoints )
 581 {
 582         bool result = false;
 583
 584         foreach ( Sprite * robot, m_spriteMap.values( sprite->gridPos() ) )
 585         {
 586                 if ( robot != sprite && ( robot->spriteType() == Robot || robot->spriteType() == Fastbot ) )
 587                 {
 588                         destroySprite( robot, calculatePoints );
 589                         result = true;
 590                 }
 591         }
 592
 593         return result;
 594 }
 595
 596
 597 void Killbots::Engine::updateScore( int changeInScore )
 598 {
 599         if ( changeInScore != 0 )
 600         {
 601                 m_score = m_score + changeInScore;
 602                 emit scoreChanged( m_score );
 603         }
 604 }
 605
 606
 607 void Killbots::Engine::updateEnergy( int changeInEnergy )
 608 {
 609         if ( m_rules->energyEnabled() && changeInEnergy != 0 )
 610         {
 611                 if ( changeInEnergy > 0 && m_energy > int( m_maxEnergy ) )
 612                 {
 613                         m_score += changeInEnergy * m_rules->pointsPerEnergyAboveMax();
 614                 }
 615                 else if ( changeInEnergy > 0 && m_energy + changeInEnergy > int( m_maxEnergy ) )
 616                 {
 617                         m_score += ( m_energy + changeInEnergy - int( m_maxEnergy ) ) * m_rules->pointsPerEnergyAboveMax();
 618                         m_energy = int( m_maxEnergy );
 619                 }
 620                 else
 621                 {
 622                         m_energy = m_energy + changeInEnergy;
 623                 }
 624
 625                 emit energyChanged( m_energy );
 626                 emit teleportSafelyAllowed( m_rules->safeTeleportEnabled() && m_energy >= m_rules->costOfSafeTeleport()  );
 627                 emit sonicScrewdriverAllowed( m_rules->sonicScrewdriverEnabled() && m_energy >= m_rules->costOfSonicScrewdriver() );
 628         }
 629 }
 630
 631
 632 void Killbots::Engine::resetBotCounts()
 633 {
 634         m_scene->beginNewAnimationStage();
 635         emit showBoardFullMessage();
 636
 637         m_maxEnergy = m_rules->maxEnergyAtGameStart();
 638         m_robotCount = m_rules->enemiesAtGameStart();
 639         m_fastbotCount = m_rules->fastEnemiesAtGameStart();
 640         m_junkheapCount = m_rules->junkheapsAtGameStart();
 641
 642         m_scene->beginNewAnimationStage();
 643         newRound(false);
 644 }
 645
 646
 647 // The hero action functions and the assessDamage functions must know the
 648 // contents of each cell. This function updates the hash that maps cells to
 649 // their contents.
 650 void Killbots::Engine::refreshSpriteMap()
 651 {
 652         m_spriteMap.clear();
 653         foreach( Sprite * bot, m_bots )
 654                 m_spriteMap.insert( bot->gridPos(), bot );
 655         foreach( Sprite * junkheap, m_junkheaps )
 656                 m_spriteMap.insert( junkheap->gridPos(), junkheap );
 657 }
 658
 659
 660 // A convenience function to query the type of a sprite any the given cell.
 661 int Killbots::Engine::spriteTypeAt( const QPoint & cell ) const
 662 {
 663         if ( m_spriteMap.contains( cell ) )
 664                 return m_spriteMap.value( cell )->spriteType();
 665         else
 666                 return NoSprite;
 667 }
 668
 669
 670 // Returns a random empty cell on the grid. Depends on a fresh spritemap.
 671 QPoint Killbots::Engine::randomEmptyCell() const
 672 {
 673         QPoint point;
 674         do
 675                 point = QPoint( KRandom::random() % m_rules->columns(), KRandom::random() % m_rules->rows() );
 676         while ( spriteTypeAt( point ) != NoSprite || point == m_hero->gridPos() );
 677         return point;
 678 }
 679
 680
 681 // Returns true if the given cell lies inside the game grid.
 682 bool Killbots::Engine::cellIsValid( const QPoint & cell ) const
 683 {
 684         return ( 0 <= cell.x()
 685                  && cell.x() < m_rules->columns()
 686                  && 0 <= cell.y()
 687                  && cell.y() < m_rules->rows()
 688                );
 689 }
 690
 691
 692 bool Killbots::Engine::moveIsValid( const QPoint & cell, HeroAction direction ) const
 693 {
 694         const QPoint cellBehindCell = cell + offsetFromDirection( direction );
 695
 696         // The short version
 697         return ( cellIsValid( cell )
 698                  && ( spriteTypeAt( cell ) == NoSprite
 699                       || ( spriteTypeAt( cell ) == Junkheap
 700                            && canPushJunkheap( m_spriteMap.value( cell ), direction )
 701                          )
 702                     )
 703                );
 704
 705
 706 /*      // The debuggable version
 707         bool result = true;
 708
 709         if ( cellIsValid( cell ) )
 710         {
 711                 if ( spriteTypeAt( cell ) != NoSprite )
 712                 {
 713                         if ( spriteTypeAt( cell ) == Junkheap )
 714                         {
 715                                 if ( !canPushJunkheap( m_spriteMap.value( cell ), direction ) )
 716                                 {
 717                                         result = false;
 718                                         kDebug() << "Move is invalid. Cannot push junkheap.";
 719                                 }
 720                         }
 721                         else
 722                         {
 723                                 result = false;
 724                                 kDebug() << "Move is invalid. Cell is occupied by an unpushable object.";
 725                         }
 726                 }
 727         }
 728         else
 729         {
 730                 result = false;
 731                 kDebug() << "Move is invalid. Cell is lies outside grid.";
 732         }
 733
 734         return result;
 735 */
 736 }
 737
 738
 739 bool Killbots::Engine::moveIsSafe( const QPoint & cell, HeroAction direction ) const
 740 {
 741         /*
 742         Warning: This algorithm might break your head. The following diagrams and descriptions try to help.
 743
 744         Note: This algorithm assumes that the proposed move has already been checked for validity.
 745
 746         Legend
 747         H = The position of the hero after the proposed move (the cell who's safeness we're trying to determine).
 748         J = The position of a junkheap after the proposed move, whether moved by the hero or sitting there already.
 749         R = The position of a robot.
 750         F = The position of a fastbot.
 751         * = A cell that we don't particularly care about in this diagram.
 752
 753         +---+---+---+---+---+
 754         | * | * | * | * | * |
 755         +---+---+---+---+---+
 756         | * |   |   | F | * |
 757         +---+---+---+---+---+
 758         | * |   | H |   | * |    If any of the neighbouring cells contain a robot or fastbot, the move is unsafe.
 759         +---+---+---+---+---+
 760         | * |   | R |   | * |
 761         +---+---+---+---+---+
 762         | * | * | * | * | * |
 763         +---+---+---+---+---+
 764
 765         +---+---+---+---+---+
 766         |   |   |   |   |   |
 767         +---+---+---+---+---+
 768         |   |   |   |   |   |
 769         +---+---+---+---+---+
 770         |   | *<==J<==H |   |    If the proposed move involved pushing a junkheap, we can ignore the cell that the junkheap
 771         +---+---+---+---+---+    will end up in, because if there were an enemy there, it would be crushed.
 772         |   |   |   |   |   |
 773         +---+---+---+---+---+
 774         |   |   |   |   |   |
 775         +---+---+---+---+---+
 776
 777         +---+---+---+---+---+
 778         |C01|   |   |   |   |
 779         +---+---+---+---+---+    Fastbots can attack from two cells away, making it trickier to determine whether they
 780         |   |N01|   |   |E01|    pose a threat. First we have to understand the attack vector of a fastbot. A fastbot
 781         +---+---+---+---+---+    attacking from a "corner" cell such as C01 will pass through a diagonal neighbour like
 782         |   |   | H |N02|E02|    like N01. Any fastbot attacking from an "edge" cell like E01, E02 or E03 will have to
 783         +---+---+---+---+---+    pass through a horizontal or vertical neighbour like N02. This mean that when checking
 784         |   |   |   |   |E03|    a diagonal neighbour we only need to check the one cell "behind" it for fastbots, but
 785         +---+---+---+---+---+    when checking a horizontal or vertical neighbour we need to check the three cells
 786         |   |   |   |   |   |    "behind" it for fastbots.
 787         +---+---+---+---+---+
 788
 789         +---+---+---+---+---+
 790         |   |   |   |   | * |
 791         +---+---+---+---+---+
 792         | * |   |   | J |   |
 793         +---+---+---+---+---+    Back to junkheaps. If a neighbouring cell contains a junkheap, we don't need to check
 794         | * | J | H |   |   |    the cells behind it for fastbots because if there were any there, they'd just collide
 795         +---+---+---+---+---+    with the junkheap anyway.
 796         | * |   |   |   |   |
 797         +---+---+---+---+---+
 798         |   |   |   |   |   |
 799         +---+---+---+---+---+
 800
 801         +---+---+---+---+---+
 802         | * | * | * | * | F |
 803         +---+---+---+---+---+
 804         | * | * | * |   | * |
 805         +---+---+---+---+---+
 806         | * | * | H | * | * |    "Corner" fastbot threats are easy enough to detect. If a diagonal neighbour is empty
 807         +---+---+---+---+---+    and the cell behind it contains a fastbot, the move is unsafe.
 808         | * | * | * | * | * |
 809         +---+---+---+---+---+
 810         | * | * | * | * | * |
 811         +---+---+---+---+---+
 812
 813         +---+---+---+---+---+
 814         | * | * | * | * | * |
 815         +---+---+---+---+---+
 816         | R | * | * | * | * |
 817         +---+---+---+---+---+    "Edge" fastbots threats are much harder to detect because any fastbots on an edge might
 818         | F |   | H | * | * |    collide with robots or other fastbots on their way to the neighbouring cell. For example,
 819         +---+---+---+---+---+    the hero in this diagram is perfectly safe because all the fastbots will be destroyed
 820         |   | * |   | * | * |    before they can become dangerous.
 821         +---+---+---+---+---+
 822         | * | F |   | F | * |
 823         +---+---+---+---+---+
 824
 825         +---+---+---+---+---+
 826         | * | F |   |   | * |
 827         +---+---+---+---+---+
 828         | * | * |   | * |   |
 829         +---+---+---+---+---+    With a bit of thought, it's easy to see that an "edge" fastbot is only a threat if there
 830         | * | * | H |   |   |    is exactly one fastbot and zero robots on that edge.
 831         +---+---+---+---+---+
 832         | * | * |   | * | F |    When you put all of the above facts together you (hopefully) get the following algorithm.
 833         +---+---+---+---+---+
 834         | * |   | F |   | * |
 835         +---+---+---+---+---+
 836         */
 837
 838         // The move is assumed safe until proven unsafe.
 839         bool result = true;
 840
 841         // If we're pushing a junkheap, store the cell that the junkheap will end up in. Otherwise store an invalid cell.
 842         const QPoint cellBehindJunkheap = ( spriteTypeAt( cell ) != Junkheap )
 843                                           ? QPoint( -1, -1 )
 844                                           : cell + offsetFromDirection( direction );
 845
 846         // We check the each of the target cells neighbours.
 847         for ( int i = Right; i <= DownRight && result; ++i )
 848         {
 849                 const QPoint neighbor = cell + offsetFromDirection( i );
 850
 851                 // If the neighbour is invalid or the cell behind the junkheap, continue to the next neighbour.
 852                 if ( !cellIsValid( neighbor ) || spriteTypeAt( neighbor ) == Junkheap || neighbor == cellBehindJunkheap )
 853                         continue;
 854
 855                 // If the neighbour contains an enemy, the move is unsafe.
 856                 if ( spriteTypeAt( neighbor ) == Robot || spriteTypeAt( neighbor ) == Fastbot )
 857                 {
 858                         result = false;
 859                 }
 860                 else
 861                 {
 862                         // neighboursNeighbour is the cell behind the neighbour, with respect to the target cell.
 863                         const QPoint neighborsNeighbor = neighbor + offsetFromDirection( i );
 864
 865                         // If we're examining a diagonal neighbour (an odd direction)...
 866                         if ( i % 2 == 1 )
 867                         {
 868                                 // ...and neighboursNeighbour is a fastbot then the move is unsafe.
 869                                 if ( spriteTypeAt( neighborsNeighbor ) == Fastbot )
 870                                         result = false;
 871                         }
 872                         // If we're examining an vertical or horizontal neighbour, things are more complicated...
 873                         else
 874                         {
 875                                 // Assemble a list of the cells behind the neighbour.
 876                                 QList<QPoint> cellsBehindNeighbor;
 877                                 cellsBehindNeighbor << neighborsNeighbor;
 878                                 // Add neighboursNeighbour's anticlockwise neighbour.
 879                                 // ( i + 2 ) % 8 is the direction a quarter turn anticlockwise from i.
 880                                 cellsBehindNeighbor << neighborsNeighbor + offsetFromDirection( ( i + 2 ) % 8 );
 881                                 // Add neighboursNeighbour's clockwise neighbour.
 882                                 // ( i + 6 ) % 8 is the direction a quarter turn clockwise from i.
 883                                 cellsBehindNeighbor << neighborsNeighbor + offsetFromDirection( ( i + 6 ) % 8 );
 884
 885                                 // Then we just count the number of fastbots and robots in the list of cells.
 886                                 int fastbotsFound = 0;
 887                                 int robotsFound = 0;
 888                                 foreach( const QPoint & cell, cellsBehindNeighbor )
 889                                 {
 890                                         if ( spriteTypeAt( cell ) == Fastbot )
 891                                                 ++fastbotsFound;
 892                                         else if ( spriteTypeAt( cell ) == Robot )
 893                                                 ++robotsFound;
 894                                 }
 895
 896                                 // If there is exactly one fastbots and zero robots, the move is unsafe.
 897                                 if ( fastbotsFound == 1 && robotsFound == 0 )
 898                                         result = false;
 899                         }
 900                 }
 901         }
 902
 903         return result;
 904 }
 905
 906
 907 bool Killbots::Engine::canPushJunkheap( const Sprite * junkheap, HeroAction direction ) const
 908 {
 909         Q_ASSERT( junkheap->spriteType() == Junkheap );
 910
 911         const QPoint nextCell = junkheap->gridPos() + offsetFromDirection( direction );
 912
 913         if ( m_rules->pushableJunkheaps() != Ruleset::None && cellIsValid( nextCell ) )
 914         {
 915                 if ( spriteTypeAt( nextCell ) == NoSprite )
 916                         return true;
 917                 else if ( spriteTypeAt( nextCell ) == Junkheap )
 918                         return m_rules->pushableJunkheaps() == Ruleset::Many && canPushJunkheap( m_spriteMap.value( nextCell ), direction );
 919                 else
 920                         return m_rules->squaskKillsEnabled();
 921         }
 922         else
 923         {
 924                 return false;
 925         }
 926 }
 927
 928
 929 QPoint Killbots::Engine::offsetFromDirection( int direction ) const
 930 {
 931         if ( direction < 0 )
 932                 direction = -direction - 1;
 933
 934         switch( direction )
 935         {
 936         case Right:
 937                 return QPoint(  1,  0 );
 938         case UpRight:
 939                 return QPoint(  1, -1 );
 940         case Up:
 941                 return QPoint(  0, -1 );
 942         case UpLeft:
 943                 return QPoint( -1, -1 );
 944         case Left:
 945                 return QPoint( -1,  0 );
 946         case DownLeft:
 947                 return QPoint( -1,  1 );
 948         case Down:
 949                 return QPoint(  0,  1 );
 950         case DownRight:
 951                 return QPoint(  1,  1 );
 952         default:
 953                 return QPoint(  0,  0 );
 954         };
 955 }