Moving Items in QGraphicsScene with Collisions

Question

I am trying to move multiple or single selected item(a rectangle) in a QGraphicsView with collision detection, so that they don't move through each other but snap to either end without blocking movement on the other axis, here is the code:

import sys
from PyQt5.QtCore import *
from PyQt5.QtGui import *
from PyQt5.QtWidgets import *

class Circle(QGraphicsRectItem):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.orgpos = None
        self.lastpos = None

class Scene(QGraphicsScene):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        circ = Circle(0,0,100,50)
        circ.setPos(500,500)
        self.addItem(circ)
        self.selected = [circ]
        circ2 = Circle(0,0,100,50)
        circ2.setPos(0,100)
        self.addItem(circ2)

    def mousePressEvent(self, event):
        self.offset = event.scenePos()
        for x in self.selected:
            x.orgpos = x.pos()

    def mouseMoveEvent(self, event):
        for item in self.selected:
            item.setPos(event.scenePos()-self.offset+item.orgpos)
            if len(item.collidingItems(Qt.IntersectsItemShape))>0:
                for x in self.selected:
                    x.setPos(x.lastpos)
                break
            item.lastpos = item.pos()

if __name__ == '__main__':
    app = QApplication(sys.argv)
    scene = Scene(0, 0, 1000, 800)
    view = QGraphicsView(scene, renderHints=QPainter.Antialiasing)
    view.show()
    sys.exit(app.exec_())

However as you can see, the item that is draggable(Lower one) doesn't move on the axis that is not colliding and just plain stops, and also if the user drags quick enough, it stops short of the colliding object. Is there any way to fix these two problems? Any help is appreciated.

The code also uses a list of items and applies same movement to all, so that in case one item collides and many are selected, they all don't move and stay together.

Answer 1

Your problem is related to the collision detection problem, which is widely known for its complexity.

Even when dealing with orthogonal objects (rectangles, without rotation), implementing an intersection algorithm is difficult, especially when dealing with movement and when expecting consistency.

Restricting the movement of an item within an enclosed orthogonal space (a convex space) is relatively easy, as we only need to prevent the coordinates based on its bounding rectangle: for example, update the vertical position to the top limit if the top edge is above it, or to the bottom limit minus the available height if the bottom edge is below that.

Restricting the movement based on other convex objects creates non-convex limitations, meaning that we cannot just "adjust" coordinates based on simple restrictions of left/right/top/bottom. We need to define a possible "proximity" implementation, and decide how the "closest" coordinate that avoids collision would fit our needs.

If the restriction is based on more than two objects, that adds further complexity: we cannot obviously check every possible coordinate, we must find an algorithm that gives the "better" result, and the problem is also in finding how "better" is decided.

The above only considers orthogonal objects (orthogonally aligned rectangles, obviously including squares), but the problem rises in complexity when using other shapes and rotations (see the closely related packing problems).

There are many methods available to achieve what requested. Some of them may be solved through external libraries and already discussed here on StackOverflow (see this and this excellent posts).
Still, consider that the concept of movement is actually an abstraction, especially when in the digital realm: every "movement" is actually an absolute change in position, no matter the possible "time" it's required; a mouse movement is actually just a new position.

Since we're dealing with simple rectangles, that may simply things a bit, and a "brute-force" approach may be reasonable.
The concept is relatively simple: based on the current item positions, check if the new mouse positions causes intersections. If it doesn't, then the "movement" is accepted. If it isn't, then consider a reasonable amount of possible acceptable positions based on the perceived movement, and choose the one that is closest to the new mouse position.

This approach is obviously sub-optimal, because it's not very efficient: it just "broadens" the extent of the possible position until a non-intersected shape is found (see the various phase approaches in the Wikipedia article about collision detection for more efficient ways to achieve this).

Still, considering the simple case, it may be acceptable.

In the following example I changed the OP implementation in order to follow proper QGraphicsItem implementation (including item selection). It works almost fine: there are some rare occurrences of "false snapping" caused by fast mouse movements: I'll consider further digging on the matter, but it works in a relatively intuitive way once the user moves the mouse enough across the opposite axis.

from random import randrange
from PyQt5.QtCore import *
from PyQt5.QtGui import *
from PyQt5.QtWidgets import *

class RectItem(QGraphicsRectItem):
    def __init__(self, x, y, w, h):
        super().__init__(0, 0, w, h)
        self.setPos(x, y)
        self.setFlag(self.ItemIsSelectable)
        self.setPen(QColor.fromHsv(
            randrange(360), 
            randrange(127, 255), 
            randrange(63, 191)
        ))


class Scene(QGraphicsScene):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        for i in range(4):
            self.addItem(RectItem(i * 100, i * 100, 100, 50))

    def checkCollision(self, event):
        if not self.selected or not self.others:
            return

        downPos = event.buttonDownScenePos(Qt.LeftButton)
        scenePos = event.scenePos()
        downDelta = scenePos - downPos

        if self.fixedPaths.intersects(self.movingPaths.translated(downDelta)):
            # local function references created for simplicity
            checkFunc = self.fixedPaths.intersects
            transFunc = self.movingPaths.translated

            deltas = [self.lastLegal]
            if downDelta.x():
                # horizontally "expand" the possible deltas until no 
                # intersection is found
                tempLeft = QPointF(downDelta)
                tempRight = QPointF(downDelta)
                deltas.extend((tempLeft, tempRight))
                while checkFunc(transFunc(tempLeft)):
                    tempLeft.setX(tempLeft.x() - 1)
                while checkFunc(transFunc(tempRight)):
                    tempRight.setX(tempRight.x() + 1)
            if downDelta.y():
                # as above, for vertical "expand"
                tempUp = QPointF(downDelta)
                tempDown = QPointF(downDelta)
                deltas.extend((tempUp, tempDown))
                while checkFunc(transFunc(tempUp)):
                    tempUp.setY(tempUp.y() + 1)
                while checkFunc(transFunc(tempDown)):
                    tempDown.setY(tempDown.y() - 1)

            # find the closest "legal" point
            deltas.sort(key=lambda p: QLineF(downDelta, p).length())
            self.lastLegal = downDelta = deltas[0]

        # using start positions allows for x/y "reset" based on the start 
        # mouse position in case geometries are adjusted
        for item, startPos in self.startPositions.items():
            item.setPos(startPos + downDelta)

    def mousePressEvent(self, event):
        super().mousePressEvent(event)
        if event.button() == Qt.LeftButton:
            # initialize variables that may be used frequently
            self.startPositions = {}
            self.lastLegal = QPointF()

            self.selected = self.selectedItems()
            self.others = []

            if self.selected:
                # create paths for future collision detection
                self.movingPaths = QPainterPath()
                self.fixedPaths = QPainterPath()
                for item in self.items():
                    if item in self.selected:
                        self.startPositions[item] = item.pos()
                        self.movingPaths.addPath(
                            item.shape().translated(item.pos()))
                    else:
                        self.others.append(item)
                        self.fixedPaths.addPath(
                            item.shape().translated(item.pos()))

    def mouseMoveEvent(self, event):
        super().mouseMoveEvent(event)
        if event.buttons() == Qt.LeftButton:
            self.checkCollision(event)


if __name__ == '__main__':
    import sys
    app = QApplication(sys.argv)
    scene = Scene(0, 0, 800, 450)
    view = QGraphicsView(scene, renderHints=QPainter.Antialiasing)
    view.show()
    sys.exit(app.exec_())

Finally, note that the above is strictly based on the assumption that item geometries are always integer based. If the view is scaled or if item geometries use non-integer geometries, the results may be unexpected.