Pygame Ελαχιστοποίηση Συγκρούσεων (Collision Detection).

[babaliaris]

Καλησπέρα!

Φτιάχνω μια μηχανή για 2D Gaming σε python με βασικό εργαλείο το pygame. Έχω φτάσει στο σημείο όπου πρέπει να
γίνονται έλεγχοι για συγκρούσεις μεταξύ αντικειμένων (Collisions). Αν θέλετε μπορείτε να δείτε και τον αλγόριθμο που
ελέγχει τις συγκρούσεις.

Spoiler:

Να σημειώσω ότι όπου βλέπετε self.sprite.pos.x είναι ένα ψεύτικο x του αντικειμένου.
Για αυτόν τον λόγο με κάποιους υπολογισμούς υπολογίζω την κανονική θέση του αντικειμένου.
Αυτό το έχω κάνει διότι το pygame θεωρεί ότι ο άξονας y- είναι πηγαίνοντας προς τα επάνω και όχι
προς τα κάτω και επιπλέον θεωρεί ότι το σημείω (0,0) είναι στην πάνω αριστερή γωνία της οθόνης.
Επομένος εγώ δίνω την ψευδαίσθηση ότι το (0,0) είναι το κέντρο της οθόνης και ότι ο y- είναι ο άξονας
πηγαίνοντας προς τα κάτω. Άρα εάν κάποιος πει self.sprite.pos.x = 0 και self.sprite.pos.y = 0 στην ουσία
εννοεί το κέντρο της οθόνης. Εγώ όμως λέω στην pygame ότι το (0,0) στην ουσία είναι resolution.x / 2 + self.sprite.pos.x
και resolution.y / 2 + self.sprite.pos.y.

class BoxCollider:

    #-_-_-_-_-_-_-_-_-_-_-_-_-_-_-Constructor-_-_-_-_-_-_-_-_-_-_-_-_-_-_-#
    def __init__(self, sprite):

        #Sprite Object.
        self.sprite = sprite

        #Offsets.
        self.negativeOffsetX = 0
        self.positiveOffsetX = 0
        self.negativeOffsetY = 0
        self.positiveOffsetY = 0

        #Collider Color.
        self.color = (0,255,0)

        #Trigger.
        self.trigger = False
    #-_-_-_-_-_-_-_-_-_-_-_-_-_-_-Constructor-_-_-_-_-_-_-_-_-_-_-_-_-_-_-#





    #=============================Set Methods=============================#

    #Set Negative Offset X.
    def setNegativeOffsetX(self, value):

        #Check type of value.
        if type(value) != int and type(value) != float:
            raise AttributeError("Value must be a number.")


        #Update value.
        self.negativeOffsetX = value



    #Set Positive Offset X.
    def setPositiveOffsetX(self, value):

        #Check type of value.
        if type(value) != int and type(value) != float:
            raise AttributeError("Value must be a number.")


        #Update value.
        self.positiveOffsetX = value



    #Set Positive Offset Y.
    def setNegativeOffsetY(self, value):

        #Check type of value.
        if type(value) != int and type(value) != float:
            raise AttributeError("Value must be a number.")


        #Update value.
        self.positiveOffsetY = value



    #Set Positive Offset Y.
    def setPositiveOffsetY(self, value):

        #Check type of value.
        if type(value) != int and type(value) != float:
            raise AttributeError("Value must be a number.")


        #Update value.
        self.negativeOffsetY = value



    #Set Color.
    def setColor(self, r, g, b):

        #Check type of r,g,b.
        if (type(r) != int and type(r) != float) or (type(g) != int and type(g) != float) or (type(b) != int and type(b) != float):
            raise AttributeError("R,G,B must be a type of int or float.")

        #Check value of r,g,b.
        if (r < 0 or r > 255) or (g < 0 or g > 255) or (b < 0 or b > 255):
            raise AttributeError("R,G,B must have a value from 0 to 255.")


        #Update the color.
        self.color = (r,g,b)



    #Set Trigger.
    def setTrigger(self, value):

        #Check type of value.
        if type(value) != bool:
            raise ValueError("Value must be type of bool.")


        #Replace old prefab with the new one.
        self.trigger = value
        
    #=============================Set Methods=============================#



    
    


    #=========================Get Collision Method========================#
    def getCollision(self, other):

        #Calculation(CPU) Complexity = 46 Operations / Call.

        #Other doesn't have a collider.
        if other.collider == None:
            return False



        #Calculation Complexity = 3 operations * 8 lines = 24 operations .
        #--------------------Calculate Required Coordinates--------------------#
        leftX1  = (self.sprite.pos.x - self.sprite.width / 2) - self.negativeOffsetX
        rightX1 = (self.sprite.pos.x + self.sprite.width / 2) + self.positiveOffsetX

        upY1    = (self.sprite.pos.y - self.sprite.height / 2) - self.positiveOffsetY
        downY1  = (self.sprite.pos.y + self.sprite.height / 2) + self.negativeOffsetY


        leftX2  = (other.pos.x - other.width / 2) - other.collider.negativeOffsetX
        rightX2 = (other.pos.x + other.width / 2) + other.collider.positiveOffsetX

        upY2    = (other.pos.y - other.height / 2) - other.collider.positiveOffsetY
        downY2  = (other.pos.y + other.height / 2) + other.collider.negativeOffsetY
        #--------------------Calculate Required Coordinates--------------------#




        #Calculation Complexity = 11 operations + 11 operations = 22 operations.
        #-----------------------Calculate for collision------------------------#
        if (rightX1 >= leftX2 and rightX1 <= rightX2) or (leftX1 <= rightX2 and leftX1 >= leftX2) or (leftX1 <= leftX2 and rightX1 >= rightX2):
            if (downY1 >= upY2 and downY1 <= downY2) or (upY1 <= downY2 and upY1 >= upY2) or (upY1 <= upY2 and downY1 >= downY2):
                return True
        #-----------------------Calculate for collision------------------------#


        #Collision didn't found.
        return False
    #=========================Get Collision Method========================#




    #==============================Draw Method============================#
    def draw(self, pygame, screen):

        sx, sy = screen.get_size()

        #--------------------Calculate Required Coordinates--------------------#
        leftX1  = (sx / 2) + self.sprite.pos.x - (self.sprite.width / 2) - (self.negativeOffsetX)
        rightX1 = (sx / 2) + self.sprite.pos.x + (self.sprite.width / 2) + (self.positiveOffsetX)

        upY1    = (sy / 2) - self.sprite.pos.y - (self.sprite.height / 2) - (self.negativeOffsetY)
        downY1  = (sy / 2) - self.sprite.pos.y + (self.sprite.height / 2) + (self.positiveOffsetY)
        #--------------------Calculate Required Coordinates--------------------#

        screen.lock()
        pygame.draw.lines(screen, self.color, True, [ (leftX1, upY1), (rightX1, upY1), (rightX1, downY1), (leftX1, downY1)], 2 )
        screen.unlock()
    #==============================Draw Method============================#

Ο παραπάνο αρλγόριθμος δημιουργεί ένα αόρατο παραλληλόγραμμο το οποίο περιβάλλει ένα αντικείμενο (Sprite). Αν αυτό το αόρατο αντικείμενο έρθει σε
επαφή με ένα άλλο τότε επιστρέφει True, διαφορετικά False.

Μέχρι τώρα για να ελέγξω για συγκρούσεις έκανα το εξής:

for i in range( len(allSprites) ):
    for j in range( i+1, len(allSprites) ):
        if allSprites[i].collider.getCollision( allSprites[j] ):
            #Do Something.

Το παραπάνω δουλεύει τέλεια αλλά είναι πάρα μα πάρα πολύ αργό!!!
H πολυπλοκότητα είναι Χ^2 - 1 !!!


Στην συνέχεια σκέφτηκα κάτι άλλο. Αντικείμενα που δεν κινούνται γιατί να τα ελέγχω μεταξύ τους αφού ποτέ δεν θα συγκρουστούν;
Έτσι χώρισα τα αντικείμενα μου σε στατικά και μή στατικά ως εξής:

allSprites = [] #All the sprites in the scene.
notStatic = [] #Sprites that sprite.isStatic = False

for sprite in allSprites :
    for movingSprite in notStatic:
        if movingSprite != sprite  and movingSprite.collider.getCollision( sprite ):
            #Do Something

Έτσι κατάφερα να ρίξω την πολυπλοκότητα από x^2 - 1 σε x + m όπου x το μέγεθος
του allSprites και m του notStatic. Αυτό βοήθησε πάρα πολύ αλλά και πάλι είναι πολύ αργό. Σύν ότι μπορεί x = m και έτσι η πολυπλοκότητα να
γίνει x^2 = m^2 άρα δεν κατάφερα και πάλι τίποτα.


Και τώρα πάμε σε αυτό που με βασανίζει αυτήν την στιγμή. Σκέφτηκα να κάνω το εξής:

Ένα τετραδικό δένδρο αναζήτησης το οποίο θα έχει τις εξής ιδιότητες:
(Αυτό το δένδρο περιέχει μόνο αντικείμενα notStatic)

-Εαν x+ και y+ τότε αποθήκευσε το sprite στο πρώτο υποδένδρο.
-Εαν x- και y+ τότε αποθήκευσε το sprite στο δεύτερο υποδένδρο.
-Εαν x- και y- τότε αποθήκευσε το sprite στο τρίτο υποδένδρο.
-Εαν x+ και y- τότε αποθήκευσε το sprite στο τέταρτο υποδένδρο.

Επομένως ο αλγοριθμός μου γίνεται ως εξής:

for sprite in allSprites:

    tree.reCreate(allSprites)

    if tree.getCollision( sprite ):
        #Do Something.

Το tree.getCollision( sprite ) στην ουσία ψάχνει με δεδομένα
το x και y του αντικειμένου sprite να βρεί κόμβους στο δένδρο για
αντικείμενα notStatic που είναι σχετικά στην ίδια περιοχή. Και βέβαια
αν το δένδρο δεν είναι εκφυλισμένο αυτός ο αλγοριθμός είναι πάρα
πολύ ποιο γρήγορος από τον προιγούμενο!!!! Το πρόβλημα είναι ότι σε κάθε
frame/second πρέπει να ξανά δημιουργώ το δένδρο όλο από την αρχή διότι
τα notStatic αντικείμενα αλλάζουν τα x και y τους καθώς κινούνται. Και αυτό είναι το
μόνο πρόβλημα που με απασχολή τώρα διότι το tree.reCreate(allSprites)
αργεί πάρα πολύ και ρίχνει τα fps στο παιχνίδι!!!



Για αυτό θα ήθελα να με πείτε τρόπους βελτίωσεις ή και άλλες μεθόδους που δουλεύουν πολύ καλύτερα.

Ευχαριστώ!

[bazzil]

δοκίμασε από την λίστα των sprite να εξαιρέσεις αυτά που έχουν απόσταση μεγαλύτερη μιας τιμής. Επειδή δεν γνωρίζω python, νήματα υποστηρίζει;

[babaliaris]

δοκίμασε από την λίστα των sprite να εξαιρέσεις αυτά που έχουν απόσταση μεγαλύτερη μιας τιμής. Επειδή δεν γνωρίζω python, νήματα υποστηρίζει;

Ναι υποστιρίζει, αλλά δεν θέλω να τρέχω διαφορετικά threads. Θέλω όλα να τρέχουν σε ένα για να κάνω την μηχανή μου όσο ποιο "ελαφριά" γίνεται.

[bazzil]

Κάποια πράγματα δεν μπορείς να τ' αποφύγεις. Στην ουσία έχεις sprites που αλλάζει το Χ μόνο, sprite που αλλάζει μόνο το Υ και sprites που αλλάζει και το Χ και το Υ. Δοκίμασε να φτιάξεις το δέντρο σου με αυτή την λογική. Μαι άλλη σκέψη που μου έρχεται τώρα είναι χρήση γράφου με βάρη στις ακμές όπου η πιο σύντομη διαδρομή είναι αυτή που επιλέγεται κάθε φορά για έλεγχο. Οι κορυφές του γράφου είναι τα sprite

[babaliaris]

Κάποια πράγματα δεν μπορείς να τ' αποφύγεις. Στην ουσία έχεις sprites που αλλάζει το Χ μόνο, sprite που αλλάζει μόνο το Υ και sprites που αλλάζει και το Χ και το Υ. Δοκίμασε να φτιάξεις το δέντρο σου με αυτή την λογική. Μαι άλλη σκέψη που μου έρχεται τώρα είναι χρήση γράφου με βάρη στις ακμές όπου η πιο σύντομη διαδρομή είναι αυτή που επιλέγεται κάθε φορά για έλεγχο. Οι κορυφές του γράφου είναι τα sprite

Δυστυχώς δεν ξέρω γράφους, αλλά θα τους μάθω στο επόμενο εξάμηνο .

[bazzil]

Δώσε βάση σε αυτό το μάθημα γιατί είναι πολύ σημαντικό. Και ας μη τα καταλαβαίνει όλα. Δεν πειράζει.

[tsigarid]

Τα loops στην Python είναι εξαιρετικά αργά. Δεν μπορείς να τα αποφύγεις, ακόμα και με το κόστος να κάνεις παραπάνω πράξεις;

[babaliaris]

Τα loops στην Python είναι εξαιρετικά αργά. Δεν μπορείς να τα αποφύγεις, ακόμα και με το κόστος να κάνεις παραπάνω πράξεις;

Ένα loop είναι αναγκαίο για να τρέχει το παιχνίδι. Τώρα από εκεί και πέρα, μπορείς να κάνεις διάφορα "κόλπα" για να τρέχει γρήγορα ο κωδικά σου. Για παράδειγμα εγώ θέλω να καταφέρω να έχω μόνο το main loop:

for sprite in allSprites:
    #Game Loop.

Και να μην υπάρχει κανένα άλλο και μάλιστα εμφωλευμένο loop. Και μέχρι τώρα μόνο το collision detection δημιουργεί αυτό το πρόβλημα.

[guardianhelm]

Πέρασε καιρός, οπότε απλά αγνόησέ με αν έχεις λύσει το πρόβλημα.

Αν πάλι όχι, μπορείς ίσως να τα κάνεις όλα numpy arrays, κάθε pixel και κελί.

Μιλάμε για κουτιά σε 2d space, σωστά; Σε αυτή την περίπτωση δεν χρειάζεται να κάνεις έλεγχο ανά αντικείμενο.

Σου αρκεί ένας πίνακας που έχει 0 όπου δεν υπάρχει αντικείμενο, και από εκεί και μετά x όταν x αντικείμενα καταλαμβάνουν ένα pixel.

Όποτε κινείται κάτι, θα αφαιρείς 1 από την προηγούμενη θέση του (όλα τα κελιά/pixels που καταλάμβανε) και θα τη προσθέτεις στην επόμενη (όλα τα κελιά/pixels που καταλαμβάνει πλέον). Σε κάθε collision check θα ελέγχεις ότι δεν υπάρχουν τιμές >1 στον πίνακά σου. Αν υπάρχει έστω και ένα pixel, έχεις collision.

Ούτε καν το game engine δεν χρειάζεσαι έτσι :P

Γλιτώνεις όλα τα for και εσωτερικά η numpy δουλεύει με vectors, οπότε θα είναι πολύ πιο γρήγορη.

Υπάρχουν βελτιστοποιήσεις, πχ μπορείς να μεταφέρεις μόνο το περίγραμμα κάθε φορά αντί για όλη την επιφάνεια, που μάλλον θα σου ρίξει την πολυπλοκότητα αρκετά (με naive υλοποίηση θα έχεις ~Ο(n+m) μεταφορές να κάνεις αντί για ~O(n*m), όπου n είναι η μεγαλύτερη από τις δύο πλευρές σε pixel και m η μικρότερη), αλλά το τι είναι πιο εύκολο να υλοποιήσεις εξαρτάται από το τι δεδομένα έχεις και δεδομένου ότι και η numpy κάνει σημαντικές βελτιστοποιήσεις, είναι πολύ πιθανό να μη χρειαστεί να κάνεις δικές σου.