1/*******************************************************************
2 *
3 * Copyright 2006 Dmitry Suzdalev <dimsuz@gmail.com>
4 *
5 * This file is part of the KDE project "KLines"
6 *
7 * KLines is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2, or (at your option)
10 * any later version.
11 *
12 * KLines is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with KLines; see the file COPYING. If not, write to
19 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 * Boston, MA 02110-1301, USA.
21 *
22 ********************************************************************/
23#include "animator.h"
24#include "scene.h"
25#include "ballitem.h"
26#include "renderer.h"
27
28#include <kdebug.h>
29#include <math.h> // for pow, sqrt
30
31// Needed by A* pathfinding algorithm
32struct PathNode
33{
34 FieldPos pos;
35 PathNode *parent;
36 int G;
37 float H;
38 float F;
39 PathNode( const FieldPos& fpos, PathNode* p = 0, int g=0, int h=0 )
40 : pos(fpos), parent(p), G(g), H(h), F(g+h) { }
41};
42
43// helper function - used in findPath()
44// returns:
45// -1 - if position not found
46// index of node in list if position is found
47static inline int indexOfNodeWithPos( const FieldPos& pos, const QList<PathNode*>& list )
48{
49 for(int i=0;i<list.count(); ++i)
50 if( list.at(i)->pos == pos )
51 return i;
52
53 return -1;
54}
55
56KLinesAnimator::KLinesAnimator( KLinesScene* scene )
57 : m_scene(scene), m_movingBall(0)
58{
59 // timing & framing setup is done in corresponding animate* functions
60
61 connect(&m_moveTimeLine, SIGNAL(frameChanged(int)), SLOT(moveAnimationFrame(int)) );
62 connect(&m_moveTimeLine, SIGNAL(finished()), SIGNAL(moveFinished()));
63
64 m_removeTimeLine.setCurveShape(QTimeLine::LinearCurve);
65 connect(&m_removeTimeLine, SIGNAL(frameChanged(int)), SLOT(removeAnimationFrame(int)) );
66 connect(&m_removeTimeLine, SIGNAL(finished()), SIGNAL(removeFinished()));
67
68 m_bornTimeLine.setCurveShape(QTimeLine::LinearCurve);
69 connect(&m_bornTimeLine, SIGNAL(frameChanged(int)), SLOT(bornAnimationFrame(int)) );
70 connect(&m_bornTimeLine, SIGNAL(finished()), SLOT(slotBornFinished()));
71}
72
73bool KLinesAnimator::isAnimating() const
74{
75 return (m_bornTimeLine.state() == QTimeLine::Running
76 || m_moveTimeLine.state() == QTimeLine::Running
77 || m_removeTimeLine.state() == QTimeLine::Running);
78}
79
80bool KLinesAnimator::animateMove( const FieldPos& from, const FieldPos& to )
81{
82 findPath(from, to);
83
84 if(m_foundPath.isEmpty())
85 return false;
86
87 m_movingBall = m_scene->ballAt(from);
88 m_movingBall->stopAnimation();
89
90 int numPoints = m_foundPath.count();
91 // there will be numPoints-1 intervals of
92 // movement (interval=cell). We want each of them to take animDuration(MoveAnim) ms
93 m_moveTimeLine.setDuration((numPoints-1)*KLinesRenderer::animDuration(KLinesRenderer::MoveAnim));
94 // each interval will take cellSize frames
95 m_moveTimeLine.setFrameRange(0, (numPoints-1)*KLinesRenderer::cellSize());
96 m_moveTimeLine.setCurrentTime(0);
97 m_moveTimeLine.start();
98 return true;
99}
100
101void KLinesAnimator::animateRemove( const QList<BallItem*>& list )
102{
103 m_moveTimeLine.stop();
104 m_removeTimeLine.stop();
105
106 if(list.isEmpty())
107 {
108 emit removeFinished();
109 return;
110 }
111
112 m_removedBalls = list;
113
114 // called here (not in constructor), to stay in sync in case theme's reloaded
115 m_removeTimeLine.setDuration(KLinesRenderer::animDuration(KLinesRenderer::DieAnim));
116 // we setup here one 'empty' frame at the end, because without it
117 // m_scene will delete 'burned' items in removeAnimFinished() slot so quickly
118 // that last frame won't get shown in the scene
119 m_removeTimeLine.setFrameRange(0, KLinesRenderer::frameCount(KLinesRenderer::DieAnim));
120
121 m_removeTimeLine.start();
122}
123
124void KLinesAnimator::animateBorn( const QList<BallItem*>& list )
125{
126 m_bornBalls = list;
127 foreach(BallItem* ball, m_bornBalls)
128 ball->setRenderSize(KLinesRenderer::cellExtent());
129
130 // called here (not in constructor), to stay in sync in case theme's reloaded
131 m_bornTimeLine.setDuration(KLinesRenderer::animDuration(KLinesRenderer::BornAnim));
132 m_bornTimeLine.setFrameRange(0, KLinesRenderer::frameCount(KLinesRenderer::BornAnim)-1);
133
134 m_bornTimeLine.setCurrentTime( 0 );
135 m_bornTimeLine.start();
136}
137
138void KLinesAnimator::moveAnimationFrame(int frame)
139{
140 int cellSize = m_moveTimeLine.endFrame() / (m_foundPath.count()-1);
141 int intervalNum = frame/cellSize;
142
143 if(intervalNum == m_foundPath.count()-1)
144 {
145 m_movingBall->setPos(m_scene->fieldToPix(m_foundPath.last()));
146 return;
147 }
148 // determine direction of movement on this interval
149 int kx=0, ky=0;
150
151 FieldPos from = m_foundPath.at(intervalNum);
152 FieldPos to = m_foundPath.at(intervalNum+1);
153
154 if( to.x - from.x > 0 )
155 kx = 1;
156 else if( to.x - from.x < 0 )
157 kx = -1;
158 else
159 kx = 0;
160
161 if( to.y - from.y > 0 )
162 ky = 1;
163 else if( to.y - from.y < 0 )
164 ky = -1;
165 else
166 ky = 0;
167
168 int frameWithinInterval = frame%cellSize;
169 QPointF pos = m_scene->fieldToPix(from);
170 m_movingBall->setPos( pos.x()+kx*frameWithinInterval,
171 pos.y()+ky*frameWithinInterval );
172}
173
174void KLinesAnimator::removeAnimationFrame(int frame)
175{
176 if(frame == KLinesRenderer::frameCount(KLinesRenderer::DieAnim))
177 return;
178 foreach(BallItem* ball, m_removedBalls)
179 ball->setSpriteKey(KLinesRenderer::animationFrameId( KLinesRenderer::DieAnim,
180 ball->color(), frame) );
181}
182
183void KLinesAnimator::bornAnimationFrame(int frame)
184{
185 foreach(BallItem* ball, m_bornBalls)
186 ball->setSpriteKey( KLinesRenderer::animationFrameId( KLinesRenderer::BornAnim,
187 ball->color(), frame) );
188}
189
190void KLinesAnimator::findPath( const FieldPos& from, const FieldPos& to )
191{
192 // Implementation of A* pathfinding algorithm
193 // Thanks to Patrick Lester for excellent tutorial on gamedev.net.
194 // See http://www.gamedev.net/reference/articles/article2003.asp
195
196 QList<PathNode*> openList;
197 QList<PathNode*> closedList;
198
199 m_foundPath.clear();
200
201 openList.append( new PathNode(from) );
202
203 PathNode *curNode=0;
204 bool pathFound = false;
205 // see exit conditions at the end of while loop below
206 while(true)
207 {
208 // find the square with lowes F(=G+H) on the open list
209 PathNode *minF = openList.at(0);
210 for(int i=1; i<openList.count(); ++i)
211 if( openList.at(i)->F < minF->F )
212 minF = openList.at(i);
213
214 // move it to closed list
215 closedList.append(minF);
216 openList.removeAll(minF);
217
218 curNode = minF;
219
220 // for each of adjacent 4 squares (upper,lower, on the left and on the right)...
221 QList<FieldPos> adjacentSquares;
222 int x = curNode->pos.x;
223 int y = curNode->pos.y;
224 if( x != 0 ) adjacentSquares.append( FieldPos(x-1,y) );
225 if( y != 0 ) adjacentSquares.append( FieldPos(x,y-1) );
226 if( x != FIELD_SIZE-1 ) adjacentSquares.append( FieldPos(x+1,y) );
227 if( y != FIELD_SIZE-1 ) adjacentSquares.append( FieldPos(x,y+1) );
228
229 foreach( const FieldPos &pos, adjacentSquares )
230 {
231 if( m_scene->ballAt(pos) != 0 ) // skip non-walkable cells
232 continue;
233
234 // skip if closed list contains this square
235 if(indexOfNodeWithPos(pos, closedList) != -1)
236 continue;
237
238 // search for node with position 'pos' in openList
239 int idx = indexOfNodeWithPos(pos, openList);
240 if(idx == -1) // not found
241 {
242 PathNode *node = new PathNode( pos );
243 node->parent = curNode;
244 node->G = curNode->G + 10;
245 // h is manhattanLength from node to target square
246 node->H = sqrt( pow( (to.x - pos.x)*10, 2. ) + pow( (to.y - pos.y)*10, 2. ) );
247 node->F = node->G+node->H;
248 openList.append( node );
249 }
250 else
251 {
252 PathNode *node = openList.at(idx);
253 // check if this path to square is better
254 if( curNode->G + 10 < node->G )
255 {
256 // yup, it's better, reparent and recalculate G,F
257 node->parent = curNode;
258 node->G = curNode->G + 10;
259 node->F = node->G + node->H;
260 }
261 }
262 } // foreach
263
264 // exit conditions:
265 // a) if closeList contains "to"
266 // b) we can't find "to" in closedList and openlist is empty
267 // => no path exists
268 int idx = indexOfNodeWithPos(to, closedList);
269 if(idx != -1)
270 {
271 pathFound = true;
272 // let's save last node in curNode variable
273 curNode = closedList.at(idx);
274 break; // while
275 }
276 else if(openList.isEmpty())
277 {
278 pathFound = false;
279 break;
280 }
281 }
282
283 if(pathFound)
284 {
285 // restoring path starting from last node:
286 PathNode* node = curNode;
287 while(node)
288 {
289 m_foundPath.prepend( node->pos );
290 node = node->parent;
291 }
292 }
293
294 // cleanup
295 qDeleteAll( openList );
296 qDeleteAll( closedList );
297}
298
299void KLinesAnimator::startGameOverAnimation()
300{
301 blockSignals(true);
302 QList<BallItem*> balls;
303 QList<QGraphicsItem*> items = m_scene->items();
304 BallItem *ball=0;
305 foreach( QGraphicsItem* item, items )
306 {
307 ball = qgraphicsitem_cast<BallItem*>(item);
308 if(ball)
309 balls.append(ball);
310 }
311 animateRemove(balls);
312}
313
314void KLinesAnimator::stopGameOverAnimation()
315{
316 blockSignals(false);
317}
318
319void KLinesAnimator::slotBornFinished()
320{
321 foreach(BallItem* ball, m_bornBalls)
322 ball->setColor(ball->color(), true);
323 emit bornFinished();
324}
325
326#include "animator.moc"
327