1 //
2 // nazghul - an old-school RPG engine
3 // Copyright (C) 2002, 2003 Gordon McNutt
4 //
5 // This program is free software; you can redistribute it and/or modify it
6 // under the terms of the GNU General Public License as published by the Free
7 // Software Foundation; either version 2 of the License, or (at your option)
8 // any later version.
9 //
10 // This program is distributed in the hope that it will be useful, but WITHOUT
11 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 // more details.
14 //
15 // You should have received a copy of the GNU General Public License along with
16 // this program; if not, write to the Free Foundation, Inc., 59 Temple Place,
17 // Suite 330, Boston, MA 02111-1307 USA
18 //
19 // Gordon McNutt
20 // gmcnutt@users.sourceforge.net
21 //
22 #include "los.h"
23
24 #include <string.h>
25
FLOODFILL_destroy(struct los * los)26 static void FLOODFILL_destroy(struct los *los)
27 {
28 }
29
floodfillCheckDistance(struct los * los,int mx,int my)30 static int floodfillCheckDistance(struct los *los, int mx, int my)
31 {
32 int d;
33 int x;
34 int y;
35
36 /* Limit LOS to the radius if given (creating a circle of visibility
37 * centered on the player). Otherwise limit it to the view dimensions
38 * (making the entire map window potentially visible). */
39 if (los->r <= 0)
40 return (!(mx < 0 || mx >= los->w || my < 0 || my >= los->h));
41
42 /* Convert coordinates to a system where the origin is in the center of
43 * the los area */
44 x = mx - los->w / 2;
45 y = my - los->h / 2;
46
47 /* And force coordinates to absolute values so we can use the simple
48 * distance formula */
49 x = (x < 0 ? -x : x);
50 y = (y < 0 ? -y : y);
51
52 /* Use a quick-and-dirty distance formula (stolen from angband los
53 * algorithm) */
54 d = ((y > x) ? (y + x / 2) : (x + y / 2));
55
56 return (d <= los->r);
57 }
58
FLOODFILL_computeRecursive(struct los * los,int vx,int vy,int mx,int my)59 static void FLOODFILL_computeRecursive(struct los *los, int vx, int vy,
60 int mx, int my)
61 {
62 int vindex;
63 int mindex;
64 int vnx;
65 int vny;
66 int mnx;
67 int mny;
68
69 /* If these are not valid viewing coordinates then return. This happens
70 * when we hit the edges of the los area. */
71 if (vx < 0 || vx >= los->w || vy < 0 || vy >= los->h)
72 return;
73
74 vindex = vy * los->w + vx;
75 mindex = my * los->w + mx;
76
77 /* If this tile has already been visited then return */
78 if (los->vmask[vindex] != 'u')
79 return;
80
81 /* If this tile is outside of the radius then return */
82 if (!floodfillCheckDistance(los, mx, my))
83 return;
84
85 /* Mark this tile as visible. */
86 los->vmask[vindex] = 1;
87
88 /* If this tile is opaque and not the tile the player is standing on
89 * then return. */
90 if (!los->alpha[mindex] && ((vx != los->w / 2) || (vy != los->h / 2)))
91 return;
92
93 /* revisit -- consider skipping diagonal neighbors */
94 /* revisit -- we could skip some neighbors if we knew which direction
95 * our parent was. We could also precheck neighbors before recurring,
96 * saving us some function call overhead */
97 /* For each of the eight neighboring tiles, call the recursive
98 * floodfill function */
99 for (vny = vy - 1, mny = my - 1; vny <= vy + 1; vny++, mny++) {
100 for (vnx = vx - 1, mnx = mx - 1; vnx <= vx + 1; vnx++, mnx++) {
101 FLOODFILL_computeRecursive(los, vnx, vny, mnx, mny);
102 }
103 }
104
105 }
106
FLOODFILL_compute(struct los * los)107 static void FLOODFILL_compute(struct los *los)
108 {
109 int i;
110 int len;
111
112 len = los->w * los->h * sizeof(unsigned char);
113
114 /* Fill the mask with the 'unvisited' flag */
115 memset(los->vmask, 'u', len);
116
117 /* Start the recursion with the center tile */
118 FLOODFILL_computeRecursive(los, los->w / 2, los->h / 2,
119 los->w / 2, los->h / 2);
120
121 /* Replace all 'unvisited' and 'visited' flags with 'nonvisible' */
122 for (i = 0; i < len; i++) {
123 switch (los->vmask[i]) {
124 case 0:
125 case 1:
126 break;
127 default:
128 los->vmask[i] = 0;
129 }
130 }
131
132 }
133
FLOODFILL_Init(struct los * los)134 struct los *FLOODFILL_Init(struct los *los)
135 {
136 los->destroy = FLOODFILL_destroy;
137 los->compute = FLOODFILL_compute;
138 return 0;
139 }
140