Collision detection on circle outside of BoundingRect

[squeegedog]

I'm working on a "tower defense" style game for a class project and I can't seem to figure out how to detect collision within a radius around a tower. I cannot simply use the boundingrect function as the area to detect collision goes beyond the actual boundingrect of the object. I tried to re-implement the shape function to create a path, but that causes the program to crash when a tower is clicked.

Can anyone give some insight on how I would create an "imaginary" circle around an object and check for collisions?

[wysota]

Add another item with a radius of your choice that is not visible and detect collisions for that item instead of your actual tower.

[squeegedog]

I actually just finished doing getting something to work by creating a QPainterPath, drawing an ellipse around the tower and then calling the QGraphicsScene::items(QPainterPath) method. However, it is REALLY slowing down the program running time when several towers are placed.

Do you predict that doing it in the manner you've suggested would be faster? I had actually looked into trying something along those lines, but I couldn't figure out how to give a new QGraphicsItem a radius. Would it be possible without creating a new sub-class of QGraphicsItem?

[wysota]

Basically the fastest approach is to go through a list of items that can collide with your tower (which is easy to keep or calculate using a bounding rectangle of the circle) and then iterate through the list and check the euclidean distance between the tower and the item. It can even be distributed among many threads if available.

[squeegedog]

Actually somehow I stumbled across the idea to limit all of my collision detecting to using the bounding rectangles and I created a new dummy class that I add to the scene and use it to detect the rectangular collisions for any given object. The problem that is now occurring is handling the collision detection for many objects becomes far too expensive a task to be handled in a single thread. This is my first experience trying to use QThread, or any type of threading for that matter, so I'm a little confused as to where and how I would send the collision detecting tasks to different threads.

Currently I have all of my collision detecting taking place in the advance(step=0) function for any of the graphicsobjects. By doing so, when the advance(step=1) call is made, the graphicsobjects can simply perform the proper task based on their current situation. Thus there should be no issue with threading out the collision detection for each object into different threads, but I'm unclear where I should put the threading code.

Should the threading be declared as its own class and then the object and scene that need to be processed for some kind of detection be passed into that class?

Or should the thread be declared within each graphicsobject and called when that object attempts to detect any collision that is occurring.

Also, would I still want to declare a main thread? It seems as though the answer would be no, as I would not want the main thread getting ahead of the collision processing and starting up the advance(step=1) processing while some of the collision detection processing is still occurring.

Thanks!

[squeegedog]

So after posting my previous question, I went to my professor to see if he could also provide some insight into threading. Well after about thirty minutes of showing him that only threading would improve the performance further from where I was, he told me to lower the frame rate and not to attempt threading.

Well, I'm not that kind of student. Shortly after I finally found an example of use that made sense and translated well into my usage, applied it to my code and everything seems to be working. Checking the processor usage on the Linux machines in our lab shows that all of the processors are taking on a shared load, where one was being over-ran before I inserted the threading.

BUT, after a few objects get on the scene, suddenly my project closes and the Debug display reads "The program has finished unexpectedly"

The only thing I can determine that would be causing the program to suddenly close without error, is I don't have a thread created to handle the "main" program, so the scene/view and everything suddenly are left without an active thread, which causes the entire program to finish.

I've tried to find different manners to create a separate thread to handle the main execution of the program so it stays active continuously when the other threading occurs, but I can't seem to figure out how/where to put the view/scene into their own thread. Adding the view returns an error about trying to thread a QWidget, and the scene isn't adding properly into a thread and running within the view.

If anyone could help me get through this last step, it would be pretty awesome to go back to my professor and say, "hey I know you said dont do this, but I did anyways, and it works, so give me an A"

Thanks

[ChrisW67]

I went to my professor to see if he could also provide some insight into threading. Well after about thirty minutes of showing him that only threading would improve the performance further from where I was, he told me to lower the frame rate and not to attempt threading.

Your professor is a wise man. Threads add complexity.

You cannot put a QGraphicsView into a thread because GUI objects must be in the GUI thread. Leave the GUI and scene in the main thread. As wysota said you can delegate the work of detailed collision checks (on candidates identified by quick checks) to threads by passing the centre and radius of each object to a processor in the other thread(s). You might like to look at QtConcurrent.

The "The program has finished unexpectedly" message is usually the result of using a null, undefined, or no-longer-valid pointer. It could also be the result of multiple threads sharing a data structure with protection. Your debugger will tell you exactly which line the crash occurred on and allow you to inspect variables while step back through callers to identify the culprit.

[squeegedog]

Your professor is a wise man. Threads add complexity.

You cannot put a QGraphicsView into a thread because GUI objects must be in the GUI thread. Leave the GUI and scene in the main thread. As wysota said you can delegate the work of detailed collision checks (on candidates identified by quick checks) to threads by passing the centre and radius of each object to a processor in the other thread(s). You might like to look at QtConcurrent.

The "The program has finished unexpectedly" message is usually the result of using a null, undefined, or no-longer-valid pointer. It could also be the result of multiple threads sharing a data structure with protection. Your debugger will tell you exactly which line the crash occurred on and allow you to inspect variables while step back through callers to identify the culprit.

While I completely understand the complexity of Threading (I actually did a 10 page paper on it for one of my prior classes), I dream one day of being a programming "god" like some of you, which means at some point I will need to understand and be able to implement such things. Since I've found a need to use it at this time, it became my current goal in life to generate a working threading code. I don't know why stupidity sometimes takes control and I don't run something in the debugger to check for more information.

QObject::killTimers: timers cannot be stopped from another thread

I Google'd this issue, and everyone else seems to be getting it from using a timer from within their Thread, which I am not, which means that somehow the destructor of the Thread must be deleting my main thread (I think)

#ifndef WORKER_H
#define WORKER_H
 
#include <QObject>
#include "gamescene.h"
#include "troop.h"
#include "colldetect.h"
 
class Worker : public QObject {
    Q_OBJECT
 
public:
    Worker(GameScene* sc, QPoint p, int x, int y, int ut, int pnum);
    ~Worker();
 
public slots:
    void process();
 
signals:
    void finished(Troop* t);
    void completed();
 
private:
    GameScene* gs;
    CollDetect* cd;
    int UserT;
    int playernum;
};
#endif // WORKER_H
 
 
//Worker.cpp file
#include "worker.h"
#include <QDebug>
 
Worker::Worker(GameScene* sc, QPoint p, int x, int y, int ut, int pnum)
{
    gs = sc;
    cd = new CollDetect(p, x, y);
    UserT = ut;
    playernum = pnum;
}
 
Worker::~Worker()
{
 
}
 
void Worker::process()
{
    gs->addItem(cd);
    QList<QGraphicsItem*> gi = cd->collidingItems(Qt::IntersectsItemBoundingRect);
    //qDebug() << "collisions: " << gi.size();
    for (int i = 0; i < gi.size(); i++)
    {
        if (gi.at(i)->type() == UserT)
        {
            if (dynamic_cast<Troop*>(gi.at(i))->playernum != playernum)
            {
                qDebug() << "troop found";
                emit finished(dynamic_cast<Troop*>(gi.at(i)));
                gs->removeItem(cd);
                emit completed();
            }
        }
    }
    emit finished(NULL);
    gs->removeItem(cd);
    emit completed();
 
}
 
//In the Troop class advance(step) function
QImage img;
img.load(image);
QThread* thread = new QThread;
Worker* worker = new Worker(myscene, QPoint(this->scenePos().x(),this->scenePos().y()), img.width(), img.height(), UserType+1, playernum);
worker->moveToThread(thread);
connect(thread, SIGNAL(started()), worker, SLOT(process()));
connect(worker, SIGNAL(completed()), thread, SLOT(quit()));
connect(worker, SIGNAL(completed()), worker, SLOT(deleteLater()));
connect(worker, SIGNAL(finished(Troop*)), this, SLOT(settarget(Troop*)));
connect(thread, SIGNAL(finished()), thread, SLOT(deleteLater()));
thread->start();

#ifndef WORKER_H
#define WORKER_H

#include <QObject>
#include "gamescene.h"
#include "troop.h"
#include "colldetect.h"

class Worker : public QObject {
    Q_OBJECT

public:
    Worker(GameScene* sc, QPoint p, int x, int y, int ut, int pnum);
    ~Worker();

public slots:
    void process();

signals:
    void finished(Troop* t);
    void completed();

private:
    GameScene* gs;
    CollDetect* cd;
    int UserT;
    int playernum;
};
#endif // WORKER_H


//Worker.cpp file
#include "worker.h"
#include <QDebug>

Worker::Worker(GameScene* sc, QPoint p, int x, int y, int ut, int pnum)
{
    gs = sc;
    cd = new CollDetect(p, x, y);
    UserT = ut;
    playernum = pnum;
}

Worker::~Worker()
{

}

void Worker::process()
{
    gs->addItem(cd);
    QList<QGraphicsItem*> gi = cd->collidingItems(Qt::IntersectsItemBoundingRect);
    //qDebug() << "collisions: " << gi.size();
    for (int i = 0; i < gi.size(); i++)
    {
        if (gi.at(i)->type() == UserT)
        {
            if (dynamic_cast<Troop*>(gi.at(i))->playernum != playernum)
            {
                qDebug() << "troop found";
                emit finished(dynamic_cast<Troop*>(gi.at(i)));
                gs->removeItem(cd);
                emit completed();
            }
        }
    }
    emit finished(NULL);
    gs->removeItem(cd);
    emit completed();

}

//In the Troop class advance(step) function
QImage img;
img.load(image);
QThread* thread = new QThread;
Worker* worker = new Worker(myscene, QPoint(this->scenePos().x(),this->scenePos().y()), img.width(), img.height(), UserType+1, playernum);
worker->moveToThread(thread);
connect(thread, SIGNAL(started()), worker, SLOT(process()));
connect(worker, SIGNAL(completed()), thread, SLOT(quit()));
connect(worker, SIGNAL(completed()), worker, SLOT(deleteLater()));
connect(worker, SIGNAL(finished(Troop*)), this, SLOT(settarget(Troop*)));
connect(thread, SIGNAL(finished()), thread, SLOT(deleteLater()));
thread->start();

To copy to clipboard, switch view to plain text mode 

---

Added after 27 minutes:

Okay, one of the big issues is coming from

gs->addItem(cd);

gs->addItem(cd);

To copy to clipboard, switch view to plain text mode 

further inspection of the cd element tells me where something is going way wrong here. The d_ptr element has a pointer to another complete graphics item, whose q_ptr has another d_ptr to another graphics item, whose q_ptr has another d_ptr to another graphics item, i think you get the point. But all the q_ptr, d_ptr, and v_ptr through the entire structure have the same values all the way down the chain. Obviously adding the collision detection item to the scene in the thread is a bad idea, it just seemed like the most straight forward approach at the time

[wysota]

I don't really see a need for threading here. How many objects do you have in your scene? 1k? 1M? Assuming 1k objects and an even distribution of objects in the scene checking collisions between objects in a circle covering 10% of the whole scene means checking collisions for 100 items. Even this can be easily avoided by keeping a list of objects that collide with the circle and updating that list when the object enters or leaves the circle.

[squeegedog]

Yeh thats the crazy part, like 100 objects on the scene and it gets beyond slow, my professor thought I was doing something wrong or detecting collisions based on actual unit shape rather than rectangles. But the thing is, all 100 objects on the scene are doing a form of collision detection and it gets REALLY lagged, beyond LAGGED. And I'm not even doing circular collision detecting, its all rectangular at the moment. Calculating the circular collision from those that collide rectangularly is very simple and can be added at any point

---

Added after 42 minutes:

Just to clarify why so many things are detecting collision, I am make a tower-defense "style" game, its actually a combination of TD and RTS, where 2-4 players connect through a network into a single game, each player has a base to defend by creating towers, and troops to send, which attack other troops and path past towers. Thus the troops and the towers need to effectively do forms of collision detection all the time to see when opposing troops are in range. I could do A LOT of coding to limit the amount of collisions each troop and tower must go through, but time simply will not permit that at this point, and threading the current detection system would give enough performance increase to allow a "decent" finished product to be released by the final sprint turn in.

[wysota]

Yeh thats the crazy part, like 100 objects on the scene and it gets beyond slow,

You must be doing something wrong then. How are you detecting collisions between the tower range and those objects? It is enough to do the detection when the object enters the radius, there is no need to perform the detection when it is far outside the radius or when it is far inside the radius (unless the object can teleport itself far from its current location).

[squeegedog]

CollDetect* cd = new CollDetect(QPoint(this->scenePos().x()-250,this->scenePos().y()-250), 500, 500);
myscene->addItem(cd);
QList<QGraphicsItem*> gi = cd->collidingItems(Qt::IntersectsItemBoundingRect);
for (int i = 0; i < gi.size(); i++)

CollDetect* cd = new CollDetect(QPoint(this->scenePos().x()-250,this->scenePos().y()-250), 500, 500);
myscene->addItem(cd);
QList<QGraphicsItem*> gi = cd->collidingItems(Qt::IntersectsItemBoundingRect);
for (int i = 0; i < gi.size(); i++)

To copy to clipboard, switch view to plain text mode 

---

Added after 4 minutes:

But honestly, the tower detection isn't where the lag is coming from right now, its the troop detecting other troops (doing in the same exact manner as above, except I'm only detecting for the actual bounding rect of the troop rather than an increased area around it). When I first inserted the tower collision using a QPath, it was very slow and I limited the collision detecting to once per second. I've never reverted that back as its fine. However, slowing down the rate at which the troops detect allows for clipping and sometimes complete missed detections

[wysota]

If you use collidingItems() then you detect collisions between each and every item in the scene. As I said before it is enough to do collision detection between items that are crossing the radius (if the "troop" is near the tower (colliding) in step A then there is no point in checking it in step A+1 since it couldn't have moved far enough to not collide with the tower).

[squeegedog]

I understand that, and it probably wouldn't take a whole lot of work to limit the troops lists that are compared against towers with fixed positions and stop some of the detections that way.

But, as previously stated, towers are NOT the problem. Its troops detecting other troops. Towers only check for collisions once per second on a 30fps game, so they aren't stalling up the processing by checking against each and every item. The troops, which all move around, are the ones who are causing the complete performance drop. They have to be checked every frame for collisions and creating limiting lists would take a much larger implementation, and still would only be a partial improvement.

a.) limit lists of troops to those within certain locations of the game and only check against those
b.) limit lists of troops to only those not on your own team

Depending on the number of players would determine the improvement that can be seen, but your also now putting a lot of extra tracking work for each and every troop, also having to occur every step A and A+1.

So, YES, I can make some small improvements through limitations etc, but in the end, detecting collisions amongst all my troops is still going to lag on a SINGLE processor.

[stampede]

but your also now putting a lot of extra tracking work for each and every troop

So change your approach, use quadtree to partition your scene, it will limit the number of needed collision detection tests between troops. Here is a nice introduction with example implementation (java, but anyway) : Using quadtrees to detect collisions in 2D space

[wysota]

I understand that, and it probably wouldn't take a whole lot of work to limit the troops lists that are compared against towers with fixed positions and stop some of the detections that way.

But, as previously stated, towers are NOT the problem. Its troops detecting other troops. Towers only check for collisions once per second on a 30fps game, so they aren't stalling up the processing by checking against each and every item. The troops, which all move around, are the ones who are causing the complete performance drop. They have to be checked every frame for collisions and creating limiting lists would take a much larger implementation, and still would only be a partial improvement.

a.) limit lists of troops to those within certain locations of the game and only check against those
b.) limit lists of troops to only those not on your own team

Depending on the number of players would determine the improvement that can be seen, but your also now putting a lot of extra tracking work for each and every troop, also having to occur every step A and A+1.

So, YES, I can make some small improvements through limitations etc, but in the end, detecting collisions amongst all my troops is still going to lag on a SINGLE processor.

What you say seems strange to me. Each troop would only do collision checking in this own neighbourhood which shouldn't be that complex. Have a look at the "colliding mice" example, increase the number of items and monitor the performance.