Adding water tiles

steg90 · June 9, 2015, 9:48am

This is what I have come up with in C#:


namespace ConsoleApplication8
{
    class FloodFill
    {
        char[,] map;

      
        List<CaveCell> CaveCells = new List<CaveCell>();

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

        public List<CaveCell> GetCaveCells()
        {
            return CaveCells;
        }

        public void fill(int x, int y, char newTile, char oldTile)
        {
            if (x < 0) return;
            if (y < 0) return;
            if (x >= map.GetLength(1)) return;
            if (y >= map.GetLength(0)) return;

            char currentTile = map[x,y];  // get current tile
            if (oldTile != currentTile) return; // 
            if (newTile == currentTile) return;  // same

           // map[x,y] = newTile;   // store x,y position

            CaveCell cell = new CaveCell(x, y);
            CaveCells.Add(cell);

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

    }

    class CaveCell
    {
        public CaveCell(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
        public int x { get; set; }
        public int y { get; set; }

        public override string ToString()
        {
            return String.Format("[{0},{1}]",x,y);
        }
    }
    class Cave
    {
        public Cave() {
            Cells = new List<CaveCell>();
        }
        public List<CaveCell> Cells { get; set; }
    }
}

class Program
    {
        static List<Cave> Caves = new List<Cave>();
        static void Main(string[] args)
        {
            char[,] map = {
           { 'O', 'O', 'O', 'O', 'X','O','O','X' },
           { 'X', 'O', 'O', 'O', 'X','O','O','X' },
           { 'X', 'O', 'O', 'O', 'X','O','O','X' },
           { 'X', 'O', 'X', 'O', 'X','X','O','X' },
           { 'X', 'X', 'X', 'X', 'X','X','O','X' },
           { 'X', 'X', 'X', 'X', 'X','X','O','X' },
           { 'X', 'X', 'X', 'X', 'X','X','X','X' }
           };
            FloodFill floodFill = new FloodFill(map);
            floodFill.fill(0, 0, '~', 'O');

          //  floodFill.fill(0, 6, '~', 'O');

            for (int y = 0; y < map.GetLength(0); y++, Console.WriteLine())
                for (int x = 0; x < map.GetLength(1); x++)
                    Console.Write(map[y, x]);

            List<CaveCell> CaveCells = floodFill.GetCaveCells();
            Cave Cave = new Cave();

            foreach (CaveCell cell in CaveCells)
            {
                Cave.Cells.Add(cell);
            }
            Caves.Add(Cave);

            foreach (Cave cave in Caves)
            {
                foreach (CaveCell cell in cave.Cells)
                {
                    Console.WriteLine(cell);
                }
            }
        }
    }

So the Caves list holds list of Caves, where each Cave has a list of it’s cells, this look ok?

Thanks

Jesse · June 9, 2015, 10:07am

Yes , that’s correct, and your most recent code is getting very close to what I’m suggesting

I just skimmed the code, so I don’t know if it’s all correct, and I don’t yet see you finding all the caves (I just see you finding one).

The first step in finalizing this will be to make sure your flood fill code works. Maybe it does - I didn’t look at it that carefully. But because you’re just searching for cells, and not modifying them in any way, you may need to add code to ensure cells aren’t visited more than once.

Once you’re sure the flood fill code works, here’s what I have in mind, in pseudocode (no guarantee of correctness):

caves = Cell[][]() // An array of arrays of cells, as discussed

function cellIsAlreadyPartOfACave(cell) {
    for each cave in caves {
        if cave.contains(cell) {
            return true
        }
    }
    return false
}

for each cell in map {
    if cell is empty && !cellIsAlreadyPartOfACave(cell) {
        caves.add(floodFill(map, cell.x, cell.y))
    }
}

This is off the top of my head and I may have missed something, but even if I got some details wrong, I think the idea is sound in principle. Your most recent code has a lot of the elements in place, although as mentioned I don’t see you finding all the caves in the map yet. But, maybe you just haven’t gotten to that.

steg90 · June 9, 2015, 10:21am

Thanks,

Yes, not got to that yet, I think to move onto the next cave, I need the max X of previous one or something or like you state, if the cell has been visited or not.

Thanks for the pseudo, looks great to me.

Jesse · June 9, 2015, 5:44pm

I don’t think you need the max x or anything like that. For one thing, that could cause you to miss a cave that was directly above or below another cave. I think just iterating over every cell in the map while skipping cells that are already included in a cave will do the trick.

steg90 · June 9, 2015, 8:32pm

Yeah, think you could be right there.

Hoping to implement tomorrow, will let you know!

Thanks

steg90 · June 10, 2015, 12:36pm

Well, think this does the trick, only done it as a test class at mo in C#, but simple to put to my Java code, what do you think?


class Program
    {
        static List<Cave> Caves = new List<Cave>();
        static void Main(string[] args)
        {
            BlankEntity[,] m = { { new CaveEntity() ,      new CaveEntity(),       new LandscapeEntity(), new LandscapeEntity() },
                                 { new LandscapeEntity() , new LandscapeEntity() , new CaveEntity(),      new LandscapeEntity() }, 
                                 { new LandscapeEntity() , new LandscapeEntity() , new LandscapeEntity(),      new LandscapeEntity() },
                               };

   
            for (int y = 0; y < m.GetLength(0); y++)   // depth
            {
                for (int x = 0; x < m.GetLength(1); x++)  // width
                {
                    FloodFill fFill = new FloodFill(m);    
                    fFill.fill(y, x);                    
                    
                    var CaveC = fFill.GetCaveCells();
                    if (CaveC.Count > 0)
                    {
                        var c = new Cave();
                        foreach (CaveCell cell in CaveC)
                        {
                            c.Cells.Add(cell);
                        }
                        Caves.Add(c);
                    }
                }
            }
            
            for (int y = 0; y < m.GetLength(0); y++, Console.WriteLine())
            {
                for (int x = 0; x < m.GetLength(1); x++)
                {
                    Console.Write(m[y,x]);
                }
            }
            foreach (Cave cave in Caves)
            {
                foreach (CaveCell cell in cave.Cells)
                {
                    Console.WriteLine(cell);
                }
                Console.WriteLine("Next cave\n");
            }

        }
    }

    class BlankEntity
    {
        public int x { get; set; }
        public int y { get; set; }
        public bool Visited { get; set; }

        public override string ToString()
        {
            return " ";
        }
    }

    class LandscapeEntity : BlankEntity
    {
        public override string ToString()
        {
            return "C";
        }
    }
    class CaveEntity : BlankEntity
    {
        public override string ToString()
        {
            return "C";
        }
    

    }

    class WaterEntity : BlankEntity
    {
        public override string ToString()
        {
            return "W";
        }
    }
}


namespace ConsoleApplication8
{
    class FloodFill
    {
        BlankEntity[,] m;
      
        List<CaveCell> CaveCells = new List<CaveCell>();

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

        public List<CaveCell> GetCaveCells()
        {
            return CaveCells;
        }

        public void fill(int x, int y)
        {
            if (x < 0) return;
            if (y < 0) return;
            if (x >= m.GetLength(0)) return;
            if (y >= m.GetLength(1)) return;

            BlankEntity currentTile = m[x,y];  // get current tile
            if (m[x, y].Visited) return;
            if (!(currentTile is CaveEntity)) return; // 
          
            m[x,y] = new WaterEntity();   // store x,y position
            m[x, y].Visited = true;

            CaveCell cell = new CaveCell(x, y);
            CaveCells.Add(cell);

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

    class CaveCell
    {
        public CaveCell(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
        public int x { get; set; }
        public int y { get; set; }

        public override string ToString()
        {
            return String.Format("[{0},{1}]",x,y);
        }
    }
    class Cave
    {
        public Cave() {
            Cells = new List<CaveCell>();
        }
        public List<CaveCell> Cells { get; set; }
    }
}

Just trying to work out now how I would fill these caves to a certain height - this a matter of calling floodfill again passing in a cave and then some how removing tops of the water in the cave?

Thanks

Jesse · June 10, 2015, 7:34pm

I didn’t proof the code for errors, but it does look conceptually correct. The true test will be applying it to the map in your first screenshot and seeing if it works!

[quote]Just trying to work out now how I would fill these caves to a certain height - this a matter of calling floodfill again passing in a cave and then some how removing tops of the water in the cave?
[/quote]
No need to flood fill again, because you already did the flood fill and you already know all the cells that are in each cave.

For filling only part of a cave with water, do this:

Find the lowest y coordinate for the cave (that is, the minimum y value for all the cells in the cave).
Find the highest y coordinate for the cave (that is, the maximum y value for all the cells in the cave).
Pick a y value somewhere between these two values.
For every cell in the cave with a y value <= the y value you picked, set it to ‘water’.

If you get everything working, I hope you’ll post a new screenshot that includes the water - I’d like to see the results

steg90 · June 10, 2015, 8:17pm

Thanks again Jesse

Yeah will hopefully get this done tomorrow while at work.

So don’t use floodfill to fill cave with water then, I already got highest Y and lowest Y, so guess just do what you have said.

What I was doing was floodfilling cave and setting to water then trying to remove some of the water tiles without much success!

Of course will do some screen shots of it

steg90 · June 11, 2015, 1:26pm

Cave generation completed. Water added. I just add up to around half-way for now, will change later and I also add
water to all the caves, again, this will also change later.

Screen shot here:

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

The odd-time had a stack over flow, that will be the flood fill algorithm, may look at trying to do a non-recursive one…

Jesse · June 11, 2015, 6:23pm

Success! And thanks for posting a screenshot - looks good.

steg90 · June 12, 2015, 7:30am

Thanks Jesse, and many thanks for all the invaluable help!

Looking like I will need to modify / rewrite the flood fill to be non-recursive, as if the caves are very big, sometimes get
a stack overflow…

steg90 · June 12, 2015, 12:15pm

Got iterative flood fill to work with some test 2d char array but in my game code, only ever produces 3 cells for each cave?

Here is the fill method:


	public void iterativeFill(int x, int y) {
		BlankEntity currentTile = map[x][y]; // get current tile
		if (currentTile == null)
			return;

		if (currentTile.visited)
			return;

		if (!(currentTile instanceof CaveEntity))
			return;

		currentTile.visited = true;

		Queue<BlankEntity> q = new LinkedList();

		q.add(map[x][y]);

		while (!q.isEmpty()) {

			BlankEntity e = q.remove();

			cell = new CaveCell(e.x, e.y);

			caveCells.add(cell);

			if (x < map.length - 1)
				if (map[x + 1][y] instanceof CaveEntity) {
					if (!map[x + 1][y].visited) {
						q.add(map[x + 1][y]);
						map[x + 1][y].visited = true;
					}
				}

			if (x > 0)
				if (map[x - 1][y] instanceof CaveEntity) {

					if (!map[x - 1][y].visited) {
						q.add(map[x - 1][y]);
						map[x - 1][y].visited = true;
					}
				}

			if (y < map[x].length - 1)
				if (map[x][y + 1] instanceof CaveEntity) {
					if (!map[x][y + 1].visited) {
						q.add(map[x][y + 1]);
						map[x][y + 1].visited = true;
					}
				}

			if (y > 0)
				if (map[x][y - 1] instanceof CaveEntity) {
					if (!map[x][y - 1].visited) {
						q.add(map[x][y - 1]);
						map[x][y - 1].visited = true;
					}
				}
		}

	}

Called up:


for(int x=0; x<worldMap.length;x++)
		{
			for(int y=0;y<worldMap[x].length;y++)
			{
				fFill = new FloodFill(worldMap);
				fFill.iterativeFill(x,y);
				ArrayList<CaveCell> cavec = fFill.caveCells;
				if(cavec.size() > 0) 
				{
					Cave c = new Cave();
					for(CaveCell cell : cavec)
					{
						c.cells.add(cell);
					}
					
					this.caves.add(c);
				}
			}
		}

I’m sure x and y need incrementing or something in the iterative fill method?

Any ideas?

Thanks