src/quick/items/qquickspriteengine.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: http://www.qt-project.org/
   6 **
   7 ** This file is part of the Declarative module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qquickspriteengine_p.h"
  43 #include "qquicksprite_p.h"
  44 #include <QDebug>
  45 #include <QPainter>
  46 #include <QSet>
  47 #include <QtGui>
  48
  49 QT_BEGIN_NAMESPACE
  50
  51 /*
  52     \internal Stochastic/Sprite engine implementation docs
  53
  54     Nomenclature: 'thing' refers to an instance of a running sprite or state. It could be renamed.
  55     States and Transitions are referred to in the state machine sense here, NOT in the QML sense.
  56
  57     The Stochastic State engine takes states with stochastic state transitions defined and transitions them.
  58     When a state is started, it's added to a list of pending updates sorted by their time they want to update.
  59     An external driver calls the update function with an elapsed time, which becomes the new time offset.
  60     The pending update stack is popped until all entries are past the current time, which simulates all intervening time.
  61
  62     The Sprite Engine subclass has two major differences. Firstly all states are sprites (and there's a new vector with them
  63     cast to sprite). Secondly, it chops up images and states to fit a texture friendly format.
  64     Before the Sprite Engine starts running, its user requests a texture assembled from all the sprite images. This
  65     texture is made by pasting the sprites into one image, with one sprite animation per row (in the future it is planned to have
  66     arbitrary X/Y start ends, but they will still be assembled and recorded here and still have to be contiguous lines).
  67     This cut-up allows the users to calcuate frame positions with a texture percentage width and elapsed time.
  68     It also means that large sprites cover multiple lines to fit inside the texture memory limit (which is a square).
  69
  70     Large sprites covering multiple lines breaks this simple interface for the users, so each line is treated as a pseudostate
  71     and it's mostly hidden from the spriteengine users (except that they'll get advanced signals where the state is the same
  72     but the visual parameters changed). These are not real states because that would get very complex with bindings. Instead,
  73     when sprite attributes are requested from a sprite that has multiple pseudostates, it returns the values for the psuedostate
  74     it is in. State advancement is intercepted and hollow for pseudostates, except the last one. The last one transitions as the
  75     state normally does.
  76 */
  77
  78 static const int NINF = -1000000;//magic number for random start time - should be more negative than a single realistic animation duration
  79 /* TODO:
  80    make sharable?
  81    solve the state data initialization/transfer issue so as to not need to make friends
  82 */
  83
  84 QQuickStochasticEngine::QQuickStochasticEngine(QObject *parent) :
  85     QObject(parent), m_timeOffset(0), m_addAdvance(false)
  86 {
  87     //Default size 1
  88     setCount(1);
  89 }
  90
  91 QQuickStochasticEngine::QQuickStochasticEngine(QList<QQuickStochasticState*> states, QObject *parent) :
  92     QObject(parent), m_states(states), m_timeOffset(0), m_addAdvance(false)
  93 {
  94     //Default size 1
  95     setCount(1);
  96 }
  97
  98 QQuickStochasticEngine::~QQuickStochasticEngine()
  99 {
 100 }
 101
 102 QQuickSpriteEngine::QQuickSpriteEngine(QObject *parent)
 103     : QQuickStochasticEngine(parent)
 104 {
 105 }
 106
 107 QQuickSpriteEngine::QQuickSpriteEngine(QList<QQuickSprite*> sprites, QObject *parent)
 108     : QQuickStochasticEngine(parent)
 109 {
 110     foreach (QQuickSprite* sprite, sprites)
 111         m_states << (QQuickStochasticState*)sprite;
 112 }
 113
 114 QQuickSpriteEngine::~QQuickSpriteEngine()
 115 {
 116 }
 117
 118
 119 int QQuickSpriteEngine::maxFrames()
 120 {
 121     return m_maxFrames;
 122 }
 123
 124 /* States too large to fit in one row are split into multiple rows
 125    This is more efficient for the implementation, but should remain an implementation detail (invisible from QML)
 126    Therefore the below functions abstract sprite from the viewpoint of classes that pass the details onto shaders
 127    But States maintain their listed index for internal structures
 128 TODO: All these calculations should be pre-calculated and cached during initialization for a significant performance boost
 129 TODO: Above idea needs to have the varying duration offset added to it
 130 */
 131 //TODO: Should these be adding advanceTime as well? But only if advanceTime was added to your startTime...
 132 /*
 133     To get these working with duration=-1, m_startTimes will be messed with should duration=-1
 134     m_startTimes will be set in advance/restart to 0->(m_framesPerRow-1) and can be used directly as extra.
 135     This makes it 'frame' instead, but is more memory efficient than two arrays and less hideous than a vector of unions.
 136 */
 137 int QQuickSpriteEngine::pseudospriteProgress(int sprite, int state, int* rowDuration)
 138 {
 139     int myRowDuration = m_duration[sprite] * m_sprites[state]->m_framesPerRow / m_sprites[state]->m_frames;
 140     if (rowDuration)
 141         *rowDuration = myRowDuration;
 142
 143     if (m_sprites[state]->reverse()) //shift start-time back by the amount of time the first frame is smaller than rowDuration
 144         return (m_timeOffset - (m_startTimes[sprite] - (myRowDuration - (m_duration[sprite] % myRowDuration))) )
 145                     / myRowDuration;
 146     else
 147         return (m_timeOffset - m_startTimes[sprite]) / myRowDuration;
 148 }
 149
 150 int QQuickSpriteEngine::spriteState(int sprite)
 151 {
 152     int state = m_things[sprite];
 153     if (!m_sprites[state]->m_generatedCount)
 154         return state;
 155
 156     int extra;
 157     if (m_sprites[state]->frameSync())
 158         extra = m_startTimes[sprite];
 159     else if (!m_duration[sprite])
 160         return state;
 161     else
 162         extra = pseudospriteProgress(sprite, state);
 163     if (m_sprites[state]->reverse())
 164         extra = (m_sprites[state]->m_generatedCount - 1) - extra;
 165
 166     return state + extra;
 167 }
 168
 169 int QQuickSpriteEngine::spriteStart(int sprite)
 170 {
 171     if (!m_duration[sprite])
 172         return m_timeOffset;
 173     int state = m_things[sprite];
 174     if (!m_sprites[state]->m_generatedCount)
 175         return m_startTimes[sprite];
 176     int rowDuration;
 177     int extra = pseudospriteProgress(sprite, state, &rowDuration);
 178     if (m_sprites[state]->reverse())
 179         return m_startTimes[sprite] + (extra ? (extra - 1)*rowDuration + (m_duration[sprite] % rowDuration) : 0);
 180     return m_startTimes[sprite] + extra*rowDuration;
 181 }
 182
 183 int QQuickSpriteEngine::spriteFrames(int sprite)
 184 {
 185     int state = m_things[sprite];
 186     if (!m_sprites[state]->m_generatedCount)
 187         return m_sprites[state]->frames();
 188
 189     int extra;
 190     if (m_sprites[state]->frameSync())
 191         extra = m_startTimes[sprite];
 192     else if (!m_duration[sprite])
 193         return m_sprites[state]->frames();
 194     else
 195         extra = pseudospriteProgress(sprite, state);
 196     if (m_sprites[state]->reverse())
 197         extra = (m_sprites[state]->m_generatedCount - 1) - extra;
 198
 199
 200     if (extra == m_sprites[state]->m_generatedCount - 1)//last state
 201         return m_sprites[state]->frames() % m_sprites[state]->m_framesPerRow;
 202     else
 203         return m_sprites[state]->m_framesPerRow;
 204 }
 205
 206 int QQuickSpriteEngine::spriteDuration(int sprite)//Full duration, not per frame
 207 {
 208     if (!m_duration[sprite])
 209         return m_duration[sprite];
 210     int state = m_things[sprite];
 211     if (!m_sprites[state]->m_generatedCount)
 212         return m_duration[sprite];
 213     int rowDuration;
 214     int extra = pseudospriteProgress(sprite, state, &rowDuration);
 215     if (m_sprites[state]->reverse())
 216         extra = (m_sprites[state]->m_generatedCount - 1) - extra;
 217
 218     if (extra == m_sprites[state]->m_generatedCount - 1)//last state
 219         return m_duration[sprite] % rowDuration;
 220     else
 221         return rowDuration;
 222 }
 223
 224 int QQuickSpriteEngine::spriteY(int sprite)
 225 {
 226     int state = m_things[sprite];
 227     if (!m_sprites[state]->m_generatedCount)
 228         return m_sprites[state]->m_rowY;
 229
 230     int extra;
 231     if (m_sprites[state]->frameSync())
 232         extra = m_startTimes[sprite];
 233     else if (!m_duration[sprite])
 234         return m_sprites[state]->m_rowY;
 235     else
 236         extra = pseudospriteProgress(sprite, state);
 237     if (m_sprites[state]->reverse())
 238         extra = (m_sprites[state]->m_generatedCount - 1) - extra;
 239
 240
 241     return m_sprites[state]->m_rowY + m_sprites[state]->m_frameHeight * extra;
 242 }
 243
 244 int QQuickSpriteEngine::spriteX(int sprite)
 245 {
 246     int state = m_things[sprite];
 247     if (!m_sprites[state]->m_generatedCount)
 248         return m_sprites[state]->m_rowStartX;
 249
 250     int extra;
 251     if (m_sprites[state]->frameSync())
 252         extra = m_startTimes[sprite];
 253     else if (!m_duration[sprite])
 254         return m_sprites[state]->m_rowStartX;
 255     else
 256         extra = pseudospriteProgress(sprite, state);
 257     if (m_sprites[state]->reverse())
 258         extra = (m_sprites[state]->m_generatedCount - 1) - extra;
 259
 260     if (extra)
 261         return 0;
 262     return m_sprites[state]->m_rowStartX;
 263 }
 264
 265 QQuickSprite* QQuickSpriteEngine::sprite(int sprite)
 266 {
 267     return m_sprites[m_things[sprite]];
 268 }
 269
 270 int QQuickSpriteEngine::spriteWidth(int sprite)
 271 {
 272     int state = m_things[sprite];
 273     return m_sprites[state]->m_frameWidth;
 274 }
 275
 276 int QQuickSpriteEngine::spriteHeight(int sprite)
 277 {
 278     int state = m_things[sprite];
 279     return m_sprites[state]->m_frameHeight;
 280 }
 281
 282 int QQuickSpriteEngine::spriteCount()//TODO: Actually image state count, need to rename these things to make sense together
 283 {
 284     return m_imageStateCount;
 285 }
 286
 287 void QQuickStochasticEngine::setGoal(int state, int sprite, bool jump)
 288 {
 289     if (sprite >= m_things.count() || state >= m_states.count()
 290             || sprite < 0 || state < 0)
 291         return;
 292     if (!jump){
 293         m_goals[sprite] = state;
 294         return;
 295     }
 296
 297     if (m_things[sprite] == state)
 298         return;//Already there
 299     m_things[sprite] = state;
 300     m_duration[sprite] = m_states[state]->variedDuration();
 301     m_goals[sprite] = -1;
 302     restart(sprite);
 303     emit stateChanged(sprite);
 304     emit m_states[state]->entered();
 305     return;
 306 }
 307
 308 QImage QQuickSpriteEngine::assembledImage()
 309 {
 310     int h = 0;
 311     int w = 0;
 312     m_maxFrames = 0;
 313     m_imageStateCount = 0;
 314     int maxSize = 0;
 315
 316     glGetIntegerv(GL_MAX_TEXTURE_SIZE, &maxSize);
 317     //qDebug() << "MAX TEXTURE SIZE" << maxSize;
 318     foreach (QQuickStochasticState* s, m_states){
 319         QQuickSprite* sprite = qobject_cast<QQuickSprite*>(s);
 320         if (sprite)
 321             m_sprites << sprite;
 322         else
 323             qDebug() << "Error: Non-sprite in QQuickSpriteEngine";
 324     }
 325
 326     foreach (QQuickSprite* state, m_sprites){
 327         if (state->frames() > m_maxFrames)
 328             m_maxFrames = state->frames();
 329
 330         QImage img(state->source().toLocalFile());
 331         if (img.isNull()) {
 332             qWarning() << "SpriteEngine: loading image failed..." << state->source().toLocalFile();
 333             return QImage();
 334         }
 335
 336         //Check that the frame sizes are the same within one engine
 337         if (!state->m_frameWidth)
 338             state->m_frameWidth = img.width() / state->frames();
 339
 340         if (!state->m_frameHeight)
 341             state->m_frameHeight = img.height();
 342
 343         if (state->frames() * state->frameWidth() > maxSize){
 344             struct helper{
 345                 static int divRoundUp(int a, int b){return (a+b-1)/b;}
 346             };
 347             int rowsNeeded = helper::divRoundUp(state->frames(), (maxSize / state->frameWidth()));
 348             if (h + rowsNeeded * state->frameHeight() > maxSize){
 349                 if (rowsNeeded * state->frameHeight() > maxSize)
 350                     qWarning() << "SpriteEngine: Animation too large to fit in one texture:" << state->source().toLocalFile();
 351                 else
 352                     qWarning() << "SpriteEngine: Animations too large to fit in one texture, pushed over the edge by:" << state->source().toLocalFile();
 353                 qWarning() << "SpriteEngine: Your texture max size today is " << maxSize;
 354             }
 355             state->m_generatedCount = rowsNeeded;
 356             h += state->frameHeight() * rowsNeeded;
 357             w = qMax(w, ((int)(maxSize / state->frameWidth())) * state->frameWidth());
 358             m_imageStateCount += rowsNeeded;
 359         }else{
 360             h += state->frameHeight();
 361             w = qMax(w, state->frameWidth() * state->frames());
 362             m_imageStateCount++;
 363         }
 364     }
 365
 366     //maxFrames is max number in a line of the texture
 367     QImage image(w, h, QImage::Format_ARGB32);
 368     image.fill(0);
 369     QPainter p(&image);
 370     int y = 0;
 371     foreach (QQuickSprite* state, m_sprites){
 372         QImage img(state->source().toLocalFile());
 373         int frameWidth = state->m_frameWidth;
 374         int frameHeight = state->m_frameHeight;
 375         if (img.height() == frameHeight && img.width() <  maxSize){//Simple case
 376             p.drawImage(0,y,img);
 377             state->m_rowY = y;
 378             state->m_rowStartX = state->m_frameX;//In case it was offset, but we took the simple route of not chopping out the other bits
 379             y += frameHeight;
 380         }else{//Chopping up image case
 381             state->m_framesPerRow = image.width()/frameWidth;
 382             state->m_rowY = y;
 383             int x = 0;
 384             int curX = state->m_frameX;
 385             int curY = state->m_frameY;
 386             int framesLeft = state->frames();
 387             while (framesLeft > 0){
 388                 if (image.width() - x + curX <= img.width()){//finish a row in image (dest)
 389                     int copied = image.width() - x;
 390                     framesLeft -= copied/frameWidth;
 391                     p.drawImage(x,y,img.copy(curX,curY,copied,frameHeight));
 392                     y += frameHeight;
 393                     curX += copied;
 394                     x = 0;
 395                     if (curX == img.width()){
 396                         curX = 0;
 397                         curY += frameHeight;
 398                     }
 399                 }else{//finish a row in img (src)
 400                     int copied = img.width() - curX;
 401                     framesLeft -= copied/frameWidth;
 402                     p.drawImage(x,y,img.copy(curX,curY,copied,frameHeight));
 403                     curY += frameHeight;
 404                     x += copied;
 405                     curX = 0;
 406                 }
 407             }
 408             if (x)
 409                 y += frameHeight;
 410         }
 411     }
 412
 413     if (image.height() > maxSize){
 414         qWarning() << "SpriteEngine: Too many animations to fit in one texture...";
 415         qWarning() << "SpriteEngine: Your texture max size today is " << maxSize;
 416         return QImage();
 417     }
 418     return image;
 419 }
 420
 421 //TODO: Add a reset() function, for completeness in the case of a SpriteEngine being restarted from 0
 422 void QQuickStochasticEngine::setCount(int c)
 423 {
 424     m_things.resize(c);
 425     m_goals.resize(c);
 426     m_duration.resize(c);
 427     m_startTimes.resize(c);
 428 }
 429
 430 void QQuickStochasticEngine::start(int index, int state)
 431 {
 432     if (index >= m_things.count())
 433         return;
 434     m_things[index] = state;
 435     m_duration[index] = m_states[state]->variedDuration();
 436     if (m_states[state]->randomStart())
 437         m_startTimes[index] = NINF;
 438     else
 439         m_startTimes[index] = 0;
 440     m_goals[index] = -1;
 441     restart(index);
 442 }
 443
 444 void QQuickStochasticEngine::stop(int index)
 445 {
 446     if (index >= m_things.count())
 447         return;
 448     //Will never change until start is called again with a new state (or manually advanced) - this is not a 'pause'
 449     for (int i=0; i<m_stateUpdates.count(); i++)
 450         m_stateUpdates[i].second.removeAll(index);
 451 }
 452
 453 void QQuickStochasticEngine::restart(int index)
 454 {
 455     bool randomStart = (m_startTimes[index] == NINF);
 456     m_startTimes[index] = m_timeOffset;
 457     if (m_addAdvance)
 458         m_startTimes[index] += m_advanceTime.elapsed();
 459     if (randomStart)
 460         m_startTimes[index] -= qrand() % m_duration[index];
 461     int time = m_duration[index] + m_startTimes[index];
 462     for (int i=0; i<m_stateUpdates.count(); i++)
 463         m_stateUpdates[i].second.removeAll(index);
 464     if (m_duration[index] >= 0)
 465         addToUpdateList(time, index);
 466 }
 467
 468 void QQuickSpriteEngine::restart(int index) //Reimplemented to recognize and handle pseudostates
 469 {
 470     bool randomStart = (m_startTimes[index] == NINF);
 471     if (m_sprites[m_things[index]]->frameSync()) {//Manually advanced
 472         m_startTimes[index] = 0;
 473         if (randomStart && m_sprites[m_things[index]]->m_generatedCount)
 474             m_startTimes[index] += qrand() % m_sprites[m_things[index]]->m_generatedCount;
 475     } else {
 476         m_startTimes[index] = m_timeOffset;
 477         if (m_addAdvance)
 478             m_startTimes[index] += m_advanceTime.elapsed();
 479         if (randomStart)
 480             m_startTimes[index] -= qrand() % m_duration[index];
 481         int time = spriteDuration(index) + m_startTimes[index];
 482         if (randomStart) {
 483             int curTime = m_timeOffset + (m_addAdvance ? m_advanceTime.elapsed() : 0);
 484             while (time < curTime) //Fast forward through psuedostates as needed
 485                 time += spriteDuration(index);
 486         }
 487
 488         for (int i=0; i<m_stateUpdates.count(); i++)
 489             m_stateUpdates[i].second.removeAll(index);
 490         addToUpdateList(time, index);
 491     }
 492 }
 493
 494 void QQuickStochasticEngine::advance(int idx)
 495 {
 496     if (idx >= m_things.count())
 497         return;//TODO: Proper fix(because this has happened and I just ignored it)
 498     int nextIdx = nextState(m_things[idx],idx);
 499     m_things[idx] = nextIdx;
 500     m_duration[idx] = m_states[nextIdx]->variedDuration();
 501     restart(idx);
 502     emit m_states[nextIdx]->entered();
 503     emit stateChanged(idx);
 504 }
 505
 506 void QQuickSpriteEngine::advance(int idx) //Reimplemented to recognize and handle pseudostates
 507 {
 508     if (idx >= m_things.count())
 509         return;//TODO: Proper fix(because this has happened and I just ignored it)
 510     if (m_duration[idx] == 0) {
 511         if (m_sprites[m_things[idx]]->frameSync()) {
 512             //Manually called, advance inner substate count
 513             m_startTimes[idx]++;
 514             if (m_startTimes[idx] < m_sprites[m_things[idx]]->m_generatedCount) {
 515                 //only a pseudostate ended
 516                 emit stateChanged(idx);
 517                 return;
 518             }
 519         }
 520         //just go past the pseudostate logic
 521     } else if (m_startTimes[idx] + m_duration[idx]
 522             > int(m_timeOffset + (m_addAdvance ? m_advanceTime.elapsed() : 0))) {
 523         //only a pseduostate ended
 524         emit stateChanged(idx);
 525         addToUpdateList(spriteStart(idx) + spriteDuration(idx) + (m_addAdvance ? m_advanceTime.elapsed() : 0), idx);
 526         return;
 527     }
 528     int nextIdx = nextState(m_things[idx],idx);
 529     m_things[idx] = nextIdx;
 530     m_duration[idx] = m_states[nextIdx]->variedDuration();
 531     restart(idx);
 532     emit m_states[nextIdx]->entered();
 533     emit stateChanged(idx);
 534 }
 535
 536 int QQuickStochasticEngine::nextState(int curState, int curThing)
 537 {
 538     int nextIdx = -1;
 539     int goalPath = goalSeek(curState, curThing);
 540     if (goalPath == -1){//Random
 541         qreal r =(qreal) qrand() / (qreal) RAND_MAX;
 542         qreal total = 0.0;
 543         for (QVariantMap::const_iterator iter=m_states[curState]->m_to.constBegin();
 544             iter!=m_states[curState]->m_to.constEnd(); iter++)
 545             total += (*iter).toReal();
 546         r*=total;
 547         for (QVariantMap::const_iterator iter= m_states[curState]->m_to.constBegin();
 548                 iter!=m_states[curState]->m_to.constEnd(); iter++){
 549             if (r < (*iter).toReal()){
 550                 bool superBreak = false;
 551                 for (int i=0; i<m_states.count(); i++){
 552                     if (m_states[i]->name() == iter.key()){
 553                         nextIdx = i;
 554                         superBreak = true;
 555                         break;
 556                     }
 557                 }
 558                 if (superBreak)
 559                     break;
 560             }
 561             r -= (*iter).toReal();
 562         }
 563     }else{//Random out of shortest paths to goal
 564         nextIdx = goalPath;
 565     }
 566     if (nextIdx == -1)//No 'to' states means stay here
 567         nextIdx = curState;
 568     return nextIdx;
 569 }
 570
 571 uint QQuickStochasticEngine::updateSprites(uint time)//### would returning a list of changed idxs be faster than signals?
 572 {
 573     //Sprite State Update;
 574     m_timeOffset = time;
 575     m_addAdvance = false;
 576     while (!m_stateUpdates.isEmpty() && time >= m_stateUpdates.first().first){
 577         foreach (int idx, m_stateUpdates.first().second)
 578             advance(idx);
 579         m_stateUpdates.pop_front();
 580     }
 581
 582     m_advanceTime.start();
 583     m_addAdvance = true;
 584     if (m_stateUpdates.isEmpty())
 585         return -1;
 586     return m_stateUpdates.first().first;
 587 }
 588
 589 int QQuickStochasticEngine::goalSeek(int curIdx, int spriteIdx, int dist)
 590 {
 591     QString goalName;
 592     if (m_goals[spriteIdx] != -1)
 593         goalName = m_states[m_goals[spriteIdx]]->name();
 594     else
 595         goalName = m_globalGoal;
 596     if (goalName.isEmpty())
 597         return -1;
 598     //TODO: caching instead of excessively redoing iterative deepening (which was chosen arbitarily anyways)
 599     // Paraphrased - implement in an *efficient* manner
 600     for (int i=0; i<m_states.count(); i++)
 601         if (m_states[curIdx]->name() == goalName)
 602             return curIdx;
 603     if (dist < 0)
 604         dist = m_states.count();
 605     QQuickStochasticState* curState = m_states[curIdx];
 606     for (QVariantMap::const_iterator iter = curState->m_to.constBegin();
 607         iter!=curState->m_to.constEnd(); iter++){
 608         if (iter.key() == goalName)
 609             for (int i=0; i<m_states.count(); i++)
 610                 if (m_states[i]->name() == goalName)
 611                     return i;
 612     }
 613     QSet<int> options;
 614     for (int i=1; i<dist; i++){
 615         for (QVariantMap::const_iterator iter = curState->m_to.constBegin();
 616             iter!=curState->m_to.constEnd(); iter++){
 617             int option = -1;
 618             for (int j=0; j<m_states.count(); j++)//One place that could be a lot more efficient...
 619                 if (m_states[j]->name() == iter.key())
 620                     if (goalSeek(j, spriteIdx, i) != -1)
 621                         option = j;
 622             if (option != -1)
 623                 options << option;
 624         }
 625         if (!options.isEmpty()){
 626             if (options.count()==1)
 627                 return *(options.begin());
 628             int option = -1;
 629             qreal r =(qreal) qrand() / (qreal) RAND_MAX;
 630             qreal total = 0;
 631             for (QSet<int>::const_iterator iter=options.constBegin();
 632                 iter!=options.constEnd(); iter++)
 633                 total += curState->m_to.value(m_states[(*iter)]->name()).toReal();
 634             r *= total;
 635             for (QVariantMap::const_iterator iter = curState->m_to.constBegin();
 636                 iter!=curState->m_to.constEnd(); iter++){
 637                 bool superContinue = true;
 638                 for (int j=0; j<m_states.count(); j++)
 639                     if (m_states[j]->name() == iter.key())
 640                         if (options.contains(j))
 641                             superContinue = false;
 642                 if (superContinue)
 643                     continue;
 644                 if (r < (*iter).toReal()){
 645                     bool superBreak = false;
 646                     for (int j=0; j<m_states.count(); j++){
 647                         if (m_states[j]->name() == iter.key()){
 648                             option = j;
 649                             superBreak = true;
 650                             break;
 651                         }
 652                     }
 653                     if (superBreak)
 654                         break;
 655                 }
 656                 r-=(*iter).toReal();
 657             }
 658             return option;
 659         }
 660     }
 661     return -1;
 662 }
 663
 664 void QQuickStochasticEngine::addToUpdateList(uint t, int idx)
 665 {
 666     for (int i=0; i<m_stateUpdates.count(); i++){
 667         if (m_stateUpdates[i].first==t){
 668             m_stateUpdates[i].second << idx;
 669             return;
 670         }else if (m_stateUpdates[i].first > t){
 671             QList<int> tmpList;
 672             tmpList << idx;
 673             m_stateUpdates.insert(i, qMakePair(t, tmpList));
 674             return;
 675         }
 676     }
 677     QList<int> tmpList;
 678     tmpList << idx;
 679     m_stateUpdates << qMakePair(t, tmpList);
 680 }
 681
 682 QT_END_NAMESPACE