Βρήκα ενδιαφέρον υλικό για την τεχνητή νοημοσύνη στα παιχνίδια. Με μια εξήγηση βασικών πραγμάτων σχετικά με την τεχνητή νοημοσύνη χρησιμοποιώντας απλά παραδείγματα, και στο εσωτερικό υπάρχουν πολλά χρήσιμα εργαλεία και μέθοδοι για την άνετη ανάπτυξη και σχεδίασή του. Το πώς, πού και πότε να τα χρησιμοποιήσετε είναι επίσης εκεί.
Τα περισσότερα από τα παραδείγματα είναι γραμμένα σε ψευδοκώδικα, επομένως δεν απαιτούνται προηγμένες γνώσεις προγραμματισμού. Κάτω από την περικοπή υπάρχουν 35 φύλλα κειμένου με εικόνες και gif, οπότε ετοιμαστείτε.
UPD. Ζητώ συγγνώμη, αλλά έχω ήδη κάνει τη δική μου μετάφραση αυτού του άρθρου στο Habré . Μπορείτε να διαβάσετε την εκδοχή του , αλλά για κάποιο λόγο μου πέρασε το άρθρο (χρησιμοποίησα την αναζήτηση, αλλά κάτι πήγε στραβά). Και επειδή γράφω σε ένα ιστολόγιο αφιερωμένο στην ανάπτυξη παιχνιδιών, αποφάσισα να αφήσω την έκδοση της μετάφρασης για τους συνδρομητές (ορισμένα σημεία έχουν διαφορετική μορφοποίηση, μερικά παραλείφθηκαν σκόπιμα κατόπιν συμβουλής των προγραμματιστών).
Τι είναι το AI;
Το παιχνίδι AI εστιάζει στις ενέργειες που πρέπει να εκτελεί ένα αντικείμενο με βάση τις συνθήκες στις οποίες βρίσκεται. Αυτό αναφέρεται συνήθως ως διαχείριση "έξυπνου πράκτορα", όπου ένας πράκτορας είναι ένας χαρακτήρας παίκτη, ένα όχημα, ένα bot ή μερικές φορές κάτι πιο αφηρημένο: μια ολόκληρη ομάδα οντοτήτων ή ακόμα και ένας πολιτισμός. Σε κάθε περίπτωση, είναι ένα πράγμα που πρέπει να βλέπει το περιβάλλον του, να παίρνει αποφάσεις με βάση αυτό και να ενεργεί σύμφωνα με αυτές. Αυτό ονομάζεται κύκλος Αίσθησης/Σκέψου/Δράσης:
- Αίσθηση: Ο πράκτορας βρίσκει ή λαμβάνει πληροφορίες για πράγματα στο περιβάλλον του που μπορεί να επηρεάσουν τη συμπεριφορά του (απειλές σε κοντινή απόσταση, αντικείμενα προς συλλογή, ενδιαφέροντα μέρη για εξερεύνηση).
- Σκέψου: Ο πράκτορας αποφασίζει πώς θα αντιδράσει (εξετάζει αν είναι αρκετά ασφαλές να συλλέξει αντικείμενα ή αν πρέπει πρώτα να πολεμήσει/κρύβει).
- Πράξη: ο πράκτορας εκτελεί ενέργειες για την εφαρμογή της προηγούμενης απόφασης (αρχίζει να κινείται προς τον εχθρό ή το αντικείμενο).
- ...τώρα η κατάσταση έχει αλλάξει λόγω των ενεργειών των χαρακτήρων, οπότε ο κύκλος επαναλαμβάνεται με νέα δεδομένα.
Το AI τείνει να εστιάζει στο τμήμα Sense του βρόχου. Για παράδειγμα, τα αυτόνομα αυτοκίνητα βγάζουν φωτογραφίες του δρόμου, τις συνδυάζουν με δεδομένα ραντάρ και lidar και τις ερμηνεύουν. Αυτό γίνεται συνήθως με τη μηχανική εκμάθηση, η οποία επεξεργάζεται τα εισερχόμενα δεδομένα και τους δίνει νόημα, εξάγοντας σημασιολογικές πληροφορίες όπως "υπάρχει ένα άλλο αυτοκίνητο 20 μέτρα μπροστά σας". Αυτά είναι τα λεγόμενα προβλήματα ταξινόμησης.
Τα παιχνίδια δεν χρειάζονται ένα πολύπλοκο σύστημα για την εξαγωγή πληροφοριών, καθώς τα περισσότερα από τα δεδομένα είναι ήδη αναπόσπαστο μέρος τους. Δεν χρειάζεται να εκτελείτε αλγόριθμους αναγνώρισης εικόνων για να προσδιορίσετε εάν υπάρχει εχθρός μπροστά - το παιχνίδι γνωρίζει ήδη και τροφοδοτεί τις πληροφορίες απευθείας στη διαδικασία λήψης αποφάσεων. Ως εκ τούτου, το μέρος της Αίσθησης του κύκλου είναι συχνά πολύ πιο απλό από το μέρος Σκέψου και Δράσε.
Περιορισμοί του παιχνιδιού AI
Η τεχνητή νοημοσύνη έχει ορισμένους περιορισμούς που πρέπει να τηρούνται:
- Το AI δεν χρειάζεται να εκπαιδευτεί εκ των προτέρων, σαν να ήταν ένας αλγόριθμος μηχανικής μάθησης. Δεν έχει νόημα να γράφεις ένα νευρωνικό δίκτυο κατά την ανάπτυξη για να παρακολουθείς δεκάδες χιλιάδες παίκτες και να μάθεις τον καλύτερο τρόπο να παίζεις εναντίον τους. Γιατί; Γιατί το παιχνίδι δεν έχει κυκλοφορήσει και δεν υπάρχουν παίκτες.
- Το παιχνίδι πρέπει να είναι διασκεδαστικό και προκλητικό, επομένως οι πράκτορες δεν θα πρέπει να βρίσκουν την καλύτερη προσέγγιση ενάντια στους ανθρώπους.
- Οι πράκτορες πρέπει να φαίνονται ρεαλιστές, ώστε οι παίκτες να νιώθουν ότι παίζουν εναντίον πραγματικών ανθρώπων. Το πρόγραμμα AlphaGo ξεπέρασε τους ανθρώπους, αλλά τα βήματα που επιλέχθηκαν απείχαν πολύ από την παραδοσιακή κατανόηση του παιχνιδιού. Εάν το παιχνίδι προσομοιώνει έναν άνθρωπο αντίπαλο, αυτό το συναίσθημα δεν πρέπει να υπάρχει. Ο αλγόριθμος πρέπει να αλλάξει έτσι ώστε να παίρνει εύλογες αποφάσεις και όχι ιδανικές.
- Το AI πρέπει να λειτουργεί σε πραγματικό χρόνο. Αυτό σημαίνει ότι ο αλγόριθμος δεν μπορεί να μονοπωλήσει τη χρήση της CPU για μεγάλες χρονικές περιόδους για τη λήψη αποφάσεων. Ακόμη και τα 10 χιλιοστά του δευτερολέπτου είναι πολύ μεγάλα, επειδή τα περισσότερα παιχνίδια χρειάζονται μόνο 16 έως 33 χιλιοστά του δευτερολέπτου για να κάνουν όλη την επεξεργασία και να προχωρήσουν στο επόμενο καρέ γραφικών.
- Στην ιδανική περίπτωση, τουλάχιστον μέρος του συστήματος θα πρέπει να βασίζεται σε δεδομένα, έτσι ώστε οι μη κωδικοποιητές να μπορούν να κάνουν αλλαγές και οι προσαρμογές να γίνονται πιο γρήγορα.
Ας δούμε τις προσεγγίσεις AI που καλύπτουν ολόκληρο τον κύκλο Sense/Think/Act.
Λήψη Βασικών Αποφάσεων
Ας ξεκινήσουμε με το πιο απλό παιχνίδι - Pong. Στόχος: μετακινήστε το κουπί έτσι ώστε η μπάλα να αναπηδήσει από αυτό αντί να πετάξει δίπλα του. Είναι σαν το τένις, όπου χάνεις αν δεν χτυπήσεις την μπάλα. Εδώ το AI έχει ένα σχετικά εύκολο έργο - να αποφασίσει προς ποια κατεύθυνση θα κινηθεί η πλατφόρμα.
Δηλώσεις υπό όρους
Για το AI στο Pong, η πιο προφανής λύση είναι να προσπαθείτε πάντα να τοποθετείτε την πλατφόρμα κάτω από την μπάλα.
Ένας απλός αλγόριθμος για αυτό, γραμμένος σε ψευδοκώδικα:
κάθε καρέ/ενημέρωση κατά τη διάρκεια του παιχνιδιού:
αν η μπάλα είναι στα αριστερά του κουπί:
μετακινήστε το κουπί αριστερά
αλλιώς αν η μπάλα είναι στα δεξιά του κουπί:
μετακινήστε το κουπί δεξιά
Εάν η πλατφόρμα κινείται με την ταχύτητα της μπάλας, τότε αυτός είναι ο ιδανικός αλγόριθμος για το AI στο Pong. Δεν χρειάζεται να περιπλέκετε τίποτα εάν δεν υπάρχουν τόσα πολλά δεδομένα και πιθανές ενέργειες για τον πράκτορα.
Αυτή η προσέγγιση είναι τόσο απλή που ολόκληρος ο κύκλος Αίσθησης/Σκέψου/Δράσης είναι ελάχιστα αντιληπτός. Αλλά είναι εκεί:
- Το μέρος της αίσθησης είναι σε δύο δηλώσεις if. Το παιχνίδι γνωρίζει πού βρίσκεται η μπάλα και πού βρίσκεται η πλατφόρμα, επομένως η τεχνητή νοημοσύνη αναζητά αυτές τις πληροφορίες.
- Το τμήμα Think περιλαμβάνεται επίσης στις δύο δηλώσεις if. Ενσωματώνουν δύο λύσεις, οι οποίες σε αυτή την περίπτωση αλληλοαποκλείονται. Ως αποτέλεσμα, επιλέγεται μία από τις τρεις ενέργειες - μετακινήστε την πλατφόρμα προς τα αριστερά, μετακινήστε την προς τα δεξιά ή μην κάνετε τίποτα εάν έχει ήδη τοποθετηθεί σωστά.
- Το τμήμα Act βρίσκεται στις προτάσεις Move Paddle Left και Move Paddle Right. Ανάλογα με το σχεδιασμό του παιχνιδιού, μπορούν να μετακινήσουν την πλατφόρμα αμέσως ή με συγκεκριμένη ταχύτητα.
Τέτοιες προσεγγίσεις ονομάζονται αντιδραστικές - υπάρχει ένα απλό σύνολο κανόνων (σε αυτήν την περίπτωση εάν δηλώσεις στον κώδικα) που αντιδρούν στην τρέχουσα κατάσταση του κόσμου και αναλαμβάνουν δράση.
Δέντρο απόφασης
Το παράδειγμα Pong είναι στην πραγματικότητα ισοδύναμο με μια επίσημη έννοια AI που ονομάζεται δέντρο αποφάσεων. Ο αλγόριθμος περνά μέσα από αυτό για να φτάσει σε ένα "φύλλο" - μια απόφαση για το ποια ενέργεια πρέπει να γίνει.
Ας φτιάξουμε ένα μπλοκ διάγραμμα του δέντρου αποφάσεων για τον αλγόριθμο της πλατφόρμας μας:
Κάθε μέρος του δέντρου ονομάζεται κόμβος - το AI χρησιμοποιεί τη θεωρία γραφημάτων για να περιγράψει τέτοιες δομές. Υπάρχουν δύο τύποι κόμβων:
- Κόμβοι απόφασης: επιλογή μεταξύ δύο εναλλακτικών με βάση τη δοκιμή κάποιας συνθήκης, όπου κάθε εναλλακτική αντιπροσωπεύεται ως ξεχωριστός κόμβος.
- Τελικοί κόμβοι: Η ενέργεια που πρέπει να εκτελεστεί που αντιπροσωπεύει την τελική απόφαση.
Ο αλγόριθμος ξεκινά από τον πρώτο κόμβο (τη «ρίζα» του δέντρου). Είτε αποφασίζει σε ποιον θυγατρικό κόμβο θα πάει, είτε εκτελεί την ενέργεια που είναι αποθηκευμένη στον κόμβο και εξέρχεται.
Ποιο είναι το όφελος ενός δέντρου αποφάσεων να κάνει την ίδια δουλειά με τις δηλώσεις if στην προηγούμενη ενότητα; Υπάρχει ένα γενικό σύστημα εδώ όπου κάθε απόφαση έχει μόνο μία προϋπόθεση και δύο πιθανά αποτελέσματα. Αυτό επιτρέπει στον προγραμματιστή να δημιουργήσει AI από δεδομένα που αντιπροσωπεύουν αποφάσεις σε ένα δέντρο χωρίς να χρειάζεται να το κωδικοποιήσει. Ας το παρουσιάσουμε σε μορφή πίνακα:
Στην πλευρά του κώδικα θα λάβετε ένα σύστημα για την ανάγνωση συμβολοσειρών. Δημιουργήστε έναν κόμβο για καθένα από αυτούς, συνδέστε τη λογική απόφασης με βάση τη δεύτερη στήλη και τους θυγατρικούς κόμβους με βάση την τρίτη και την τέταρτη στήλη. Πρέπει ακόμα να προγραμματίσετε τις συνθήκες και τις ενέργειες, αλλά τώρα η δομή του παιχνιδιού θα είναι πιο περίπλοκη. Εδώ προσθέτετε πρόσθετες αποφάσεις και ενέργειες και, στη συνέχεια, προσαρμόζετε ολόκληρο το AI επεξεργάζοντας απλώς το αρχείο κειμένου ορισμού δέντρου. Στη συνέχεια, μεταφέρετε το αρχείο σε έναν σχεδιαστή παιχνιδιού, ο οποίος μπορεί να αλλάξει τη συμπεριφορά χωρίς να μεταγλωττίσει ξανά το παιχνίδι ή να αλλάξει τον κώδικα.
Τα δέντρα αποφάσεων είναι πολύ χρήσιμα όταν δημιουργούνται αυτόματα από ένα μεγάλο σύνολο παραδειγμάτων (για παράδειγμα, χρησιμοποιώντας τον αλγόριθμο ID3). Αυτό τα καθιστά ένα αποτελεσματικό και υψηλής απόδοσης εργαλείο για την ταξινόμηση καταστάσεων με βάση τα δεδομένα που λαμβάνονται. Ωστόσο, πηγαίνουμε πέρα από ένα απλό σύστημα επιλογής ενεργειών από τους πράκτορες.
Σενάρια
Αναλύσαμε ένα σύστημα δέντρων αποφάσεων που χρησιμοποιούσε προ-δημιουργημένες συνθήκες και ενέργειες. Το άτομο που σχεδιάζει το AI μπορεί να οργανώσει το δέντρο όπως θέλει, αλλά πρέπει ακόμα να βασιστεί στον κωδικοποιητή που τα προγραμμάτισε όλα. Τι θα γινόταν αν μπορούσαμε να δώσουμε στον σχεδιαστή τα εργαλεία για να δημιουργήσει τις δικές του συνθήκες ή ενέργειες;
Για να μην χρειάζεται ο προγραμματιστής να γράψει κώδικα για τις συνθήκες Is Ball Left Of Paddle και Is Ball Right Of Paddle, μπορεί να δημιουργήσει ένα σύστημα στο οποίο ο σχεδιαστής θα γράψει συνθήκες για να ελέγξει αυτές τις τιμές. Τότε τα δεδομένα του δέντρου αποφάσεων θα μοιάζουν με αυτό:
Αυτό είναι ουσιαστικά το ίδιο όπως στον πρώτο πίνακα, αλλά οι λύσεις μέσα τους έχουν τον δικό τους κώδικα, λίγο σαν το υπό όρους μέρος μιας πρότασης if. Στην πλευρά του κώδικα, αυτό θα διάβαζε στη δεύτερη στήλη για τους κόμβους απόφασης, αλλά αντί να αναζητήσει μια συγκεκριμένη συνθήκη για εκτέλεση (Is Ball Left Of Paddle), αξιολογεί την υπό όρους έκφραση και επιστρέφει αναλόγως true ή false. Αυτό γίνεται χρησιμοποιώντας τη γλώσσα σεναρίου Lua ή Angelscript. Χρησιμοποιώντας τα, ένας προγραμματιστής μπορεί να πάρει αντικείμενα στο παιχνίδι του (μπάλα και κουπί) και να δημιουργήσει μεταβλητές που θα είναι διαθέσιμες στο σενάριο (ball.position). Επίσης, η γλώσσα σεναρίου είναι πιο απλή από την C++. Δεν απαιτεί πλήρες στάδιο μεταγλώττισης, επομένως είναι ιδανικό για γρήγορη προσαρμογή της λογικής του παιχνιδιού και επιτρέπει στους «μη κωδικοποιητές» να δημιουργούν οι ίδιοι τις απαραίτητες λειτουργίες.
Στο παραπάνω παράδειγμα, η γλώσσα δέσμης ενεργειών χρησιμοποιείται μόνο για την αξιολόγηση της έκφρασης υπό όρους, αλλά μπορεί επίσης να χρησιμοποιηθεί για ενέργειες. Για παράδειγμα, τα δεδομένα Move Paddle Right θα μπορούσαν να γίνουν μια δήλωση σεναρίου (ball.position.x += 10). Για να ορίζεται και η δράση στο σενάριο, χωρίς να χρειάζεται προγραμματισμός Move Paddle Right.
Μπορείτε να προχωρήσετε ακόμη περισσότερο και να γράψετε ολόκληρο το δέντρο αποφάσεων σε μια γλώσσα σεναρίου. Αυτός θα είναι κώδικας με τη μορφή εντολών υπό όρους με σκληρό κώδικα, αλλά θα βρίσκονται σε εξωτερικά αρχεία δέσμης ενεργειών, δηλαδή μπορούν να αλλάξουν χωρίς να γίνει εκ νέου μεταγλώττιση ολόκληρου του προγράμματος. Μπορείτε συχνά να επεξεργαστείτε το αρχείο σεναρίου κατά τη διάρκεια του παιχνιδιού για να δοκιμάσετε γρήγορα διαφορετικές αποκρίσεις AI.
Απόκριση εκδήλωσης
Τα παραπάνω παραδείγματα είναι τέλεια για το Pong. Διαχειρίζονται συνεχώς τον κύκλο Sense/Think/Act και ενεργούν με βάση την τελευταία κατάσταση του κόσμου. Αλλά σε πιο σύνθετα παιχνίδια πρέπει να αντιδράτε σε μεμονωμένα γεγονότα και να μην αξιολογείτε τα πάντα ταυτόχρονα. Το Pong σε αυτή την περίπτωση είναι ήδη ένα κακό παράδειγμα. Ας διαλέξουμε ένα άλλο.
Φανταστείτε έναν σκοπευτή όπου οι εχθροί είναι ακίνητοι μέχρι να εντοπίσουν τον παίκτη, μετά από τον οποίο ενεργούν ανάλογα με την «εξειδίκευσή» του: κάποιος θα τρέξει να «ορμήσει», κάποιος θα επιτεθεί από μακριά. Εξακολουθεί να είναι ένα βασικό αντιδραστικό σύστημα - "αν εντοπιστεί ένας παίκτης, κάνε κάτι" - αλλά μπορεί λογικά να αναλυθεί σε συμβάν Player Seen και Reaction (επιλέξτε μια απάντηση και εκτελέστε την).
Αυτό μας φέρνει πίσω στον κύκλο Αίσθησης/Σκεφτείτε/Πράξτε. Μπορούμε να κωδικοποιήσουμε ένα τμήμα Sense που θα ελέγχει κάθε καρέ εάν το AI βλέπει τη συσκευή αναπαραγωγής. Αν όχι, δεν συμβαίνει τίποτα, αλλά αν δει, τότε δημιουργείται το συμβάν Player Seen. Ο κώδικας θα έχει μια ξεχωριστή ενότητα που λέει "όταν συμβεί το συμβάν Player Seen, κάντε", όπου είναι η απάντηση που χρειάζεστε για να αντιμετωπίσετε τα τμήματα Think and Act. Έτσι, θα ρυθμίσετε τις αντιδράσεις στο συμβάν Player Seen: για τον χαρακτήρα «βιαστικό» - ChargeAndAttack και για τον ελεύθερο σκοπευτή - HideAndSnipe. Αυτές οι σχέσεις μπορούν να δημιουργηθούν στο αρχείο δεδομένων για γρήγορη επεξεργασία χωρίς να χρειάζεται να γίνει εκ νέου μεταγλώττιση. Η γλώσσα δέσμης ενεργειών μπορεί να χρησιμοποιηθεί και εδώ.
Λήψη δύσκολων αποφάσεων
Αν και τα απλά συστήματα αντίδρασης είναι πολύ ισχυρά, υπάρχουν πολλές καταστάσεις όπου δεν επαρκούν. Μερικές φορές χρειάζεται να λάβετε διαφορετικές αποφάσεις με βάση το τι κάνει ο πράκτορας αυτήν τη στιγμή, αλλά είναι δύσκολο να το φανταστεί κανείς ως προϋπόθεση. Μερικές φορές υπάρχουν πάρα πολλές συνθήκες για να τις αναπαραστήσουν αποτελεσματικά σε ένα δέντρο αποφάσεων ή σε ένα σενάριο. Μερικές φορές χρειάζεται να εκτιμήσετε εκ των προτέρων πώς θα αλλάξει η κατάσταση πριν αποφασίσετε για το επόμενο βήμα. Απαιτούνται πιο εξελιγμένες προσεγγίσεις για την επίλυση αυτών των προβλημάτων.
Μηχανή πεπερασμένης κατάστασης
Η μηχανή πεπερασμένης κατάστασης ή FSM (μηχανή πεπερασμένης κατάστασης) είναι ένας τρόπος να πούμε ότι ο πράκτορας μας βρίσκεται αυτήν τη στιγμή σε μία από τις πολλές πιθανές καταστάσεις και ότι μπορεί να μεταβεί από τη μια κατάσταση στην άλλη. Υπάρχει ένας ορισμένος αριθμός τέτοιων πολιτειών—εξ ου και το όνομα. Το καλύτερο παράδειγμα από τη ζωή είναι ένα φανάρι. Υπάρχουν διαφορετικές ακολουθίες φώτων σε διαφορετικά μέρη, αλλά η αρχή είναι η ίδια - κάθε κατάσταση αντιπροσωπεύει κάτι (σταματήστε, περπατήστε κ.λπ.). Ένα φανάρι βρίσκεται σε μία μόνο κατάσταση ανά πάσα στιγμή και μετακινείται από το ένα στο άλλο με βάση απλούς κανόνες.
Είναι παρόμοια ιστορία με τα NPC στα παιχνίδια. Για παράδειγμα, ας πάρουμε έναν φύλακα με τις ακόλουθες καταστάσεις:
- Περιπολία.
- Επίθεση.
- φυγή.
Και αυτές οι προϋποθέσεις για την αλλαγή της κατάστασής του:
- Αν ο φύλακας δει τον εχθρό, επιτίθεται.
- Εάν ο φρουρός επιτεθεί αλλά δεν βλέπει πλέον τον εχθρό, επιστρέφει για περιπολία.
- Εάν ένας φρουρός επιτεθεί αλλά τραυματιστεί βαριά, τρέχει μακριά.
Μπορείτε επίσης να γράψετε if-statements με μια μεταβλητή κατάσταση φύλακα και διάφορους ελέγχους: υπάρχει κάποιος εχθρός κοντά, ποιο είναι το επίπεδο υγείας του NPC κ.λπ. Ας προσθέσουμε μερικές ακόμη καταστάσεις:
- Αδράνεια - μεταξύ περιπολιών.
- Αναζήτηση - όταν ο αντιληπτός εχθρός έχει εξαφανιστεί.
- Εύρεση βοήθειας - όταν ένας εχθρός εντοπίζεται, αλλά είναι πολύ δυνατός για να πολεμήσει μόνος του.
Η επιλογή για καθένα από αυτά είναι περιορισμένη - για παράδειγμα, ο φρουρός δεν θα ψάξει για έναν κρυφό εχθρό εάν έχει χαμηλή υγεία.
Σε τελική ανάλυση, υπάρχει μια τεράστια λίστα με "αν" , Οτι " μπορεί να γίνει πολύ δυσκίνητη, επομένως πρέπει να επισημοποιήσουμε μια μέθοδο που μας επιτρέπει να έχουμε κατά νου τις καταστάσεις και τις μεταβάσεις μεταξύ κρατών. Για να γίνει αυτό, λαμβάνουμε υπόψη όλες τις καταστάσεις και κάτω από κάθε κατάσταση σημειώνουμε σε μια λίστα όλες τις μεταβάσεις σε άλλες καταστάσεις, μαζί με τις προϋποθέσεις που είναι απαραίτητες για αυτές.
Αυτός είναι ένας πίνακας μετάβασης κατάστασης - ένας ολοκληρωμένος τρόπος αναπαράστασης του FSM. Ας σχεδιάσουμε ένα διάγραμμα και ας έχουμε μια πλήρη επισκόπηση του τρόπου με τον οποίο αλλάζει η συμπεριφορά του NPC.
Το διάγραμμα αντικατοπτρίζει την ουσία της λήψης αποφάσεων για αυτόν τον πράκτορα με βάση την τρέχουσα κατάσταση. Επιπλέον, κάθε βέλος δείχνει μια μετάβαση μεταξύ των καταστάσεων εάν η συνθήκη δίπλα του είναι αληθής.
Κάθε ενημέρωση ελέγχουμε την τρέχουσα κατάσταση του πράκτορα, εξετάζουμε τη λίστα με τις μεταβάσεις και εάν πληρούνται οι προϋποθέσεις για τη μετάβαση, αποδέχεται τη νέα κατάσταση. Για παράδειγμα, κάθε καρέ ελέγχει εάν ο χρονοδιακόπτης των 10 δευτερολέπτων έχει λήξει, και αν ναι, τότε ο φύλακας πηγαίνει από την κατάσταση αδράνειας στην περιπολία. Με τον ίδιο τρόπο, η κατάσταση επιτιθέμενης ελέγχει την υγεία του πράκτορα - αν είναι χαμηλή, τότε περνά στην κατάσταση Φυγής.
Αυτό είναι ο χειρισμός των μεταβάσεων μεταξύ των κρατών, αλλά τι γίνεται με τη συμπεριφορά που σχετίζεται με τα ίδια τα κράτη; Όσον αφορά την υλοποίηση της πραγματικής συμπεριφοράς για μια συγκεκριμένη κατάσταση, υπάρχουν συνήθως δύο τύποι "αγκίστρου" όπου αναθέτουμε ενέργειες στο FSM:
- Ενέργειες που εκτελούμε περιοδικά για την τρέχουσα κατάσταση.
- Οι ενέργειες που κάνουμε κατά τη μετάβαση από τη μια κατάσταση στην άλλη.
Παραδείγματα για τον πρώτο τύπο. Η κατάσταση περιπολίας θα μετακινήσει τον πράκτορα κατά μήκος της διαδρομής περιπολίας κάθε καρέ. Η κατάσταση επίθεσης θα επιχειρήσει να ξεκινήσει μια επίθεση σε κάθε πλαίσιο ή μετάβαση σε μια κατάσταση όπου αυτό είναι δυνατό.
Για τον δεύτερο τύπο, σκεφτείτε τη μετάβαση "εάν ο εχθρός είναι ορατός και ο εχθρός είναι πολύ δυνατός, τότε μεταβείτε στην κατάσταση Εύρεση Βοήθειας. Ο πράκτορας πρέπει να επιλέξει πού θα απευθυνθεί για βοήθεια και να αποθηκεύσει αυτές τις πληροφορίες, έτσι ώστε η κατάσταση Εύρεση βοήθειας να γνωρίζει πού να πάει. Μόλις βρεθεί βοήθεια, ο πράκτορας επιστρέφει στην κατάσταση επίθεσης. Σε αυτό το σημείο, θα θέλει να πει στον σύμμαχο για την απειλή, οπότε μπορεί να προκύψει η ενέργεια NotifyFriendOfThreat.
Για άλλη μια φορά, μπορούμε να δούμε αυτό το σύστημα μέσα από το φακό του κύκλου Sense/Think/Act. Η αίσθηση ενσωματώνεται στα δεδομένα που χρησιμοποιούνται από τη λογική μετάβασης. Think - μεταβάσεις διαθέσιμες σε κάθε κατάσταση. Και το Act εκτελείται από ενέργειες που εκτελούνται περιοδικά εντός μιας κατάστασης ή σε μεταβάσεις μεταξύ κρατών.
Μερικές φορές η συνεχής μεταβατική ψηφοφορία μπορεί να είναι δαπανηρή. Για παράδειγμα, εάν κάθε πράκτορας εκτελεί σύνθετους υπολογισμούς σε κάθε καρέ για να καθορίσει εάν μπορεί να δει εχθρούς και να καταλάβει εάν μπορεί να μεταβεί από την κατάσταση Περιπολίας σε Επίθεση, αυτό θα πάρει πολύ χρόνο CPU.
Σημαντικές αλλαγές στην κατάσταση του κόσμου μπορούν να θεωρηθούν ως γεγονότα που θα υποστούν επεξεργασία καθώς συμβαίνουν. Αντί το FSM να ελέγχει τη συνθήκη μετάβασης "μπορεί ο αντιπρόσωπός μου να δει τη συσκευή αναπαραγωγής;" κάθε καρέ, μπορεί να διαμορφωθεί ένα ξεχωριστό σύστημα ώστε να ελέγχει λιγότερο συχνά (π.χ. 5 φορές ανά δευτερόλεπτο). Και το αποτέλεσμα είναι να εκδίδεται το Player Seen όταν περάσει η επιταγή.
Αυτό μεταβιβάζεται στο FSM, το οποίο θα πρέπει τώρα να μεταβεί στη συνθήκη που έλαβε το συμβάν Player Seen και να ανταποκριθεί ανάλογα. Η συμπεριφορά που προκύπτει είναι η ίδια εκτός από μια σχεδόν ανεπαίσθητη καθυστέρηση πριν από την απόκριση. Αλλά η απόδοση έχει βελτιωθεί ως αποτέλεσμα του διαχωρισμού του τμήματος Sense σε ένα ξεχωριστό μέρος του προγράμματος.
Ιεραρχική μηχανή πεπερασμένης κατάστασης
Ωστόσο, η εργασία με μεγάλα FSM δεν είναι πάντα βολική. Αν θέλουμε να επεκτείνουμε την κατάσταση επίθεσης για να διαχωρίσουμε το MeleeAttacking και το RangedAttacking, θα πρέπει να αλλάξουμε τις μεταβάσεις από όλες τις άλλες καταστάσεις που οδηγούν στην κατάσταση Attacking (τρέχουσα και μελλοντική).
Ίσως παρατηρήσατε ότι στο παράδειγμά μας υπάρχουν πολλές διπλές μεταβάσεις. Οι περισσότερες μεταβάσεις στην κατάσταση αδράνειας είναι πανομοιότυπες με τις μεταβάσεις στην κατάσταση περιπολίας. Καλό θα ήταν να μην επαναλαμβανόμαστε, ειδικά αν προσθέσουμε περισσότερες παρόμοιες καταστάσεις. Είναι λογικό να ομαδοποιήσουμε το Idling και το Patrolling κάτω από τη γενική ετικέτα του "non-combat", όπου υπάρχει μόνο ένα κοινό σύνολο μεταβάσεων σε καταστάσεις μάχης. Αν σκεφτούμε αυτή την ετικέτα ως κράτος, τότε το Idling και το Patrolling γίνονται υποκράτη. Ένα παράδειγμα χρήσης ενός ξεχωριστού πίνακα μετάβασης για ένα νέο μη μαχητικό υποκράτος:
Κύριες καταστάσεις:
Κατάσταση εκτός μάχης:
Και σε μορφή διαγράμματος:
Είναι το ίδιο σύστημα, αλλά με μια νέα κατάσταση χωρίς μάχη που περιλαμβάνει το Idling και το Patrolling. Με κάθε κατάσταση να περιέχει ένα FSM με υποκαταστάσεις (και αυτές οι υποκαταστάσεις, με τη σειρά τους, περιέχουν τα δικά τους FSM - και ούτω καθεξής για όσο διάστημα χρειάζεστε), παίρνουμε μια Ιεραρχική Μηχανή Πεπερασμένης Κατάστασης ή HFSM (ιεραρχική μηχανή πεπερασμένης κατάστασης). Ομαδοποιώντας το μη μαχητικό κράτος, κόψαμε ένα σωρό περιττές μεταβάσεις. Μπορούμε να κάνουμε το ίδιο για κάθε νέα πολιτεία με κοινές μεταβάσεις. Για παράδειγμα, εάν στο μέλλον επεκτείνουμε την κατάσταση Attacking στις καταστάσεις MeleeAttacking και MissileAttacking, θα είναι υποκράτη που μεταβαίνονται μεταξύ τους με βάση την απόσταση από τον εχθρό και τη διαθεσιμότητα πυρομαχικών. Ως αποτέλεσμα, πολύπλοκες συμπεριφορές και υποσυμπεριφορές μπορούν να αναπαρασταθούν με ένα ελάχιστο διπλότυπες μεταβάσεις.
Δέντρο συμπεριφοράς
Με το HFSM δημιουργούνται πολύπλοκοι συνδυασμοί συμπεριφορών με απλό τρόπο. Ωστόσο, υπάρχει μια μικρή δυσκολία ότι η λήψη αποφάσεων με τη μορφή μεταβατικών κανόνων σχετίζεται στενά με την τρέχουσα κατάσταση. Και σε πολλά παιχνίδια αυτό ακριβώς χρειάζεται. Και η προσεκτική χρήση της ιεραρχίας του κράτους μπορεί να μειώσει τον αριθμό των επαναλήψεων μετάβασης. Αλλά μερικές φορές χρειάζεστε κανόνες που λειτουργούν ανεξάρτητα από την κατάσταση στην οποία βρίσκεστε ή που ισχύουν σχεδόν σε οποιαδήποτε πολιτεία. Για παράδειγμα, εάν η υγεία ενός πράκτορα πέσει στο 25%, θα θέλετε να τραπεί σε φυγή ανεξάρτητα από το αν ήταν σε μάχη, αδράνεια ή μιλώντας - θα πρέπει να προσθέσετε αυτήν την κατάσταση σε κάθε κατάσταση. Και αν αργότερα ο σχεδιαστής σας θέλει να αλλάξει το χαμηλό όριο υγείας από 25% σε 10%, τότε αυτό θα πρέπει να γίνει ξανά.
Στην ιδανική περίπτωση, αυτή η κατάσταση απαιτεί ένα σύστημα στο οποίο οι αποφάσεις σχετικά με το «σε ποια κατάσταση θα είναι» είναι εκτός των ίδιων των πολιτειών, προκειμένου να γίνονται αλλαγές μόνο σε ένα μέρος και να μην αγγίζουν τις συνθήκες μετάβασης. Τα δέντρα συμπεριφοράς εμφανίζονται εδώ.
Υπάρχουν διάφοροι τρόποι για την εφαρμογή τους, αλλά η ουσία είναι περίπου η ίδια για όλους και μοιάζει με ένα δέντρο αποφάσεων: ο αλγόριθμος ξεκινά με έναν κόμβο «ρίζας» και το δέντρο περιέχει κόμβους που αντιπροσωπεύουν είτε αποφάσεις είτε ενέργειες. Ωστόσο, υπάρχουν μερικές βασικές διαφορές:
- Οι κόμβοι επιστρέφουν τώρα μία από τις τρεις τιμές: Επιτυχία (αν η εργασία έχει ολοκληρωθεί), Αποτυχία (αν δεν μπορεί να ξεκινήσει) ή Εκτέλεση (εάν εξακολουθεί να εκτελείται και δεν υπάρχει τελικό αποτέλεσμα).
- Δεν υπάρχουν άλλοι κόμβοι απόφασης για να επιλέξετε ανάμεσα σε δύο εναλλακτικές. Αντίθετα, είναι κόμβοι Decorator, οι οποίοι έχουν έναν θυγατρικό κόμβο. Εάν τα καταφέρουν, εκτελούν τον μοναδικό θυγατρικό τους κόμβο.
- Οι κόμβοι που εκτελούν ενέργειες επιστρέφουν μια τιμή Εκτελούμενη για να αναπαραστήσουν τις ενέργειες που εκτελούνται.
Αυτό το μικρό σύνολο κόμβων μπορεί να συνδυαστεί για να δημιουργήσει έναν μεγάλο αριθμό πολύπλοκων συμπεριφορών. Ας φανταστούμε τον προφυλακτήρα HFSM από το προηγούμενο παράδειγμα ως δέντρο συμπεριφοράς:
Με αυτή τη δομή δεν θα πρέπει να υπάρχει προφανής μετάβαση από τις καταστάσεις αδράνειας/περιπολίας σε επιτιθέμενες ή άλλες καταστάσεις. Εάν ένας εχθρός είναι ορατός και η υγεία του χαρακτήρα είναι χαμηλή, η εκτέλεση θα σταματήσει στον κόμβο Φεύγοντας, ανεξάρτητα από τον κόμβο που εκτελούσε προηγουμένως - Περιπολία, Αδράνεια, Επίθεση ή οποιονδήποτε άλλο.
Τα δέντρα συμπεριφοράς είναι πολύπλοκα—υπάρχουν πολλοί τρόποι σύνθεσής τους και η εύρεση του σωστού συνδυασμού διακοσμητών και σύνθετων κόμβων μπορεί να είναι δύσκολη. Υπάρχουν επίσης ερωτήσεις σχετικά με το πόσο συχνά πρέπει να ελέγχουμε το δέντρο - θέλουμε να περάσουμε από κάθε μέρος του ή μόνο όταν έχει αλλάξει μία από τις συνθήκες; Πώς αποθηκεύουμε την κατάσταση που σχετίζεται με τους κόμβους - πώς γνωρίζουμε πότε είμαστε σε αδράνεια για 10 δευτερόλεπτα ή πώς γνωρίζουμε ποιοι κόμβοι εκτελούσαν την τελευταία φορά, ώστε να μπορούμε να επεξεργαστούμε σωστά την ακολουθία;
Αυτός είναι ο λόγος που υπάρχουν πολλές υλοποιήσεις. Για παράδειγμα, ορισμένα συστήματα έχουν αντικαταστήσει τους κόμβους διακοσμητών με ενσωματωμένους διακοσμητές. Επαναξιολογούν το δέντρο όταν αλλάζουν οι συνθήκες του διακοσμητή, βοηθούν στη σύνδεση κόμβων και παρέχουν περιοδικές ενημερώσεις.
Σύστημα που βασίζεται σε βοηθητικά προγράμματα
Ορισμένα παιχνίδια έχουν πολλούς διαφορετικούς μηχανισμούς. Είναι επιθυμητό να λαμβάνουν όλα τα οφέλη των απλών και γενικών κανόνων μετάβασης, αλλά όχι απαραίτητα με τη μορφή ενός πλήρους δέντρου συμπεριφοράς. Αντί να έχετε ένα σαφές σύνολο επιλογών ή ένα δέντρο πιθανών ενεργειών, είναι ευκολότερο να εξετάσετε όλες τις ενέργειες και να επιλέξετε την καταλληλότερη αυτή τη στιγμή.
Το σύστημα που βασίζεται σε Utility θα βοηθήσει ακριβώς σε αυτό. Αυτό είναι ένα σύστημα όπου ο πράκτορας έχει μια ποικιλία ενεργειών και επιλέγει ποιες θα εκτελέσει με βάση τη σχετική χρησιμότητα του καθενός. Όπου η χρησιμότητα είναι ένα αυθαίρετο μέτρο του πόσο σημαντικό ή επιθυμητό είναι για τον πράκτορα να εκτελέσει αυτήν την ενέργεια.
Η υπολογισμένη χρησιμότητα μιας ενέργειας με βάση την τρέχουσα κατάσταση και το περιβάλλον, ο πράκτορας μπορεί να ελέγξει και να επιλέξει την καταλληλότερη άλλη κατάσταση ανά πάσα στιγμή. Αυτό είναι παρόμοιο με το FSM, εκτός από τις περιπτώσεις όπου οι μεταβάσεις καθορίζονται από μια εκτίμηση για κάθε πιθανή κατάσταση, συμπεριλαμβανομένης της τρέχουσας. Λάβετε υπόψη ότι επιλέγουμε την πιο χρήσιμη ενέργεια για να προχωρήσουμε (ή να παραμείνουμε αν την έχουμε ήδη ολοκληρώσει). Για περισσότερη ποικιλία, αυτή θα μπορούσε να είναι μια ισορροπημένη αλλά τυχαία επιλογή από μια μικρή λίστα.
Το σύστημα εκχωρεί ένα αυθαίρετο εύρος τιμών χρησιμότητας — για παράδειγμα, από 0 (εντελώς ανεπιθύμητο) έως 100 (εντελώς επιθυμητό). Κάθε ενέργεια έχει έναν αριθμό παραμέτρων που επηρεάζουν τον υπολογισμό αυτής της τιμής. Επιστρέφοντας στο παράδειγμα του φύλακα μας:
Οι μεταβάσεις μεταξύ των ενεργειών είναι διφορούμενες - οποιαδήποτε κατάσταση μπορεί να ακολουθήσει οποιαδήποτε άλλη. Οι προτεραιότητες ενεργειών βρίσκονται στις επιστρεφόμενες τιμές βοηθητικού προγράμματος. Εάν ένας εχθρός είναι ορατός και αυτός ο εχθρός είναι ισχυρός και η υγεία του χαρακτήρα είναι χαμηλή, τότε τόσο το Fleeing όσο και το FindingHelp θα επιστρέψουν υψηλές μη μηδενικές τιμές. Σε αυτήν την περίπτωση, το FindingHelp θα είναι πάντα υψηλότερο. Ομοίως, οι μη μάχιμες δραστηριότητες δεν επιστρέφουν ποτέ πάνω από 50, επομένως θα είναι πάντα χαμηλότερες από τις μάχιμες. Πρέπει να το λάβετε υπόψη κατά τη δημιουργία ενεργειών και τον υπολογισμό της χρησιμότητάς τους.
Στο παράδειγμά μας, οι ενέργειες επιστρέφουν είτε μια σταθερή σταθερή τιμή είτε μία από δύο σταθερές τιμές. Ένα πιο ρεαλιστικό σύστημα θα επέστρεφε μια εκτίμηση από ένα συνεχές εύρος τιμών. Για παράδειγμα, η ενέργεια Fleeing επιστρέφει υψηλότερες τιμές χρησιμότητας εάν η υγεία του πράκτορα είναι χαμηλή και η ενέργεια Επίθεση επιστρέφει χαμηλότερες τιμές χρησιμότητας εάν ο εχθρός είναι πολύ ισχυρός. Εξαιτίας αυτού, η δράση Φυγή έχει προτεραιότητα έναντι της Επίθεσης σε οποιαδήποτε κατάσταση ο πράκτορας αισθάνεται ότι δεν έχει αρκετή υγεία για να νικήσει τον εχθρό. Αυτό επιτρέπει την ιεράρχηση των ενεργειών βάσει οποιουδήποτε αριθμού κριτηρίων, καθιστώντας αυτήν την προσέγγιση πιο ευέλικτη και μεταβλητή από ένα δέντρο συμπεριφοράς ή ένα FSM.
Κάθε ενέργεια έχει πολλές προϋποθέσεις για τον υπολογισμό του προγράμματος. Μπορούν να γραφτούν σε γλώσσα σεναρίου ή ως μια σειρά από μαθηματικούς τύπους. Το Sims, το οποίο προσομοιώνει την καθημερινή ρουτίνα ενός χαρακτήρα, προσθέτει ένα επιπλέον επίπεδο υπολογισμού - ο πράκτορας λαμβάνει μια σειρά από "κίνητρα" που επηρεάζουν τις αξιολογήσεις χρησιμότητας. Εάν ένας χαρακτήρας πεινάει, θα γίνει ακόμα πιο πεινασμένος με την πάροδο του χρόνου και η χρησιμότητα της ενέργειας EatFood θα αυξάνεται μέχρι να την εκτελέσει ο χαρακτήρας, μειώνοντας το επίπεδο πείνας και επιστρέφοντας την τιμή EatFood στο μηδέν.
Η ιδέα της επιλογής ενεργειών με βάση ένα σύστημα αξιολόγησης είναι αρκετά απλή, επομένως ένα σύστημα που βασίζεται σε Utility μπορεί να χρησιμοποιηθεί ως μέρος των διαδικασιών λήψης αποφάσεων AI, παρά ως πλήρης αντικατάστασή τους. Το δέντρο αποφάσεων μπορεί να ζητήσει μια βαθμολογία χρησιμότητας δύο θυγατρικών κόμβων και να επιλέξει τον υψηλότερο. Ομοίως, ένα δέντρο συμπεριφοράς μπορεί να έχει έναν σύνθετο κόμβο Utility για να αξιολογήσει τη χρησιμότητα των ενεργειών για να αποφασίσει ποιο παιδί θα εκτελέσει.
Κίνηση και πλοήγηση
Στα προηγούμενα παραδείγματα, είχαμε μια πλατφόρμα που μετακινούσαμε αριστερά ή δεξιά και έναν φρουρό που περιπολούσε ή επιτέθηκε. Αλλά πώς ακριβώς χειριζόμαστε την κίνηση των πρακτόρων σε μια χρονική περίοδο; Πώς ορίζουμε την ταχύτητα, πώς αποφεύγουμε τα εμπόδια και πώς σχεδιάζουμε μια διαδρομή όταν το να φτάσουμε σε έναν προορισμό είναι πιο δύσκολο από την απλή κίνηση σε ευθεία γραμμή; Ας το δούμε αυτό.
Διοίκηση
Στο αρχικό στάδιο, θα υποθέσουμε ότι κάθε πράκτορας έχει μια τιμή ταχύτητας, η οποία περιλαμβάνει πόσο γρήγορα κινείται και προς ποια κατεύθυνση. Μπορεί να μετρηθεί σε μέτρα ανά δευτερόλεπτο, χιλιόμετρα ανά ώρα, εικονοστοιχεία ανά δευτερόλεπτο κ.λπ. Ανακαλώντας τον βρόχο Sense/Think/Act, μπορούμε να φανταστούμε ότι το τμήμα Think επιλέγει μια ταχύτητα και το τμήμα Act εφαρμόζει αυτή την ταχύτητα στον πράκτορα. Συνήθως τα παιχνίδια έχουν ένα σύστημα φυσικής που κάνει αυτήν την εργασία για εσάς, μαθαίνοντας την τιμή ταχύτητας κάθε αντικειμένου και προσαρμόζοντάς το. Επομένως, μπορείτε να αφήσετε το AI με ένα καθήκον - να αποφασίσετε ποια ταχύτητα πρέπει να έχει ο πράκτορας. Εάν γνωρίζετε πού πρέπει να βρίσκεται ο πράκτορας, τότε πρέπει να τον μετακινήσετε στη σωστή κατεύθυνση με μια καθορισμένη ταχύτητα. Μια πολύ ασήμαντη εξίσωση:
επιθυμητό_ταξίδι = προορισμό_θέση – θέση_πράκτορα
Φανταστείτε έναν κόσμο 2D. Ο πράκτορας βρίσκεται στο σημείο (-2,-2), ο προορισμός είναι κάπου στα βορειοανατολικά στο σημείο (30, 20) και η απαιτούμενη διαδρομή για να φτάσει ο πράκτορας εκεί είναι (32, 22). Ας υποθέσουμε ότι αυτές οι θέσεις μετρώνται σε μέτρα - αν πάρουμε την ταχύτητα του παράγοντα στα 5 μέτρα ανά δευτερόλεπτο, τότε θα κλιμακώσουμε το διάνυσμα μετατόπισής μας και θα πάρουμε ταχύτητα περίπου (4.12, 2.83). Με αυτές τις παραμέτρους, ο πράκτορας θα έφτανε στον προορισμό του σε σχεδόν 8 δευτερόλεπτα.
Μπορείτε να υπολογίσετε ξανά τις τιμές ανά πάσα στιγμή. Εάν ο πράκτορας ήταν στα μισά του δρόμου προς τον στόχο, η κίνηση θα ήταν το μισό του μήκους, αλλά επειδή η μέγιστη ταχύτητα του πράκτορα είναι 5 m/s (το αποφασίσαμε παραπάνω), η ταχύτητα θα είναι η ίδια. Αυτό λειτουργεί επίσης για κινούμενους στόχους, επιτρέποντας στον πράκτορα να κάνει μικρές αλλαγές καθώς κινούνται.
Θέλουμε όμως μεγαλύτερη ποικιλία - για παράδειγμα, αυξάνοντας αργά την ταχύτητα για την προσομοίωση ενός χαρακτήρα που κινείται από την όρθια στάση στο τρέξιμο. Το ίδιο μπορεί να γίνει στο τέλος πριν σταματήσει. Αυτά τα χαρακτηριστικά είναι γνωστά ως συμπεριφορές διεύθυνσης, καθεμία από τις οποίες έχει συγκεκριμένα ονόματα: Αναζήτηση, Φυγή, Άφιξη κ.λπ. Η ιδέα είναι ότι δυνάμεις επιτάχυνσης μπορούν να εφαρμοστούν στην ταχύτητα του πράκτορα, με βάση τη σύγκριση της θέσης και της τρέχουσας ταχύτητας του πράκτορα με τον προορισμό στο προκειμένου να χρησιμοποιήσετε διαφορετικές μεθόδους μετάβασης προς τον στόχο.
Κάθε συμπεριφορά έχει λίγο διαφορετικό σκοπό. Η αναζήτηση και η άφιξη είναι τρόποι για να μετακινήσετε έναν πράκτορα σε έναν προορισμό. Η αποφυγή εμποδίων και ο διαχωρισμός προσαρμόζουν την κίνηση του πράκτορα για να αποφύγετε εμπόδια στο δρόμο προς τον στόχο. Η ευθυγράμμιση και η συνοχή κρατούν τους πράκτορες να κινούνται μαζί. Οποιοσδήποτε αριθμός διαφορετικών συμπεριφορών διεύθυνσης μπορεί να αθροιστεί για να παραχθεί ένα ενιαίο διάνυσμα διαδρομής λαμβάνοντας υπόψη όλους τους παράγοντες. Ένας πράκτορας που χρησιμοποιεί τις συμπεριφορές άφιξης, διαχωρισμού και αποφυγής εμποδίων για να μείνει μακριά από τοίχους και άλλους πράκτορες. Αυτή η προσέγγιση λειτουργεί καλά σε ανοιχτές τοποθεσίες χωρίς περιττές λεπτομέρειες.
Σε πιο δύσκολες συνθήκες, η προσθήκη διαφορετικών συμπεριφορών λειτουργεί χειρότερα - για παράδειγμα, ένας πράκτορας μπορεί να κολλήσει σε έναν τοίχο λόγω μιας σύγκρουσης μεταξύ Άφιξης και Αποφυγής εμποδίων. Επομένως, πρέπει να εξετάσετε τις επιλογές που είναι πιο περίπλοκες από την απλή προσθήκη όλων των τιμών. Ο τρόπος είναι αυτός: αντί να αθροίζετε τα αποτελέσματα κάθε συμπεριφοράς, μπορείτε να εξετάσετε την κίνηση προς διαφορετικές κατευθύνσεις και να επιλέξετε την καλύτερη επιλογή.
Ωστόσο, σε ένα σύνθετο περιβάλλον με αδιέξοδα και επιλογές για το ποιο δρόμο να ακολουθήσουμε, θα χρειαστούμε κάτι ακόμα πιο προηγμένο.
Βρίσκοντας τρόπο
Οι συμπεριφορές διεύθυνσης είναι εξαιρετικές για απλή κίνηση σε ανοιχτό χώρο (γήπεδο ποδοσφαίρου ή αρένα) όπου η μετάβαση από το Α στο Β είναι μια ευθεία διαδρομή με μικρές μόνο παρακάμψεις γύρω από εμπόδια. Για πολύπλοκες διαδρομές, χρειαζόμαστε μονοπάτι, που είναι ένας τρόπος να εξερευνήσουμε τον κόσμο και να αποφασίσουμε για μια διαδρομή μέσω αυτού.
Το πιο απλό είναι να εφαρμόσετε ένα πλέγμα σε κάθε τετράγωνο δίπλα στον πράκτορα και να αξιολογήσετε ποια από αυτά επιτρέπεται να μετακινηθούν. Αν ένα από αυτά είναι προορισμός, τότε ακολουθήστε τη διαδρομή από κάθε τετράγωνο προς το προηγούμενο μέχρι να φτάσετε στην αρχή. Αυτή είναι η διαδρομή. Διαφορετικά, επαναλάβετε τη διαδικασία με άλλα κοντινά τετράγωνα μέχρι να βρείτε τον προορισμό σας ή να ξεμείνετε από τετράγωνα (που σημαίνει ότι δεν υπάρχει πιθανή διαδρομή). Αυτό είναι που είναι επίσημα γνωστό ως Breadth-First Search ή BFS (breadth-first search algorithm). Σε κάθε βήμα κοιτάζει προς όλες τις κατευθύνσεις (άρα πλάτος, «πλάτος»). Ο χώρος αναζήτησης είναι σαν ένα μέτωπο κύματος που κινείται μέχρι να φτάσει στην επιθυμητή θέση - ο χώρος αναζήτησης επεκτείνεται σε κάθε βήμα μέχρι να συμπεριληφθεί το τελικό σημείο, μετά το οποίο μπορεί να εντοπιστεί στην αρχή.
Ως αποτέλεσμα, θα λάβετε μια λίστα με τετράγωνα κατά μήκος των οποίων συντάσσεται η επιθυμητή διαδρομή. Αυτή είναι η διαδρομή (επομένως, εύρεση διαδρομής) - μια λίστα με μέρη που θα επισκεφτεί ο πράκτορας ενώ ακολουθεί τον προορισμό.
Δεδομένου ότι γνωρίζουμε τη θέση κάθε τετραγώνου στον κόσμο, μπορούμε να χρησιμοποιήσουμε συμπεριφορές διεύθυνσης για να κινηθούμε κατά μήκος της διαδρομής - από τον κόμβο 1 στον κόμβο 2, μετά από τον κόμβο 2 στον κόμβο 3 και ούτω καθεξής. Η απλούστερη επιλογή είναι να κατευθυνθείτε προς το κέντρο του επόμενου τετραγώνου, αλλά μια ακόμα καλύτερη επιλογή είναι να σταματήσετε στη μέση της άκρης μεταξύ του τρέχοντος τετραγώνου και του επόμενου. Εξαιτίας αυτού, ο πράκτορας θα μπορεί να κόβει τις γωνίες σε απότομες στροφές.
Ο αλγόριθμος BFS έχει επίσης μειονεκτήματα - διερευνά τόσα τετράγωνα προς τη «λάθος» κατεύθυνση όσο και προς τη «σωστή». Εδώ μπαίνει στο παιχνίδι ένας πιο σύνθετος αλγόριθμος που ονομάζεται A* (A star). Λειτουργεί με τον ίδιο τρόπο, αλλά αντί να εξετάζει τυφλά τα τετράγωνα γειτόνων (μετά γείτονες γειτόνων, μετά γείτονες γειτόνων κ.λπ.), συλλέγει τους κόμβους σε μια λίστα και τους ταξινομεί έτσι ώστε ο επόμενος κόμβος που εξετάζεται να είναι πάντα ο αυτή που οδηγεί στη συντομότερη διαδρομή. Οι κόμβοι ταξινομούνται με βάση μια ευρετική που λαμβάνει υπόψη δύο πράγματα: το «κόστος» μιας υποθετικής διαδρομής προς το επιθυμητό τετράγωνο (συμπεριλαμβανομένου τυχόν κόστους ταξιδιού) και μια εκτίμηση του πόσο μακριά είναι αυτό το τετράγωνο από τον προορισμό (προκατάληψη της αναζήτησης στο σωστή κατεύθυνση).
Αυτό το παράδειγμα δείχνει ότι ο πράκτορας εξερευνά ένα τετράγωνο κάθε φορά, επιλέγοντας κάθε φορά το διπλανό που είναι το πιο πολλά υποσχόμενο. Το μονοπάτι που προκύπτει είναι το ίδιο με το BFS, αλλά λήφθηκαν λιγότερα τετράγωνα στη διαδικασία - κάτι που έχει μεγάλο αντίκτυπο στην απόδοση του παιχνιδιού.
Κίνηση χωρίς πλέγμα
Αλλά τα περισσότερα παιχνίδια δεν είναι τοποθετημένα σε ένα πλέγμα και συχνά είναι αδύνατο να το κάνετε χωρίς να θυσιαστεί ο ρεαλισμός. Χρειάζονται συμβιβασμοί. Τι μέγεθος πρέπει να έχουν τα τετράγωνα; Πολύ μεγάλο και δεν θα μπορούν να αναπαραστήσουν σωστά μικρούς διαδρόμους ή στροφές, πολύ μικρές και θα υπάρχουν πάρα πολλά τετράγωνα για αναζήτηση, κάτι που τελικά θα πάρει πολύ χρόνο.
Το πρώτο πράγμα που πρέπει να καταλάβουμε είναι ότι ένα πλέγμα μας δίνει ένα γράφημα συνδεδεμένων κόμβων. Οι αλγόριθμοι A* και BFS στην πραγματικότητα λειτουργούν σε γραφήματα και δεν ενδιαφέρονται καθόλου για το πλέγμα μας. Θα μπορούσαμε να βάλουμε κόμβους οπουδήποτε στον κόσμο του παιχνιδιού: εφόσον υπάρχει σύνδεση μεταξύ οποιωνδήποτε δύο συνδεδεμένων κόμβων, καθώς και μεταξύ των σημείων έναρξης και τέλους και τουλάχιστον ενός από τους κόμβους, ο αλγόριθμος θα λειτουργεί εξίσου καλά όπως πριν. Αυτό ονομάζεται συχνά σύστημα σημείων διαδρομής, καθώς κάθε κόμβος αντιπροσωπεύει μια σημαντική θέση στον κόσμο που μπορεί να είναι μέρος οποιουδήποτε αριθμού υποθετικών μονοπατιών.
Παράδειγμα 1: ένας κόμπος σε κάθε τετράγωνο. Η αναζήτηση ξεκινά από τον κόμβο όπου βρίσκεται ο πράκτορας και καταλήγει στον κόμβο του επιθυμητού τετραγώνου.
Παράδειγμα 2: Ένα μικρότερο σύνολο κόμβων (σημεία διαδρομής). Η αναζήτηση ξεκινά από το τετράγωνο του πράκτορα, περνά από τον απαιτούμενο αριθμό κόμβων και μετά συνεχίζει στον προορισμό.
Αυτό είναι ένα εντελώς ευέλικτο και ισχυρό σύστημα. Χρειάζεται όμως λίγη προσοχή για να αποφασίσετε πού και πώς θα τοποθετήσετε ένα σημείο, διαφορετικά οι πράκτορες μπορεί απλώς να μην δουν το πλησιέστερο σημείο και να μην μπορούν να ξεκινήσουν τη διαδρομή. Θα ήταν ευκολότερο αν μπορούσαμε να τοποθετήσουμε αυτόματα σημεία με βάση τη γεωμετρία του κόσμου.
Εδώ εμφανίζεται το πλέγμα πλοήγησης ή το navmesh (πλέγμα πλοήγησης). Αυτό είναι συνήθως ένα δισδιάστατο πλέγμα τριγώνων που επικαλύπτεται στη γεωμετρία του κόσμου - οπουδήποτε επιτρέπεται στον πράκτορα να περπατήσει. Καθένα από τα τρίγωνα στο πλέγμα γίνεται κόμβος στο γράφημα και έχει έως και τρία γειτονικά τρίγωνα που γίνονται γειτονικοί κόμβοι στο γράφημα.
Αυτή η εικόνα είναι ένα παράδειγμα από τη μηχανή Unity - ανέλυσε τη γεωμετρία στον κόσμο και δημιούργησε ένα navmesh (στο στιγμιότυπο οθόνης σε ανοιχτό μπλε). Κάθε πολύγωνο σε ένα navmesh είναι μια περιοχή όπου ένας πράκτορας μπορεί να σταθεί ή να μετακινηθεί από ένα πολύγωνο σε άλλο πολύγωνο. Σε αυτό το παράδειγμα, τα πολύγωνα είναι μικρότερα από τους ορόφους στους οποίους βρίσκονται - αυτό γίνεται προκειμένου να ληφθεί υπόψη το μέγεθος του πράκτορα, το οποίο θα εκτείνεται πέρα από την ονομαστική του θέση.
Μπορούμε να αναζητήσουμε μια διαδρομή μέσα από αυτό το πλέγμα, χρησιμοποιώντας πάλι τον αλγόριθμο A*. Αυτό θα μας δώσει μια σχεδόν τέλεια διαδρομή στον κόσμο, η οποία λαμβάνει υπόψη όλη τη γεωμετρία και δεν απαιτεί περιττούς κόμβους και δημιουργία σημείων διαδρομής.
Η εύρεση διαδρομής είναι ένα πολύ ευρύ θέμα για το οποίο δεν αρκεί μια ενότητα ενός άρθρου. Εάν θέλετε να το μελετήσετε λεπτομερέστερα, τότε αυτό θα σας βοηθήσει .
Σχεδιασμός
Με το μονοπάτι μάθαμε ότι μερικές φορές δεν αρκεί απλώς να επιλέγουμε μια κατεύθυνση και να κινούμαστε - πρέπει να διαλέξουμε μια διαδρομή και να κάνουμε μερικές στροφές για να φτάσουμε στον επιθυμητό προορισμό μας. Μπορούμε να γενικεύσουμε αυτήν την ιδέα: η επίτευξη ενός στόχου δεν είναι απλώς το επόμενο βήμα, αλλά μια ολόκληρη σειρά όπου μερικές φορές χρειάζεται να κοιτάξετε μπροστά πολλά βήματα για να μάθετε ποιο πρέπει να είναι το πρώτο. Αυτό ονομάζεται προγραμματισμός. Το Pathfinding μπορεί να θεωρηθεί ως μία από τις πολλές επεκτάσεις του προγραμματισμού. Όσον αφορά τον κύκλο μας Sense/Think/Act, αυτό είναι όπου το τμήμα Think σχεδιάζει πολλαπλά μέρη Act για το μέλλον.
Ας δούμε το παράδειγμα του επιτραπέζιου παιχνιδιού Magic: The Gathering. Πηγαίνουμε πρώτα με το παρακάτω σετ καρτών στα χέρια μας:
- Βάλτος - Δίνει 1 μαύρη μάνα (κάρτα γης).
- Δάσος - δίνει 1 πράσινη μάνα (κάρτα γης).
- Fugitive Wizard - Απαιτείται 1 μπλε μάνα για κλήση.
- Elvish Mystic - Απαιτείται 1 πράσινο μάνα για να κληθεί.
Αγνοούμε τα υπόλοιπα τρία φύλλα για να το κάνουμε πιο εύκολο. Σύμφωνα με τους κανόνες, ένας παίκτης επιτρέπεται να παίξει 1 χαρτί γης ανά γύρο, μπορεί να "πατήσει" αυτό το φύλλο για να βγάλει μάνα από αυτό και στη συνέχεια να κάνει ξόρκια (συμπεριλαμβανομένης της κλήσης ενός πλάσματος) ανάλογα με την ποσότητα μάνα. Σε αυτήν την κατάσταση, ο άνθρωπος παίκτης ξέρει να παίζει Forest, να πατάει 1 πράσινο μάνα και μετά να καλεί τον Elvish Mystic. Αλλά πώς μπορεί το παιχνίδι AI να το καταλάβει αυτό;
Εύκολος προγραμματισμός
Η τετριμμένη προσέγγιση είναι να δοκιμάσετε κάθε ενέργεια με τη σειρά μέχρι να μην μείνουν οι κατάλληλες. Κοιτώντας τις κάρτες, το AI βλέπει τι μπορεί να παίξει ο Swamp. Και το παίζει. Απομένουν άλλες ενέργειες από αυτή τη σειρά; Δεν μπορεί να καλέσει ούτε τον Elvish Mystic ούτε τον Fugitive Wizard, καθώς απαιτούν πράσινο και μπλε μάνα αντίστοιχα για να τους καλέσουν, ενώ το Swamp παρέχει μόνο μαύρο μάνα. Και δεν θα μπορεί πλέον να παίζει Forest, γιατί έχει ήδη παίξει το Swamp. Έτσι, το παιχνίδι AI ακολούθησε τους κανόνες, αλλά το έκανε άσχημα. Μπορεί να βελτιωθεί.
Ο προγραμματισμός μπορεί να βρει μια λίστα ενεργειών που φέρνουν το παιχνίδι στην επιθυμητή κατάσταση. Όπως κάθε τετράγωνο σε ένα μονοπάτι είχε γείτονες (στο μονοπάτι), κάθε δράση σε ένα σχέδιο έχει επίσης γείτονες ή διαδόχους. Μπορούμε να αναζητήσουμε αυτές τις ενέργειες και τις επόμενες ενέργειες μέχρι να φτάσουμε στην επιθυμητή κατάσταση.
Στο παράδειγμά μας, το επιθυμητό αποτέλεσμα είναι «καλέστε ένα πλάσμα αν είναι δυνατόν». Στην αρχή της στροφής, βλέπουμε μόνο δύο πιθανές ενέργειες που επιτρέπονται από τους κανόνες του παιχνιδιού:
1. Παίξτε Swamp (αποτέλεσμα: Swamp στο παιχνίδι)
2. Παίξτε Forest (αποτέλεσμα: Forest στο παιχνίδι)
Κάθε ενέργεια που γίνεται μπορεί να οδηγήσει σε περαιτέρω ενέργειες και να κλείσει άλλες, ανάλογα και πάλι με τους κανόνες του παιχνιδιού. Φανταστείτε ότι παίξαμε Swamp - αυτό θα αφαιρέσει το Swamp ως το επόμενο βήμα (το έχουμε ήδη παίξει) και αυτό θα αφαιρέσει επίσης το Forest (γιατί σύμφωνα με τους κανόνες μπορείτε να παίξετε ένα χαρτί γης ανά γύρο). Μετά από αυτό, το AI προσθέτει τη λήψη 1 μαύρου μάνα ως επόμενο βήμα, επειδή δεν υπάρχουν άλλες επιλογές. Αν προχωρήσει και επιλέξει Tap the Swamp, θα λάβει 1 μονάδα μαύρης μάνας και δεν θα μπορεί να κάνει τίποτα με αυτό.
1. Παίξτε Swamp (αποτέλεσμα: Swamp στο παιχνίδι)
1.1 "Tap" Swamp (αποτέλεσμα: Swamp "tapped", +1 μονάδα μαύρου μάνα)
Δεν υπάρχουν διαθέσιμες ενέργειες - ΤΕΛΟΣ
2. Παίξτε Forest (αποτέλεσμα: Forest στο παιχνίδι)
Ο κατάλογος των ενεργειών ήταν σύντομος, φτάσαμε σε αδιέξοδο. Επαναλαμβάνουμε τη διαδικασία για το επόμενο βήμα. Παίζουμε Forest, ανοίγουμε τη δράση "get 1 green mana", η οποία με τη σειρά της θα ανοίξει την τρίτη δράση - καλέστε τον Elvish Mystic.
1. Παίξτε Swamp (αποτέλεσμα: Swamp στο παιχνίδι)
1.1 "Tap" Swamp (αποτέλεσμα: Swamp "tapped", +1 μονάδα μαύρου μάνα)
Δεν υπάρχουν διαθέσιμες ενέργειες - ΤΕΛΟΣ
2. Παίξτε Forest (αποτέλεσμα: Forest στο παιχνίδι)
2.1 "Tap" Forest (αποτέλεσμα: Το δάσος είναι "tapped", +1 μονάδα πράσινου μάνα)
2.1.1 Summon Elvish Mystic (αποτέλεσμα: Elvish Mystic στο παιχνίδι, -1 πράσινο μάνα)
Δεν υπάρχουν διαθέσιμες ενέργειες - ΤΕΛΟΣ
Τέλος, εξερευνήσαμε όλες τις πιθανές ενέργειες και βρήκαμε ένα σχέδιο που καλεί ένα πλάσμα.
Αυτό είναι ένα πολύ απλοποιημένο παράδειγμα. Συνιστάται να επιλέξετε το καλύτερο δυνατό σχέδιο και όχι οποιοδήποτε σχέδιο που πληροί κάποια κριτήρια. Είναι γενικά δυνατό να αξιολογηθούν πιθανά σχέδια με βάση το αποτέλεσμα ή το συνολικό όφελος από την εφαρμογή τους. Μπορείτε να κερδίσετε 1 πόντο για να παίξετε μια κάρτα γης και 3 πόντους για να καλέσετε ένα πλάσμα. Το να παίξετε το Swamp θα ήταν ένα σχέδιο 1 πόντου. Και παίζοντας Forest → Tap the Forest → summon Elvish Mystic θα δώσει αμέσως 4 πόντους.
Έτσι λειτουργεί ο προγραμματισμός στο Magic: The Gathering, αλλά η ίδια λογική ισχύει και σε άλλες καταστάσεις. Για παράδειγμα, μετακινώντας ένα πιόνι για να δημιουργηθεί χώρος στον επίσκοπο να κινηθεί στο σκάκι. Ή κρυφτείτε πίσω από έναν τοίχο για να τραβήξετε με ασφάλεια σε XCOM όπως αυτό. Σε γενικές γραμμές, καταλαβαίνετε την ιδέα.
Βελτιωμένος προγραμματισμός
Μερικές φορές υπάρχουν πάρα πολλές πιθανές ενέργειες για να εξεταστεί κάθε δυνατή επιλογή. Επιστρέφοντας στο παράδειγμα με το Magic: The Gathering: ας πούμε ότι στο παιχνίδι και στο χέρι σας υπάρχουν αρκετές κάρτες γης και πλασμάτων - ο αριθμός των πιθανών συνδυασμών κινήσεων μπορεί να είναι δεκάδες. Υπάρχουν αρκετές λύσεις στο πρόβλημα.
Η πρώτη μέθοδος είναι η ανάστροφη αλυσίδα. Αντί να δοκιμάσετε όλους τους συνδυασμούς, είναι προτιμότερο να ξεκινήσετε με το τελικό αποτέλεσμα και να προσπαθήσετε να βρείτε μια άμεση διαδρομή. Αντί να πάμε από τη ρίζα του δέντρου σε ένα συγκεκριμένο φύλλο, κινούμαστε προς την αντίθετη κατεύθυνση - από το φύλλο στη ρίζα. Αυτή η μέθοδος είναι ευκολότερη και πιο γρήγορη.
Εάν ο εχθρός έχει 1 υγεία, μπορείτε να βρείτε το σχέδιο "προσφορά 1 ή περισσότερων ζημιών". Για να επιτευχθεί αυτό, πρέπει να πληρούνται ορισμένες προϋποθέσεις:
1. Μπορεί να προκληθεί ζημιά από ξόρκι - πρέπει να είναι στο χέρι.
2. Για να κάνεις ξόρκι, χρειάζεσαι μάνα.
3. Για να αποκτήσετε μάνα, πρέπει να παίξετε μια κάρτα γης.
4. Για να παίξετε μια κάρτα γης, πρέπει να την έχετε στο χέρι σας.
Ένας άλλος τρόπος είναι η καλύτερη αναζήτηση. Αντί να δοκιμάσουμε όλα τα μονοπάτια, επιλέγουμε το καταλληλότερο. Τις περισσότερες φορές, αυτή η μέθοδος παρέχει το βέλτιστο σχέδιο χωρίς περιττό κόστος αναζήτησης. Το A* είναι μια μορφή καλύτερης πρώτης αναζήτησης - εξετάζοντας τις πιο υποσχόμενες διαδρομές από την αρχή, μπορεί ήδη να βρει την καλύτερη διαδρομή χωρίς να χρειάζεται να ελέγξει άλλες επιλογές.
Μια ενδιαφέρουσα και ολοένα και πιο δημοφιλής επιλογή αναζήτησης καλύτερης πρώτης είναι η Αναζήτηση στο δέντρο του Μόντε Κάρλο. Αντί να μαντεύει ποια σχέδια είναι καλύτερα από άλλα κατά την επιλογή κάθε επόμενης ενέργειας, ο αλγόριθμος επιλέγει τυχαίους διαδόχους σε κάθε βήμα μέχρι να φτάσει στο τέλος (όταν το σχέδιο οδήγησε σε νίκη ή ήττα). Το τελικό αποτέλεσμα χρησιμοποιείται στη συνέχεια για την αύξηση ή τη μείωση του βάρους των προηγούμενων επιλογών. Επαναλαμβάνοντας αυτή τη διαδικασία πολλές φορές στη σειρά, ο αλγόριθμος δίνει μια καλή εκτίμηση για το ποια είναι η καλύτερη επόμενη κίνηση, ακόμα κι αν αλλάξει η κατάσταση (αν ο εχθρός αναλάβει δράση για να παρέμβει στον παίκτη).
Καμία ιστορία σχετικά με τον προγραμματισμό σε παιχνίδια δεν θα ήταν πλήρης χωρίς Σχεδιασμό δράσης με προσανατολισμό στο στόχο ή GOAP (σχεδιασμός δράσης με προσανατολισμό στο στόχο). Αυτή είναι μια ευρέως χρησιμοποιούμενη και συζητημένη μέθοδος, αλλά εκτός από μερικές διακριτικές λεπτομέρειες, είναι ουσιαστικά η μέθοδος αλυσίδων προς τα πίσω για την οποία μιλήσαμε νωρίτερα. Εάν ο στόχος ήταν να «καταστραφεί ο παίκτης» και ο παίκτης βρίσκεται πίσω από το κάλυμμα, το σχέδιο θα μπορούσε να είναι: να καταστρέψετε με μια χειροβομβίδα → να το πάρετε → να το πετάξετε.
Συνήθως υπάρχουν πολλοί στόχοι, ο καθένας με τη δική του προτεραιότητα. Εάν ο στόχος υψηλότερης προτεραιότητας δεν μπορεί να ολοκληρωθεί (κανένας συνδυασμός ενεργειών δεν δημιουργεί ένα σχέδιο "σκότωσε τον παίκτη" επειδή ο παίκτης δεν είναι ορατός), το AI θα επιστρέψει σε στόχους χαμηλότερης προτεραιότητας.
Εκπαίδευση και προσαρμογή
Έχουμε ήδη πει ότι η τεχνητή νοημοσύνη του παιχνιδιού συνήθως δεν χρησιμοποιεί μηχανική εκμάθηση επειδή δεν είναι κατάλληλη για τη διαχείριση πρακτόρων σε πραγματικό χρόνο. Αυτό όμως δεν σημαίνει ότι δεν μπορείτε να δανειστείτε κάτι από αυτήν την περιοχή. Θέλουμε έναν αντίπαλο σε ένα σουτέρ από τον οποίο μπορούμε να μάθουμε κάτι. Για παράδειγμα, μάθετε για τις καλύτερες θέσεις στον χάρτη. Ή ένας αντίπαλος σε ένα παιχνίδι μάχης που θα μπλοκάρει τις συχνά χρησιμοποιούμενες σύνθετες κινήσεις του παίκτη, παρακινώντας τον να χρησιμοποιήσει άλλους. Έτσι η μηχανική μάθηση μπορεί να είναι αρκετά χρήσιμη σε τέτοιες καταστάσεις.
Στατιστικά και Πιθανότητες
Πριν μπούμε σε πολύπλοκα παραδείγματα, ας δούμε πόσο μακριά μπορούμε να φτάσουμε λαμβάνοντας μερικές απλές μετρήσεις και χρησιμοποιώντας τις για να λάβουμε αποφάσεις. Για παράδειγμα, στρατηγική σε πραγματικό χρόνο - πώς προσδιορίζουμε εάν ένας παίκτης μπορεί να ξεκινήσει μια επίθεση στα πρώτα λεπτά του παιχνιδιού και ποια άμυνα να προετοιμαστεί έναντι αυτού; Μπορούμε να μελετήσουμε τις προηγούμενες εμπειρίες ενός παίκτη για να καταλάβουμε ποιες μπορεί να είναι οι μελλοντικές αντιδράσεις. Αρχικά, δεν έχουμε τέτοια ακατέργαστα δεδομένα, αλλά μπορούμε να τα συλλέξουμε - κάθε φορά που το AI παίζει ενάντια σε έναν άνθρωπο, μπορεί να καταγράφει την ώρα της πρώτης επίθεσης. Μετά από μερικές συνεδρίες, θα λάβουμε έναν μέσο όρο του χρόνου που θα χρειαστεί για να επιτεθεί ο παίκτης στο μέλλον.
Υπάρχει επίσης ένα πρόβλημα με τις μέσες τιμές: αν ένας παίκτης βιάστηκε 20 φορές και έπαιξε αργά 20 φορές, τότε οι απαιτούμενες τιμές θα είναι κάπου στη μέση και αυτό δεν θα μας δώσει τίποτα χρήσιμο. Μια λύση είναι ο περιορισμός των δεδομένων εισόδου - τα τελευταία 20 τεμάχια μπορούν να ληφθούν υπόψη.
Μια παρόμοια προσέγγιση χρησιμοποιείται κατά την εκτίμηση της πιθανότητας ορισμένων ενεργειών με την υπόθεση ότι οι προηγούμενες προτιμήσεις του παίκτη θα είναι οι ίδιες στο μέλλον. Αν ένας παίκτης μας επιτεθεί πέντε φορές με βολίδα, δύο φορές με κεραυνό και μία με μάχη σώμα με σώμα, είναι προφανές ότι προτιμά τη βολίδα. Ας κάνουμε παρέκταση και ας δούμε την πιθανότητα χρήσης διαφορετικών όπλων: βολίδα=62,5%, κεραυνός=25% και μάχη σώμα με σώμα=12,5%. Το παιχνίδι μας AI πρέπει να προετοιμαστεί για να προστατευτεί από τη φωτιά.
Μια άλλη ενδιαφέρουσα μέθοδος είναι να χρησιμοποιήσετε τον ταξινομητή Naive Bayes για τη μελέτη μεγάλων ποσοτήτων δεδομένων εισόδου και την ταξινόμηση της κατάστασης έτσι ώστε το AI να αντιδρά με τον επιθυμητό τρόπο. Οι ταξινομητές Bayes είναι περισσότερο γνωστοί για τη χρήση τους σε φίλτρα ανεπιθύμητης αλληλογραφίας. Εκεί εξετάζουν τις λέξεις, τις συγκρίνουν με το πού έχουν εμφανιστεί αυτές οι λέξεις στο παρελθόν (σε spam ή όχι) και εξάγουν συμπεράσματα σχετικά με τα εισερχόμενα email. Μπορούμε να κάνουμε το ίδιο πράγμα ακόμα και με λιγότερες εισροές. Με βάση όλες τις χρήσιμες πληροφορίες που βλέπει το AI (όπως ποιες εχθρικές μονάδες δημιουργούνται, ή ποια ξόρκια χρησιμοποιούν ή ποιες τεχνολογίες ερεύνησαν) και το τελικό αποτέλεσμα (πόλεμος ή ειρήνη, ορμή ή άμυνα κ.λπ.) - θα επιλέξουμε την επιθυμητή συμπεριφορά AI.
Όλες αυτές οι μέθοδοι εκπαίδευσης είναι επαρκείς, αλλά συνιστάται η χρήση τους με βάση τα δεδομένα δοκιμών. Το AI θα μάθει να προσαρμόζεται στις διαφορετικές στρατηγικές που έχουν χρησιμοποιήσει οι δοκιμαστές σας. Το AI που προσαρμόζεται στον παίκτη μετά την κυκλοφορία μπορεί να γίνει πολύ προβλέψιμο ή πολύ δύσκολο να νικηθεί.
Προσαρμογή βάσει αξίας
Δεδομένου του περιεχομένου του κόσμου του παιχνιδιού μας και των κανόνων, μπορούμε να αλλάξουμε το σύνολο των τιμών που επηρεάζουν τη λήψη αποφάσεων, αντί να χρησιμοποιούμε απλώς τα δεδομένα εισόδου. Κάνουμε αυτό:
- Αφήστε το AI να συλλέξει δεδομένα για την κατάσταση του κόσμου και βασικά γεγονότα κατά τη διάρκεια του παιχνιδιού (όπως παραπάνω).
- Ας αλλάξουμε μερικές σημαντικές τιμές με βάση αυτά τα δεδομένα.
- Εφαρμόζουμε τις αποφάσεις μας με βάση την επεξεργασία ή την αξιολόγηση αυτών των αξιών.
Για παράδειγμα, ένας πράκτορας έχει πολλά δωμάτια για να διαλέξει σε έναν χάρτη σκοποβολής πρώτου προσώπου. Κάθε δωμάτιο έχει τη δική του αξία, η οποία καθορίζει πόσο επιθυμητό είναι να το επισκεφτείτε. Το AI επιλέγει τυχαία σε ποιο δωμάτιο θα πάει με βάση την τιμή. Στη συνέχεια, ο πράκτορας θυμάται σε ποιο δωμάτιο σκοτώθηκε και μειώνει την αξία του (την πιθανότητα να επιστρέψει εκεί). Ομοίως για την αντίστροφη κατάσταση - εάν ο πράκτορας καταστρέψει πολλούς αντιπάλους, τότε η αξία του δωματίου αυξάνεται.
μοντέλο Markov
Τι θα γινόταν αν χρησιμοποιούσαμε τα δεδομένα που συλλέγαμε για να κάνουμε προβλέψεις; Εάν θυμόμαστε κάθε δωμάτιο στο οποίο βλέπουμε έναν παίκτη για μια συγκεκριμένη χρονική περίοδο, θα προβλέψουμε σε ποιο δωμάτιο μπορεί να πάει ο παίκτης. Παρακολουθώντας και καταγράφοντας τις κινήσεις του παίκτη στα δωμάτια (τιμές), μπορούμε να τις προβλέψουμε.
Ας πάρουμε τρία δωμάτια: κόκκινο, πράσινο και μπλε. Και επίσης οι παρατηρήσεις που καταγράψαμε παρακολουθώντας την περίοδο του αγώνα:
Ο αριθμός των παρατηρήσεων σε κάθε δωμάτιο είναι σχεδόν ίσος - ακόμα δεν ξέρουμε πού να κάνουμε ένα καλό μέρος για μια ενέδρα. Η συλλογή στατιστικών στοιχείων περιπλέκεται επίσης από την εκ νέου αναπαραγωγή παικτών, οι οποίοι εμφανίζονται ομοιόμορφα σε όλο τον χάρτη. Αλλά τα δεδομένα σχετικά με το επόμενο δωμάτιο που εισάγουν αφού εμφανιστούν στον χάρτη είναι ήδη χρήσιμα.
Μπορεί να φανεί ότι το πράσινο δωμάτιο ταιριάζει στους παίκτες - οι περισσότεροι άνθρωποι μετακινούνται από το κόκκινο δωμάτιο σε αυτό, το 50% των οποίων παραμένει εκεί περαιτέρω. Το μπλε δωμάτιο, αντίθετα, δεν είναι δημοφιλές· σχεδόν κανείς δεν πηγαίνει σε αυτό, και αν το πάει, δεν μένει πολύ.
Όμως τα δεδομένα μας λένε κάτι πιο σημαντικό - όταν ένας παίκτης βρίσκεται σε ένα μπλε δωμάτιο, το επόμενο δωμάτιο που θα τον δούμε θα είναι κόκκινο, όχι πράσινο. Παρόλο που το πράσινο δωμάτιο είναι πιο δημοφιλές από το κόκκινο δωμάτιο, η κατάσταση αλλάζει εάν ο παίκτης βρίσκεται στο μπλε δωμάτιο. Η επόμενη κατάσταση (δηλαδή το δωμάτιο στο οποίο θα πάει ο παίκτης) εξαρτάται από την προηγούμενη κατάσταση (δηλαδή το δωμάτιο στο οποίο βρίσκεται αυτή τη στιγμή). Επειδή διερευνούμε τις εξαρτήσεις, θα κάνουμε πιο ακριβείς προβλέψεις από ό,τι αν απλώς μετρούσαμε τις παρατηρήσεις ανεξάρτητα.
Η πρόβλεψη μιας μελλοντικής κατάστασης με βάση δεδομένα από μια προηγούμενη κατάσταση ονομάζεται μοντέλο Markov, και τέτοια παραδείγματα (με δωμάτια) ονομάζονται αλυσίδες Markov. Δεδομένου ότι τα μοτίβα αντιπροσωπεύουν την πιθανότητα αλλαγών μεταξύ διαδοχικών καταστάσεων, εμφανίζονται οπτικά ως FSM με πιθανότητα γύρω από κάθε μετάβαση. Προηγουμένως, χρησιμοποιούσαμε το FSM για να αναπαραστήσουμε την κατάσταση συμπεριφοράς στην οποία βρισκόταν ένας πράκτορας, αλλά αυτή η έννοια επεκτείνεται σε οποιαδήποτε κατάσταση, είτε σχετίζεται με τον πράκτορα είτε όχι. Σε αυτήν την περίπτωση, οι καταστάσεις αντιπροσωπεύουν το δωμάτιο που καταλαμβάνει ο πράκτορας:
Αυτός είναι ένας απλός τρόπος αναπαράστασης της σχετικής πιθανότητας αλλαγών κατάστασης, δίνοντας στο AI κάποια δυνατότητα να προβλέψει την επόμενη κατάσταση. Μπορείτε να προβλέψετε πολλά βήματα μπροστά.
Εάν ένας παίκτης βρίσκεται στο πράσινο δωμάτιο, υπάρχει 50% πιθανότητα να παραμείνει εκεί την επόμενη φορά που θα παρατηρηθεί. Ποιες είναι όμως οι πιθανότητες να είναι ακόμα εκεί και μετά; Όχι μόνο υπάρχει περίπτωση ο παίκτης να παρέμεινε στο πράσινο δωμάτιο μετά από δύο παρατηρήσεις, αλλά υπάρχει και περίπτωση να φύγει και να επιστρέψει. Ακολουθεί ο νέος πίνακας λαμβάνοντας υπόψη τα νέα δεδομένα:
Δείχνει ότι η πιθανότητα να δεις τον παίκτη στο πράσινο δωμάτιο μετά από δύο παρατηρήσεις θα είναι ίση με 51% - 21% ότι θα είναι από το κόκκινο δωμάτιο, 5% από αυτές ότι ο παίκτης θα επισκεφτεί το μπλε δωμάτιο μεταξύ τους και Το 25% ότι ο παίκτης δεν θα φύγει από το πράσινο δωμάτιο.
Ο πίνακας είναι απλώς ένα οπτικό εργαλείο - η διαδικασία απαιτεί μόνο πολλαπλασιασμό των πιθανοτήτων σε κάθε βήμα. Αυτό σημαίνει ότι μπορείτε να κοιτάξετε μακριά στο μέλλον με μια προειδοποίηση: υποθέτουμε ότι η πιθανότητα να μπείτε σε ένα δωμάτιο εξαρτάται εξ ολοκλήρου από το τρέχον δωμάτιο. Αυτό ονομάζεται ιδιοκτησία Markov - η μελλοντική κατάσταση εξαρτάται μόνο από το παρόν. Αλλά αυτό δεν είναι XNUMX% ακριβές. Οι παίκτες μπορούν να αλλάξουν αποφάσεις ανάλογα με άλλους παράγοντες: επίπεδο υγείας ή ποσότητα πυρομαχικών. Επειδή δεν καταγράφουμε αυτές τις τιμές, οι προβλέψεις μας θα είναι λιγότερο ακριβείς.
N-γραμμάρια
Τι γίνεται με το παράδειγμα ενός παιχνιδιού μάχης και της πρόβλεψης των σύνθετων κινήσεων του παίκτη; Το ίδιο! Αλλά αντί για μία κατάσταση ή γεγονός, θα εξετάσουμε ολόκληρες τις ακολουθίες που συνθέτουν μια σύνθετη απεργία.
Ένας τρόπος για να γίνει αυτό είναι να αποθηκεύσετε κάθε είσοδο (όπως Kick, Punch ή Block) σε ένα buffer και να γράψετε ολόκληρο το buffer ως συμβάν. Έτσι, ο παίκτης πατάει επανειλημμένα Kick, Kick, Punch για να χρησιμοποιήσει την επίθεση SuperDeathFist, το σύστημα AI αποθηκεύει όλες τις εισόδους σε ένα buffer και θυμάται τις τρεις τελευταίες που χρησιμοποιήθηκαν σε κάθε βήμα.
(Οι γραμμές με έντονους χαρακτήρες είναι όταν ο παίκτης ξεκινά την επίθεση SuperDeathFist.)
Το AI θα δει όλες τις επιλογές όταν ο παίκτης επιλέξει Kick, ακολουθούμενο από ένα άλλο Kick, και στη συνέχεια παρατηρήσει ότι η επόμενη είσοδος είναι πάντα Punch. Αυτό θα επιτρέψει στον πράκτορα να προβλέψει τη σύνθετη κίνηση του SuperDeathFist και να την αποκλείσει αν είναι δυνατόν.
Αυτές οι ακολουθίες γεγονότων ονομάζονται N-γραμμάρια, όπου N είναι ο αριθμός των αποθηκευμένων στοιχείων. Στο προηγούμενο παράδειγμα ήταν 3-γραμμάρια (τρίγραμμα), που σημαίνει: οι δύο πρώτες καταχωρήσεις χρησιμοποιούνται για την πρόβλεψη της τρίτης. Αντίστοιχα, σε ένα 5-γραμμάριο, οι τέσσερις πρώτες εγγραφές προβλέπουν την πέμπτη και ούτω καθεξής.
Ο σχεδιαστής πρέπει να επιλέξει προσεκτικά το μέγεθος των N-γραμμαρίων. Ένα μικρότερο N απαιτεί λιγότερη μνήμη αλλά αποθηκεύει και λιγότερο ιστορικό. Για παράδειγμα, ένα 2-γραμμάριο (bigram) θα καταγράψει Kick, Kick ή Kick, Punch, αλλά δεν θα μπορεί να αποθηκεύσει Kick, Kick, Punch, επομένως το AI δεν θα ανταποκρίνεται στον συνδυασμό SuperDeathFist.
Από την άλλη πλευρά, οι μεγαλύτεροι αριθμοί απαιτούν περισσότερη μνήμη και η τεχνητή νοημοσύνη θα είναι πιο δύσκολο να εκπαιδευτεί αφού θα υπάρχουν πολλές περισσότερες πιθανές επιλογές. Εάν είχατε τρεις πιθανές εισόδους Kick, Punch ή Block και χρησιμοποιούσαμε ένα 10-γραμμάριο, θα ήταν περίπου 60 χιλιάδες διαφορετικές επιλογές.
Το μοντέλο διγράμματος είναι μια απλή αλυσίδα Markov - κάθε ζεύγος προηγούμενης κατάστασης/τρέχουσας κατάστασης είναι ένα δίγραμμο και μπορείτε να προβλέψετε τη δεύτερη κατάσταση με βάση την πρώτη. Τα 3-γραμμάρια και μεγαλύτερα N-γραμμάρια μπορούν επίσης να θεωρηθούν ως αλυσίδες Markov, όπου όλα τα στοιχεία (εκτός από το τελευταίο στο N-gram) μαζί σχηματίζουν την πρώτη κατάσταση και το τελευταίο στοιχείο τη δεύτερη. Το παράδειγμα του παιχνιδιού μάχης δείχνει την πιθανότητα μετάβασης από την κατάσταση Kick and Kick στην κατάσταση Kick and Punch. Αντιμετωπίζοντας πολλαπλές εγγραφές ιστορικού εισόδου ως μια ενιαία μονάδα, ουσιαστικά μετατρέπουμε την ακολουθία εισόδου σε μέρος της συνολικής κατάστασης. Αυτό μας δίνει την ιδιότητα Markov, η οποία μας επιτρέπει να χρησιμοποιούμε αλυσίδες Markov για να προβλέψουμε την επόμενη είσοδο και να μαντέψουμε ποια σύνθετη κίνηση θα είναι η επόμενη.
Συμπέρασμα
Μιλήσαμε για τα πιο κοινά εργαλεία και προσεγγίσεις στην ανάπτυξη της τεχνητής νοημοσύνης. Εξετάσαμε επίσης τις καταστάσεις στις οποίες πρέπει να χρησιμοποιηθούν και πού είναι ιδιαίτερα χρήσιμες.
Αυτό θα πρέπει να είναι αρκετό για να κατανοήσετε τα βασικά του παιχνιδιού AI. Αλλά, φυσικά, αυτές δεν είναι όλες οι μέθοδοι. Λιγότερο δημοφιλή, αλλά όχι λιγότερο αποτελεσματικά περιλαμβάνουν:
- αλγόριθμοι βελτιστοποίησης, συμπεριλαμβανομένων αλγορίθμων αναρρίχησης σε λόφο, κατάβασης κλίσης και γενετικών αλγορίθμων
- αλγόριθμοι αντίθετης αναζήτησης/προγραμματισμού (minimax και alpha-beta κλάδεμα)
- μέθοδοι ταξινόμησης (perceptrons, νευρωνικά δίκτυα και μηχανές υποστήριξης διανυσμάτων)
- συστήματα για την επεξεργασία της αντίληψης και της μνήμης των παραγόντων
- αρχιτεκτονικές προσεγγίσεις στο AI (υβριδικά συστήματα, αρχιτεκτονικές υποσυνόλων και άλλοι τρόποι επικάλυψης συστημάτων AI)
- εργαλεία κινουμένων σχεδίων (σχεδιασμός και συντονισμός κίνησης)
- παράγοντες απόδοσης (επίπεδο λεπτομέρειας, ανά πάσα στιγμή και αλγόριθμοι χρονικής λεπτομέρειας)
Πηγές Διαδικτύου σχετικά με το θέμα:
1. Το GameDev.net έχει Και .
2. περιέχει πολλές παρουσιάσεις και άρθρα για ένα ευρύ φάσμα θεμάτων που σχετίζονται με την ανάπτυξη παιχνιδιών AI.
3. περιλαμβάνει θέματα από το GDC AI Summit, πολλά από τα οποία είναι διαθέσιμα δωρεάν.
4. Χρήσιμο υλικό μπορείτε επίσης να βρείτε στον ιστότοπο .
5. Ο Tommy Thompson, ερευνητής AI και προγραμματιστής παιχνιδιών, κάνει βίντεο στο YouTube με επεξήγηση και μελέτη της τεχνητής νοημοσύνης σε εμπορικά παιχνίδια.
Βιβλία με θέμα:
1. Η σειρά βιβλίων Game AI Pro είναι μια συλλογή σύντομων άρθρων που εξηγούν πώς να εφαρμόσετε συγκεκριμένες λειτουργίες ή πώς να λύσετε συγκεκριμένα προβλήματα.
2. Η σειρά AI Game Programming Wisdom είναι ο προκάτοχος της σειράς Game AI Pro. Περιέχει παλαιότερες μεθόδους, αλλά σχεδόν όλες είναι σχετικές ακόμα και σήμερα.
3. είναι ένα από τα βασικά κείμενα για όλους όσους θέλουν να κατανοήσουν το γενικό πεδίο της τεχνητής νοημοσύνης. Αυτό δεν είναι ένα βιβλίο για την ανάπτυξη παιχνιδιών - διδάσκει τα βασικά της AI.
Πηγή: www.habr.com