Jump to content


Member Since 14 Dec 2013
Offline Last Active Mar 06 2017 09:48 AM

Topics I've Started

Creating rectangles with contiguous filled grid cell

25 June 2015 - 11:06 AM

Hi. I'm currently trying to find a solution to a grid filling problem. Unfortunately, i'm having trouble imagining the implementation.


I will explain. In a 2D grid, a cell can be filled or not. I need to retrieve the total number of contiguous rectangles that can be formed by the filled regions. I'm fairly sure what i'm looking after have a name, but it's hard to google it without the proper name.
I have attached an image of what i mean at the end of this post.


Currently, i have a double for loop for each rows and each columns. I remember the amount of "widths" of consecutive filled cell of the last row and if the current row have the same "widths" at the same place, i add one to that width height. But this is where i'm stuck, i can't find the rest of the logic.

// This function will calculate the number of void zone and store it in mVoidZones
void MapManager::CalculateVoidZones()
    // array of rectangle (X, Y, W, H).

    std::vector<SDL_Point> lastcorners;
    std::vector<int> widths;
    std::vector<int> heights;

    // scan a col. 
    for(int col = 0; col < mInfo->GetCol(); col++)
        // remember the current width a consecutive void state.
        int width = 0;
        SDL_Point lastcorner = SDL_Point();
        lastcorner.x = -1;
        lastcorner.y = -1;

        // scan a row.
        for(int row = 0; row < mInfo->GetRow(); row++)
            // fetch if the cell is "filled"
            if(GetTile(row, col)->IsState(STATE_TILE_VOID))
                // add a corner
                if(lastcorner.x == -1 && lastcorner.y == -1)
                    lastcorner.x = col;
                    lastcorner.y = row;
                    width = 1;

                // increment the current width
                else if (lastcorner.x == col - 1)

            // a gap is found. Close the current width.
            else if(width > 0)

                lastcorner.x = -1;
                lastcorner.y = -1;
                width = 0;

    // TODO this function is incomplete.
    // It is missing the "corner" comparison, then adding the height 
    // then creating the rectangle and pushing it to mVoidZones.

Take note that the grid can be massively scrambled or even checkered, creating a huge number of small rectangles.


As always, thank you for your time. I will continue searching in the meantime.

How should i process about embedding a SDL2 game into QT to make a level editor.

28 November 2014 - 11:32 AM

Hello everyone.


The video game engine i'm working on is amost complete. Right now i'm working on refactoring part i don't like. One of the part i do not like is the current level editor.

It's currently a seperate window that have the basic fonctionality (see screenshot). So i wants to make everything nicer and do a level editor using QT.


I want to make a basic QT Dialog that have embedded inside the game engine. However, i'm very confused about how i should do it. Right now, i'm struggling to make SDL2 work within QT and i'm not even sure if it's the right approche i'm doing. I'm currently able to draw with SDL2 within QT, but i really don't know how to make my game work inside.


Some detail: i'm using QT 5.3.x via Vs2012 (not qteditor). My game engine is an executable that use SDL2 for graphic, sound and key inputs. I've heard i might have problem with graphic rendering and sound, so i'm hesitant on how to proceed. Should i make my game engine a DLL to run within QT or is a .Exe okay? If more information is needed, i will give it.


As always, thank you very much for your time.

ps. Sorry for my english.


Culling points from a polygon.

28 August 2014 - 10:01 PM

Hello everyone,


i am currently experiencing a problem figuring an algorithm to remove unneeded points from a polygon structure. Normally i wouldn't consider posting here, but this one got me stumped for quite a while.


So here is the problem:


I have a std::vector of a Point structure that form a convexe polygon.

Somes of the points in the vector may be not needed and could be removed without changing the shape of the polygon.

I need to figure out how to remove thoses unneeded points.

I have attached a picture representating this array of points.
As you can see, two point can be removed without changing the shape of the polygon (50,0 and 50,50)


Here is more informations:

The polygon will always be contained within a known range (xmin to xmax, ymin to ymax).

A point always have X or Y equals either known min-max value (can be both). So if xmin = 0, xmax = 100, ymin = 0, ymax = 50, the point (25,25) is impossible.

The polygon is not always a simple square or rectangle and can be anything convexe (Trapeze, triangle, losange, etc...).

The array will always be sorted clockwise but the first point is not always 0,0.


Here is what i already tried to solve this problem:

I tried looking for points in the middle of a side and removing them . I think the idea is good, but my logic is faulty, though.
This algorythm work for a simple rectange but fail with anything more complexe, like a trapeze.

void Cull( std::vector<CVector> &_vertices, float _xmin, float _ymin, float _xmax, float _ymax )
    // Work for a simple square or rectangle, but fail for anything else like a trapeze.
        CVector lastvalidx = _vertices[0];
        CVector lastvalidy = _vertices[0];

        for(unsigned i = 1; i < _vertices.size();)
            int n = i + 1 < _vertices.size() ? i + 1 : 0; // next point

            //Remove any point that is in the middle of a plane
            if( ( (_vertices[i].x != lastvalidx.x && (_vertices[i].x != _xmin && _vertices[i].x != _xmax) ) ||
                (_vertices[i].y != lastvalidy.y && (_vertices[i].y != _ymin && _vertices[i].y != _ymax) ) ) )
                //remove the point, since it is not needed.
                _vertices.erase(std::remove(_vertices.begin(), _vertices.end(), _vertices[i]), _vertices.end());
               lastvalidx = _vertices[i];
               lastvalidy = _vertices[i++];


If you would take a look at my problem, i will be thankful. I will continue trying to solve it on my side in the meantime.
I really hope my problem is not too confusing to understand. If more information is needed, i will post it.
As always, thank you very much for your time.

My physic engine is done, but i'm still not satisfied. Physic book related.

02 June 2014 - 11:21 AM

Hello everyone.


On and off for the last 6 month, i've worked on my 2D physic engin directly integrated in the game i'm working on.
I have gone through several iteration, each one being better and better than the last one.


The current build is "acceptable", which mean it have every features that will be in my final game, like polygonal collision detection and resolution, slopes, rotating bounding boxes, skeletal anchors and more. It is by no means perfect. I am aware of a couple bugs here and there.


But i feel i can do better, more optimized or just more robust. I've read a lot of tutorial on the web to achieve everything so far, but i think i've come to a point where i need to read a good 2d physic book to make my engin better and better.


I have done some research to find good books, but everything i find so far have 3d physic as the main focus. The few 2d book i have found don't have a lot of reviews or have somes bogus reviews.


Would you recommend a good 2d physic book?
I am looking for an advanced book.


Thank you very much for your time.

Is this commenting macro safe to use?

22 May 2014 - 10:18 PM

Hello everyone.


I'm using a simple macro to comment out part of my code in release build, but i'm wondering if this could lead to some sort of problem, as i'm trying to cheat the precompiller into adding comments against the rule.


I use this to avoid writing duplicated code.


Basically, here is the macro

#if defined DEBUG
#define MACRO 
#define MACRO );/ ## /

What it does is: If i'm in debug build, it does nothing. If i'm in release build, it close a function and comment the rest of the line.

The "/ ## /" part is needed to trick the compiler into thinking comment dont exist. But they do.


This is how i use the macro. (The code is simplified)

//Initialize a long list of interfaced classes into a map, allowing easy Factory access.
void Bar()
    //Assume each different letters is an interfaced class
    Foo(A0, A1 MACRO, A2, A3, A4);
    Foo(B0, B1 MACRO, B2, B3, B4);
    // Many Foo later...
    Foo(Z0, Z1 MACRO, Z2, Z3, Z4);

#if defined DEBUG
//Types don't really matter. Just the number of parameters is interesting.
void Foo(Type0, Type1, Type2, Type3, Type4)
    // Do something, in debug
void Foo(Type0, Type1)
    // Do something, in release

As you can see, in release build, the compiler will see "Foo(A0, A1 );" as the comment will clear the rest of the line.
This way, i avoid writing this code:

#if defined DEBUG
Foo(A0, A1, A2, A3, A4);
Foo(B0, B1, B2, B3, B4);
// Many Foo later...
Foo(Z0, Z1, Z2, Z3, Z4);
Foo(A0, A1);
Foo(B0, B1);
// Many Foo later...
Foo(Z0, Z1);

The reason i use it is to avoir writing duplicate code to avoid possible Copy/Paste errors.

As of writing this post, the macro work fine in either build, but i have this strange feeling i'm doing something cringe-worthy.


Am i really going overboard just to avoid writing duplicated code?

If so, is there other options?