Generating Grid Algorithm

Hello,

Currently creating a randomly generated "top-down" viewed map of a city. Where you get to set a X and Y value, and set a density, and that'll tell how many buildings you want in the city, and for the city generation I created a algorithm.

• Get X, Y, and Density value, set by myself
• Run through two loops, X and Y, and instantiate 'something'
• that "something" is based on the density... For example, a Density of 0.5 will yield a 50% of generating a building or generating nothing
• Then it'll get that building or empty lot and do a check if it can fit
• If it can't fit, find another piece that can fit, otherwise instantiate that building.

Here the actual code, if you want to see

Spoiler: Grid Building

Code (CSharp):

1. public void GenerateCity(int _height, int _width, float _density)
2.     {
3.         ClearCity();
4.         GameObject temp = null;
5.  
6.         for(int x = 0; x < _width; x++)
7.         {
8.             for (int y = 0; y < _height; y++)
9.             {
10.                 float randDensity = Random.Range(0f, 1f);
11.                 int randBuilding = Random.Range(0, buildings.Length);
12.                 int randEmpty = Random.Range(0, empty.Length);
13.                 bool putEmpty = false;
14.  
15.                 if (randDensity <= _density)
16.                 {
17.                     if (isValidPlacement(buildings[randBuilding].GetComponent<Building>().gridPositions, x * offset, y * offset, _height, _width))
18.                         temp = Instantiate(buildings[randBuilding], new Vector3(x * offset, y * offset, 0f), Quaternion.identity) as GameObject;
19.                     else
20.                         putEmpty = true;
21.                 }
22.                 else
23.                 {
24.                     if (isValidPlacement(empty[randEmpty].GetComponent<Building>().gridPositions, x * offset, y * offset, _height, _width))
25.                         temp = Instantiate(empty[randEmpty], new Vector3(x * offset, y * offset, 0f), Quaternion.identity) as GameObject;
26.                     else
27.                         putEmpty = true;
28.                 }
29.  
30.                 if(putEmpty)
31.                 {
32.                     foreach (GameObject e in empty)
33.                     {
34.                         if (isValidPlacement(e.GetComponent<Building>().gridPositions, x * offset, y * offset, _height, _width))
35.                             temp = Instantiate(e, new Vector3(x * offset, y * offset, 0f), Quaternion.identity) as GameObject;
36.                     }
37.                 }
38.  
39.                 temp.transform.parent = this.gameObject.transform;
40.             }
41.         }
42.         temp = null;
43.     }
44.  
45.     private void ClearCity()
46.     {
47.         foreach(Transform g in transform)
48.             Destroy(g.gameObject);
49.     }
50.  
51.     private bool isValidPlacement(List<Vector2> _v, float _xOff, float _yOff, int _h, int _w)
52.     {
53.         int counter = 0;
54.  
55.         foreach (Vector2 v2 in _v)
56.         {
57.             RaycastHit2D hit = Physics2D.Raycast(new Vector2(v2.x + _xOff, v2.y + _yOff), Vector2.down, 0.01f);
58.             if (hit.collider == null)
59.                 if (v2.x + _xOff < (_w * offset) && v2.y + _yOff < (_h * offset))
60.                     counter++;
61.         }
62.  
63.         if (counter == _v.Count)
64.             return true;
65.  
66.         return false;
67.     }

HOWEVER, this is where the main part of the question lies...
If you view my code, the function "isValidPlacement" uses Vector2 locations and checks a raycast to see if anything is there

And these Vector2 values come from this script that is placed in each building tile.

Spoiler: Hard-Coded Vector2

Code (CSharp):

1.  public List<Vector2> gridPositions
2.     {
3.         get
4.         {
5.             BoxCollider2D c = GetComponent<BoxCollider2D>();
6.             float x = c.size.x;
7.             float y = c.size.y;
8.  
9.             List<Vector2> temp = new List<Vector2>();
10.             if (x == 0.32f && y == 0.32f)
11.             {
12.                 temp.Add(new Vector2(0.16f, 0.16f));
13.             }
14.             else if (x == 0.32f && y == 0.64f)
15.             {
16.                 temp.Add(new Vector2(0.16f, 0.16f));
17.                 temp.Add(new Vector2(0.16f, 0.48f));
18.             }
19.             else if (x == 0.64f && y == 0.32f)
20.             {
21.                 temp.Add(new Vector2(0.16f, 0.16f));
22.                 temp.Add(new Vector2(0.48f, 0.16f));
23.             }
24.             else if (x == 0.64f && y == 0.64f)
25.             {
26.                 temp.Add(new Vector2(0.16f, 0.16f));
27.                 temp.Add(new Vector2(0.16f, 0.48f));
28.                 temp.Add(new Vector2(0.48f, 0.16f));
29.                 temp.Add(new Vector2(0.48f, 0.48f));
30.             }
31.             return temp;
32.         }
33.     }

As you can see in the code, I "hard-coded" the position, so for example if a sprite is (0.32,0.32), it'll use the position (0.16,0.16), which is the center point, and this will work for (32,64) [essentially 2x1 tiles, and so on]

HOWEVER NOW THIS IS WHERE THE ACTUAL QUESTION LIES
Is there a certain Algorithm that I can implement that will locate center points of certain sprites based on a size, So if I have an irregular L-shaped sprite it can cut it into 3 piece and located the center points of those?

TL;DR Is there an algorithm that cuts a sprite into separate blocks, then returns the center points. Here's a picture to illustrate this

 

Are all your shapes going to be 32x32 blocks just stuck together?
If the answer to the above is yes, How many different shapes do you think you'd realisticlly want in your game. (1x1, 1x2, 2x1, .... 3x3 } etc?
Whats the largest AxB size for A and B?
How likely do you think it is that the code needs to be extensible for larger AxB sizes?

As with many things cases in programming, having a firm grasp on your design is necessary to implement the best coding. I'm not saying you don't, but the rest of us don't know what your design is so it would be hard to suggest a best approach.

 

Yes, every tile will be 32x32 stuck together like so...


So the problem is, to place a piece I'm checking if the position is taken or not, but to do that I want to divide pieces into 32x32 and then get the center of the piece, then do a raycast from that center position.

If there's a better or efficient way, I'd love to know, otherwise this is the way I went with.

 

Sounds like most of your tiles will be fairly small in 32x32 terms. I think the following implementation is probably easiest if say everything is 5x5 or smaller (160x160).

Create a class that has all the information about these buildings you need + the following:

1. bool[,] footprint = new bool[5,5]; // this will hold true false if the building has a square in that spot or not. So a 5x5 buidling would be all true. a 1x1 square would have footprint[0,0] = true, and the rest is false;
2. int x,y position into a grid defined below.
3. int baseX,baseY. This is an index into footPrint that holds the base square of this object. Almost always this will equal 0,0. However, imagine a cross shape. footprint[0,0] = false for a cross. So you BaseX = 0, but BaseY = 1. This is going to make it easier to place buildings later.

Now you make an Array to hold all these objects:

Code (CSharp):

1. BuildingObject[]  buildings;

As you create more buildings put them in this array.

Now you need a two dimensional array this going to be your entire Area. One square of this grid will be a single 32x32 block:

Code (CSharp):

1. int[,] grid = new int[Width,Height];  // total map area

Whenever you place a building onto the map, you map its footprint onto this grid. You set the grid value equal to the buidlings index into buildings array.
For example lets say the 3rd building you create (buildings[2]) is a 2x1 tile. (64x32). its going to be put at position 4,5. You would then set:
grid[4,5] = 2 grid[5,5] = 2;

Now you intitalize grid[,] to all -1. Then when you want to place a building you just check its entire footprint (all the trues) versus the grid and if its all -1 you can place it. If you get any number that isn't -1.. that means a building is already there.

Now you don't have to worry about any code to figure out center of sprites and all that. Just wrote a function to correctly set an Buildings footprint (the correct shape it is) and method to check grid based on that footprint and its base Location If you need help with that let me know. This method should handle any irregular shape you want.

The footprint array is a fairly naive approach, but it will work well with buildings of small tile width/height . If you were working with things that could be 100x100 tiles.. having every object have a 100x100 boolean array would get out of hand. But i suspect for you purposes it should work fine.

 

Thanks Takatok, definitely lots of information here, I'll try to implement this later and get back to you if I have any questions!

Truly appreciate it, cheers!