Prohibit collision of a movable QGraphicsItem with other items

Question

Final Edit

I figured out the issue and posted a solution as an answer below. If you have stumbled here from google looking for a decent way to move QGraphicsItems / QGraphicsObjects via the ItemIsMovable flag while avoiding collision with other nodes, I included a working itemChange method at the very end of my answer.

My original project dealt with snapping nodes to an arbitrary grid, but that is easily removed and not required at all for this solution to work. Efficiency wise, it's not the most clever use of data structures or algorithms, so if you end up with a lot of nodes on the screen you may want to try something more intelligent.

---

Original Question

I have a subclassed QGraphicsItem, Node, that sets the flags for ItemIsMovable and ItemSendsGeometryChanges. These Node objects have overriden shape() and boundingRect() functions that give them a basic rectangle to move around.

Moving a node around with the mouse calls the itemChange() function as expected, and I can call a snapPoint() function that forces the moved Node to always snap to a grid. (This is a simple function that returns a new QPointF based on a given param, where the new point is restricted to the closest coordinate on the actual snapping grid). This works perfectly as it is now.

My big issue is that I'd like to avoid snapping into a position that collides with other Nodes. That is, if I move a Node into a resulting (snapped to grid) location, I'd like the collidingItems() list to be completely empty.

I can accurately detect the collidingItems after the ItemPositionHasChanged flag gets thrown in itemChange(), but unfortunately this is after the Node is already moved. More to the point, I found this collision list isn't properly updated until the Node returns from the initial itemChange() (which is bad since the Node has already been moved into an invalid location that overlaps some other nodes).

Here's the itemChange() function I've got so far:

QVariant Node::itemChange(GraphicsItemChange change, const QVariant &value)
{
    if ( change == ItemPositionChange && scene() )
    {
        // Snap the value to the grid
        QPointF pt = value.toPointF();
        QPointF snapped = snapPoint(pt);

        // How much we've moved by
        qreal delX = snapped.x() - pos().x();
        qreal delY = snapped.y() - pos().y();

        // We didn't move enough to justify a new snapped position
        // Visually, this results in no changes and no collision testing
        // is required, so we can quit early
        if ( delX == 0 && delY == 0 )
            return snapped;

        // If we're here, then we know the Node's position has actually
        // updated, and we know exactly how far it's moved based on delX
        // and delY (which is constrained to the snap grid dimensions)
        // for example: delX may be -16 and delY may be 0 if we've moved 
        // left on a grid of 16px size squares

        // Ideally, this is the location where I'd like to check for
        // collisions before returning the snapped point. If I can detect
        // if there are any nodes colliding with this one now, I can avoid
        // moving it at all and avoid the ItemPositionHasChanged checks
        // below

        return snapped;
    }
    else if ( change == ItemPositionHasChanged && scene())
    {
        // This gets fired after the Node actually gets moved (once return
        // snapped gets called above)

        // The collidingItems list is now validly set and can be compared
        // but unfortunately its too late, as we've already moved into a
        // potentially offending position that overlaps other Nodes

        if ( collidingItems().empty() )
        {
            // This is okay
        }
        else
        {
            // This is bad! This is what we wanted to avoid
        }
    }

    return QGraphicsItem::itemChange(change, value);
}

What I've tried

I tried storing the delX and delY changes, and if we entered the final else block above, I tried to reverse the previous move with moveBy(-lastDelX, -lastDelY). This had some horrible results, since this gets called while the mouse is still pressed and moving the Node itself (which ends up moving the Node many times while attempting to move around a collision, often resulting in the Node flying off the side of the screen very quickly).

I also tried storing previous (known valid) points, and calling a setX and setY on the position to revert back if a collision was found, but this also had similar issues to the above approach.

Conclusion

If I could find a way to detect the collidingItems() accurately before the move even happens, I'd be able to avoid the ItemPositionHasChanged block altogether, making sure that the ItemPositionChange only returns points that are valid, and thus avoiding any logic for moving to a previously valid position.

Thanks for your time, and please let me know if you need more code or examples to illustrate the issue better.

Edit 1:

I think I've stumbled onto a technique that will probably form the basis for the actual solution, but I still need some help since it's not entirely working.

In the itemChange() function before the last return snapped;, I added the following code:

// Make a copy of the shape and translate it correctly
// This should be equivalent to the shape formed after a successful
// move (i.e. after return snapped;)
QPainterPath path = shape();
path.translate(delX, delY);

// Examine all the other items to see if they collide with the desired
// shape....
for (QGraphicsItem* other : canvas->items() )
{
    if ( other == this ) // don't care about this node, obviously
       continue;

    if ( other->collidesWithPath(path) )
    {
       // We should hopefully only reach this if another
       // item collides with the desired path. If that happens,
       // we don't want to move this node at all. Unfortunately,
       // we always seem to enter this block even when the nodes
       // shouldn't actually collide.
       qDebug() << "Found collision?";
       return pos();
    }
}

// Should only reach this if no collisions found, so we're okay to move
return snapped;

...but this doesn't work either. Any new node always enters the collidesWithPath block, even though they are nowhere near each other. The canvas object in the above code is just the QGraphicsView that holds all of these Node objects, in case that's unclear too.

Any ideas how to make the collidesWithPath work correctly? Is the path that copied the shape() wrong? I'm not sure what's going wrong here, as the comparison of the two shapes seems to work fine after the move completes (i.e. I can detect collisions accurately afterwards). I can upload the entire code if that helps.

Answer 1

I figured it out. I was indeed on the right track with the shape() call modification. Instead of actually testing against the full shape object itself, which is a path object whose collision testing may be more complex and inefficient, I wrote an extra function based on this thread that compares two QRectF (which is essentially what the shape call returns anyway):

bool rectsCollide(QRectF a, QRectF b)
{
    qreal ax1, ax2, ay1, ay2;
    a.getCoords(&ax1, &ay1, &ax2, &ay2);

    qreal bx1, bx2, by1, by2;
    b.getCoords(&bx1, &by1, &bx2, &by2);

    return ( ax1 < bx2 &&
             ax2 > bx1 &&
             ay1 < by2 &&
             ay2 > by1 );
}

Then, in the same area as the edit of the original post:

QRectF myTranslatedRect = getShapeRect();
myTranslatedRect.translate(delX, delY);

for (QGraphicsItem* other : canvas->items() )
{
    if ( other == this )
        continue;

    Node* n = (Node*)other;
    if ( rectsCollide( myTranslatedRect, n->getShapeRect() ) )
        return pos();
}

return snapped;

And that works with a little helper function getShapeRect() which basically just returns the same rectangle used in the overriden shape() function, but in QRectF form instead of a QPainterPath.

This solution seems to work pretty good. The Nodes can be moved freely (while still constrained to the snap grid), except in the case where it might overlap another node. In that case, no movement is displayed.

Edit 1:

I spent some more time working on this to get a slightly better result, and I figured I'd share since I feel like moving nodes around with collision is something that may be pretty common. In the above code, "dragging" a node against a long node / set of nodes that would collide with the currently dragged node has some unwanted effects; namely, since we just default to return pos() on any collision, we never move at all -- even if it were possible to move in the X or Y direction successfully. This occurs on a diagonal drag against a collider (kind of hard to explain, but if you're building a similar project with the above code, you can see it in action when you attempt to drag a node alongside another). We can easily detect this condition with a few minor changes:

Instead of checking rectsCollide() against a single translated rectangle, we can have two separate rects; one that is translated in the X direction and one that is translated in the Y. The for loop now checks to make sure any X movement is valid independently from the Y movement. After the for loop, we can just check against those cases to determine the final movement.

Here's the final itemChange() method that you can use freely in your code:

QVariant Node::itemChange(GraphicsItemChange change, const QVariant &value)
{
    if ( change == ItemPositionChange && scene() )
    {
        // Figure out the new point
        QPointF snapped = snapPoint(value.toPointF());

        // deltas to store amount of change
        qreal delX = snapped.x() - pos().x();
        qreal delY = snapped.y() - pos().y();

        // No changes
        if ( delX == 0 && delY == 0 )
            return snapped;

        // Check against all the other items for collision
        QRectF translateX = getShapeRect();
        QRectF translateY = getShapeRect();
        translateX.translate(delX, 0);
        translateY.translate(0, delY);

        bool xOkay = true;
        bool yOkay = true;

        for ( QGraphicsItem* other : canvas->items())
        {
            if (other == this)
                continue;

            if ( rectsCollide(translateX, ((Node*)other)->getShapeRect()) )
                xOkay = false;
            if ( rectsCollide(translateY, ((Node*)other)->getShapeRect()) )
                yOkay = false;
        }

        if ( xOkay && yOkay ) // Both valid, so move to the snapped location
            return snapped;
        else if ( xOkay ) // Move only in the X direction
        {
            QPointF r = pos();
            r.setX(snapped.x());
            return r;
        }
        else if ( yOkay ) // Move only in the Y direction
        {
            QPointF r = pos();
            r.setY(snapped.y());
            return r;
        }
        else // Don't move at all
            return pos();
    }

    return QGraphicsItem::itemChange(change, value);
}

For the above code, it is actually pretty trivial to avoid any kind of snapping behavior, if you want free movement not constrained to a grid. The fix for that is just to change the line that calls the snapPoint() function and just use the original value instead. Feel free to comment if you have any questions.