hints and tips needed

Vano2005 · July 9th, 2005, 11:13 PM

i want to do something like a random terrain generator
so i just wanted to ask you if anyone know how to do it

what i want is this:

to make a map: 8x16
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][][]

and make some squares with "water" 0,
and make some squares with "land" 1;
the problem is when i randomly fill an array with ones and zeros
it comes out bad, 1's and 0's are all over the place.
and what i want is for "land" to have some big 4x4 or 4x6 square and same for "water",

so does anyone has any hints or tips on how to do it ?

thx

vano.

planoie · July 10th, 2005, 06:36 AM

Here's a rough idea:
A. generate a random coordinate
B. generate a random area size (4x4/4x6)
C. check to see if the area (B) starting at the coordinate (A) is already occuppied by land ("1")
D. If not (C) then fill all matrix cells of area (B) starting at coord (A) with land ("1")

How often you repeat will have to be determined on whether you want a specific number of land areas, or perhaps a certain percentage of the entire area consisting of land. You should also put in a safety check that the algorithm doesn't get itself into a loop it can't leave. If the right combination of areas are created but you haven't satisfied the "It's done" condition you could get stuck in a loop.

-Peter

jacob · July 10th, 2005, 06:52 AM

Sorry, I couldn't help myself... It was a fun problem... The classes underneath have a base class for either a LandTerrain or a LakeTerrain, which is as you specified, with the exception that the corners of the lakes have been rounded a bit (primitive way though).

The Main method creates a LandTerrain and Lakeify the terrain. The Lakeify method takes a series of arguments where number of min and max number of lakes can be specified and min and max values for the size of the lakes. This is an example from the code posted...

Code:

1111111001111111
1111110000111111
1111110000111111
1111111001111111
1111111111110011
1111111111100001
1111111111100001
1111111111100001

But it is rather fun to increase the size of the landscape to e.g. 80x80.

Code:

using System;

namespace Terrain
{
    class BaseTerrain
    {
        public int Width
        {
            get{ return this.width; }
        }
        private int width;

        public int Height
        {
            get{ return this.height; }
        }
        private int height;

        protected int[,] terrain = null;

        public BaseTerrain(int height, int width)
        {
            this.width = width;
            this.height = height;

            this.terrain = new int[height, width];
        }


        protected void Initialize(int val)
        {
            for(int i = 0; i < this.height; i++)
                for(int j = 0; j < this.width; j++)
                    this.terrain[i, j] = val;
        }


        public int Get(int i, int j)
        {
            return this.terrain[i, j];
        }


        public override string ToString()
        {
            string s = String.Empty;
            for(int i = 0; i < this.height; i++)
            {
                for(int j = 0; j < this.width; j++)
                    s += this.terrain[i, j];
                s += "\n";
            }
            return s;
        }

    }


    class LandTerrain : BaseTerrain
    {
        public LandTerrain(int height, int width) : base(height, width)
        {
            this.Initialize(1);
        }


        public void Lakeify(int minx, int miny, int maxx, int maxy, 
            int minlakes, int maxlakes)
        {
            int nlakes = (new Random()).Next(minlakes, maxlakes);

            int h, w;
            Random size = new Random();

            int starty, startx;            
            Random pos = new Random();

            for(int i = 0; i < nlakes; i++)
            {
                h = size.Next(miny, maxy);
                w = size.Next(minx, maxx);

                starty = pos.Next(this.Height - 1);
                startx = pos.Next(this.Width - 1);        

                this.PutLake(new LakeTerrain(h, w), starty, startx);
            }
        }


        public void PutLake(LakeTerrain lake, int starty, int startx)
        {
            for(int i = 0; i < lake.Height; i++)
                for(int j = 0; j < lake.Width; j++)
                    if(starty+i < this.Height && startx+j < this.Width)
                        this.terrain[starty + i, startx + j] = lake.Get(i, j);
        }
    }


    class LakeTerrain : BaseTerrain
    {
        public LakeTerrain(int height, int width) : base(height, width)
        {
            this.Initialize(0);
            this.RoundingLake();
        }

        /// <summary>Primitive way of rounding corners on lake.</summary>
        private void RoundingLake()
        {
            this.terrain[0,0] = 1;
            this.terrain[0, width - 1] = 1;
            this.terrain[height - 1, 0] = 1;
            this.terrain[height - 1, width - 1] = 1;
        }
    }


    class TerrainMain
    {
        [STAThread]
        static void Main(string[] args)
        {
            LandTerrain terrain = null;
            try
            {
                terrain = new LandTerrain(8, 16);
                terrain.Lakeify(4, 4, 4, 6, 2, 4);

                Console.WriteLine(terrain.ToString());
            }
            catch(Exception e)
            {
                Console.WriteLine(e.Message);            
            }
        }
    }
}

There is a small thing which I haven't done. If two lakes are merged the corners does not come out right. However, then you have something to do as well :) See example of this corner thing here...

Code:

1111111111111100000011111
1111111111111010000001111
1111111111111000000000111
1100111111111100000000111
1000011111111110000001111
1000011111111110000001111
1000011111111100000000111
1100111111111100000000111
1111111111111100000000111
1111110001111100000000111
1111100000111110000001111
1111100000111111100000001
1100100000111111000000000
1000010001111111000000010
1000000000111110000000000

Hope it helps, Jacob.

Vano2005 · July 11th, 2005, 12:49 PM

Jacob,
can you please put some comments in your code,
i find it extremely difficult to follow

i didn't get to that level i c++
so i don't know what this means

so can you please put some coments in yourcode on what your doing and why your doing it.

i also found a way to make a desent terrain

first i take a smaller array
2x4 or 4x8

then i load it with randoms 0's and 1's

then i expand it by the factor of 4 or 8;

so that every point on array 2x4
would accupy 4x4 points on the bigger array
example:

2x4
0 0 1 0
0 1 1 0

when expanded to 4x8

0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
0 0 1 1 1 1 0 0
0 0 1 1 1 1 0 0

so 1x1 square now occupies 2x2 square

so when 2x4 is expanded to 8x16
the square areas are at least 4x4
then when matrix is expanded it's easier to cut off some cornes round some edges and make some tiny island or lakes

however i would like to understand the way you do it

thx

vano.

jacob · July 12th, 2005, 09:30 AM

Alright, I have put some comments in the code. Start in the Main method and follow the flow. The Main method makes an instance of a land terrain, and put a number of lakes into it.

Both a land terrain and a lake terrain is considered to be terrain and therefore both classes inherrit BaseTerrain.

Code:

using System;
using System.Collections;

namespace Terrain
{
    /// <summary>Base class for terrains, and a terrain can be both a land
    /// terrain and a water terrain (1 and 0).</summary>
    class BaseTerrain
    {
        /// <summary>Terrain width (land or lake)</summary>
        public int Width
        {
            get{ return this.width; }
        }
        private int width;

        /// <summary>Terrain height (land or lake)</summary>
        public int Height
        {
            get{ return this.height; }
        }
        private int height;

        protected int[,] terrain = null;

        /// <summary>Constructor which construct a terrain. It does not 
        /// initialize the terrain with 1s and 0s, but it initializes the 
        /// size.</summary>
        /// <param name="height">Height of the terrain.</param>
        /// <param name="width">Width of the terrain.</param>
        public BaseTerrain(int height, int width)
        {
            this.width = width;
            this.height = height;

            this.terrain = new int[height, width];
        }


        /// <summary>Puts the value given as argument into every cell in 
        /// the terrain cells.</summary>
        /// <param name="val">The value to put into the cell.</param>
        protected void Initialize(int val)
        {
            // Walking through two dimentional array.
            for(int i = 0; i < this.height; i++)
                for(int j = 0; j < this.width; j++)
                    this.terrain[i, j] = val;
        }


        /// <summary>Gets a value from the terrain.</summary>
        /// <param name="i">y coordinate.</param>
        /// <param name="j">x coordinate.</param>
        /// <returns>Value of the cell.</returns>
        public int Get(int i, int j)
        {
            return this.terrain[i, j];
        }


        /// <summary>To string method. Outputs the terrain.</summary>
        /// <returns>String representation of terrain.</returns>
        public override string ToString()
        {
            string s = String.Empty;
            for(int i = 0; i < this.height; i++)
            {
                for(int j = 0; j < this.width; j++)
                    s += this.terrain[i, j];
                s += "\n";
            }
            return s;
        }

    }


    class LandTerrain : BaseTerrain
    {
        /// <summary>Constructs a land terrain with the dimentions given as
        /// arguments to the constructor. Puts 1s in all cells.</summary>
        /// <param name="height">Height of the terrain.</param>
        /// <param name="width">Width of the terrain.</param>
        public LandTerrain(int height, int width) : base(height, width)
        {
            this.Initialize(1);
        }


        /// <summary>Puts a series of lakes into the terrain, which is 
        /// basically to put another value into some of the cells.</summary>
        /// <param name="minx">Minimum width of the lakes.</param>
        /// <param name="miny">Minimum height of the lakes.</param>
        /// <param name="maxx">Maximum width of the lakes.</param>
        /// <param name="maxy">Maximum height of the lakes.</param>
        /// <param name="minlakes">Minimum number of lakes.</param>
        /// <param name="maxlakes">Maximum number of lakes.</param>
        public void Lakeify(int minx, int miny, int maxx, int maxy, 
            int minlakes, int maxlakes)
        {
            /* Generate a random number between the specified values.
             * The number is the number of lakes to put in the land
             * terrain. */
            int nlakes = (new Random()).Next(minlakes, maxlakes);

            int h, w;
            Random size = new Random();

            int starty, startx;            
            Random pos = new Random();

            // For every lake to create in the terrain...
            for(int i = 0; i < nlakes; i++)
            {
                // Generate a random height.
                h = size.Next(miny, maxy);
                // Generate a random width.
                w = size.Next(minx, maxx);

                // Generate a random y coordinate.
                starty = pos.Next(this.Height - 1);
                // Generate a random x coordinate.
                startx = pos.Next(this.Width - 1);        

                // Puts the random lake into the land terrain.
                this.PutLake(new LakeTerrain(h, w), starty, startx);
            }
        }


        /// <summary>Takes a lake and a position and puts the lake into the
        /// terrain, which is only setting another value in some cells; i.e.
        /// changing 1 to 0.</summary>
        /// <param name="lake">The lake to put in terrain.</param>
        /// <param name="starty">y start coordinate.</param>
        /// <param name="startx">x start coordinate.</param>
        public void PutLake(LakeTerrain lake, int starty, int startx)
        {
            // Go through each row in the lake two-dimentional lake array.
            for(int i = 0; i < lake.Height; i++)
                // Go through each column in the lake array.
                for(int j = 0; j < lake.Width; j++)
                    // If the cell is still inside the land terrain..
                    if(starty+i < this.Height && startx+j < this.Width)
                        /* Change the value of the terrain to the value of the 
                         * lake */
                        this.terrain[starty + i, startx + j] = lake.Get(i, j);
        }
    }


    class LakeTerrain : BaseTerrain
    {
        /// <summary>Constructing a lake terrain, which is an area consisting
        /// of 0s in a two-dimentional array.</summary>
        /// <param name="height">Height of the lake.</param>
        /// <param name="width">Width of the lake.</param>
        public LakeTerrain(int height, int width) : base(height, width)
        {
            // Put 0s in the lake.
            this.Initialize(0);

            // Put 1s back in the corners of the square to make it less square.
            this.RoundingLake();
        }


        /// <summary>Primitive way of rounding corners on lake.</summary>
        private void RoundingLake()
        {
            this.terrain[0,0] = 1;
            this.terrain[0, this.Width - 1] = 1;
            this.terrain[this.Height - 1, 0] = 1;
            this.terrain[this.Height - 1, this.Width - 1] = 1;
        }
    }


    class TerrainMain
    {
        [STAThread]
        static void Main(string[] args)
        {
            LandTerrain terrain = null;
            try
            {
                // Making a land terrain of height 12 and width 25.
                terrain = new LandTerrain(15, 25);

                /* Put between 2 and 14 lakes lakes into the land terrain
                 * where each lake is minimum 4x4 and maximum 12x11. */
                terrain.Lakeify(4, 4, 12, 11, 2, 14);

                // Write string representation of land terrain.
                Console.WriteLine(terrain.ToString());
            }
            catch(Exception e)
            {
                Console.WriteLine(e.Message);            
            }
        }
    }
}

this means the instance of the class you are currently in. Therefore, if you use this in the LandTerrain class it just mean the current object of the class. Do not think about this. It is actually only really relevant in something like this...

Code:

        public BaseTerrain(int height, int width)
        {
            this.width = width;
            this.height = height;
        }

... since you say that the width variable in this class is set to the value given as argument (same name). You explicitly tell that there is a difference.

Jacob.

jacob · July 12th, 2005, 09:34 AM

I might add that I like the though where you make a small representation first and the expand it, since you this way don't get islands.

However, you will get very rough lakes, since single pixel lakes expanded is still a square.

Jacob.

Vano2005 · July 13th, 2005, 11:42 AM

this is a little output demo from my program

first/rough draft
8x16
0110000101100110
1001000011101000
1111101111100100
0011001001100100
0001101101111001
0000000101100000
0000100001000101
1111101101000100

then expanded by factor of 2 and smothed out a little

16x32

00111100000000110011110000111100
01111110000000011111110000000000
11111010000000001111110001000000
11111011100000011111110001100000
11111111100000011111110000100000
11111111110001111111110000100000
00011111110001111111110001100000
00000111100001000111111110100000
00000111110000100111111111000001
00000000000001100111111110000001
00000000000001110111111110000000
00000000000000000111100000000000
00000000000000000111100000010001
00000001100000000111100000010001
11111111100000000111100000010000
11111111110011110011000000110000

also i have this rought edge smother that cuts the corners and does alot of randomization in a bit more detail.

this is the source code for the rough edge smother:

void addDetail (int big [] [], int w, int h)
    {
    intcorner1[][] = {
        {1, 0, 0},
        {1, 0, 0},
        {1, 1, 1}};
    int corner2[][] = {
        {1, 1, 1},
        {1, 0, 0},
        {1, 0, 0}};
    int corner3[][] = {
        {1, 1, 1},
        {0, 0, 1},
        {0, 0, 1}};
    int corner4[][] = {
        {0, 0, 1},
        {0, 0, 1},
        {1, 1, 1}};

    int compare [3][3];

    int similarity1 = 0;
    int similarity2 = 0;
    int similarity3 = 0;
    int similarity4 = 0;


    compare [0] [0] = big [w - 1] [h - 1];//top left
    compare [0] [1] = big [w - 1] [h];
    compare [0] [2] = big [w - 1] [h + 1];//top right
    compare [1] [0] = big [w] [h - 1];
    compare [1] [1] = big [w] [h]; //center
    compare [1] [2] = big [w] [h + 1];
    compare [2] [0] = big [w + 1] [h - 1];//bottom left
    compare [2] [1] = big [w + 1] [h];
    compare [2] [2] = big [w + 1] [h + 1];//bottom right

    for (int i = 0 ; i < 3 ; i++)
    {
        for (int j = 0 ; j < 3 ; j++)
        {
        if (compare [i] [j] == corner1 [i] [j])
            similarity1++;

        if (compare [i] [j] == corner2 [i] [j])
            similarity2++;

        if (compare [i] [j] == corner3 [i] [j])
            similarity3++;

        if (compare [i] [j] == corner4 [i] [j])
            similarity4++;

        }
    }
    if (similarity1 >= 8 || similarity2 >= 8 || similarity3 >=8 || similarity4 >= 8)
    {
        big [w] [h] = 1;
    }
    else if (similarity1 == 0 || similarity2 ==0 || similarity3 ==0 || similarity4 ==0)
        big [w] [h] = 0;
}

this is a very rought copy of it, i'm planning to modify it

so what it basically does is takes a square from the "big" array
and the finds all the surrounding squares making a 3x3 "compare" array where the initial location is in the center

then it compares it to the corner# arrays
if they are axactly the same then the center is turned into "1"
and if they are completely different then the center is turned into "0",
the only way they can be completely different if all 1's in corner# array are 0's in "canpare" array, and if al the 0's in "corner#" array are 1's in "compare" array

the value is stored in "similarity#"
and if "similarity#" is equals to 9 (maximum) then they are similar and if similarity is 0 they are the opposite

however to get some random affects i just change "9"(complete similarity) into something different like >=7 or <=6

that way it randomizes the map but doesn't change it completely