So, I created a grid using a list. No problem. However, when it comes to manipulating the grid the way I need it's become a bit of a hassle and i'm looking for opinions on the best way to handle this. Here are my requirements for my grid:

1. Layout a grid that is 20W X 30H, however the screen will only display 20W X 15H.

2. We will be spawning bricks, but I only want them to spawn off screen. I've figured out how to do that, but if I change the structure, it's important that I retain that ability.

3. The first brick will spawn anywhere in the offscreen section of the grid. After that, each brick will spawn so that it has at least one adjacent brick that it is touching.

4. When a brick spawns, I need to somehow remove that grid space from the list of available brick spaces so that it doesn't try to put 2 bricks in the same location.

3 and 4 are the ones I'm having trouble with. I started working with just a list and had bricks spawning off screen the way I wanted but they were simply scattered. The problem with the list is that when I spawn a brick, i simply remove that entry from the list. Well then I have nothing to check against to see if there are any adjacent bricks.

Someone suggested using a 2D array because it would be more efficient than a list and easier to check if bricks were touching. I had another person suggest using 2 lists and 2 2-dimensional arrays to cover all bases, but this seems a bit heavy handed to me. I also had a friend suggest using hash tables, which I have not used before, but after reading about them they also seem like a viable answer. I'm just wondering if anyone has any ideas or suggestions on the best way to keep this as lightweight as possible while still getting the work done. Thanks!

Using a 2 dimensional array isn't heavy handed, what I meant was heavy handed was the example someone gave to me was to use 2 2d arrays AND 2 lists, so four of these things all together. Seems like a bit much. Here is what I'm worried about with a 2D array. Once we get down to the point where there are only 1 or 2 bricks left to place, how much of a performance hit is it going to be when it's randomly selecting locations for bricks and keeps hitting spots that are already taken. So it's generating a random number, then checking to see if it's ok, then trying again. It seems like this could be a pretty good performance hit. While with the list, I can simply take away from the list so the only options it has are valid, but then that leads me to the issue I mentioned above about how to then check for adjacent bricks.

Sorry. Didn't see the C#, Unity tag. This can easily be converted should you desire. Best of luck.

OK; this was a quick few minute mock-up and just an idea... I did not test this, add validation, const correctness, etc. Strictly just a mock-up. With that being said, I don't see the problem with a 1D array. It can easily be done for the entire grid as well as only the visible portion of the grid.

Here are a few simple structures that could define the game tile as well as the grid cell. The idea with the grid cell is to have an occupied flag. When you go to place a tile, query a cell, etc. then you can easily see if there is a tile placed there already. Another nice thing is if you want to remove a tile. When you remove a tile you can simply set the occupied flag to false to allow a new tile to be placed there.

struct GameTile
{
    //--Tile POD implementation
};

struct GridCell
{
    bool Occupied;
    GameTile Tile;
};

Here is an example class showing the basic concept of working with the grid. Of course you can set your access modifiers however you want:

class Grid
{
private:
    const static int GRID_ROWS = 30;
    const static int GRID_COLUMNS = 20;
    const static int SCREEN_GRID_ROWS = 15; //--The number of visible rows on the screen. This should, of course, be
                                            //--less than the number of GRID_ROWS

    GridCell cells[GRID_COLUMNS * GRID_ROWS] = { 0 };

public:
    GameTile GetCellTile(int x, int y)
    {
        return cells[GetCellIndex(x, y)].Tile;
    }

    void SetCellTile(int x, int y, GameTile tile)
    {
        cells[GetCellIndex(x, y)].Tile = tile;

        SetOccupied(x, y, true);
    }

    void RemoveCellTile(int x, int y)
    {
        //--No need to actually remove anything... just set the cell as unoccupied.
        SetOccupied(x, y, false);
    }

    bool CellIsOccupied(int x, int y)
    {
        return cells[GetCellIndex(x, y)].Occupied;
    }

    void SetOccupied(int x, int y, bool occupied)
    {
        cells[GetCellIndex(x, y)].Occupied = occupied;
    }

public:
    void AutoPlaceTile(int x, int y, GameTile tile)
    {
        if (!CellIsOccupied(x, y))
        {
            SetCellTile(x, y, tile);

            return;
        }

        //--Add logic to check neighbor tiles and place new tiles
    }

private:
    //--This will give you the index for the entire array
    int GetCellIndex(int x, int y)
    {
        if (x < 0 || x > GRID_COLUMNS)
        {
            //--Handle this
        }

        if (y < 0 || y > GRID_ROWS)
        {
            //--Handle this
        }

        return y * GRID_COLUMNS + x;
    }

    //--This will only give you the index to tiles visible on the screen.
    //--I'm guessing that the non-visible cells are all above the visible cells.
    int GetScreenCellIndex(int x, int y)
    {
        auto screenY = SCREEN_GRID_ROWS + y; //This needs tested...

        if (x < 0 || x > GRID_COLUMNS)
        {
            //--Handle this
        }

        if (screenY < 0 || screenY > GRID_ROWS)
        {
            //--Handle this
        }

        return screenY * GRID_COLUMNS + x;
    }
};

I hope this will help give you an idea or two so you can finish your implementation. I don't know exactly how you want your blocks to flow, but with this it should be relatively easy to perform the auto tile placement logic.

@Rutin no I'm not seeing a performance issue now, but this is the first part of the game that I am coding and it's the core piece that almost everything else will be based around. The point of me being worried about it now is to make sure that it gets coded correctly now, so I don't have to try to come back and fix it later. I think I've gathered enough information to figure out what I'm going to do. I've got about a hundred different ways this can be done, but I've decided to just go with a way that makes the most sense and seems the most simple to me. So I'll use that and see what it gets me. Thanks for the help!

4 hours ago, Rutin said:

I personally would never use anything one-dimensional when representing a grid layout, I would use a 2D Array or a dynamic container type if needed.

If you're just wanting to spawn bricks in a 20x30 grid, you can use either a 2D Array, or a 2D List.

There are many ways to toggle available spaces, you can simply use a 2D List that holds an object type representing a tile, and can contain a boolean for set or not set, as well as anything else regarding that tile. You can also have a secondary 2D Array that contains 0 for empty, and 1 for occupied. Once you have this set it's extremely easy to check for adjacent spots to confirm if tiles are set or not. Example: myMap[y][x].isSet() or if you're using another Array: if myMap[y][x] == 0 { }

I'm the complete opposite, I never use 2d arrays.

They're terrible for cache and any code you write to access them ends up being written in reverse order anyway so any semblance or clarity they have is lost. I usually just wrap a 1d array in code to access it that gives it a simple to understand interface. Avoids all the previous problems and has clarity.

56 minutes ago, Rutin said:

I look at 2D Arrays as so : Map[Col][Row] its very easy to read...

In memory Map[2][3] would be:

[0,0], [0,1], [0, 2], [1, 0], [1, 1], [1, 2]

So if you loop left to right in columns you'd actually be jumping by using [x][y] -> [col][row].

Which quickly gets confusing, though you can make it work if you reverse everything.

If you use something like a vector of vectors though then the cache problem is major since you'll be jumping between elements that are probably in completely different sections of memory. In the case of containers like that a single container is much more effective.

In either case your average person would expect Cartesian coordinates for the style of a grid, i.e. : [x, y]. Which is probably what you should stick to, but that means adding wrapper code to your array or accessing everything backwards, including in loops.

Well, I say Cartesian, in reality its more common to address grid maps from top left and moving right and down, but you get the idea.