Annotation of brogue-ce/src/brogue/Grid.c, Revision 1.1.1.1
1.1 rubenllo 1: /*
2: * Grid
3: * Brogue
4: *
5: * Created by Brian Walker on 12/7/12.
6: * Copyright 2012. All rights reserved.
7: *
8: * This file is part of Brogue.
9: *
10: * This program is free software: you can redistribute it and/or modify
11: * it under the terms of the GNU Affero General Public License as
12: * published by the Free Software Foundation, either version 3 of the
13: * License, or (at your option) any later version.
14: *
15: * This program is distributed in the hope that it will be useful,
16: * but WITHOUT ANY WARRANTY; without even the implied warranty of
17: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18: * GNU Affero General Public License for more details.
19: *
20: * You should have received a copy of the GNU Affero General Public License
21: * along with this program. If not, see <http://www.gnu.org/licenses/>.
22: */
23:
24: #include "Rogue.h"
25: #include "IncludeGlobals.h"
26:
27:
28: // mallocing two-dimensional arrays! dun dun DUN!
29: short **allocGrid() {
30: short i;
31: short **array = malloc(DCOLS * sizeof(short *));
32:
33: array[0] = malloc(DROWS * DCOLS * sizeof(short));
34: for(i = 1; i < DCOLS; i++) {
35: array[i] = array[0] + i * DROWS;
36: }
37: return array;
38: }
39:
40: void freeGrid(short **array) {
41: free(array[0]);
42: free(array);
43: }
44:
45: void copyGrid(short **to, short **from) {
46: short i, j;
47:
48: for(i = 0; i < DCOLS; i++) {
49: for(j = 0; j < DROWS; j++) {
50: to[i][j] = from[i][j];
51: }
52: }
53: }
54:
55: void fillGrid(short **grid, short fillValue) {
56: short i, j;
57:
58: for(i = 0; i < DCOLS; i++) {
59: for(j = 0; j < DROWS; j++) {
60: grid[i][j] = fillValue;
61: }
62: }
63: }
64:
65: // Highlight the portion indicated by hiliteCharGrid with the hiliteColor at the hiliteStrength -- both latter arguments are optional.
66: void hiliteGrid(short **grid, color *hiliteColor, short hiliteStrength) {
67: short i, j, x, y;
68: color hCol;
69:
70: assureCosmeticRNG;
71:
72: if (hiliteColor) {
73: hCol = *hiliteColor;
74: } else {
75: hCol = yellow;
76: }
77:
78: bakeColor(&hCol);
79:
80: if (!hiliteStrength) {
81: hiliteStrength = 75;
82: }
83:
84: for (i=0; i<DCOLS; i++) {
85: for (j=0; j<DROWS; j++) {
86: if (grid[i][j]) {
87: x = mapToWindowX(i);
88: y = mapToWindowY(j);
89:
90: displayBuffer[x][y].needsUpdate = true;
91: displayBuffer[x][y].backColorComponents[0] = clamp(displayBuffer[x][y].backColorComponents[0] + hCol.red * hiliteStrength / 100, 0, 100);
92: displayBuffer[x][y].backColorComponents[1] = clamp(displayBuffer[x][y].backColorComponents[1] + hCol.green * hiliteStrength / 100, 0, 100);
93: displayBuffer[x][y].backColorComponents[2] = clamp(displayBuffer[x][y].backColorComponents[2] + hCol.blue * hiliteStrength / 100, 0, 100);
94: displayBuffer[x][y].foreColorComponents[0] = clamp(displayBuffer[x][y].foreColorComponents[0] + hCol.red * hiliteStrength / 100, 0, 100);
95: displayBuffer[x][y].foreColorComponents[1] = clamp(displayBuffer[x][y].foreColorComponents[1] + hCol.green * hiliteStrength / 100, 0, 100);
96: displayBuffer[x][y].foreColorComponents[2] = clamp(displayBuffer[x][y].foreColorComponents[2] + hCol.blue * hiliteStrength / 100, 0, 100);
97: }
98: }
99: }
100: restoreRNG;
101: }
102:
103: void findReplaceGrid(short **grid, short findValueMin, short findValueMax, short fillValue) {
104: short i, j;
105:
106: for(i = 0; i < DCOLS; i++) {
107: for(j = 0; j < DROWS; j++) {
108: if (grid[i][j] >= findValueMin && grid[i][j] <= findValueMax) {
109: grid[i][j] = fillValue;
110: }
111: }
112: }
113: }
114:
115: // Flood-fills the grid from (x, y) along cells that are within the eligible range.
116: // Returns the total count of filled cells.
117: short floodFillGrid(short **grid, short x, short y, short eligibleValueMin, short eligibleValueMax, short fillValue) {
118: enum directions dir;
119: short newX, newY, fillCount = 1;
120:
121: brogueAssert(fillValue < eligibleValueMin || fillValue > eligibleValueMax);
122:
123: grid[x][y] = fillValue;
124: for (dir = 0; dir < 4; dir++) {
125: newX = x + nbDirs[dir][0];
126: newY = y + nbDirs[dir][1];
127: if (coordinatesAreInMap(newX, newY)
128: && grid[newX][newY] >= eligibleValueMin
129: && grid[newX][newY] <= eligibleValueMax) {
130: fillCount += floodFillGrid(grid, newX, newY, eligibleValueMin, eligibleValueMax, fillValue);
131: }
132: }
133: return fillCount;
134: }
135:
136: void drawRectangleOnGrid(short **grid, short x, short y, short width, short height, short value) {
137: short i, j;
138:
139: for (i=x; i < x+width; i++) {
140: for (j=y; j<y+height; j++) {
141: grid[i][j] = value;
142: }
143: }
144: }
145:
146: void drawCircleOnGrid(short **grid, short x, short y, short radius, short value) {
147: short i, j;
148:
149: for (i=max(0, x - radius - 1); i < max(DCOLS, x + radius); i++) {
150: for (j=max(0, y - radius - 1); j < max(DROWS, y + radius); j++) {
151: if ((i-x)*(i-x) + (j-y)*(j-y) < radius * radius + radius) {
152: grid[i][j] = value;
153: }
154: }
155: }
156: }
157:
158: void intersectGrids(short **onto, short **from) {
159: short i, j;
160: for(i = 0; i < DCOLS; i++) {
161: for(j = 0; j < DROWS; j++) {
162: if (onto[i][j] && from[i][j]) {
163: onto[i][j] = true;
164: } else {
165: onto[i][j] = false;
166: }
167: }
168: }
169: }
170:
171: void uniteGrids(short **onto, short **from) {
172: short i, j;
173: for(i = 0; i < DCOLS; i++) {
174: for(j = 0; j < DROWS; j++) {
175: if (!onto[i][j] && from[i][j]) {
176: onto[i][j] = from[i][j];
177: }
178: }
179: }
180: }
181:
182: void invertGrid(short **grid) {
183: short i, j;
184: for(i = 0; i < DCOLS; i++) {
185: for(j = 0; j < DROWS; j++) {
186: grid[i][j] = !grid[i][j];
187: }
188: }
189: }
190:
191: // Fills grid locations with the given value if they match any terrain flags or map flags.
192: // Otherwise does not change the grid location.
193: void getTerrainGrid(short **grid, short value, unsigned long terrainFlags, unsigned long mapFlags) {
194: short i, j;
195: for(i = 0; i < DCOLS; i++) {
196: for(j = 0; j < DROWS; j++) {
197: if (grid[i][j] != value && cellHasTerrainFlag(i, j, terrainFlags) || (pmap[i][j].flags & mapFlags)) {
198: grid[i][j] = value;
199: }
200: }
201: }
202: }
203:
204: void getTMGrid(short **grid, short value, unsigned long TMflags) {
205: short i, j;
206: for(i = 0; i < DCOLS; i++) {
207: for(j = 0; j < DROWS; j++) {
208: if (grid[i][j] != value && cellHasTMFlag(i, j, TMflags)) {
209: grid[i][j] = value;
210: }
211: }
212: }
213: }
214:
215: void getPassableArcGrid(short **grid, short minPassableArc, short maxPassableArc, short value) {
216: short i, j, count;
217: for(i = 0; i < DCOLS; i++) {
218: for(j = 0; j < DROWS; j++) {
219: if (grid[i][j] != value) {
220: count = passableArcCount(i, j);
221: if (count >= minPassableArc && count <= maxPassableArc) {
222: grid[i][j] = value;
223: }
224: }
225: }
226: }
227: }
228:
229: short validLocationCount(short **grid, short validValue) {
230: short i, j, count;
231: count = 0;
232: for(i = 0; i < DCOLS; i++) {
233: for(j = 0; j < DROWS; j++) {
234: if (grid[i][j] == validValue) {
235: count++;
236: }
237: }
238: }
239: return count;
240: }
241:
242: short leastPositiveValueInGrid(short **grid) {
243: short i, j, leastPositiveValue = 0;
244: for(i = 0; i < DCOLS; i++) {
245: for(j = 0; j < DROWS; j++) {
246: if (grid[i][j] > 0 && (leastPositiveValue == 0 || grid[i][j] < leastPositiveValue)) {
247: leastPositiveValue = grid[i][j];
248: }
249: }
250: }
251: return leastPositiveValue;
252: }
253:
254: // Takes a grid as a mask of valid locations, chooses one randomly and returns it as (x, y).
255: // If there are no valid locations, returns (-1, -1).
256: void randomLocationInGrid(short **grid, short *x, short *y, short validValue) {
257: const short locationCount = validLocationCount(grid, validValue);
258: short i, j;
259:
260: if (locationCount <= 0) {
261: *x = *y = -1;
262: return;
263: }
264: short index = rand_range(0, locationCount - 1);
265: for(i = 0; i < DCOLS && index >= 0; i++) {
266: for(j = 0; j < DROWS && index >= 0; j++) {
267: if (grid[i][j] == validValue) {
268: if (index == 0) {
269: *x = i;
270: *y = j;
271: }
272: index--;
273: }
274: }
275: }
276: return;
277: }
278:
279: // Finds the lowest positive number in a grid, chooses one location with that number randomly and returns it as (x, y).
280: // If there are no valid locations, returns (-1, -1).
281: void randomLeastPositiveLocationInGrid(short **grid, short *x, short *y, boolean deterministic) {
282: const short targetValue = leastPositiveValueInGrid(grid);
283: short locationCount;
284: short i, j, index;
285:
286: if (targetValue == 0) {
287: *x = *y = -1;
288: return;
289: }
290:
291: locationCount = 0;
292: for(i = 0; i < DCOLS; i++) {
293: for(j = 0; j < DROWS; j++) {
294: if (grid[i][j] == targetValue) {
295: locationCount++;
296: }
297: }
298: }
299:
300: if (deterministic) {
301: index = locationCount / 2;
302: } else {
303: index = rand_range(0, locationCount - 1);
304: }
305:
306: for(i = 0; i < DCOLS && index >= 0; i++) {
307: for(j = 0; j < DROWS && index >= 0; j++) {
308: if (grid[i][j] == targetValue) {
309: if (index == 0) {
310: *x = i;
311: *y = j;
312: }
313: index--;
314: }
315: }
316: }
317: return;
318: }
319:
320: boolean getQualifyingPathLocNear(short *retValX, short *retValY,
321: short x, short y,
322: boolean hallwaysAllowed,
323: unsigned long blockingTerrainFlags,
324: unsigned long blockingMapFlags,
325: unsigned long forbiddenTerrainFlags,
326: unsigned long forbiddenMapFlags,
327: boolean deterministic) {
328: short **grid, **costMap;
329: short loc[2];
330:
331: // First check the given location to see if it works, as an optimization.
332: if (!cellHasTerrainFlag(x, y, blockingTerrainFlags | forbiddenTerrainFlags)
333: && !(pmap[x][y].flags & (blockingMapFlags | forbiddenMapFlags))
334: && (hallwaysAllowed || passableArcCount(x, y) <= 1)) {
335:
336: *retValX = x;
337: *retValY = y;
338: return true;
339: }
340:
341: // Allocate the grids.
342: grid = allocGrid();
343: costMap = allocGrid();
344:
345: // Start with a base of a high number everywhere.
346: fillGrid(grid, 30000);
347: fillGrid(costMap, 1);
348:
349: // Block off the pathing blockers.
350: getTerrainGrid(costMap, PDS_FORBIDDEN, blockingTerrainFlags, blockingMapFlags);
351: if (blockingTerrainFlags & (T_OBSTRUCTS_DIAGONAL_MOVEMENT | T_OBSTRUCTS_PASSABILITY)) {
352: getTerrainGrid(costMap, PDS_OBSTRUCTION, T_OBSTRUCTS_DIAGONAL_MOVEMENT, 0);
353: }
354:
355: // Run the distance scan.
356: grid[x][y] = 1;
357: costMap[x][y] = 1;
358: dijkstraScan(grid, costMap, true);
359: findReplaceGrid(grid, 30000, 30000, 0);
360:
361: // Block off invalid targets that aren't pathing blockers.
362: getTerrainGrid(grid, 0, forbiddenTerrainFlags, forbiddenMapFlags);
363: if (!hallwaysAllowed) {
364: getPassableArcGrid(grid, 2, 10, 0);
365: }
366:
367: // Get the solution.
368: randomLeastPositiveLocationInGrid(grid, retValX, retValY, deterministic);
369:
370: // dumpLevelToScreen();
371: // displayGrid(grid);
372: // if (coordinatesAreInMap(*retValX, *retValY)) {
373: // hiliteCell(*retValX, *retValY, &yellow, 100, true);
374: // }
375: // temporaryMessage("Qualifying path selected:", true);
376:
377: freeGrid(grid);
378: freeGrid(costMap);
379:
380: // Fall back to a pathing-agnostic alternative if there are no solutions.
381: if (*retValX == -1 && *retValY == -1) {
382: if (getQualifyingLocNear(loc, x, y, hallwaysAllowed, NULL,
383: (blockingTerrainFlags | forbiddenTerrainFlags),
384: (blockingMapFlags | forbiddenMapFlags),
385: false, deterministic)) {
386: *retValX = loc[0];
387: *retValY = loc[1];
388: return true; // Found a fallback solution.
389: } else {
390: return false; // No solutions.
391: }
392: } else {
393: return true; // Found a primary solution.
394: }
395: }
396:
397: void cellularAutomataRound(short **grid, char birthParameters[9], char survivalParameters[9]) {
398: short i, j, nbCount, newX, newY;
399: enum directions dir;
400: short **buffer2;
401:
402: buffer2 = allocGrid();
403: copyGrid(buffer2, grid); // Make a backup of grid in buffer2, so that each generation is isolated.
404:
405: for(i=0; i<DCOLS; i++) {
406: for(j=0; j<DROWS; j++) {
407: nbCount = 0;
408: for (dir=0; dir< DIRECTION_COUNT; dir++) {
409: newX = i + nbDirs[dir][0];
410: newY = j + nbDirs[dir][1];
411: if (coordinatesAreInMap(newX, newY)
412: && buffer2[newX][newY]) {
413:
414: nbCount++;
415: }
416: }
417: if (!buffer2[i][j] && birthParameters[nbCount] == 't') {
418: grid[i][j] = 1; // birth
419: } else if (buffer2[i][j] && survivalParameters[nbCount] == 't') {
420: // survival
421: } else {
422: grid[i][j] = 0; // death
423: }
424: }
425: }
426:
427: freeGrid(buffer2);
428: }
429:
430: // Marks a cell as being a member of blobNumber, then recursively iterates through the rest of the blob
431: short fillContiguousRegion(short **grid, short x, short y, short fillValue) {
432: enum directions dir;
433: short newX, newY, numberOfCells = 1;
434:
435: grid[x][y] = fillValue;
436:
437: // Iterate through the four cardinal neighbors.
438: for (dir=0; dir<4; dir++) {
439: newX = x + nbDirs[dir][0];
440: newY = y + nbDirs[dir][1];
441: if (!coordinatesAreInMap(newX, newY)) {
442: break;
443: }
444: if (grid[newX][newY] == 1) { // If the neighbor is an unmarked region cell,
445: numberOfCells += fillContiguousRegion(grid, newX, newY, fillValue); // then recurse.
446: }
447: }
448: return numberOfCells;
449: }
450:
451: // Loads up **grid with the results of a cellular automata simulation.
452: void createBlobOnGrid(short **grid,
453: short *retMinX, short *retMinY, short *retWidth, short *retHeight,
454: short roundCount,
455: short minBlobWidth, short minBlobHeight,
456: short maxBlobWidth, short maxBlobHeight, short percentSeeded,
457: char birthParameters[9], char survivalParameters[9]) {
458:
459: short i, j, k;
460: short blobNumber, blobSize, topBlobNumber, topBlobSize;
461:
462: short topBlobMinX, topBlobMinY, topBlobMaxX, topBlobMaxY, blobWidth, blobHeight;
463: //short buffer2[maxBlobWidth][maxBlobHeight]; // buffer[][] is already a global short array
464: boolean foundACellThisLine;
465:
466: // Generate blobs until they satisfy the minBlobWidth and minBlobHeight restraints
467: do {
468: // Clear buffer.
469: fillGrid(grid, 0);
470:
471: // Fill relevant portion with noise based on the percentSeeded argument.
472: for(i=0; i<maxBlobWidth; i++) {
473: for(j=0; j<maxBlobHeight; j++) {
474: grid[i][j] = (rand_percent(percentSeeded) ? 1 : 0);
475: }
476: }
477:
478: // colorOverDungeon(&darkGray);
479: // hiliteGrid(grid, &white, 100);
480: // temporaryMessage("Random starting noise:", true);
481:
482: // Some iterations of cellular automata
483: for (k=0; k<roundCount; k++) {
484: cellularAutomataRound(grid, birthParameters, survivalParameters);
485:
486: // colorOverDungeon(&darkGray);
487: // hiliteGrid(grid, &white, 100);
488: // temporaryMessage("Cellular automata progress:", true);
489: }
490:
491: // colorOverDungeon(&darkGray);
492: // hiliteGrid(grid, &white, 100);
493: // temporaryMessage("Cellular automata result:", true);
494:
495: // Now to measure the result. These are best-of variables; start them out at worst-case values.
496: topBlobSize = 0;
497: topBlobNumber = 0;
498: topBlobMinX = maxBlobWidth;
499: topBlobMaxX = 0;
500: topBlobMinY = maxBlobHeight;
501: topBlobMaxY = 0;
502:
503: // Fill each blob with its own number, starting with 2 (since 1 means floor), and keeping track of the biggest:
504: blobNumber = 2;
505:
506: for(i=0; i<DCOLS; i++) {
507: for(j=0; j<DROWS; j++) {
508: if (grid[i][j] == 1) { // an unmarked blob
509: // Mark all the cells and returns the total size:
510: blobSize = fillContiguousRegion(grid, i, j, blobNumber);
511: if (blobSize > topBlobSize) { // if this blob is a new record
512: topBlobSize = blobSize;
513: topBlobNumber = blobNumber;
514: }
515: blobNumber++;
516: }
517: }
518: }
519:
520: // Figure out the top blob's height and width:
521: // First find the max & min x:
522: for(i=0; i<DCOLS; i++) {
523: foundACellThisLine = false;
524: for(j=0; j<DROWS; j++) {
525: if (grid[i][j] == topBlobNumber) {
526: foundACellThisLine = true;
527: break;
528: }
529: }
530: if (foundACellThisLine) {
531: if (i < topBlobMinX) {
532: topBlobMinX = i;
533: }
534: if (i > topBlobMaxX) {
535: topBlobMaxX = i;
536: }
537: }
538: }
539:
540: // Then the max & min y:
541: for(j=0; j<DROWS; j++) {
542: foundACellThisLine = false;
543: for(i=0; i<DCOLS; i++) {
544: if (grid[i][j] == topBlobNumber) {
545: foundACellThisLine = true;
546: break;
547: }
548: }
549: if (foundACellThisLine) {
550: if (j < topBlobMinY) {
551: topBlobMinY = j;
552: }
553: if (j > topBlobMaxY) {
554: topBlobMaxY = j;
555: }
556: }
557: }
558:
559: blobWidth = (topBlobMaxX - topBlobMinX) + 1;
560: blobHeight = (topBlobMaxY - topBlobMinY) + 1;
561:
562: } while (blobWidth < minBlobWidth
563: || blobHeight < minBlobHeight
564: || topBlobNumber == 0);
565:
566: // Replace the winning blob with 1's, and everything else with 0's:
567: for(i=0; i<DCOLS; i++) {
568: for(j=0; j<DROWS; j++) {
569: if (grid[i][j] == topBlobNumber) {
570: grid[i][j] = 1;
571: } else {
572: grid[i][j] = 0;
573: }
574: }
575: }
576:
577: // Populate the returned variables.
578: *retMinX = topBlobMinX;
579: *retMinY = topBlobMinY;
580: *retWidth = blobWidth;
581: *retHeight = blobHeight;
582: }
CVSweb
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to Grid.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [contributed] / brogue-ce / src / brogue