Γεια χαρά, Επισκέπτης

ΘΕΜΑ: Collision Detection Pygame

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3679

babaliaris1
Αποσυνδεμένος
python
Δημοσιεύσεις: 445
Ληφθείσες Ευχαριστίες 75

Καλησπέρα.

Προσπαθώ να κάνω έναν μηχανισμό ο οποίος ελέγχει αν τα αντικείμενα στο παιχνίδι μου
έρθουν σε επαφή.

Μέχρι τώρα έχω κάνει τα εξής:

Στην κλάση Sprite έφτιαξα μια μέθοδο get_collision(other_sprite) η οποία επιστρέφει
True εάν το self έρθει σε επαφή με το other_sprite.

Στην συνέχεια έφτιαξα τον μηχανισμό ως εξής:

Συγκέντρωσα όλλα τα αντικειμενα Sprites που υπάρχουν στο παιχνίδι σε μια λίστα
και έγραψα το παρακάτω

for obj_1 in objects:
 
    for obj_2 in objects:
 
        if obj_2.get_collision(obj_1):
            obj_2.on_collision(obj_1)

Το παραπάνω loop κάνει όλους του πιθανούς συνδιασμούς και αν η get_collision ισχύει σε
κάποια από αυτά τα ζευγάρια τότε η on_collision(collided_obj) καλείτε για το συγκεκριμένο
sprite object και ότι κώδικας υπάρχει μέσα στην on_collision τρέχει.

Ο μηχανισμός μου δουλεύει όπως θέλω αλλά κοστίζει πάρα πολύ!!!

50 sprite objects να υπάρχουν στην σκηνή το παιχνίδι αρχίζει να "λαγκάρει" αν και
50 sprite objects είναι πολύ λίγα.

Και είναι λογικό γιατί όχι μόνο τα δυο for loop έχουν πολυπλοκότητα N^2 , αλλά επίσης
ο κώδικας της get_collision είναι βαρής.

πχ αν έχω 200 sprite objects μέσα στην λίστα τότε τα 2 for loop θα κάνουν 200 x 200
= 40.000 επαναλήψεις που σημένει ότι ο κώδικας της get_collision θα κληθεί
40.000 φορές. Πολύ αργός ο κωδικάς μου.

Μήπως ξέρει κανείς κάποιον καλήτερο τρόπο για να το κάνω αυτό;
Προσπαθώ να το σκεφτώ εδώ και πόσες μέρες και δεν τα καταφέρνω.

My GitHub Page

My Facebook Programming Page

Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3680

pmav99
Αποσυνδεμένος
Author
Δημοσιεύσεις: 684
Ληφθείσες Ευχαριστίες 111

Βασικά κάτι τέτοιο θες: www.pygame.org/docs/ref/sprite.html#pygame.sprite.spritecollide

Από εκεί και πέρα, στο inner loop δεν έχει νόημα να εξετάζεις όλα τα sprites με όλα τα sprites. Τα sprites τα οποία έχουν εξεταστεί μπορείς να τα εξαιρείς από το inner loop

Δηλαδή, αν έχεις πχ τα ακόλουθα sprites:
Α, Β, C, D, E

αυτό που θες να κάνεις είναι να ελέγξεις μόνο τους ακόλουθους συνδυασμούς:
AB, AC, AD, AE
BC, BD, BE
CD, CE
DE

Γενικά για συνδυασμούς, αντί να κάνεις δικές σου αλχημείες καλύτερα να χρησιμοποιήσεις το itertools.combinations
docs.python.org/2/library/itertools.html#itertools.combinations

LaTeX στα Ελληνικά

Τελευταία διόρθωση: 7 Χρόνια 10 Μήνες πριν από pmav99.

Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3681

babaliaris1
Αποσυνδεμένος
python
Δημοσιεύσεις: 445
Ληφθείσες Ευχαριστίες 75

pmav99 έγραψε:

Βασικά κάτι τέτοιο θες: www.pygame.org/docs/ref/sprite.html#pygame.sprite.spritecollide

Από εκεί και πέρα, στο inner loop δεν έχει νόημα να εξετάζεις όλα τα sprites με όλα τα sprites. Τα sprites τα οποία έχουν εξεταστεί μπορείς να τα εξαιρείς από το inner loop

Δηλαδή, αν έχεις πχ τα ακόλουθα sprites:
Α, Β, C, D, E

αυτό που θες να κάνεις είναι να ελέγξεις μόνο τους ακόλουθους συνδυασμούς:
AB, AC, AD, AE
BC, BD, BE
CD, CE
DE

Γενικά για συνδυασμούς, αντί να κάνεις δικές σου αλχημείες καλύτερα να χρησιμοποιήσεις το itertools.combinations
docs.python.org/2/library/itertools.html#itertools.combinations

Αυτό δηλαδή;

for i in range(0, len(this.objects) ):
 
            obj = this.objects[i]
 
            #Render the object.
            obj.render(screen, core)
 
 
 
            for j in range(i+1, len(this.objects) ):
 
                obj2 = this.objects[j]
 
                if obj2.is_prefab or obj.is_prefab:
                    continue
 
                elif ( obj2.get_collision(obj) and obj2.brain != None):
                    obj2.brain.on_collision(obj)
 
                elif ( obj.get_collision(obj2) and obj.brain != None):
                    obj.brain.on_collision(obj2)

Πάντος είναι τρομερό!
Ο αλγόριθμος έγινε πολύ ποιο γρήγορος απότι ήταν (Δεν μπορώ να αποδήξω πόσο ποιο γρήγορος
αλλα τέλος πάντων).

Θέλω να πω και κάτι άλλο.

Αν υποθέσω ότι μόνο τα αντικείμενα το οποία είναι ορατά στον παίχτη (δηλαδή αυτά που
η συντεραγμένες τους είναι μέσα στα όρια της ανάλυσης του παραθύρου) μπορούν να
ελεγχτούν για collision detection , θα ήταν καλό αυτό;

Αλλά για να βρω ποια αντικείμενα είναι μέσα στα όρια του παραθύρου πρέπει πάλι να έχω
ένα loop που να το ελέγχει αυτό:

for obj in this.objects:
    if obj.isInsideScreen():
        collide_objects.append(obj)

και μετά να έχω κάτι τέτοιο:

for i in range(0, len(this.collide_objects) ):
 
            obj = this.collide_objects[i]
 
 
 
            for j in range(i+1, len(this.collide_objects) ):
 
                obj2 = this.collide_objects[j]
 
                if obj2.is_prefab or obj.is_prefab:
                    continue
 
                elif ( obj2.get_collision(obj) and obj2.brain != None):
                    obj2.brain.on_collision(obj)
 
                elif ( obj.get_collision(obj2) and obj.brain != None):
                    obj.brain.on_collision(obj2)

Θα λειτουργεί αρκετά καλά ή όχι;

My GitHub Page

My Facebook Programming Page

Τελευταία διόρθωση: 7 Χρόνια 10 Μήνες πριν από babaliaris1.

Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3682

pmav99 Αποσυνδεμένος Author Δημοσιεύσεις: 684 Ληφθείσες Ευχαριστίες 111	import itertools for (obj1, obj2) in itertools.combinations(this.objects, 2): if obj1.is_prefab or obj2.is_prefab: continue elif ( obj2.get_collision(obj1) and obj2.brain != None): obj2.brain.on_collision(obj) elif ( obj1.get_collision(obj2) and obj2.brain != None): obj1.brain.on_collision(obj2) else: raise ValueError
	LaTeX στα Ελληνικά Τελευταία διόρθωση: 7 Χρόνια 10 Μήνες πριν από pmav99. Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3683

babaliaris1 Αποσυνδεμένος python Δημοσιεύσεις: 445 Ληφθείσες Ευχαριστίες 75	Εκανα update το προιγουμενο μου post.
	My GitHub Page My Facebook Programming Page Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3684

pmav99
Αποσυνδεμένος
Author
Δημοσιεύσεις: 684
Ληφθείσες Ευχαριστίες 111

> Αν υποθέσω ότι μόνο τα αντικείμενα το οποία είναι ορατά στον παίχτη (δηλαδή αυτά που
η συντεραγμένες τους είναι μέσα στα όρια της ανάλυσης του παραθύρου) μπορούν να
ελεγχτούν για collision detection , θα ήταν καλό αυτό;

Εξαρτάται. Αν έχεις πολλά sprites που είναι εκτός οθόνης, τότε λογικά θα είναι πιο γρήγορο. Γενικά όσο πιο πολλά sprites κάνεις filter out, τόσο πιο λίγους συνδυασμούς θα έχεις να ελέγξεις. Αλλά δοκίμασε, ό,τι και να σου πούμε από εδώ δεν έχει πολύ νόημα.

ΥΓ. Please γράφε python... enumerate(), itertools.combination(), self

LaTeX στα Ελληνικά

Τελευταία διόρθωση: 7 Χρόνια 10 Μήνες πριν από pmav99.

Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3685

babaliaris1 Αποσυνδεμένος python Δημοσιεύσεις: 445 Ληφθείσες Ευχαριστίες 75	pmav99 έγραψε: ΥΓ. Please γράφε python... enumerate(), itertools.combination(), self Δηλαδή το itertools τη καλύτερο θα κάνει από αυτό που έκανα εγώ (με τα 2 for loops) Αφού ο δικός μου αλγοριθμός τα συνδιάζει ανα 2. Το ιδιο δεν κάνει και το itertools;
	My GitHub Page My Facebook Programming Page Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3686

pmav99
Αποσυνδεμένος
Author
Δημοσιεύσεις: 684
Ληφθείσες Ευχαριστίες 111

Αν δεν έχεις κάνει κανένα λάθος θα κάνουν το ίδιο.

Για να το καταλάβεις, συνέκρινε κώδικα παρόμοιο με το δικό σου:

letters = ["a", "c", "d", "e", "f", "g"]
number_of_letters = len(letters)
for i in range(number_of_letters):
    letter = letters[i]
    print("%d\t%s" % (i, letter))

VS pythonic code

letters = ["a", "c", "d", "e", "f", "g"]
for (i, letter) in enumerate(letters):
    print("%d\t%s" % (i, letter))

Εν γένει οι συναρτήσεις της Std Lib θα είναι πιο γρήγορες, πιο σίγουρες και πιο σαφείς. Δεν νομίζω ότι τίθεται ζήτημα σύγκρισης. Από εκεί και πέρα, its your project, και περί ορέξεως κολοκυθόπιτα. Το this πάντως μην το χρησιμοποιείς. Το 99.9% του κώδικα εκεί έξω χρησιμοποιεί self.

LaTeX στα Ελληνικά

Τελευταία διόρθωση: 7 Χρόνια 10 Μήνες πριν από pmav99.

Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Οι ακόλουθοι χρήστες είπαν "Σε Ευχαριστώ": babaliaris1

Συζήτηση

Προγραμματισμός

Αναζήτηση Βοήθειας

Collision Detection Pygame

ΘΕΜΑ: Collision Detection Pygame

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3679

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3680

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3681

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3682

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3683

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3684

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3685

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3686

Μενού Συζήτησης

Λίστα Ταχυδρομείου

ΘΕΜΑ: Collision Detection Pygame

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3679

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3680

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3681

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3682

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3683

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3684

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3685

Collision Detection Pygame 7 Χρόνια 10 Μήνες πριν #3686

Μοιράσου το!

Μενού Συζήτησης

Λίστα Ταχυδρομείου