Henry Hatsworth kind of blocks minigame, std::vector sorting or alternative?

Question

I'm not sure if this is the right place to post this, or if I'm doing it right. But I believe I've kept to the rules. If not, please let me know and I'll remove my post or edit it accordingly.

I'm building a mini game that's inspired by Henry Hatsworth and I'm trying to recreate the blocks part of the game. I've rewrote a huge part of it after coming up with a "better" way, but now I'm stuck with a problem I thought would be easier to solve.

My first implementation was a multi-array "grid" that each held a block entity, but at some point I rewrote a huge chunk of it and made each block entity be a thing of its own rather than being tied to a "grid", they could fall collide with each other freely without having to check with a grid system.

So my rework had me use a std::vector instead, saving each block in the field in it, and removing/adding them as they were generated and destroyed. Each frame I loop through the vector and execute each block's think() function.

My problem comes with needing to sort the vector, preferably from lowest x&y to highest. Or am I perhaps missing an easier way? Perhaps there's a way I haven't thought of yet or am unaware of. This is a screenshot of the field

I have two issues with this so far. The first is that I don't really know of a way to match the blocks while using a vector. At least not without very efficiently going through the vector many, many times. Secondly, when I poll through the vector, at some point the blocks are going to be crisscross in terms of x/y positions as making combinations will make other blocks above the ones destroyed fall down.

I have thought of building a grid to place the blocks into, but that will have me going through the vector a lot of times as well. But as I said, perhaps I'm going about this all wrong and I could be doing it much easier, or differently.

Hopefully a better elaboration:

In main.cpp I have a std::vector containing a Block, a Block being an object with its own properties like xpos, ypos, etc. Each Block has it's position on the screen. Each frame I go through the vector and execute each Block's think() function which moves them up on the screen (until they reach a certain position and are destroyed). Now in a grid, the positions are pretty logical. If you have a grid of [8][8] you have a field that's 8 by 8 that you can easily match blocks by doing something as simple as:

int selectedBlockType = block[0][0].type;
if(selectedBlockType == block[0][1].type && selectedBlockType == block[0][2].type){
    // The 3 blocks match, destroy them and mark the blocks above these as "falling"
}

However in the vector you don't really have a grid you can easily reference off of, especially not since the blocks are moving up by 0.1px each frame. So far I've been using colission rects I've named blockBeacon (as seen in block.h), but I'd still have to go through the vector many times to check for colliding collision rects of blocks that are next to each other.

In every frame I do:

// This is defined at the start, before the game loop, but for the
// sake of explanation I'll just include it down here
std::vector<block> blocks; // This holds our blocks I erase and push other blocks into

// Loop through the vector
for(int i = 0; i < blocks.size(){
    blocks[i].think();
}

Then a bit further down, I'd use:

// Pass through the vector containing all the blocks in the field
fieldManager.pollField(blocks);

Which is where my problem would be I don't actually know how to efficiently (without going through the vector many times) see if the blocks are next to each other. I hope this better explains my issue.

The noteworthy files explaining my problem are main.cpp and fieldmanager.cpp. entity.h and block.h/cpp may also help better understand what I'm doing. (I'd link them but apparently I need more rep to be able to post more than 1 link, so I included my GitHub URL below.)

The entire source of the project is at my github: https://github.com/AeriusOhara/legend-of-elements/tree/master/legend-of-elements I apologize in advance if the codebase is terrible, I'm self-taught and still learning (tips or criticisms are always welcome though!)

Answer 1

From your question I think you want a way to efficiently access a block's neighbours vertically.

I'm not sure why you decided you want a std::vector instead of a grid made of a 8x8 array (you know you can iterate through every block in an array too), but I think the array is the better choice. If you really want to use a std::vector, then you may want to sort all the blocks by x-coordinate, then y-coordinate and you will actually now end up with a grid, where you have block[x][y] = vector_name[x + y*blocks_per_line]. With a decent sorting algorithm like quicksort you can do this every frame incredibly fast. If you don't want to sort them, then the only way is to iterate through all of them.