WoobyCTF, The Visibility Grid
February 19, 2012 19:56
As graduation with my undergraduate degree looms increasingly closer, it seems that, even though I'm taking a relatively small number of credit hours, classes have begun to get extremely difficult and time consuming. Nevertheless, I have found time here and there to continue work on my game as well as on this website. While I'm not able to make leaps and bounds of progress every week, I'm happy to continue making even a little progress every week.
I acutally spent a big chunk of time this past couple of weeks with the back-end of this website. Like I've mentioned in other posts, I decided to stay away from tools like wordpress or other blogging utilities and instead build up my own. While it's not perfect, it has been quite enjoyable to build it up from scratch. The process of modifying the backend of this site included a number of things. First, I completely redid the schema of my database. I originally built it up before I had any real knowledge of databases. Since then, I have operated in environments of over 1000 tables and have taken a databases class.
With that new knowledge, I went back in, exported all the data that I had, built up a new schema, and put all of the old information in the new format. It really was a chore to maintain all the data but was definitely worth it. Additionally, I built up a new system for displaying blog posts from both the front page (with a just a small snippet of the post) as well as displaying the entire post on its specific page. While all of my php is not built in a true MVC format, it's built in a nice, appropriately separated fashion. I felt like the size of this site doesn't really fill the need for a true MVC framework.
After putting the new format of the site together, I finally spent some more time building up my game. I established some of the stances that characters can be in (look, run, walk, crawl) and built up the classes for those. Additionally, I started looking into the format that I'd like to save maps into. In the future, I'd like to have some kind of random terrain generation, but for now I need some kind of maps to be able to test on. I began work on my MapWriter and MapReader classes which will be responsible for saving and loading maps in my own format. I've always saved files as strict text which ends up being excessively large so I looked into saving maps in a binary format. I figure all I need to actually save maps is the dimension of the map and then a huge array of bytes which relate to the appropriate celltype that goes there. I'm sure there will be more data to save in the future but for now that should be plenty. One thing that might be interesting to put together in the future would be a map editor so that the user can create maps themselves as well as using the random terrain generation. I'll have to put that on my to-do list since, to be honest, that's the first time I've thought about that. It might be beneficial to make a map-editor for myself so that I can create a few maps to experiment on to begin with.
On my previous post, I talked about how I had solved the visibility problem. After a couple weeks, I decided that I ultimately didn't like that form of determining visibility. After some more thinking, I came up with a simpler iterative algorithm which relies on averages of neighbor cells to determine its own visibility. So, let's say a character is in a stance that gives them a max visibility of 3 (for the sake of example). We'll make a 7x7 grid where the center of that grid is the location of the character. To begin, we'll fan out in the x and y directions and fill in the visibility of those cells. Each cell on the horizontal or vertical of the center cell relies only on one other cell to calculate its own visibility value. Say a cell is a river type with visibility 5 and the cell before it has a visibility 3. This cell will have a visibility of 8.
Once that is done, we start filling in the four remaining sectors working our way out from the center. Each of these cells will take the average of its neigbors which have a smaller manhattan distance from the center (which will always be two). The following pictures illustrate this.
And here is that algorithm coded up:
public boolean[][] getVisibilityGrid(MapGrid map) {
int gridSize = stance.getViewDistance() * 2 + 1;
int numIterations = stance.getViewDistance();
float visibilityGrid[][] = new float[gridSize][gridSize];
boolean returnGrid[][] = new boolean[gridSize][gridSize];
int centerCoord = numIterations;
MapGrid gameMap = map;
Point2D worldCoord;
Point2D gridCoord;
//calculate initial 4 directions
for (int i = 1; i <= stance.getViewDistance(); i++) {
//Left
gridCoord = new Point2D(centerCoord - i, centerCoord);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = gameMap.getVisibilityAt(worldCoord.x, worldCoord.y) + visibilityGrid[gridCoord.x + 1][gridCoord.y];
//Right
gridCoord = new Point2D(centerCoord + i, centerCoord);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = gameMap.getVisibilityAt(worldCoord.x, worldCoord.y) + visibilityGrid[gridCoord.x - 1][gridCoord.y];
//Up
gridCoord = new Point2D(centerCoord, centerCoord - i);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = gameMap.getVisibilityAt(worldCoord.x, worldCoord.y) + visibilityGrid[gridCoord.x][gridCoord.y + 1];
//Down
gridCoord = new Point2D(centerCoord, centerCoord + i);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = gameMap.getVisibilityAt(worldCoord.x, worldCoord.y) + visibilityGrid[gridCoord.x][gridCoord.y - 1];
}
for (int i = 1; i <= stance.getViewDistance(); i++) {
for (int j = 1; j <= stance.getViewDistance(); j++) {
//UpperLeftArea
gridCoord = new Point2D(centerCoord - i, centerCoord - j);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = (((visibilityGrid[gridCoord.x + 1][gridCoord.y] + visibilityGrid[gridCoord.x][gridCoord.y + 1]) / 2) + gameMap.getVisibilityAt(worldCoord.x, worldCoord.y));
//UpperRightArea
gridCoord = new Point2D(centerCoord - i, centerCoord + j);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = (((visibilityGrid[gridCoord.x - 1][gridCoord.y] + visibilityGrid[gridCoord.x][gridCoord.y + 1]) / 2) + gameMap.getVisibilityAt(worldCoord.x, worldCoord.y));
//LowerLeftArea
gridCoord = new Point2D(centerCoord + i, centerCoord - j);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = (((visibilityGrid[gridCoord.x + 1][gridCoord.y] + visibilityGrid[gridCoord.x][gridCoord.y - 1]) / 2) + gameMap.getVisibilityAt(worldCoord.x, worldCoord.y));
//LowerRightArea
gridCoord = new Point2D(centerCoord + i, centerCoord + j);
worldCoord = translateGridCoordToMapCoords(gridCoord.x, gridCoord.y, gridSize);
visibilityGrid[gridCoord.x][gridCoord.y] = (((visibilityGrid[gridCoord.x - 1][gridCoord.y] + visibilityGrid[gridCoord.x][gridCoord.y - 1]) / 2) + gameMap.getVisibilityAt(worldCoord.x, worldCoord.y));
}
}
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridSize; j++) {
returnGrid[i][j] = (visibilityGrid[i][j] < stance.getViewDistance());
}
}
return returnGrid;
}
private Point2D translateGridCoordToMapCoords(int x, int y, int gridSize) {
Point2D toReturn = new Point2D();
int halfGrid = (gridSize - 1) / 2;
toReturn.x = (xLocation - (halfGrid - x));
toReturn.y = (yLocation - (halfGrid - y));
return toReturn;
}
private class Point2D {
public int x;
public int y;
public Point2D() {
}
public Point2D(int x, int y) {
this.x = x;
this.y = y;
}
}
