Grid.c

/*
 *  Grid
 *  Brogue
 *
 *  Created by Brian Walker on 12/7/12.
 *  Copyright 2012. All rights reserved.
 *
 *  This file is part of Brogue.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "Rogue.h"
#include "IncludeGlobals.h"


// mallocing two-dimensional arrays! dun dun DUN!
short **allocGrid() {
	short i;
	short **array = malloc(DCOLS * sizeof(short *));
    
	array[0] = malloc(DROWS * DCOLS * sizeof(short));
	for(i = 1; i < DCOLS; i++) {
		array[i] = array[0] + i * DROWS;
	}
	return array;
}

void freeGrid(short **array) {
	free(array[0]);
	free(array);
}

void copyGrid(short **to, short **from) {
	short i, j;
	
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void fillGrid(short **grid, short fillValue) {
	short i, j;
	
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
			grid[i][j] = fillValue;
		}
	}
}

// Highlight the portion indicated by hiliteCharGrid with the hiliteColor at the hiliteStrength -- both latter arguments are optional.
void hiliteGrid(short **grid, color *hiliteColor, short hiliteStrength) {
	short i, j, x, y;
	color hCol;
	
	assureCosmeticRNG;
	
	if (hiliteColor) {
		hCol = *hiliteColor;
	} else {
		hCol = yellow;
	}
	
	bakeColor(&hCol);
	
	if (!hiliteStrength) {
		hiliteStrength = 75;
	}
	
	for (i=0; i<DCOLS; i++) {
		for (j=0; j<DROWS; j++) {
			if (grid[i][j]) {
				x = mapToWindowX(i);
				y = mapToWindowY(j);
				
				displayBuffer[x][y].needsUpdate = true;
				displayBuffer[x][y].backColorComponents[0] = clamp(displayBuffer[x][y].backColorComponents[0] + hCol.red * hiliteStrength / 100, 0, 100);
				displayBuffer[x][y].backColorComponents[1] = clamp(displayBuffer[x][y].backColorComponents[1] + hCol.green * hiliteStrength / 100, 0, 100);
				displayBuffer[x][y].backColorComponents[2] = clamp(displayBuffer[x][y].backColorComponents[2] + hCol.blue * hiliteStrength / 100, 0, 100);
				displayBuffer[x][y].foreColorComponents[0] = clamp(displayBuffer[x][y].foreColorComponents[0] + hCol.red * hiliteStrength / 100, 0, 100);
				displayBuffer[x][y].foreColorComponents[1] = clamp(displayBuffer[x][y].foreColorComponents[1] + hCol.green * hiliteStrength / 100, 0, 100);
				displayBuffer[x][y].foreColorComponents[2] = clamp(displayBuffer[x][y].foreColorComponents[2] + hCol.blue * hiliteStrength / 100, 0, 100);
			}
		}
	}
	restoreRNG;
}

void findReplaceGrid(short **grid, short findValueMin, short findValueMax, short fillValue) {
	short i, j;
	
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] >= findValueMin && grid[i][j] <= findValueMax) {
                grid[i][j] = fillValue;
            }
		}
	}
}

// Flood-fills the grid from (x, y) along cells that are within the eligible range.
// Returns the total count of filled cells.
short floodFillGrid(short **grid, short x, short y, short eligibleValueMin, short eligibleValueMax, short fillValue) {
    enum directions dir;
	short newX, newY, fillCount = 1;
    
    brogueAssert(fillValue < eligibleValueMin || fillValue > eligibleValueMax);
    
    grid[x][y] = fillValue;
    for (dir = 0; dir < 4; dir++) {
        newX = x + nbDirs[dir][0];
        newY = y + nbDirs[dir][1];
        if (coordinatesAreInMap(newX, newY)
            && grid[newX][newY] >= eligibleValueMin
            && grid[newX][newY] <= eligibleValueMax) {
            fillCount += floodFillGrid(grid, newX, newY, eligibleValueMin, eligibleValueMax, fillValue);
        }
    }
    return fillCount;
}

void drawRectangleOnGrid(short **grid, short x, short y, short width, short height, short value) {
    short i, j;
    
    for (i=x; i < x+width; i++) {
        for (j=y; j<y+height; j++) {
            grid[i][j] = value;
        }
    }
}

void drawCircleOnGrid(short **grid, short x, short y, short radius, short value) {
    short i, j;
    
    for (i=max(0, x - radius - 1); i < max(DCOLS, x + radius); i++) {
        for (j=max(0, y - radius - 1); j < max(DROWS, y + radius); j++) {
            if ((i-x)*(i-x) + (j-y)*(j-y) < radius * radius + radius) {
                grid[i][j] = value;
            }
        }
    }
}

void intersectGrids(short **onto, short **from) {
    short i, j;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (onto[i][j] && from[i][j]) {
                onto[i][j] = true;
            } else {
                onto[i][j] = false;
            }
        }
    }
}

void uniteGrids(short **onto, short **from) {
    short i, j;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (!onto[i][j] && from[i][j]) {
                onto[i][j] = from[i][j];
            }
        }
    }
}

void invertGrid(short **grid) {
    short i, j;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            grid[i][j] = !grid[i][j];
        }
    }
}

// Fills grid locations with the given value if they match any terrain flags or map flags.
// Otherwise does not change the grid location.
void getTerrainGrid(short **grid, short value, unsigned long terrainFlags, unsigned long mapFlags) {
    short i, j;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] != value && cellHasTerrainFlag(i, j, terrainFlags) || (pmap[i][j].flags & mapFlags)) {
                grid[i][j] = value;
            }
        }
    }
}

void getTMGrid(short **grid, short value, unsigned long TMflags) {
    short i, j;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] != value && cellHasTMFlag(i, j, TMflags)) {
                grid[i][j] = value;
            }
        }
    }
}

void getPassableArcGrid(short **grid, short minPassableArc, short maxPassableArc, short value) {
    short i, j, count;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] != value) {
                count = passableArcCount(i, j);
                if (count >= minPassableArc && count <= maxPassableArc) {
                    grid[i][j] = value;
                }
            }
        }
    }
}

short validLocationCount(short **grid, short validValue) {
    short i, j, count;
    count = 0;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] == validValue) {
                count++;
            }
        }
    }
    return count;
}

short leastPositiveValueInGrid(short **grid) {
    short i, j, leastPositiveValue = 0;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] > 0 && (leastPositiveValue == 0 || grid[i][j] < leastPositiveValue)) {
                leastPositiveValue = grid[i][j];
            }
        }
    }
    return leastPositiveValue;
}

// Takes a grid as a mask of valid locations, chooses one randomly and returns it as (x, y).
// If there are no valid locations, returns (-1, -1).
void randomLocationInGrid(short **grid, short *x, short *y, short validValue) {
    const short locationCount = validLocationCount(grid, validValue);
    short i, j;
    
    if (locationCount <= 0) {
        *x = *y = -1;
        return;
    }
    short index = rand_range(0, locationCount - 1);
	for(i = 0; i < DCOLS && index >= 0; i++) {
		for(j = 0; j < DROWS && index >= 0; j++) {
            if (grid[i][j] == validValue) {
                if (index == 0) {
                    *x = i;
                    *y = j;
                }
                index--;
            }
        }
    }
    return;
}

// Finds the lowest positive number in a grid, chooses one location with that number randomly and returns it as (x, y).
// If there are no valid locations, returns (-1, -1).
void randomLeastPositiveLocationInGrid(short **grid, short *x, short *y, boolean deterministic) {
    const short targetValue = leastPositiveValueInGrid(grid);
    short locationCount;
    short i, j, index;
    
    if (targetValue == 0) {
        *x = *y = -1;
        return;
    }
    
    locationCount = 0;
	for(i = 0; i < DCOLS; i++) {
		for(j = 0; j < DROWS; j++) {
            if (grid[i][j] == targetValue) {
                locationCount++;
            }
        }
    }
    
    if (deterministic) {
        index = locationCount / 2;
    } else {
        index = rand_range(0, locationCount - 1);
    }
    
	for(i = 0; i < DCOLS && index >= 0; i++) {
		for(j = 0; j < DROWS && index >= 0; j++) {
            if (grid[i][j] == targetValue) {
                if (index == 0) {
                    *x = i;
                    *y = j;
                }
                index--;
            }
        }
    }
    return;
}

boolean getQualifyingPathLocNear(short *retValX, short *retValY,
                                 short x, short y,
                                 boolean hallwaysAllowed,
                                 unsigned long blockingTerrainFlags,
                                 unsigned long blockingMapFlags,
                                 unsigned long forbiddenTerrainFlags,
                                 unsigned long forbiddenMapFlags,
                                 boolean deterministic) {
    short **grid, **costMap;
    short loc[2];
    
    // First check the given location to see if it works, as an optimization.
    if (!cellHasTerrainFlag(x, y, blockingTerrainFlags | forbiddenTerrainFlags)
        && !(pmap[x][y].flags & (blockingMapFlags | forbiddenMapFlags))
        && (hallwaysAllowed || passableArcCount(x, y) <= 1)) {
        
        *retValX = x;
        *retValY = y;
        return true;
    }
    
    // Allocate the grids.
    grid = allocGrid();
    costMap = allocGrid();
    
    // Start with a base of a high number everywhere.
    fillGrid(grid, 30000);
    fillGrid(costMap, 1);
    
    // Block off the pathing blockers.
    getTerrainGrid(costMap, PDS_FORBIDDEN, blockingTerrainFlags, blockingMapFlags);
    if (blockingTerrainFlags & (T_OBSTRUCTS_DIAGONAL_MOVEMENT | T_OBSTRUCTS_PASSABILITY)) {
        getTerrainGrid(costMap, PDS_OBSTRUCTION, T_OBSTRUCTS_DIAGONAL_MOVEMENT, 0);
    }
    
    // Run the distance scan.
    grid[x][y] = 1;
    costMap[x][y] = 1;
    dijkstraScan(grid, costMap, true);
    findReplaceGrid(grid, 30000, 30000, 0);
    
    // Block off invalid targets that aren't pathing blockers.
    getTerrainGrid(grid, 0, forbiddenTerrainFlags, forbiddenMapFlags);
    if (!hallwaysAllowed) {
        getPassableArcGrid(grid, 2, 10, 0);
    }
    
    // Get the solution.
    randomLeastPositiveLocationInGrid(grid, retValX, retValY, deterministic);
    
//    dumpLevelToScreen();
//    displayGrid(grid);
//    if (coordinatesAreInMap(*retValX, *retValY)) {
//        hiliteCell(*retValX, *retValY, &yellow, 100, true);
//    }
//    temporaryMessage("Qualifying path selected:", true);
    
    freeGrid(grid);
    freeGrid(costMap);
    
    // Fall back to a pathing-agnostic alternative if there are no solutions.
    if (*retValX == -1 && *retValY == -1) {
        if (getQualifyingLocNear(loc, x, y, hallwaysAllowed, NULL,
                                 (blockingTerrainFlags | forbiddenTerrainFlags),
                                 (blockingMapFlags | forbiddenMapFlags),
                                 false, deterministic)) {
            *retValX = loc[0];
            *retValY = loc[1];
            return true; // Found a fallback solution.
        } else {
            return false; // No solutions.
        }
    } else {
        return true; // Found a primary solution.
    }
}

void cellularAutomataRound(short **grid, char birthParameters[9], char survivalParameters[9]) {
    short i, j, nbCount, newX, newY;
    enum directions dir;
    short **buffer2;
    
    buffer2 = allocGrid();
    copyGrid(buffer2, grid); // Make a backup of grid in buffer2, so that each generation is isolated.
    
    for(i=0; i<DCOLS; i++) {
        for(j=0; j<DROWS; j++) {
            nbCount = 0;
            for (dir=0; dir< DIRECTION_COUNT; dir++) {
                newX = i + nbDirs[dir][0];
                newY = j + nbDirs[dir][1];
                if (coordinatesAreInMap(newX, newY)
                    && buffer2[newX][newY]) {
                    
                    nbCount++;
                }
            }
            if (!buffer2[i][j] && birthParameters[nbCount] == 't') {
                grid[i][j] = 1;	// birth
            } else if (buffer2[i][j] && survivalParameters[nbCount] == 't') {
                // survival
            } else {
                grid[i][j] = 0;	// death
            }
        }
    }
    
    freeGrid(buffer2);
}

// Marks a cell as being a member of blobNumber, then recursively iterates through the rest of the blob
short fillContiguousRegion(short **grid, short x, short y, short fillValue) {
    enum directions dir;
	short newX, newY, numberOfCells = 1;
	
	grid[x][y] = fillValue;
	
	// Iterate through the four cardinal neighbors.
	for (dir=0; dir<4; dir++) {
		newX = x + nbDirs[dir][0];
		newY = y + nbDirs[dir][1];
		if (!coordinatesAreInMap(newX, newY)) {
			break;
		}
		if (grid[newX][newY] == 1) { // If the neighbor is an unmarked region cell,
			numberOfCells += fillContiguousRegion(grid, newX, newY, fillValue); // then recurse.
		}
	}
	return numberOfCells;
}

// Loads up **grid with the results of a cellular automata simulation.
void createBlobOnGrid(short **grid,
                      short *retMinX, short *retMinY, short *retWidth, short *retHeight,
                      short roundCount,
                      short minBlobWidth, short minBlobHeight,
					  short maxBlobWidth, short maxBlobHeight, short percentSeeded,
					  char birthParameters[9], char survivalParameters[9]) {
    
	short i, j, k;
	short blobNumber, blobSize, topBlobNumber, topBlobSize;
    
    short topBlobMinX, topBlobMinY, topBlobMaxX, topBlobMaxY, blobWidth, blobHeight;
	//short buffer2[maxBlobWidth][maxBlobHeight]; // buffer[][] is already a global short array
	boolean foundACellThisLine;
	
	// Generate blobs until they satisfy the minBlobWidth and minBlobHeight restraints
	do {
		// Clear buffer.
        fillGrid(grid, 0);
		
		// Fill relevant portion with noise based on the percentSeeded argument.
		for(i=0; i<maxBlobWidth; i++) {
			for(j=0; j<maxBlobHeight; j++) {
				grid[i][j] = (rand_percent(percentSeeded) ? 1 : 0);
			}
		}
		
//        colorOverDungeon(&darkGray);
//        hiliteGrid(grid, &white, 100);
//        temporaryMessage("Random starting noise:", true);
		
		// Some iterations of cellular automata
		for (k=0; k<roundCount; k++) {
			cellularAutomataRound(grid, birthParameters, survivalParameters);
            
//            colorOverDungeon(&darkGray);
//            hiliteGrid(grid, &white, 100);
//            temporaryMessage("Cellular automata progress:", true);
		}
        
//        colorOverDungeon(&darkGray);
//        hiliteGrid(grid, &white, 100);
//        temporaryMessage("Cellular automata result:", true);
        
		// Now to measure the result. These are best-of variables; start them out at worst-case values.
		topBlobSize =   0;
		topBlobNumber = 0;
		topBlobMinX =   maxBlobWidth;
		topBlobMaxX =   0;
		topBlobMinY =   maxBlobHeight;
		topBlobMaxY =   0;
        
		// Fill each blob with its own number, starting with 2 (since 1 means floor), and keeping track of the biggest:
		blobNumber = 2;
		
		for(i=0; i<DCOLS; i++) {
			for(j=0; j<DROWS; j++) {
				if (grid[i][j] == 1) { // an unmarked blob
					// Mark all the cells and returns the total size:
					blobSize = fillContiguousRegion(grid, i, j, blobNumber);
					if (blobSize > topBlobSize) { // if this blob is a new record
						topBlobSize = blobSize;
						topBlobNumber = blobNumber;
					}
					blobNumber++;
				}
			}
		}
		
		// Figure out the top blob's height and width:
		// First find the max & min x:
		for(i=0; i<DCOLS; i++) {
			foundACellThisLine = false;
			for(j=0; j<DROWS; j++) {
				if (grid[i][j] == topBlobNumber) {
					foundACellThisLine = true;
					break;
				}
			}
			if (foundACellThisLine) {
				if (i < topBlobMinX) {
					topBlobMinX = i;
				}
				if (i > topBlobMaxX) {
					topBlobMaxX = i;
				}
			}
		}
		
		// Then the max & min y:
		for(j=0; j<DROWS; j++) {
			foundACellThisLine = false;
			for(i=0; i<DCOLS; i++) {
				if (grid[i][j] == topBlobNumber) {
					foundACellThisLine = true;
					break;
				}
			}
			if (foundACellThisLine) {
				if (j < topBlobMinY) {
					topBlobMinY = j;
				}
				if (j > topBlobMaxY) {
					topBlobMaxY = j;
				}
			}
		}
        
		blobWidth =		(topBlobMaxX - topBlobMinX) + 1;
		blobHeight =	(topBlobMaxY - topBlobMinY) + 1;
        
	} while (blobWidth < minBlobWidth
             || blobHeight < minBlobHeight
             || topBlobNumber == 0);
	
	// Replace the winning blob with 1's, and everything else with 0's:
    for(i=0; i<DCOLS; i++) {
        for(j=0; j<DROWS; j++) {
			if (grid[i][j] == topBlobNumber) {
				grid[i][j] = 1;
			} else {
				grid[i][j] = 0;
			}
		}
	}
    
    // Populate the returned variables.
    *retMinX = topBlobMinX;
    *retMinY = topBlobMinY;
    *retWidth = blobWidth;
    *retHeight = blobHeight;
}