← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to tools/designer/src/designer/extra/fov.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/designer/src/designer/extra/fov.cpp
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 2005-2005 Trolltech AS. All rights reserved.
 
4
** Copyright (C) 2002-2005 Bj�rn Bergstr�m
 
5
**
 
6
** This file is part of the designer application of the Qt Toolkit.
 
7
**
 
8
** This file may be distributed under the terms of the Q Public License
 
9
** as defined by Trolltech AS of Norway and appearing in the file
 
10
** LICENSE.QPL included in the packaging of this file.
 
11
**
 
12
** This file may be distributed and/or modified under the terms of the
 
13
** GNU General Public License version 2 as published by the Free Software
 
14
** Foundation and appearing in the file LICENSE.GPL included in the
 
15
** packaging of this file.
 
16
**
 
17
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
18
**   information about Qt Commercial License Agreements.
 
19
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
20
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
21
**
 
22
** Contact info@trolltech.com if any conditions of this licensing are
 
23
** not clear to you.
 
24
**
 
25
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
26
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
27
**
 
28
****************************************************************************/
 
29
 
 
30
/*
 
31
 *
 
32
 * implementation of recursive shadowcasting
 
33
 *
 
34
 * 020125: Bj�rn Bergstr�m - changed from float to double to remove compiler
 
35
 *         warnings
 
36
 * 020125: Bj�rn Bergstr�m - included a check to avoid orthogonal edges to be
 
37
 *         scanned more than once
 
38
 * 020125: Greg McIntyre - declared the nwL, neL etc in FOV::start outside the
 
39
 *         for loops
 
40
 *
 
41
 */
 
42
 
 
43
#include "fov.h"
 
44
#include "oublietteplan.h"
 
45
#include <stdlib.h>
 
46
 
 
47
double FOV::slope(double x1, double y1, double x2, double y2)
 
48
{
 
49
        double xDiff=x1-x2;
 
50
        double yDiff=y1-y2;
 
51
 
 
52
        if(yDiff != 0)
 
53
        {
 
54
                return xDiff/yDiff;
 
55
        }
 
56
        else
 
57
        {
 
58
                return 0;
 
59
        }
 
60
}
 
61
 
 
62
double FOV::invSlope(double x1, double y1, double x2, double y2)
 
63
{
 
64
        double slope=this->slope(x1,y1,x2,y2);
 
65
 
 
66
        if(slope != 0)
 
67
        {
 
68
                return 1/slope;
 
69
        }
 
70
        else
 
71
        {
 
72
                return 0;
 
73
        }
 
74
}
 
75
 
 
76
 
 
77
/* scanNW2N
 
78
        scans the octant covering the area from north west to north from left to 
 
79
        right
 
80
        the method ignores the octants starting and ending cells since they have
 
81
        been applied in FOV::start
 
82
*/
 
83
void FOV::scanNW2N(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
84
{
 
85
        if(distance > maxRadius)
 
86
        {
 
87
                return;
 
88
        }
 
89
 
 
90
        // calculate start and end cell of the scan
 
91
        int xStart=(int)((double)xCenter + 0.5 - (startSlope * distance));
 
92
        int xEnd=(int)((double)xCenter + 0.5 - (endSlope * distance));
 
93
        int yCheck=yCenter - distance;
 
94
 
 
95
        // is the starting cell the leftmost cell in the octant?
 
96
        // NO: call applyCell() to starting cell 
 
97
        // YES: it has already been applied in FOV::start()
 
98
        if(xStart != xCenter-(1*distance))
 
99
        {
 
100
                this->applyCell(map,xStart,yCheck);
 
101
        }
 
102
 
 
103
        // find out if starting cell blocks LOS
 
104
        bool prevBlocked=this->scanCell(map,xStart,yCheck);
 
105
 
 
106
        // scan from the cell after the starting cell (xStart+1) to end cell of
 
107
        // scan (xCheck<=xEnd)
 
108
        for(int xCheck=xStart+1; xCheck<=xEnd; xCheck++)
 
109
        {
 
110
                // is the current cell the rightmost cell in the octant?
 
111
                // NO: call applyCell() to current cell 
 
112
                // YES: it has already been applied in FOV::start()
 
113
                if(xCheck != xCenter)
 
114
                {
 
115
                        // apply cell
 
116
                        this->applyCell(map,xCheck,yCheck);
 
117
                }
 
118
                
 
119
                // cell blocks LOS
 
120
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
121
                // hit a 'new' section of walls. a new scan will be started with an
 
122
                // endSlope that 'brushes' by to the left of the blocking cell
 
123
                //
 
124
                // +---+a####+---+  @ = [xCenter+0.5,yCenter+0.5]
 
125
                // |   |#####|   |  a = old [xCheck,yCheck]
 
126
                // |   |#####|   |  b = new [xCheck-0.00001,yCheck+0.99999]
 
127
                // |   |#####|   |
 
128
                // +---b#####+---+
 
129
                // +---++---++---+
 
130
                // |   ||   ||   |
 
131
                // |   ||   || @ |
 
132
                // |   ||   ||   |
 
133
                // +---++---++---+
 
134
                //
 
135
                if(this->scanCell(map,xCheck,yCheck))
 
136
                {
 
137
                        if(!prevBlocked)
 
138
                        {
 
139
                                this->scanNW2N(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck-0.000001,(double)yCheck+0.999999));
 
140
                        }
 
141
                        prevBlocked=true;
 
142
                }
 
143
 
 
144
                // cell doesn't block LOS
 
145
                // if the cell is the first non-blocking cell after a section of walls
 
146
                // we need to calculate a new startSlope that 'brushes' by to the right
 
147
                // of the blocking cells
 
148
                //
 
149
                // #####a---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
150
                // #####|   ||   |  a = new and old [xCheck,yCheck]
 
151
                // #####|   ||   |
 
152
                // #####|   ||   |
 
153
                // #####+---++---+
 
154
                // +---++---++---+
 
155
                // |   ||   ||   |
 
156
                // |   ||   || @ |
 
157
                // |   ||   ||   |
 
158
                // +---++---++---+
 
159
                //
 
160
                else
 
161
                {
 
162
                        if(prevBlocked)
 
163
                        {
 
164
                                startSlope=this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck);
 
165
                        }
 
166
                        prevBlocked=false;
 
167
                }
 
168
        }
 
169
 
 
170
        // if the last cell of the scan didn't block LOS a new scan should be
 
171
        // started
 
172
        if(!prevBlocked)
 
173
        {
 
174
                this->scanNW2N(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
175
        }
 
176
}
 
177
 
 
178
 
 
179
/* scanNE2N
 
180
        scans the octant covering the area from north east to north from right to 
 
181
        left
 
182
        the method ignores the octants starting and ending cells since they have
 
183
        been applied in FOV::start
 
184
*/
 
185
void FOV::scanNE2N(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
186
{
 
187
        if(distance > maxRadius)
 
188
        {
 
189
                return;
 
190
        }
 
191
 
 
192
        // calculate start and end cell of the scan
 
193
        int xStart=(int)((double)xCenter + 0.5 - (startSlope * distance));
 
194
        int xEnd=(int)((double)xCenter + 0.5 - (endSlope * distance));
 
195
        int yCheck=yCenter - distance;
 
196
 
 
197
        // is starting cell the rightmost cell in the octant?
 
198
        // NO: call applyCell() to starting cell 
 
199
        // YES: it has already been applied in FOV::start()
 
200
        if(xStart != xCenter-(-1*distance))
 
201
        {
 
202
                this->applyCell(map,xStart,yCheck);
 
203
        }
 
204
 
 
205
        // find out if starting cell blocks LOS
 
206
        bool prevBlocked=this->scanCell(map,xStart,yCheck);
 
207
 
 
208
        // scan from the cell after the starting cell (xStart-1) to end cell of
 
209
        // scan (xCheck>=xEnd)
 
210
        for(int xCheck=xStart-1; xCheck>=xEnd; xCheck--)
 
211
        {
 
212
                // is the current cell the leftmost cell in the octant?
 
213
                // NO: call applyCell() to current cell 
 
214
                // YES: it has already been applied in FOV::start()
 
215
                if(xCheck != xCenter)
 
216
                {
 
217
                        // apply cell
 
218
                        this->applyCell(map,xCheck,yCheck);
 
219
                }
 
220
                
 
221
                // cell blocks LOS
 
222
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
223
                // hit a 'new' section of walls. a new scan will be started with an
 
224
                // endSlope that 'brushes' by to the right of the blocking cell
 
225
                //
 
226
                // +---+a####+---+  @ = [xCenter+0.5,yCenter+0.5]
 
227
                // |   |#####|   |  a = old [xCheck,yCheck]
 
228
                // |   |#####|   |  b = new [xCheck+0.9999,yCheck-0.00001]
 
229
                // |   |#####|   |
 
230
                // +---+#####b---+
 
231
                // +---++---++---+
 
232
                // |   ||   ||   |
 
233
                // | @ ||   ||   |
 
234
                // |   ||   ||   |
 
235
                // +---++---++---+
 
236
                //
 
237
                if(this->scanCell(map,xCheck,yCheck))
 
238
                {
 
239
                        if(!prevBlocked)
 
240
                        {
 
241
                                this->scanNE2N(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+1,(double)yCheck+0.99999));
 
242
                        }
 
243
                        prevBlocked=true;
 
244
                }
 
245
 
 
246
                // cell doesn't block LOS
 
247
                // if the cell is the first non-blocking cell after a section of walls
 
248
                // we need to calculate a new startSlope that 'brushes' by to the left
 
249
                // of the blocking cells
 
250
                //
 
251
                // +---+a---b#####  @ = [xCenter+0.5,yCenter+0.5]
 
252
                // |   ||   |#####  a = old [xCheck,yCheck]
 
253
                // |   ||   |#####  b = new [xCheck+0.99999,yCheck]
 
254
                // |   ||   |#####
 
255
                // +---++---+#####
 
256
                // +---++---++---+
 
257
                // |   ||   ||   |
 
258
                // | @ ||   ||   |
 
259
                // |   ||   ||   |
 
260
                // +---++---++---+
 
261
                //
 
262
                else
 
263
                {
 
264
                        if(prevBlocked)
 
265
                        {
 
266
                                startSlope=this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.9999999,(double)yCheck);
 
267
                        }
 
268
                        prevBlocked=false;
 
269
                }
 
270
        }
 
271
 
 
272
        // if the last cell of the scan didn't block LOS a new scan should be
 
273
        // started
 
274
        if(!prevBlocked)
 
275
        {
 
276
                this->scanNE2N(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
277
        }
 
278
}
 
279
 
 
280
 
 
281
/* scanNW2W
 
282
        scans the octant covering the area from north west to west from top to 
 
283
        bottom
 
284
        the method ignores the octants starting and ending cells since they have
 
285
        been applied in FOV::start
 
286
*/
 
287
void FOV::scanNW2W(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
288
{
 
289
        if(distance > maxRadius)
 
290
        {
 
291
                return;
 
292
        }
 
293
 
 
294
        // calculate start and end cell of the scan
 
295
        int yStart=(int)((double)yCenter + 0.5 - (startSlope * distance));
 
296
        int yEnd=(int)((double)yCenter + 0.5 - (endSlope * distance));
 
297
        int xCheck=xCenter - distance;
 
298
 
 
299
        // is starting cell the topmost cell in the octant?
 
300
        // NO: call applyCell() to starting cell 
 
301
        // YES: it has already been applied in FOV::start()
 
302
        if(yStart != yCenter-(1*distance))
 
303
        {
 
304
                this->applyCell(map,xCheck,yStart);
 
305
        }
 
306
 
 
307
        // find out if starting cell blocks LOS
 
308
        bool prevBlocked=this->scanCell(map,xCheck,yStart);
 
309
 
 
310
        // scan from the cell after the starting cell (yStart+1) to end cell of
 
311
        // scan (yCheck<=yEnd)
 
312
        for(int yCheck=yStart+1; yCheck<=yEnd; yCheck++)
 
313
        {
 
314
                // is the current cell the bottommost cell in the octant?
 
315
                // NO: call applyCell() to current cell 
 
316
                // YES: it has already been applied in FOV::start()
 
317
                if(yCheck != yCenter)
 
318
                {
 
319
                        // apply cell
 
320
                        this->applyCell(map,xCheck,yCheck);
 
321
                }
 
322
                
 
323
                // cell blocks LOS
 
324
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
325
                // hit a 'new' section of walls. a new scan will be started with an
 
326
                // endSlope that 'brushes' by the top of the blocking cell (see fig.)
 
327
                //
 
328
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
329
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
330
                // |   ||   ||   |  b = new [xCheck+0.99999,yCheck-0.00001]
 
331
                // |   ||   ||   |
 
332
                // +---b+---++---+
 
333
                // a####+---++---+
 
334
                // #####|   ||   |
 
335
                // #####|   ||   |
 
336
                // #####|   ||   |
 
337
                // #####+---++---+
 
338
                // +---++---++---+
 
339
                // |   ||   ||   |
 
340
                // |   ||   || @ |
 
341
                // |   ||   ||   |
 
342
                // +---++---++---+
 
343
                //
 
344
                if(this->scanCell(map,xCheck,yCheck))
 
345
                {
 
346
                        if(!prevBlocked)
 
347
                        {
 
348
                                this->scanNW2W(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.99999,(double)yCheck-0.00001));
 
349
                        }
 
350
                        prevBlocked=true;
 
351
                }
 
352
 
 
353
                // cell doesn't block LOS
 
354
                // if the cell is the first non-blocking cell after a section of walls
 
355
                // we need to calculate a new startSlope that 'brushes' by the bottom
 
356
                // of the blocking cells
 
357
                //
 
358
                // #####+---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
359
                // #####|   ||   |  a = old and new [xCheck,yCheck]
 
360
                // #####|   ||   |
 
361
                // #####|   ||   |
 
362
                // #####+---++---+
 
363
                // a---++---++---+
 
364
                // |   ||   ||   |
 
365
                // |   ||   ||   |
 
366
                // |   ||   ||   |
 
367
                // +---++---++---+
 
368
                // +---++---++---+
 
369
                // |   ||   ||   |
 
370
                // |   ||   || @ |
 
371
                // |   ||   ||   |
 
372
                // +---++---++---+
 
373
                //
 
374
                else
 
375
                {
 
376
                        if(prevBlocked)
 
377
                        {
 
378
                                startSlope=this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck);
 
379
                        }
 
380
                        prevBlocked=false;
 
381
                }
 
382
        }
 
383
 
 
384
        // if the last cell of the scan didn't block LOS a new scan should be
 
385
        // started
 
386
        if(!prevBlocked)
 
387
        {
 
388
                this->scanNW2W(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
389
        }
 
390
}
 
391
 
 
392
/* scanSW2W
 
393
        scans the octant covering the area from southe west to west from bottom to 
 
394
        top
 
395
        the method ignores the octants starting and ending cells since they have
 
396
        been applied in FOV::start
 
397
*/
 
398
void FOV::scanSW2W(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
399
{
 
400
        if(distance > maxRadius)
 
401
        {
 
402
                return;
 
403
        }
 
404
 
 
405
        // calculate start and end cell of the scan
 
406
        int yStart=(int)((double)yCenter + 0.5 - (startSlope * distance));
 
407
        int yEnd=(int)((double)yCenter + 0.5 - (endSlope * distance));
 
408
        int xCheck=xCenter - distance;
 
409
 
 
410
        // is starting cell the bottommost cell in the octant?
 
411
        // NO: call applyCell() to starting cell 
 
412
        // YES: it has already been applied in FOV::start()
 
413
        if(yStart != yCenter-(-1*distance))
 
414
        {
 
415
                this->applyCell(map,xCheck,yStart);
 
416
        }
 
417
 
 
418
        // find out if starting cell blocks LOS
 
419
        bool prevBlocked=this->scanCell(map,xCheck,yStart);
 
420
 
 
421
        // scan from the cell after the starting cell (yStart-1) to end cell of
 
422
        // scan (yCheck>=yEnd)
 
423
        for(int yCheck=yStart-1; yCheck>=yEnd; yCheck--)
 
424
        {
 
425
                // is the current cell the topmost cell in the octant?
 
426
                // NO: call applyCell() to current cell 
 
427
                // YES: it has already been applied in FOV::start()
 
428
                if(yCheck != yCenter)
 
429
                {
 
430
                        // apply cell
 
431
                        this->applyCell(map,xCheck,yCheck);
 
432
                }
 
433
                
 
434
                // cell blocks LOS
 
435
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
436
                // hit a 'new' section of walls. a new scan will be started with an
 
437
                // endSlope that 'brushes' by the bottom of the blocking cell
 
438
                //
 
439
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
440
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
441
                // |   ||   || @ |  b = new [xCheck+0.99999,yCheck+1]
 
442
                // |   ||   ||   |
 
443
                // +---++---++---+
 
444
                // a####+---++---+
 
445
                // #####|   ||   |
 
446
                // #####|   ||   |
 
447
                // #####|   ||   |
 
448
                // #####+---++---+
 
449
                // +---b+---++---+
 
450
                // |   ||   ||   |
 
451
                // |   ||   ||   |
 
452
                // |   ||   ||   |
 
453
                // +---++---++---+
 
454
                //
 
455
                if(this->scanCell(map,xCheck,yCheck))
 
456
                {
 
457
                        if(!prevBlocked)
 
458
                        {
 
459
                                this->scanSW2W(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.99999,(double)yCheck+1));
 
460
                        }
 
461
                        prevBlocked=true;
 
462
                }
 
463
 
 
464
                // cell doesn't block LOS
 
465
                // if the cell is the first non-blocking cell after a section of walls
 
466
                // we need to calculate a new startSlope that 'brushes' by the top of
 
467
                // the blocking cells
 
468
                //
 
469
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
470
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
471
                // |   ||   || @ |  b = new [xCheck,yCheck+0.99999]
 
472
                // |   ||   ||   |
 
473
                // +---++---++---+
 
474
                // a---++---++---+
 
475
                // |   ||   ||   |
 
476
                // |   ||   ||   |
 
477
                // |   ||   ||   |
 
478
                // b---++---++---+
 
479
                // #####+---++---+
 
480
                // #####|   ||   |
 
481
                // #####|   ||   |
 
482
                // #####|   ||   |
 
483
                // #####+---++---+
 
484
                //
 
485
                else
 
486
                {
 
487
                        if(prevBlocked)
 
488
                        {
 
489
                                startSlope=this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck+0.99999);
 
490
                        }
 
491
                        prevBlocked=false;
 
492
                }
 
493
        }
 
494
 
 
495
        // if the last cell of the scan didn't block LOS a new scan should be
 
496
        // started
 
497
        if(!prevBlocked)
 
498
        {
 
499
                this->scanSW2W(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
500
        }
 
501
}
 
502
 
 
503
 
 
504
/* scanSW2S
 
505
        scans the octant covering the area from south west to south from left to 
 
506
        right
 
507
        the method ignores the octants starting and ending cells since they have
 
508
        been applied in FOV::start
 
509
*/
 
510
void FOV::scanSW2S(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
511
{
 
512
        if(distance > maxRadius)
 
513
        {
 
514
                return;
 
515
        }
 
516
 
 
517
        // calculate start and end cell of the scan
 
518
        int xStart=(int)((double)xCenter + 0.5 + (startSlope * distance));
 
519
        int xEnd=(int)((double)xCenter + 0.5 + (endSlope * distance));
 
520
        int yCheck=yCenter + distance;
 
521
 
 
522
        // is the starting cell the leftmost cell in the octant?
 
523
        // NO: call applyCell() to starting cell 
 
524
        // YES: it has already been applied in FOV::start()
 
525
        if(xStart != xCenter+(-1*distance))
 
526
        {
 
527
                this->applyCell(map,xStart,yCheck);
 
528
        }
 
529
 
 
530
        // find out if starting cell blocks LOS
 
531
        bool prevBlocked=this->scanCell(map,xStart,yCheck);
 
532
 
 
533
        // scan from the cell after the starting cell (xStart+1) to end cell of
 
534
        // scan (xCheck<=xEnd)
 
535
        for(int xCheck=xStart+1; xCheck<=xEnd; xCheck++)
 
536
        {
 
537
                // is the current cell the rightmost cell in the octant?
 
538
                // NO: call applyCell() to current cell 
 
539
                // YES: it has already been applied in FOV::start()
 
540
                if(xCheck != xCenter)
 
541
                {
 
542
                        // apply cell
 
543
                        this->applyCell(map,xCheck,yCheck);
 
544
                }
 
545
                
 
546
                // cell blocks LOS
 
547
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
548
                // hit a 'new' section of walls. a new scan will be started with an
 
549
                // endSlope that 'brushes' by to the left of the blocking cell
 
550
                //
 
551
                // +---++---++---+
 
552
                // |   ||   ||   |
 
553
                // |   ||   || @ |
 
554
                // |   ||   ||   |
 
555
                // +---++---++---+
 
556
                // +---ba####+---+  @ = [xCenter+0.5,yCenter+0.5]
 
557
                // |   |#####|   |  a = old [xCheck,yCheck]
 
558
                // |   |#####|   |  b = new [xCheck-0.00001,yCheck]
 
559
                // |   |#####|   |
 
560
                // +---+#####+---+
 
561
                //
 
562
                if(this->scanCell(map,xCheck,yCheck))
 
563
                {
 
564
                        if(!prevBlocked)
 
565
                        {
 
566
                                this->scanSW2S(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck-0.00001,(double)yCheck));
 
567
                        }
 
568
                        prevBlocked=true;
 
569
                }
 
570
 
 
571
                // cell doesn't block LOS
 
572
                // if the cell is the first non-blocking cell after a section of walls
 
573
                // we need to calculate a new startSlope that 'brushes' by to the right
 
574
                // of the blocking cells
 
575
                //
 
576
                // +---++---++---+
 
577
                // |   ||   ||   |
 
578
                // |   ||   || @ |
 
579
                // |   ||   ||   |
 
580
                // +---++---++---+
 
581
                // #####a---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
582
                // #####|   ||   |  a = old [xCheck,yCheck]
 
583
                // #####|   ||   |  b = new [xCheck,yCheck+0.99999]
 
584
                // #####|   ||   |
 
585
                // #####b---++---+
 
586
                //
 
587
                else
 
588
                {
 
589
                        if(prevBlocked)
 
590
                        {
 
591
                                startSlope=this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck+0.99999);
 
592
                        }
 
593
                        prevBlocked=false;
 
594
                }
 
595
        }
 
596
 
 
597
        // if the last cell of the scan didn't block LOS a new scan should be
 
598
        // started
 
599
        if(!prevBlocked)
 
600
        {
 
601
                this->scanSW2S(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
602
        }
 
603
}
 
604
 
 
605
 
 
606
/* scanSE2S
 
607
        scans the octant covering the area from south east to south from right to 
 
608
        left
 
609
        the method ignores the octants starting and ending cells since they have
 
610
        been applied in FOV::start
 
611
*/
 
612
void FOV::scanSE2S(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
613
{
 
614
        if(distance > maxRadius)
 
615
        {
 
616
                return;
 
617
        }
 
618
 
 
619
        // calculate start and end cell of the scan
 
620
        int xStart=(int)((double)xCenter + 0.5 + (startSlope * distance));
 
621
        int xEnd=(int)((double)xCenter + 0.5 + (endSlope * distance));
 
622
        int yCheck=yCenter + distance;
 
623
 
 
624
        // is starting cell the rightmost cell in the octant?
 
625
        // NO: call applyCell() to starting cell 
 
626
        // YES: it has already been applied in FOV::start()
 
627
        if(xStart != xCenter+(1*distance))
 
628
        {
 
629
                this->applyCell(map,xStart,yCheck);
 
630
        }
 
631
 
 
632
        // find out if starting cell blocks LOS
 
633
        bool prevBlocked=this->scanCell(map,xStart,yCheck);
 
634
 
 
635
        // scan from the cell after the starting cell (xStart-1) to end cell of
 
636
        // scan (xCheck>=xEnd)
 
637
        for(int xCheck=xStart-1; xCheck>=xEnd; xCheck--)
 
638
        {
 
639
                // is the current cell the leftmost cell in the octant?
 
640
                // NO: call applyCell() to current cell 
 
641
                // YES: it has already been applied in FOV::start()
 
642
                if(xCheck != xCenter)
 
643
                {
 
644
                        // apply cell
 
645
                        this->applyCell(map,xCheck,yCheck);
 
646
                }
 
647
                
 
648
                // cell blocks LOS
 
649
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
650
                // hit a 'new' section of walls. a new scan will be started with an
 
651
                // endSlope that 'brushes' by to the right of the blocking cell
 
652
                //
 
653
                // +---++---++---+
 
654
                // |   ||   ||   |
 
655
                // | @ ||   ||   |
 
656
                // |   ||   ||   |
 
657
                // +---++---++---+
 
658
                // +---+a####b---+  @ = [xCenter+0.5,yCenter+0.5]
 
659
                // |   |#####|   |  a = old [xCheck,yCheck]
 
660
                // |   |#####|   |  b = new [xCheck+1,yCheck]
 
661
                // |   |#####|   |
 
662
                // +---+#####+---+
 
663
                //
 
664
                if(this->scanCell(map,xCheck,yCheck))
 
665
                {
 
666
                        if(!prevBlocked)
 
667
                        {
 
668
                                this->scanSE2S(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+1,(double)yCheck));
 
669
                        }
 
670
                        prevBlocked=true;
 
671
                }
 
672
 
 
673
                // cell doesn't block LOS
 
674
                // if the cell is the first non-blocking cell after a section of walls
 
675
                // we need to calculate a new startSlope that 'brushes' by to the left
 
676
                // of the blocking cells
 
677
                //
 
678
                // +---++---++---+
 
679
                // |   ||   ||   |
 
680
                // | @ ||   ||   |
 
681
                // |   ||   ||   |
 
682
                // +---++---++---+
 
683
                // +---+a---+#####  @ = [xCenter+0.5,yCenter+0.5]
 
684
                // |   ||   |#####  a = old [xCheck,yCheck]
 
685
                // |   ||   |#####  b = new [xCheck+0.99999,yCheck+0.99999]
 
686
                // |   ||   |#####
 
687
                // +---++---b#####
 
688
                //
 
689
                else
 
690
                {
 
691
                        if(prevBlocked)
 
692
                        {
 
693
                                startSlope=this->slope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.99999,(double)yCheck+0.99999);
 
694
                        }
 
695
                        prevBlocked=false;
 
696
                }
 
697
        }
 
698
 
 
699
        // if the last cell of the scan didn't block LOS a new scan should be
 
700
        // started
 
701
        if(!prevBlocked)
 
702
        {
 
703
                this->scanSE2S(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
704
        }
 
705
}
 
706
 
 
707
 
 
708
/* scanNE2E
 
709
        scans the octant covering the area from north east to east from top to 
 
710
        bottom
 
711
        the method ignores the octants starting and ending cells since they have
 
712
        been applied in FOV::start
 
713
*/
 
714
void FOV::scanNE2E(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
715
{
 
716
        if(distance > maxRadius)
 
717
        {
 
718
                return;
 
719
        }
 
720
 
 
721
        // calculate start and end cell of the scan
 
722
        int yStart=(int)((double)yCenter + 0.5 + (startSlope * distance));
 
723
        int yEnd=(int)((double)yCenter + 0.5 + (endSlope * distance));
 
724
        int xCheck=xCenter + distance;
 
725
 
 
726
        // is starting cell the topmost cell in the octant?
 
727
        // NO: call applyCell() to starting cell 
 
728
        // YES: it has already been applied in FOV::start()
 
729
        if(yStart != yCenter+(-1*distance))
 
730
        {
 
731
                this->applyCell(map,xCheck,yStart);
 
732
        }
 
733
 
 
734
        // find out if starting cell blocks LOS
 
735
        bool prevBlocked=this->scanCell(map,xCheck,yStart);
 
736
 
 
737
        // scan from the cell after the starting cell (yStart+1) to end cell of
 
738
        // scan (yCheck<=yEnd)
 
739
        for(int yCheck=yStart+1; yCheck<=yEnd; yCheck++)
 
740
        {
 
741
                // is the current cell the bottommost cell in the octant?
 
742
                // NO: call applyCell() to current cell 
 
743
                // YES: it has already been applied in FOV::start()
 
744
                if(yCheck != yCenter)
 
745
                {
 
746
                        // apply cell
 
747
                        this->applyCell(map,xCheck,yCheck);
 
748
                }
 
749
                
 
750
                // cell blocks LOS
 
751
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
752
                // hit a 'new' section of walls. a new scan will be started with an
 
753
                // endSlope that 'brushes' by the top of the blocking cell (see fig.)
 
754
                //
 
755
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
756
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
757
                // |   ||   ||   |  b = new [xCheck,yCheck-0.00001]
 
758
                // |   ||   ||   |
 
759
                // +---++---+b---+
 
760
                // +---++---+a####
 
761
                // |   ||   |#####
 
762
                // |   ||   |#####
 
763
                // |   ||   |#####
 
764
                // +---++---+#####
 
765
                // +---++---++---+
 
766
                // |   ||   ||   |
 
767
                // | @ ||   ||   |
 
768
                // |   ||   ||   |
 
769
                // +---++---++---+
 
770
                //
 
771
                if(this->scanCell(map,xCheck,yCheck))
 
772
                {
 
773
                        if(!prevBlocked)
 
774
                        {
 
775
                                this->scanNE2E(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck-0.00001));
 
776
                        }
 
777
                        prevBlocked=true;
 
778
                }
 
779
 
 
780
                // cell doesn't block LOS
 
781
                // if the cell is the first non-blocking cell after a section of walls
 
782
                // we need to calculate a new startSlope that 'brushes' by the bottom
 
783
                // of the blocking cells
 
784
                //
 
785
                // +---++---+#####  @ = [xCenter+0.5,yCenter+0.5]
 
786
                // |   ||   |#####  a = old [xCheck,yCheck]
 
787
                // |   ||   |#####  b = new [xCheck+0.99999,yCheck]
 
788
                // |   ||   |#####
 
789
                // +---++---+#####
 
790
                // +---++---+a---b
 
791
                // |   ||   ||   |
 
792
                // |   ||   ||   |
 
793
                // |   ||   ||   |
 
794
                // +---++---++---+
 
795
                // +---++---++---+
 
796
                // |   ||   ||   |
 
797
                // | @ ||   ||   |
 
798
                // |   ||   ||   |
 
799
                // +---++---++---+
 
800
                //
 
801
                else
 
802
                {
 
803
                        if(prevBlocked)
 
804
                        {
 
805
                                startSlope=this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.99999,(double)yCheck);
 
806
                        }
 
807
                        prevBlocked=false;
 
808
                }
 
809
        }
 
810
 
 
811
        // if the last cell of the scan didn't block LOS a new scan should be
 
812
        // started
 
813
        if(!prevBlocked)
 
814
        {
 
815
                this->scanNE2E(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
816
        }
 
817
}
 
818
 
 
819
/* scanSE2E
 
820
        scans the octant covering the area from south east to east from bottom to 
 
821
        top
 
822
        the method ignores the octants starting and ending cells since they have
 
823
        been applied in FOV::start
 
824
*/
 
825
void FOV::scanSE2E(OublietteLevel *map, int xCenter, int yCenter, int distance, int maxRadius, double startSlope, double endSlope)
 
826
{
 
827
        if(distance > maxRadius)
 
828
        {
 
829
                return;
 
830
        }
 
831
 
 
832
        // calculate start and end cell of the scan
 
833
        int yStart=(int)((double)yCenter + 0.5 + (startSlope * distance));
 
834
        int yEnd=(int)((double)yCenter + 0.5 + (endSlope * distance));
 
835
        int xCheck=xCenter + distance;
 
836
 
 
837
        // is starting cell the bottommost cell in the octant?
 
838
        // NO: call applyCell() to starting cell 
 
839
        // YES: it has already been applied in FOV::start()
 
840
        if(yStart != yCenter+(1*distance))
 
841
        {
 
842
                this->applyCell(map,xCheck,yStart);
 
843
        }
 
844
 
 
845
        // find out if starting cell blocks LOS
 
846
        bool prevBlocked=this->scanCell(map,xCheck,yStart);
 
847
 
 
848
        // scan from the cell after the starting cell (yStart-1) to end cell of
 
849
        // scan (yCheck>=yEnd)
 
850
        for(int yCheck=yStart-1; yCheck>=yEnd; yCheck--)
 
851
        {
 
852
                // is the current cell the topmost cell in the octant?
 
853
                // NO: call applyCell() to current cell 
 
854
                // YES: it has already been applied in FOV::start()
 
855
                if(yCheck != yCenter)
 
856
                {
 
857
                        // apply cell
 
858
                        this->applyCell(map,xCheck,yCheck);
 
859
                }
 
860
                
 
861
                // cell blocks LOS
 
862
                // if previous cell didn't block LOS (prevBlocked==false) we have
 
863
                // hit a 'new' section of walls. a new scan will be started with an
 
864
                // endSlope that 'brushes' by the bottom of the blocking cell
 
865
                //
 
866
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
867
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
868
                // | @ ||   ||   |  b = new [xCheck,yCheck+1]
 
869
                // |   ||   ||   |
 
870
                // +---++---++---+
 
871
                // +---++---+a####
 
872
                // |   ||   |#####
 
873
                // |   ||   |#####
 
874
                // |   ||   |#####
 
875
                // +---++---+#####
 
876
                // +---++---+b---+
 
877
                // |   ||   ||   |
 
878
                // |   ||   ||   |
 
879
                // |   ||   ||   |
 
880
                // +---++---++---+
 
881
                //
 
882
                if(this->scanCell(map,xCheck,yCheck))
 
883
                {
 
884
                        if(!prevBlocked)
 
885
                        {
 
886
                                this->scanSE2E(map,xCenter,yCenter,distance+1,maxRadius,startSlope,this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck,(double)yCheck+1));
 
887
                        }
 
888
                        prevBlocked=true;
 
889
                }
 
890
 
 
891
                // cell doesn't block LOS
 
892
                // if the cell is the first non-blocking cell after a section of walls
 
893
                // we need to calculate a new startSlope that 'brushes' by the top of
 
894
                // the blocking cells
 
895
                //
 
896
                // +---++---++---+  @ = [xCenter+0.5,yCenter+0.5]
 
897
                // |   ||   ||   |  a = old [xCheck,yCheck]
 
898
                // | @ ||   ||   |  b = new [xCheck+0.99999,yCheck+0.99999]
 
899
                // |   ||   ||   |
 
900
                // +---++---++---+
 
901
                // +---++---+a---+
 
902
                // |   ||   ||   |
 
903
                // |   ||   ||   |
 
904
                // |   ||   ||   |
 
905
                // +---++---++---b
 
906
                // +---++---+#####
 
907
                // |   ||   |#####
 
908
                // |   ||   |#####
 
909
                // |   ||   |#####
 
910
                // +---++---+#####
 
911
                //
 
912
                else
 
913
                {
 
914
                        if(prevBlocked)
 
915
                        {
 
916
                                startSlope=this->invSlope((double)xCenter+0.5,(double)yCenter+0.5,(double)xCheck+0.99999,(double)yCheck+0.99999);
 
917
                        }
 
918
                        prevBlocked=false;
 
919
                }
 
920
        }
 
921
 
 
922
        // if the last cell of the scan didn't block LOS a new scan should be
 
923
        // started
 
924
        if(!prevBlocked)
 
925
        {
 
926
                this->scanSE2E(map,xCenter,yCenter,distance+1,maxRadius,startSlope,endSlope);
 
927
        }
 
928
}
 
929
 
 
930
 
 
931
void FOV::start(OublietteLevel *map, unsigned int x, unsigned int y, int maxRadius)
 
932
{
 
933
        if(map == NULL)
 
934
        {
 
935
                return;
 
936
        }
 
937
 
 
938
        // apply starting cell
 
939
        this->applyCell(map,x,y);
 
940
 
 
941
        if(maxRadius > 0)
 
942
        {
 
943
                // scan and apply north
 
944
                // until a blocking cell is hit or
 
945
                // until maxRadius is reached
 
946
                int nL;
 
947
                for(nL=1; nL<=maxRadius; nL++)
 
948
                {
 
949
                        this->applyCell(map,x,y-nL);
 
950
                        if(this->scanCell(map,x,y-nL))
 
951
                        {
 
952
                                break;
 
953
                        }
 
954
                }
 
955
 
 
956
                // scan and apply north east
 
957
                // until a blocking cell is hit or
 
958
                // until maxRadius is reached
 
959
                int neL;
 
960
                for(neL=1; neL<=maxRadius; neL++)
 
961
                {
 
962
                        this->applyCell(map,x+neL,y-neL);
 
963
                        if(this->scanCell(map,x+neL,y-neL))
 
964
                        {
 
965
                                break;
 
966
                        }
 
967
                }
 
968
 
 
969
                // scan and apply east
 
970
                // until a blocking cell is hit or
 
971
                // until maxRadius is reached
 
972
                int eL;
 
973
                for(eL=1; eL<=maxRadius; eL++)
 
974
                {
 
975
                        this->applyCell(map,x+eL,y);
 
976
                        if(this->scanCell(map,x+eL,y))
 
977
                        {
 
978
                                break;
 
979
                        }
 
980
                }
 
981
 
 
982
                // scan and apply south east
 
983
                // until a blocking cell is hit or
 
984
                // until maxRadius is reached
 
985
                int seL;
 
986
                for(seL=1; seL<=maxRadius; seL++)
 
987
                {
 
988
                        this->applyCell(map,x+seL,y+seL);
 
989
                        if(this->scanCell(map,x+seL,y+seL))
 
990
                        {
 
991
                                break;
 
992
                        }
 
993
                }
 
994
 
 
995
                // scan and apply south
 
996
                // until a blocking cell is hit or
 
997
                // until maxRadius is reached
 
998
                int sL;
 
999
                for(sL=1; sL<=maxRadius; sL++)
 
1000
                {
 
1001
                        this->applyCell(map,x,y+sL);
 
1002
                        if(this->scanCell(map,x,y+sL))
 
1003
                        {
 
1004
                                break;
 
1005
                        }
 
1006
                }
 
1007
 
 
1008
                // scan and apply south west
 
1009
                // until a blocking cell is hit or
 
1010
                // until maxRadius is reached
 
1011
                int swL;
 
1012
                for(swL=1; swL<=maxRadius; swL++)
 
1013
                {
 
1014
                        this->applyCell(map,x-swL,y+swL);
 
1015
                        if(this->scanCell(map,x-swL,y+swL))
 
1016
                        {
 
1017
                                break;
 
1018
                        }
 
1019
                }
 
1020
 
 
1021
                // scan and apply west
 
1022
                // until a blocking cell is hit or
 
1023
                // until maxRadius is reached
 
1024
                int wL;
 
1025
                for(wL=1; wL<=maxRadius; wL++)
 
1026
                {
 
1027
                        this->applyCell(map,x-wL,y);
 
1028
                        if(this->scanCell(map,x-wL,y))
 
1029
                        {
 
1030
                                break;
 
1031
                        }
 
1032
                }
 
1033
 
 
1034
                // scan and apply north west
 
1035
                // until a blocking cell is hit or
 
1036
                // until maxRadius is reached
 
1037
                int nwL;
 
1038
                for(nwL=1; nwL<=maxRadius; nwL++)
 
1039
                {
 
1040
                        this->applyCell(map,x-nwL,y-nwL);
 
1041
                        if(this->scanCell(map,x-nwL,y-nwL))
 
1042
                        {
 
1043
                                break;
 
1044
                        }
 
1045
                }
 
1046
 
 
1047
 
 
1048
                // scan the octant covering the area from north west to north
 
1049
                // if it isn't blocked
 
1050
                if(nL!=1 || nwL!=1)
 
1051
                {
 
1052
                        this->scanNW2N(map,x,y,1,maxRadius,1,0);
 
1053
                }
 
1054
 
 
1055
                // scan the octant covering the area from north east to north
 
1056
                // if it isn't blocked
 
1057
                if(nL!=1 || neL!=1)
 
1058
                {
 
1059
                        this->scanNE2N(map,x,y,1,maxRadius,-1,0);
 
1060
                }
 
1061
 
 
1062
                // scan the octant covering the area from north west to west
 
1063
                // if it isn't blocked
 
1064
                if(nwL!=1 || wL!=1)
 
1065
                {
 
1066
                        this->scanNW2W(map,x,y,1,maxRadius,1,0);
 
1067
                }
 
1068
 
 
1069
                // scan the octant covering the area from south west to west
 
1070
                // if it isn't blocked
 
1071
                if(swL!=1 || wL!=1)
 
1072
                {
 
1073
                        this->scanSW2W(map,x,y,1,maxRadius,-1,0);
 
1074
                }
 
1075
 
 
1076
                // scan the octant covering the area from south west to south
 
1077
                // if it isn't blocked
 
1078
                if(swL!=1 || sL!=1)
 
1079
                {
 
1080
                        this->scanSW2S(map,x,y,1,maxRadius,-1,0);
 
1081
                }
 
1082
 
 
1083
                // scan the octant covering the area from south east to south
 
1084
                // if it isn't blocked
 
1085
                if(seL!=1 || sL!=1)
 
1086
                {
 
1087
                        this->scanSE2S(map,x,y,1,maxRadius,1,0);
 
1088
                }
 
1089
 
 
1090
                // scan the octant covering the area from north east to east
 
1091
                // if it isn't blocked
 
1092
                if(neL!=1 || eL!=1)
 
1093
                {
 
1094
                        this->scanNE2E(map,x,y,1,maxRadius,-1,0);
 
1095
                }
 
1096
 
 
1097
                // scan the octant covering the area from south east to east
 
1098
                // if it isn't blocked
 
1099
                if(seL!=1 || eL!=1)
 
1100
                {
 
1101
                        this->scanSE2E(map,x,y,1,maxRadius,1,0);
 
1102
                }
 
1103
 
 
1104
        }
 
1105
}
 
1106
 
 
1107
bool SIMPLEFOV::scanCell(OublietteLevel *map, int x, int y)
 
1108
{
 
1109
        return map->blockLOS(x,y);
 
1110
}
 
1111
 
 
1112
void SIMPLEFOV::applyCell(OublietteLevel *map, int x, int y)
 
1113
{
 
1114
        map->updateTileFlags(QPoint(x, y), Tile::Explored);
 
1115
}