Annotation of brogue-ce/src/brogue/Grid.c, Revision 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