Adding water tiles

Hi,

Was wondering how I could add water tiles to my caves, the caves are generated using cellular automata which basically
sets certain cells to blank or walls in 2d array giving illusion of caves. Now, I don’t know the position of these
as there is no real concept of caves, just blank cells, so this is making it difficult to add water tiles.

Anybody any ideas of how I could do this?

Here is my ‘cave’ generation code: (web site here for my blog of the game:

https://sites.google.com/site/sterrialand/development/news/cavesarelookinggood



package com.mygdx.game;

import java.util.Random;

public class CellularAutomata {

	private BlankEntity[][] map = null;
	private BlankEntity[][] newMap = null;
	private Random r = new Random();
	private int chanceToStartAlive, w, h, death, life;
	
	public CellularAutomata(int w, int h, int chanceToStartAlive, int death,
			int life) {
		this.w = w;
		this.h = h;
		this.chanceToStartAlive = chanceToStartAlive;
		this.death = death;
		this.life = life;		
	}

	public void initialiseMap() {
		map = new BlankEntity[w][h];
		for (int x = 0; x < map.length; x++)
			for (int y = 0; y < map[0].length; y++)
				map[x][y] = r.nextInt(100) > chanceToStartAlive ? new LandscapeEntity(x,y) : null;
	}

	// Debug
	public void displayMap() {
		if (map != null) {
			for (int x = 0; x < map.length; x++, System.out.println())
				for (int y = 0; y < map[0].length; y++)
					System.out.print(map[x][y]);
		}
	}

	public BlankEntity[][] getMap() {
		return map;
	}
	
	public BlankEntity[][] doSimulationStep() {
		newMap = new BlankEntity[w][h];
		for (int x = 0; x < map.length; x++) {
			for (int y = 0; y < map[0].length; y++) {
				int nbs = countAliveNeighbours(map, x, y);
				if (map[x][y] instanceof LandscapeEntity)
					newMap[x][y] = nbs <= life ? null : new LandscapeEntity(x,y);
				else
					newMap[x][y] = nbs > death ? new LandscapeEntity(x,y) : null;
			}
		}
		map = newMap;
		return newMap;
	}

	private int countAliveNeighbours(BlankEntity[][] map, int x, int y) {
		int count = 0;
		for (int i = -1; i < 2; i++) {
			for (int j = -1; j < 2; j++) {
				int neighbour_x = x + i;
				int neighbour_y = y + j;
				if (i == 0 && j == 0) { // do nothing as this is us!
				} else if (neighbour_x < 0 || neighbour_y < 0
						|| neighbour_x >= map.length
						|| neighbour_y >= map[0].length) {
					count++;
				} else if (map[neighbour_x][neighbour_y] instanceof LandscapeEntity)
					count++;
			}
		}
		return count;
	}
}



and the BlankEntity class


package com.mygdx.game;

import com.badlogic.gdx.graphics.g2d.Batch;
import com.badlogic.gdx.graphics.g2d.TextureRegion;

enum GrassType{ TOP, LEFT, RIGHT, FLAT};

class BlankEntity {

	public int x,y;

	protected final int size = 4;   //  4 if 16x16, 5 if using 32x32 tiles

	public BlankEntity(int x, int y)
	{
		this.x = x; this.y = y;

	}
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][0],x << size,y << size);  //0,0
	}
	@Override
	public String toString() {
		return ".";
	}
}

class LandscapeEntity extends BlankEntity{

	public LandscapeEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[0][0],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return "#";
	}
}
class LandscapeEntityRight extends BlankEntity{

	public LandscapeEntityRight(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[2][1],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return "#";
	}
}
class LandscapeEntityLeft extends BlankEntity{

	public LandscapeEntityLeft(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[2][0],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return "#";
	}
}

class CaveEntity extends BlankEntity{

	public CaveEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][1],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return ".";
	}
}
class CaveRightEntity extends CaveEntity{

	public CaveRightEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][3],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return ";";
	}
}
class CaveLeftEntity extends CaveEntity{

	public CaveLeftEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][2],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return ":";
	}
}
class CaveTopEntity extends CaveEntity{

	public CaveTopEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][4],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return ":";
	}
}
class CaveBottomEntity extends CaveEntity{

	public CaveBottomEntity(int x, int y)
	{
		super(x,y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[1][5],x << size,y << size);
	}
	
	@Override
	public String toString() {
		return ":";
	}
}

class LavaEntity extends BlankEntity {
	
	public LavaEntity(int x, int y)
	{
		super(x, y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[26][4],x << size,y << size); // 6,5
	}
}

class GrassEntity extends BlankEntity{
	
	private GrassType type;
	
	public GrassType getGrassType() { return type; }
	
	public GrassEntity(int x, int y, GrassType type)
	{
		super(x, y);
		this.type = type;
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[0][3], x << size, y << size);
	}
}

class WeedsEntity extends BlankEntity{
	
	public WeedsEntity(int x, int y)
	{
		super(x, y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[13][0], x << size, y << size);
	}
}

class GrassLeftEntity extends GrassEntity{
	
	public GrassLeftEntity(int x, int y)
	{
		super(x, y, GrassType.LEFT);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[0][2], x << size, y << size);
	}
}
class GrassRightEntity extends GrassEntity{
	
	public GrassRightEntity(int x, int y)
	{
		super(x, y, GrassType.RIGHT);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[0][4], x << size, y << size);
	}
}
class GrassTopEntity extends GrassEntity{
	
	public GrassTopEntity(int x, int y)
	{
		super(x, y, GrassType.TOP);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[0][5], x << size, y << size);
	}
}
class CoalEntity extends BlankEntity{
	
	public CoalEntity(int x, int y)
	{
		super(x, y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[2][2], x << size, y << size);  // 0,19
	}
}
class RockEntity extends BlankEntity{
	
	public RockEntity(int x, int y)
	{
		super(x, y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[2][10], x << size, y << size);  // 0,1
	}
}
class WaterEntity extends BlankEntity{
	
	public WaterEntity(int x, int y)
	{
		super(x, y);
	}
	
	public void draw(Batch batch, TextureRegion[][] t)
	{
		batch.draw(t[2][0], x << size, y << size);
	}
}

Hope somebody can shed some light on how I can do this.

Thanks

Still struggling with this, thinking somehow working out how to determine start and end of a cave…

How do other people add water tiles to their caves?

Any ideas are welcome and appreciated.

Thanks

Since no one’s replied yet, I’ll go ahead and ask, are you just looking for a good way to choose empty cells in the grid in which to place water?

If someone doesn’t offer a solution soon, one thing that might help would be to take the screenshot you linked to, manually draw in some water where you think it’d be reasonable for it to be using an image editing program, and then post the edited image here. That way we could see what you’re going for.

Will do.

How do I put an image in the post btw?!

I’ve uploaded images of what I am after:

https://sites.google.com/site/sterrialand/development/news/addingwaterhow

Thanks

I haven’t done it here, but I see an ‘image’ button in the post editing tools. You might have to host it somewhere though. Or, you could just link to it like you did with the other one.

Meanwhile though, I’ll offer a quick suggestion. There’s probably a more or less canonical solution to this (I haven’t searched online), so maybe this isn’t the way to do it, but it’s what comes to mind.

If you start with an empty cell and do a flood fill, with the constraint that the fill doesn’t go higher than the initially selected cell, you should get a volume of water that looks correct given gravity and flow (if I’m not mistaken). The trick would then be to choose reasonable initial cells. How to do that depends, I think, on what kind of effect you’re looking for (e.g. how much water, maximum volume or depth, and so on). For that, you could just describe what you have in mind, or provide an image as mentioned earlier.

Saw your image. Do you want to fill entire caves with water? Or just parts of them?

Hi thanks for that,

Yeah,just want to fill parts of the caves.

Again, the caves are just of type CaveEntity,CaveLeftEntity,CaveRightEntity,CaveBottomEntity and CaveTopEntity - basically just a tile - so I cannot
determine atm the start and end of a cave.

Thanks

Ok, I think a flood fill is what you want then. Just start in an empty cell and do a full flood fill - that will fill the entire cave with water. Then, if you only want to fill part of the cave, start removing rows from the top of the fill until you’re below some minimum volume or depth threshold. There are some configurations this won’t give you (such as isolated pools at different levels in the same cave), but it should be a good starting point. (As far as determining the bounds of a cave, all you need to know is whether a cell is empty or not, which I assume is information you have available.)

Hi,

Thanks again.

Yes, I do know what cells are the CaveEntity ones. So, you are saying if I pick one of these cells, a flood fill will fill the cave - does this not need a start, end position or something?
Also, I’d be struggling to move onto the next cave as they are just cells, I’ve nothing stored that says there is a cave at this position, one at that position etc if you know what I mean.

A floodfill usually has a start node, target color (tile), replacement color(tile).

Maybe I’m over complicating this?!

Thanks

A flood fill only needs a cell to start in. From there, the algorithm will (by its nature) fill all available space until it has nowhere else to go.

[quote]Also, I’d be struggling to move onto the next cave as they are just cells, I’ve nothing stored that says there is a cave at this position, one at that position etc if you know what I mean.
[/quote]
If this is all preprocessed and performance isn’t a concern, then you can find all the individual caves using flood fills as well. The algorithm would go something like this (off the top of my head, no guarantee of correctness):

Mark all the cells in the map as initially ‘unvisited’. Then for each cell in the map, check to see if it’s empty (a cave cell). If it’s both empty and unvisited, start a flood fill in that cell. For every cell the flood fill touches (including the initial cell), flag that cell as ‘visited’ and add it to a list for cave N. ‘N’ should start at zero, and increment at the end of each flood fill.

At the end of this process you should have something like an array of arrays of cell references, where each inner array in the outer array contains all the cells in a single cave.

This information (where the caves are) could be useful for a number of purposes, I imagine, but it could also easily be used to add water. Just pick a few caves at random, and set all the cells in the cave to ‘water’. If you don’t want to fill the entire cave, ‘clip’ the water volume off at a specified height.

[quote]A floodfill usually has a start node, target color (tile), replacement color(tile).
[/quote]
Maybe you already know this, but the ‘color’ part is just an abstraction, so don’t let it distract you. A flood fill is a general algorithm that can be used for things other than colors. In fact, in the case of finding all the caves, you wouldn’t be replacing one thing with another; you’d just be finding the bounds of an open area.

Based on what you’re describing, I think the algorithm I described earlier may be what you want, as it will tell you exactly where all the caves are and allow you (possibly among other things) to place water easily. If it’s still not entirely clear, let me know and I’ll try to provide some more info.

Many thanks Jesse, really appreciate your help and advice with this.

I’ve coded this class up for testing purposes for flood fill:


package com.mygdx.utils;


public class FloodFill {

	char[][] map;
	
	public FloodFill(char[][] map)
	{
		this.map = map;
	}
	
	public void fill(int x, int y, char newTile, char oldTile) {
		if(x <0) return;
		if(y<0) return;
		if(x > map.length) return;
		if(y > map[x].length) return;
		
		char currentTile = map[x][y];  // get current tile
		if(oldTile != currentTile) return; // 
		if(newTile == currentTile) return;  // same
		
		map[x][y] = newTile;
		
		fill(x-1,y, newTile, oldTile);
		fill(x+1,y, newTile, oldTile);
		fill(x,y -1, newTile, oldTile);
		fill(x,y+1, newTile, oldTile);
	}
	
	public static void main(String[] argv)
	{
		char map[][] =
	        {
	            { 'O', 'O', 'O', 'O', 'X' },
	            { 'X', 'O', 'O', 'O', 'X' },
	            { 'X', 'O', 'O', 'O', 'X' },
	            { 'X', 'O', 'O', 'O', 'X' },
	            { 'X', 'X', 'X', 'X', 'X' },
	            { 'X', 'X', 'X', 'X', 'X' },
	            { 'X', 'X', 'X', 'X', 'X' }
	        };
	        FloodFill floodFill = new FloodFill(map);
	        floodFill.fill(0, 0, '*', 'O');
	        
	        for(int x=0;x<map.length;x++, System.out.println())
	        	for(int y=0;y<map[x].length;y++) 
	        		System.out.print(map[x][y]);
	        
	}
	
}


Seems to work, as long as the cell you are starting with is the one to be replaced. Thus, would start with a cave cell and use the above, problem is,
the array width, this would do my whole map, not just the width of a cave as I don’t know what this would be. This is why it would be good if I could get the caves
width. Is it possible to do this?

Thanks

Should these:

if(x > map.length) return;
      if(y > map[x].length) return;

Perhaps be >= rather than >?

Also, with a recursive implementation like this one, you may get a stack overflow if the area to fill is large enough. For this reason, a stack-based implementation that doesn’t use recursion might be preferable.

[quote]Thus, would start with a cave cell and use the above, problem is,
the array width, this would do my whole map, not just the width of a cave as I don’t know what this would be. This is why it would be good if I could get the caves
width. Is it possible to do this?
[/quote]
I think either I’m misunderstanding what you’re getting at, or you may be misunderstanding the flood fill algorithm a little. The flood fill algorithm, properly implemented, doesn’t need any information other than a starting cell and the grid itself. The flood fill would not fill your whole map, just the cave in which it started. You don’t need to know the width of the cave or anything like that, and in any case the ‘width’ of a cave isn’t really well defined, given that different parts of the cave may have different widths.

If I’m misunderstanding what you mean, maybe you could provide a more concrete example, that is, show a case where the flood fill algorithm wouldn’t do what you want.

Hi,

What I meant was, it would fill all the caves in my map completely - I do want some of them not to have water in them and others to have some :slight_smile:

I know what you mean about the recursion, but think my caves aren’t that big so could be ok but may later look into using one without recursion using a queue.

I used this before using the simple flood fill you mentioned:


for (int x = 0; x < GRASS_START - (DIRT_START + 2); x++) {
			for (int y = 1; y < w - 1; y++) {
				int index = 0;
				int start = 0;
				int end = 0;
				boolean found = false;
				if (worldMap[y][x + DIRT_START] instanceof CaveLeftEntity ||
						worldMap[y][x + DIRT_START] instanceof CaveBottomEntity ||
						worldMap[y][x+DIRT_START] instanceof CaveTopEntity) // bottom
																			// of
																			// a
																			// cave
				{
					start = y;
					do {
						if (index + y >= w - 1)
							break;

						index++;

						if (worldMap[y + index][x + DIRT_START] instanceof CaveRightEntity) {
							found = true;
							end = y+index;
							break;
						}
					} while (!(worldMap[y + index][x + DIRT_START] instanceof CaveRightEntity));
					if (found) {
						System.out.printf("Start from:%d end at:%d", start,end);
						for(int j=start; j<=end;j++) {
							worldMap[j][x + DIRT_START] = new WaterEntity(j,x + DIRT_START);
					//	    break;	
						}
					}
					
				}
			}

Thanks again.

I think my answer is that if the flood fill fills all your caves, then there’s something wrong with your implementation or how you’re conceptualizing things (I couldn’t tell you what exactly without digging through your code though). If you start a flood fill in one of the caves, it should fill that cave and that cave only. If anything other than that happens, then something is wrong.

Sorry I can’t be more specific. I’m fairly confident though that flood fill is what you want here - it’s just a matter of working out whatever conceptual or technical problems are in the way.

Hi,

It will do what you say, but it is determining where a cave is - guess just where there is a cave entity, seems obvious now, lol.

Just need to fill some with water and others not.

Thanks

This is my flood fill for filling map when map is made up of BlankEntity objects like in my game:


public class FloodFill {

	BlankEntity[][] map;

	public FloodFill(BlankEntity[][] map) {
		this.map = map;
	}

	public void fill(int x, int y, WaterEntity newTile, CaveEntity oldTile) {
		if (x < 0)
			return;
		if (y < 0)
			return;
		if (x >= map.length)
			return;
		if (y >= map[x].length)
			return;

		BlankEntity currentTile = map[x][y]; // get current tile
		if (!(currentTile instanceof CaveEntity))
			return;

		map[x][y] = new WaterEntity(x, y);// newTile;

		fill(x - 1, y, newTile, oldTile);
		fill(x + 1, y, newTile, oldTile);
		fill(x, y - 1, newTile, oldTile);
		fill(x, y + 1, newTile, oldTile);
	}

	public static void main(String[] argv) {
		BlankEntity map[][] = {
				{ new CaveEntity(0, 0), new CaveEntity(1, 0),
						new CaveEntity(2, 0) },
				{ new LandscapeEntity(0, 1), new LandscapeEntity(1, 1),
						new LandscapeEntity(2, 1) }, };

		// display original map
		for (int x = 0; x < map.length; x++, System.out.println())
			for (int y = 0; y < map[x].length; y++)
				System.out.print(map[x][y]);

		FloodFill floodFill = new FloodFill(map);
		floodFill.fill(0, 0, new WaterEntity(0, 0), new CaveEntity(0, 0));

		// display after flood fill
		System.out.println();
		for (int x = 0; x < map.length; x++, System.out.println())
			for (int y = 0; y < map[x].length; y++)
				System.out.print(map[x][y]);

	}

}

Seems to work, but working out position of caves still confusing?

I’ve put the above into my game now and wrote a method to find the first cave entity cell so we can get a flood fill, I’ve put a screenshot of this here:

https://sites.google.com/site/sterrialand/development/news/floodfillfirsteffort

Now, how to move to next cave? Or, how not to fill this cave completely?

Thanks

Sorry to repeat myself, but I think my answer will be similar to before. Let me try describing it again though.

You should be able to use flood fill to find all the caves in your map.

First, think about how you’d like to store the locations of the caves. Here’s one way you could do it. Each cave could be represented by an array of references to cells (that is, the array contains all the empty cells that make up the cave). These ‘cave arrays’ would then be stored in an array. So, you’d have an array of arrays of cell references, where the outer array is a list of all the caves, and the inner arrays represent the caves themselves.

You would build these lists (as a preprocessing step) like this. Mark all cells as unvisited (one way or another - you could just give the cells a boolean ‘visited’ flag). Then, iterate over all the cells in the map. At each cell, if it’s empty (a cave cell) and hasn’t yet been visited, start a flood fill there. When the flood fill is complete, you’ve found one of your caves. Add the cave cells to the list (the array of arrays), and mark all the cells in the cave as visited so they won’t be processed again. At the completion of this process, you should have your array of arrays listing all the caves in the map. Now, this is off the top of my head, so it’s possible I’ve missed something. But, I’m fairly confident that this, or something like it, should work.

Once you have your list of caves, you can do whatever you want with them. For example, you could select a few of them at random to add water to.

To fill up a cave completely, you would just set all the cells in the cave to ‘water’. To fill up a cave partially, find the lowest and highest cell y values for the cave, choose a y value in between the two, and then set all the cells in the cave that are <= this y value to ‘water’. Note that there are certain types of configurations this won’t give you, such as isolated pools of water at different levels in the same cave, but otherwise it should give you suitable results.

If I haven’t missed anything, the above approach should address all the issues you’ve mentioned, and should find all the caves in your map for you automatically. I’d recommend giving what I’ve described here a go, and posting back if it’s not working or if there are aspects of it that aren’t clear.

Thanks Jesse,

All sounds good to me. So on completion of flood fill, I can say this is a cave, add all the positions of the cells here into an array - would you do this as the flood fill is processing so you
have the positions of the cells for the ‘cave’ in question?

Thanks again,
Steve

If I understand you correctly, yes, you’d collect the cells for the cave as the flood fill is processing. In other words, the flood fill doesn’t make any changes or anything (like changing one tile type to another) - it just gathers information. The only thing you do every time the flood fill visits a new cell is add that cell to a collection, and then when the flood fill is complete, you return the collection, and that’s your cave. Then later you can do whatever you want with that collection, like adding water.

If you get stuck on anything, I can probably sketch some pseudocode outlining the algorithm.

Thanks Jesse,

I’m doing some code in cough cough C# to do this then going port to Java for my game.
The flood fill will need to store the cave cells x,y position I’m taking it.