Hello.

Currently and ~third week of me doing collision, and it isn't turning out as i hoped for.

The basic idea is simple:
1: Check if player somehow issues for unit to move

2: If unit is issued to move calculate movement rate using delta time and units movement speed

3: Check if the position unit wants to move is walkable and store position

4: If the position is not walkable do pixel perfect collision and store position

5: Move unit to position

Done!, right that was simple.

Doing this in code is all fun and games but it hurts getting unexpected results time after time...

i am storing unit position in float, unit movement is in floats so i can increase and decrease its movement speed by those little amount and still make it visible.

I am trying to achieve so i can have many units on map just minding their business.

I have units and i can make them wonder linear direction once (500+rand()%500) milliseconds, and its hauling massive amount of units at low cpu usage (2000+ units to get 2-3% cpu usage) the issues starts when i add collision detection for each movement.
Performance drops drastically and i am pretty sure i am doing collision wrong, collision i am checking for is just getting unit position it is gonna move to and then checking is tile/tiles walkable (its just a boolean that tile class holds and is of course true if walkable false if solid)(1-4 tile checked) if the tiles checked 1-4 any are walkable==false i don't allow movement.

Somehow i don't like the performance i am getting and i am looking for some kind of nourishment because i am procrastinating this and it is really holding me back.

I am feeling i need to progress to higher difficulty but the "beast" is overcoming me ATM.

Anyway i am doing 2d, tile based, top down view, survival game its gonna be nothing special but in order to learn i need to do new stuff and doing real time movement with collision detection is one of those so any suggestions are greatly appreciated!

What i am asking for is, how did you deal with a issue that you couldn't figure out?

I am probably right now just writing so i don't go back to pen and paper and think how else i could handle movement to get better performance, after all i want to add little more AI logic in there and for it to still work on low end computer, but its out of my reach for the moment.

I always deal issues I have the same way: "Someone must have had this problem before, let's google it" and although sometimes it takes more than the first hit (or search term because of different terms used) to figure out the answer, it's almost always been an issue for someone and the answer is right there.

I find that a lot of people seem to think their problem is unique (not saying you're saying that :P), but it is very very likely the issue has already been resolved in multiple ways and a simple google search is all that is needed.

In your case, simply google "2D collision detection" and your programming language of choice or perhaps even just the API, you'll probably end up with some answers you don't need because it's not fast. Google "Fast 2D collision detection" or something similar and keep refining until you get what you need.

Want to do it all by yourself? Re-invent the wheel and such. Make a clear overview of what exactly you are doing and what exactly you want to achieve. Ask questions to yourself. First thing that comes up in my head when thinking about collision detection: "Does the object on the top left of the screen really need to know about the one in the bottom right corner, considering they're not going to collide before the one right next to me, perhaps I could divide the screen in regions/grid and do the checks in there"

Things like this come easier with practice and experience. Don't try to re-invent the wheel because you think it's better if you come up with everything yourself because mostly (not always!) when you're just starting, it will not be the best solution and better/more common solutions are right there in front of you if you did that simple google search.

Good luck! :)

What i am asking for is, how did you deal with a issue that you couldn't figure out?

I break the issue into smaller issues. Repeat until each issue is solvable.

For a performance issue this often requires taking lots of measurements. Once you have isolated it to an area, take more measurements. Repeat until the measurements isolate the problem. If necessary, brainstorm with others who have more experience to help identify causes and solutions.

I have units and i can make them wonder linear direction once (500+rand()%500) milliseconds, and its hauling massive amount of units at low cpu usage (2000+ units to get 2-3% cpu usage) the issues starts when i add collision detection for each movement.

Without knowing more about the problem, my first guess is that you are testing too many objects.

Are you testing against every object globally, or are you limiting testing only against the objects that are nearby? A loose quadtree can help there.

If you are testing against only the local objects, use a profiler to see which functions are slow or are too-frequently called, then take steps to fix them.

Also, are you testing collision each and every frame? This may be unnecessary if movement logic and path-finding take place at tile-level granularity. For example, if an entity always walks fully onto a tile or not at all, even if the movement is animated over several frames, you only need to check for collision once for each movement, not for every frame in between.

What kind of pathfinding are you using? (from your post it seems like you're using basic, two point, linear interpolation)

What kind of collision detection are you using? (from your post it seems like you're want to use pixel-by-pixel/per-pixel collision detection)

Consider the differences between collision detection and collision response.

1: Check if player somehow issues for unit to move
2: If unit is issued to move calculate movement rate using delta time and units movement speed
3: Check if the position unit wants to move is walkable and store position
4: If the position is not walkable do pixel perfect collision and store position
5: Move unit to position

You probably need to set the current tile to walkable and the destination tile to !walkable after your first step. Considering your only collision detection is a boolean on a tile, you need some kind a collision response for that. This could be done by placing the unit on an adjacent tile, if the destination is !walkable. Alternatively, if you want "pixel perfect collision", you should implement real collision detection and response, and only use the tile system for pathfinding.

I'm sorry I didn't really answer you're question about why your losing performance, but without more information and/or the actual source code, it is impossible to say.

Somehow i don't like the performance i am getting and i am looking for some kind of nourishment because i am procrastinating this and it is really holding me back.

how many units, and whats your fps?

So to describe more about my collision.

Units and tiles are size of 32 pixels in height and width.

Units each (500+rand()%500) get to pick action. If their last action is not finished they will continue doing current action.

When action is done a bool(isActionDone = true) marking for next unit loop that unit can take new action.

When unit acts it does following

moveDirY = rand()%4;//0 = noDir, 1 = up, 2 = down, 3 = noDir
moveDirX = rand()%4+2;//2 = noDir, 3 = left, 4 = right, 5 = noDir
if(moveDirY == up)
moveAmountY = -(rand()%96 + 32);
else if(moveDirY == down)
moveAmountY = (rand()%96 + 32);

Same occures for X movement and in case of noDir moveDir is set to 0 at begining of the loop.

Then units "move();" function is issues

allTypes toPositive(allTypes num)
{
if(num < 0)
    num *= -1;
return num;
}
 
bool Map::CheckTileWalkable(float posX, float posY);//returns true if tile is walkable
//I will explain about this later
 
moveAmount = unitMoveRate * deltaTime;
 
if(toPositive(moveAmountY) > 0)
{
if(objMap.CheckTileWalkable(unitPosX, unitPosY + moveAmount) == true)
    unitPosY += moveAmount;
}
//Same occurs for X except for X values

Now for the map collision detection witch i think is the problem in my case.

There are four cases i need to check before execute.

1:

if(int(unitPosX)%TILE_SIZE/*32*/ == 0) //Checking if units X is directly only one tile if so check only 1 tile vertically, if false check 2 tiles vertically.

2: same as case 1 except checking for y

3:There is a bool(bool isWalkable = true) and from above code we can see witch tiles to check so the cases for tile check is

x=1 y=1, or x=2 y=1, or x=1 y=2, or x=2 y=2.
So i have 1D array of tiles that is stored in vector

for(int y = 0; y <= tilesToCheckY; y++)
{
    for(int x = 0; x < tilesToCheckX; x++)
    {
        if(mapVec[(unitPosX%TILE_SIZE)+x + (((unitPosY%TILE_SIZE)+y)*mapSizeX).isWalkable == false)
            isWalkable = false;
    }
}
return isWalkable;

IMO i am looking for a better way to provide illusion of units just wandering around map from time to time, and from the posts i read there was one great idea.

Check collision only once and store a path, then move unit along that path. This will be my next step i will attempt.

NOTE:: Not actual code, i do not have my project on this harddrive atm, i will update if i get huge desire to do so.

Somehow i don't like the performance i am getting and i am looking for some kind of nourishment because i am procrastinating this and it is really holding me back.

how many units, and whats your fps?

Do note i am not ignoring, but my hard drive is out of my reach at the moment i will post as soon as i have it.

EDIT:: Posting the code in case someone will need it

The following code is for unit getting random movement direction on X and Y and moving according to data stored in class.]

Pixel perfect collision included, if you are struggling.. ^^ feel free to use it.

//.h
class AI
{
public:
    AI(int & dt, Map & objMap);
protected:
    void LoopAI(BaseUnitForMap & objUnit);
    void MoveDecidePosition();
    void MoveExecute();
    void MovePixelPerfectX();
    void MovePixelPerfectY();

private:
    int & dt;
    BaseUnitForMap * objUnitptr;
    Map * objMap;
    int toPositive(int num);

    int moveAmountX, moveAmountY;
    bool isSprinting;
    bool movePixelPerfectX, movePixelPerfectY;
    int tempI;
};
 
//.cpp
void AI::MoveDecidePosition()
{
    int directionY = rand()%4;//Decide 0 nowhere, 1 up, 2 down, 3 nowhere
    //int directionY = 2;//Decide 0 nowhere, 1 up, 2 down, 3 nowhere
    int directionX = rand()%4+2;//Decide 2 = nowhere, 3 left, 4 right, 5 nowhere
    //int directionX = 0;//Decide 2 = nowhere, 3 left, 4 right, 5 nowhere
    if(directionY == en::Dirrection::up)
    {
        objUnitptr->moveAmountAIY = rand()%64+16;
        objUnitptr->moveDirY = en::Dirrection::up;
    }
    else if(directionY == en::Dirrection::down)
    {
        objUnitptr->moveAmountAIY = rand()%64+16;
        objUnitptr->moveDirY = en::Dirrection::down;
    }
    if(directionX == en::Dirrection::left)
    {
        objUnitptr->moveAmountAIX = rand()%64+16;
        objUnitptr->moveDirX = en::Dirrection::left;
    }
    else if(directionX == en::Dirrection::right)
    {
        objUnitptr->moveAmountAIX = rand()%64+16;
        objUnitptr->moveDirX = en::Dirrection::right;
    }
    //if(directionX > 0 && directionY > 2)
    objUnitptr->acting = true;
}

void AI::MoveExecute()
{
        //Horizontal
        if(objUnitptr->moveDirX == en::Dirrection::left)
            moveAmountX = -objUnitptr->movementRate * dt;
        else if(objUnitptr->moveDirX == en::Dirrection::right)
            moveAmountX = objUnitptr->movementRate * dt;
        else
            moveAmountX = 0;
        //Vertical
        if(objUnitptr->moveDirY == en::Dirrection::up)
            moveAmountY = -objUnitptr->movementRate * dt;
        else if(objUnitptr->moveDirY == en::Dirrection::down)
            moveAmountY = objUnitptr->movementRate * dt;
        else
            moveAmountY = 0;
    
//Move X
    if(moveAmountX != 0)
    {
        if(objMap->CHECKOutOfBounds(objUnitptr->posX + moveAmountX, objUnitptr->posY) == false)
        {
            //std::cout<<"pass1"<<std::endl;
            if(objMap->CHECKWalkable(objUnitptr->posX + moveAmountX, objUnitptr->posY) == true)
            {
                //std::cout<<"pass2"<<std::endl;
                objUnitptr->posX += moveAmountX;
                movePixelPerfectX = true;
            }
            else if(movePixelPerfectX == true)
                MovePixelPerfectX();
            //else
                //std::cout<<"Coll1"<<std::endl;
        }
        else if(movePixelPerfectX == true)
                MovePixelPerfectX();
        //else
            //std::cout<<"OOB1"<<std::endl;
    }

//Move Y
    if(moveAmountY != 0)
    {
        if(objMap->CHECKOutOfBounds(objUnitptr->posX, objUnitptr->posY + moveAmountY) == false)
        {
            if(objMap->CHECKWalkable(objUnitptr->posX, objUnitptr->posY + moveAmountY) == true)
            {
                objUnitptr->posY += moveAmountY;
                movePixelPerfectY = true;
            }
            else if(movePixelPerfectY == true)
                MovePixelPerfectY();
            //else
                //std::cout<<"Coll2"<<std::endl;
        }
        else if(movePixelPerfectY == true)
                MovePixelPerfectY();
        //else
            //std::cout<<"OOB2"<<std::endl;
    }

    //std::cout<<"MAX:"<<moveAmountX<<" MAY:"<<moveAmountY<<std::endl;
    if(objUnitptr->moveAmountAIX - toPositive(moveAmountX) < 1 &&
        objUnitptr->moveAmountAIY - toPositive(moveAmountY) < 1)
    {
        //std::cout<<"1"<<std::endl;
        objUnitptr->acting = false;
    }
    else
    {
        //std::cout<<"2"<<std::endl;
        objUnitptr->moveAmountAIX -= toPositive(moveAmountX);
        objUnitptr->moveAmountAIY -= toPositive(moveAmountY);
    }
}

void AI::MovePixelPerfectX()
{
//Moving PP X
    //std::cout<<"PP1 posX"<<objUnitptr->posX<<std::endl;
    movePixelPerfectX = false;
    if(objUnitptr->moveDirX == en::Dirrection::left)
    {
        objUnitptr->posX -= (objUnitptr->posX % TILE_SIZE);
        //else do nothing
    }
    else if(objUnitptr->moveDirX == en::Dirrection::right)
    {
        tempI = objUnitptr->posX % TILE_SIZE;
        if(tempI != 0)
            objUnitptr->posX += TILE_SIZE - (objUnitptr->posX % TILE_SIZE);
    }
    //std::cout<<"PP1 end posX"<<objUnitptr->posX<<std::endl;
}

void AI::MovePixelPerfectY()
{
//Moving PP Y
    //std::cout<<"PP1 posY"<<objUnitptr->posY<<std::endl;
    movePixelPerfectY = false;
    if(objUnitptr->moveDirY == en::Dirrection::up)
    {
        objUnitptr->posY -= (objUnitptr->posY % TILE_SIZE);
    }
    else if(objUnitptr->moveDirY == en::Dirrection::down)
    {
        tempI = objUnitptr->posY % TILE_SIZE;
        if(tempI != 0)
            objUnitptr->posY += TILE_SIZE - (objUnitptr->posY % TILE_SIZE);
    }
    //std::cout<<"PP1 end posY"<<objUnitptr->posY<<std::endl;
}

int AI::toPositive(int num)
{
    if(num < 0)
        return num *= -1;
    return num;
}