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 |
32 | struct 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 |
47 | static 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 | |
56 | KLinesAnimator::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 | |
73 | bool 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 | |
80 | bool 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 | |
101 | void 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 | |
124 | void 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 | |
138 | void 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 | |
174 | void 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 | |
183 | void KLinesAnimator::bornAnimationFrame(int frame) |
184 | { |
185 | foreach(BallItem* ball, m_bornBalls) |
186 | ball->setSpriteKey( KLinesRenderer::animationFrameId( KLinesRenderer::BornAnim, |
187 | ball->color(), frame) ); |
188 | } |
189 | |
190 | void 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 | |
299 | void 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 | |
314 | void KLinesAnimator::stopGameOverAnimation() |
315 | { |
316 | blockSignals(false); |
317 | } |
318 | |
319 | void 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 | |