A* Pathfinding για Αρχάριους

Δημιουργός: Patrick Lester (Τελευταία ενημέρωση Ιούλιος 18, 2005)

Μετάφραση: Σωτήρης Χατζόπουλος (Μάιος 11, 2006)


Ο αλγόριθμος Α*(προφέρεται Α-άστρο) ίσως να είναι περίπλοκος για αρχάριους. Ενώ υπάρχουν αρκετά άρθρα στον παγκόσμιο ιστό τα οποία εξηγούν τον Α*, τα περισσότερα έχουν γραφτεί για αυτούς που κατανοούν ήδη τα βασικά. Το παρόν άρθρο απευθύνεται σε κάποιον πραγματικά αρχάριο.

Το συγκεκριμένο άρθρο δεν αποτελεί το απόλυτο άρθρο στον θέμα. Αντί αυτού περιγράφει τα θεμελιώδη και προετοιμάζει τον αναγνώστη δίνοντας του τις βάσεις για να ασχοληθεί με ποιο προχωρημένο υλικό. Σύνδεσμοι σε κάποια από τα καλύτερα άρθρα για επιπλέον μελέτη δίνονται στο τέλος του παρόντος άρθρου.

Τέλος αυτό το άρθρο δεν αναφέρεται σε κάποια συγκεκριμένη γλώσσα προγραμματισμού. Θα πρέπει να μπορείτε να προσαρμόσετε ότι υπάρχει εδώ σε οποιαδήποτε γλώσσα. Όπως και θα αναμένετε, έχω συμπεριλάβει ένα σύνδεσμο σε ένα πρόγραμμα ως παράδειγμα στο τέλος του άρθρου. Το πρόγραμμα περιέχει 2 εκδόσεις: Η μια σε C++ και η δεύτερη σε Blitz Basic. Επιπλέον περιέχει εκτελέσιμα αν θέλετε να δείτε τον Α* σε δράση.

Αλλά ας προχωρήσουμε στο ζουμί ξεκινώντας από τα αρχικά…

Εισαγωγή: Η περιοχή διερεύνησης

Ας υποθέσουμε ότι κάποιος θέλει να πάει από το σημείο Α στο σημείο Β. Ας υποθέσουμε επιπλέον ότι ένας τοίχος διαχωρίζει τα δύο σημεία. Αυτό διευκρινίζεται πιο κάτω, όπου το πράσινο τετράγωνο αντιστοιχεί στο σημείο έναρξης Α, το κόκκινο στο σημείο τερματισμού και τα μπλε τετράγωνα στον ενδιάμεσο τοίχο.

   
[
Εικόνα 1]

Το πρώτο πράγμα που θα έχετε προσέξει είναι ότι έχουμε προσαρμόσει την περιοχή διερεύνησης σε ένα τετραγωνικό πλέγμα. Απλοποιώντας την περιοχή διερεύνησης όπως έχουμε κάνει εδώ είναι το πρώτο βήμα στο pathfinding. Αυτή η συγκεκριμένη μέθοδος απλοποιεί την περιοχή διερεύνησης σε έναν απλό 2-διάστατο πίνακα. Κάθε στοιχείο του πίνακα αναπαριστά ένα από τα τετράγωνα του πλέγματος η κατάσταση του χαρακτηρίζεται ως προσπελάσιμη ή μη- προσπελάσιμη. Το μονοπάτι αποκαλύπτεται βρίσκοντας πια τετράγωνα πρέπει να διαβούμε για να πάμε από το Α στο Β. Μόλις το μονοπάτι βρεθεί το υποκείμενο μπορεί να κινηθεί από το κέντρο του αρχικού τετραγώνου στο κέντρο του επόμενου τετραγώνου ακολουθώντας τη διαδρομή μέχρι να φθάσει στον στόχο.

Αυτά τα κεντρικά σημεία ονομάζονται κόμβοι. Όταν διαβάσετε για pathfinding αλλού συχνά θα δείτε ότι πολλοί αναφέρονται σε κόμβούς .Αλλά γιατί δεν τους αποκαλούμε απλά, τετράγωνα;Διότι είναι πιθανό να διαχωρίσουμε την περιοχή διερεύνησης σε κάτι άλλο αντί για τετράγωνα. Θα μπορούσε για παράδειγμα να ήταν παραλληλόγραμμα, εξάγωνα, τρίγωνα ή κάποιο άλλο σχήμα. Και οι κόμβοι θα μπορούσαν να τοποθετηθούν οπουδήποτε μέσα σε αυτά τα σχήματα – στο κέντρο ή στις κορυφές ή κάπου αλλού. Παρά ταύτα χρησιμοποιούμε αυτό το σύστημα επειδή είναι το απλούστερο.

Ξεκινώντας την αναζήτηση

Εφόσον έχουμε απλοποιήσει την περιοχή διερεύνησης σε ένα ευμεταχείριστο αριθμό κόμβων, όπως κάναμε και στην προκειμένη περίπτωση με το πλέγμα, το επόμενο βήμα είναι να ανακαλύψουμε πια είναι η συντομότερη διαδρομή. Τα κάνουμε αυτό ξεκινώντας από το σημείο έναρξης Α, εξετάζοντας τα γειτονικά τετράγωνα και γενικά ψάχνοντας τα τετράγωνα μέχρι να βρούμε τον στόχο. 

Ξεκινάμε την αναζήτηση κάνοντας τα ακόλουθα:

1.      Αρχίζουμε από το σημείο έναρξης Α και το προσθέτουμε ως προς εξέταση σε μια «ανοικτή λίστα» από τετράγωνα. Η ανοικτή λίστα είναι σαν μια λίστα αγορών. Μέχρι τώρα υπάρχει μόνο ένα στοιχείο στη λίστα αλλά θα προστεθούν και άλλα αργότερα. Περιέχει τετράγωνα που πιθανόν να βρεθούν πάνω στο μονοπάτι που θα πάρουμε αλλά ίσως και όχι. Βασικά, αυτή είναι μια λίστα από τετράγωνα που θα χρειαστεί να τσεκαριστούν.

2.      Κοιτάτε όλα τα προσπελάσιμα γειτονικά τετράγωνα του σημείου Α αγνοώντας τετράγωνα με τοίχους, νερό, ή άλλη απρόσιτη περιοχή. Προσθέστε τα στην ανοικτή λίστα επίσης. Για κάθε ένα από αυτά τα τετράγωνα σώστε το τετράγωνο Α ως «πατέρα» όλων αυτών. Αυτό το τετράγωνο-πατέρας είναι σημαντικό όταν θέλουμε να εντοπίσουμε το μονοπάτι. Θα εξηγηθεί με λεπτομέρεια αργότερα.

3.      Αφαιρέστε το αρχικό τετράγωνο Α από την ανοικτή λίστα και προσθέστε το στην «κλειστή λίστα» από τετράγωνα όπου δεν χρειάζεται να κοιτάξετε ξανά προς το παρόν.

 

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

 


  [
Εικόνα 2]

Στη συνέχεια επιλέγουμε ένα από τα γειτονικά τετράγωνα της ανοικτής λίστας και λίγο πολύ επαναλαμβάνουμε την προηγούμενη διαδικασία. Αλλά ποιο τετράγωνο επιλέγουμε;Αυτό με το μικρότερο F.

Βαθμολόγηση μονοπατιού

Το κλειδί για να καθορίσουμε ποια τετράγωνα θα χρησιμοποιήσουμε όταν ψάχνουμε το μονοπάτι είναι η ακόλουθη εξίσωση:

F = G + H

όπου

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

·        Η = το εκτιμούμενο κόστος απόστασης ώστε να κινηθούμε από ένα δεδομένο τετράγωνο στο πλέγμα στον τελικό προορισμό Β. Αυτό συχνά αναφέρεται ως ευρετική μέθοδος(heuristic) και συχνά προκαλεί σύγχυση. Ο λόγος που αποκαλείται έτσι είναι ότι πρόκειται για μια εκτίμηση. Στην πραγματικότητα δεν ξέρουμε την ακριβή απόσταση έως ότου να βρεθεί το μονοπάτι λόγω των εμποδίων(τοίχοι, νερό κλπ.). Σε αυτό το άρθρο δίνεται ένας τρόπος υπολογισμού του Η αλλά υπάρχουν πλείστοι άλλοι όπου μπορεί κάποιος να βρει σε άλλα άρθρα στο web.

Το μονοπάτι μας παράγεται εξετάζοντας συνεχώς την ανοικτή λίστα και επιλέγοντας το τετράγωνο που έχει το μικρότερο F. Αυτή η διαδικασία θα εξηγηθεί με περισσότερη λεπτομέρεια στα επόμενα. Αλλά πρώτα ας δούμε καλύτερα πως θα υπολογίσουμε την εξίσωση.

Όπως περιγράφτηκε πιο πάνω, το G είναι το κόστος της κίνησης από το αρχικό σημείο σε ένα δεδομένο τετράγωνο παίρνοντας το μονοπάτι που παράχθηκε έως εκεί. Σε αυτό το παράδειγμα θα αντιστοιχίσουμε ένα κόστος 10 μονάδων σε κάθε οριζόντιο ή κάθετο τετράγωνο που κινηθήκαμε και ένα κόστος 14 μονάδων για μια διαγώνια κίνηση. Χρησιμοποιούμε αυτούς τους αριθμούς επειδή η απόσταση για να κινηθούμε διαγώνια είναι η τετραγωνική ρίζα του 2(μη πανικοβάλλεστε)  ή σχεδόν 1.414 φορές την απόσταση(κόστος) για μία οριζόντια ή κάθετη κίνηση. Χρησιμοποιούμε τις τιμές 10 και 14 για ευκολία. Η αναλογία είναι σχεδόν σωστή και επιπλέον αποφεύγουμε τα δεκαδικά και τον υπολογισμό τετραγωνικών ριζών πράγμα που δεν επιβαρύνει τον υπολογιστή μας σε επιπλέον υπολογισμούς. Όπως θα δούμε αργότερα, το pathfinding μπορεί να γίνει πολύ αργό αν δεν κάνουμε τέτοιες συντομεύσεις.

Εφόσον προσπαθούμε να υπολογίσουμε το G κατά μήκος ενός συγκεκριμένου μονοπατιού μέχρι ένα δοσμένο τετράγωνο ο τρόπος υπολογισμού του G αυτού του τετραγώνου είναι να πάρουμε το G του πατέρα του και σε αυτό να προσθέσουμε 10 ή 14 αναλόγως με αν το δοσμένο τετράγωνο βρίσκεται σε διαγώνια ή σε ορθογώνια(μη-διαγώνια) θέση σε σχέση με τον πατέρα του. Η χρησιμότητα αυτής της μεθόδου θα γίνει προφανής λίγο αργότερα στο συγκεκριμένο παράδειγμα όταν θα βρισκόμαστε πάνω από ένα τετράγωνο μακριά από την αρχή.

Το H μπορεί να υπολογιστεί με διάφορους τρόπους. Η μέθοδος που θα χρησιμοποιήσουμε εδώ λέγεται μέθοδος Manhattan, όπου σύμφωνα με αυτήν υπολογίζεις τον συνολικό αριθμό τετραγώνων οριζόντιας και κάθετης κίνησης έως τον τελικό στόχο τετράγωνο χωρίς τη χρήση διαγώνιας κίνησης και αγνοώντας όλα τα πιθανά εμπόδια που μπορούν να βρεθούν στη διαδρομή. Στη συνέχεια πολλαπλασιάζουμε το σύνολο των τετραγώνων με 10 όπου είναι το κόστος κάθετης ή οριζόντιας κίνησης. Η μέθοδος (πιθανόν) καλείται μέθοδος Manhattan διότι είναι σα να υπολογίζεις τον αριθμό των πολεοδομικών τετραγώνων από ένα μέρος σε κάποιο άλλο, όπου δεν μπορείς να κινηθείς διαγώνια.

Διαβάζοντας αυτή την περιγραφή ίσως πει κάποιος ότι αυτή η ευρετική είναι μόνο μια χονδροειδής εκτίμηση της απομένουσας απόστασης μεταξύ του τρέχοντος τετραγώνου και του στόχου. Αυτό όμως δεν είναι απόλυτο. Στην πραγματικότητα μόνο προσπαθούμε να εκτιμήσουμε την υπόλοιπη απόσταση κατά μήκος του μονοπατιού(όπου συνήθως είναι μεγαλύτερη). Όσο καλύτερη είναι η εκτίμηση μας τόσο γρηγορότερος θα είναι ο αλγόριθμος. Αν όμως υπερεκτιμήσουμε την απόσταση δεν είναι σίγουρο ότι θα πάρουμε το συντομότερο μονοπάτι. Σε αυτές τι περιπτώσεις λέμε ότι έχουμε «απαράδεκτη ευρετική»( inadmissible heuristic).

Τεχνικός σε αυτό το παράδειγμα, η μέθοδος Manhattan είναι απαράδεκτη διότι υπερεκτιμά ελαφρώς την εναπομένουσα απόσταση. Αλλά θα την χρησιμοποιήσουμε διότι είναι αρκετά ευκολότερη στην κατανόηση και γιατί το σφάλμα είναι αρκετά μικρό. Στην σπάνια περίπτωση όπου το μονοπάτι δεν είναι το συντομότερο δυνατό θα είναι σχεδόν το συντομότερο. Θέλετε να μάθετε περισσότερα;Μπορείτε να βρείτε επιπλέον σημειώσεις επί της ευρετικής εδώ.

Το F υπολογίζεται προσθέτοντας τα G και H. Τα αποτελέσματα του πρώτου βήματος φαίνονται στην επόμενη εικόνα. Τα F, G  και H είναι γραμμένα σε κάθε τετράγωνο. Όπως υποδεικνύεται στο τετράγωνο αμέσως δεξιά του αρχικού το F βρίσκετε πάνω αριστερά, το G κάτω αριστερά και το H κάτω δεξιά.

 
  [
Εικόνα 3] 

Ας κοιτάξουμε το τετράγωνο με τα γράμματα όπου G = 10. Έχει αυτή την τιμή διότι βρίσκεται μόνο ένα τετράγωνο από το αρχικό και σε οριζόντια κατεύθυνση. Τα τετράγωνα ακριβώς από πάνω ,κάτω και αριστερά από το αρχικό τετράγωνο έχουν όλα G ίσο με 10. Τα διαγώνια τετράγωνα έχουν G = 14.

 Οι τιμή του H υπολογίζεται εκτιμώντας την απόσταση μέχρι το κόκκινο τετράγωνο με βάση τη μέθοδο Manhattan, δηλαδή κινούμενοι μόνο οριζόντια ή κάθετα και αγνοώντας τον τοίχο στη μέση. Βάσει αυτής της μεθόδου το τετράγωνο αμέσως δεξιά του αρχικού τετραγώνου βρίσκεται 3 τετράγωνα μακριά από το κόκκινο τετράγωνο και συνεπώς το H παίρνει την τιμή 30. Το τετράγωνο αμέσως πάνω από αυτό με τα γράμματα  βρίσκεται 4 τετράγωνα μακριά από το κόκκινο(θυμηθείτε υπολογίζουμε μόνο οριζόντιες και κάθετες αποστάσεις) και έχει H = 40. Τώρα θα μπορείτε να δείτε πως υπολογίζεται το H και για τα άλλα τεράγωνα.

Το F για κάθε τετράγωνο, υπολογίζεται όπως είπαμε προσθέτοντας τα G και H.

 

Συνεχίζοντας το ψάξιμο

Για να συνεχίσουμε απλά διαλέγουμε το τετράγωνο με το χαμηλότερο F από όλα όσα είναι στην ανοικτή λίστα. Ύστερα κάνουμε τα ακόλουθα με το επιλεγμένο τετράγωνο:

4)Το βγάζουμε από την ανοικτή λίστα και το εισάγουμε στην κλειστή.

5)Τσεκάρουμε όλα τα διπλανά τετράγωνα .Αγνοώντας όλα αυτά που βρίσκονται στην κλειστή λίστα και αυτά που είναι απροσπέλαστα(περιοχές με τοίχους, νερό κλπ.) προσθέτουμε τετράγωνα στην ανοικτή λίστα αν αυτά δεν βρίσκονται ήδη εκεί. Κάνουμε το επιλεγμένο τετράγωνο πατέρα των νέων τετραγώνων.

6)Αν διπλανό ένα τετράγωνο βρίσκεται ήδη στην ανοικτή λίστα τσεκάρουμε αν αυτό είναι καλύτερο. Με άλλα λόγια βλέπουμε αν αυτό έχει μικρότερο G αν το χρησιμοποιήσουμε για να πάμε εκεί. Αν όχι δεν κάνουμε τίποτα.

Από την άλλη, αν το G της νέας διαδρομής είναι μικρότερο, αλλάξτε τον πατέρα του διπλανού τετραγώνου στο επιλεγμένο τετράγωνο(στο παραπάνω διάγραμμα αλλάξτε την κατεύθυνση του δείκτη ώστε να δείχνει στο επιλεγμένο τετράγωνο). Τέλος υπολογίστε ξανά τα F και G αυτού του τετραγώνου. Αν σας φαίνεται μπερδεμένο δείτε την επόμενη εικόνα.

 

Ας δούμε καλύτερα πως λειτουργεί. Από τα 9 αρχικά μας τετράγωνα έχουμε αφήσει 8 στην ανοικτή λίστα αφότου το αρχικό τετράγωνο μπήκε στην κλειστή λίστα. Από αυτά, αυτό με το χαμηλότερο F είναι το αμέσως δεξιά από το αρχικό με F = 40. Έτσι επιλέγουμε αυτό το τετράγωνο ως το επόμενο μας τετράγωνο. Αυτό με το μπλε περίγραμμα στην επόμενη εικόνα.

 

   
[
Εικόνα 4] 

Πρώτα το βγάζουμε από την ανοικτή λίστα και το βάζουμε στην κλειστή(για αυτό έχει και το μπλε περίγραμμα). Ύστερα ελέγχουμε και τα διπλανά τετράγωνα. Αυτά αμέσως δεξιά από αυτό είναι τοίχος οπότε τα αγνοούμε. Αυτό αμέσως αριστερά είναι το αρχικό τετράγωνο. Αυτό βρίσκεται στην κλειστή λίστα οπότε το αγνοούμε επίσης.

Τα υπόλοιπα 4 τετράγωνα βρίσκονται ήδη στην ανοικτή λίστα και συνεπώς πρέπει να ελέγξουμε αν τα μονοπάτια προς αυτά είναι καλύτερα για να φτάσουμε χρησιμοποιώντας το επιλεγμένο τετράγωνο, συγκρίνοντας τις τιμές των G τους. Ας δούμε το τετράγωνο ακριβώς επάνω από το επιλεγμένο τετράγωνο. Η τρέχουσα τιμή του G είναι 14. Αν αντί αυτού πηγαίναμε εκεί μέσω του επιλεγμένου τετραγώνου η τιμή του G θα ήταν 20(10 για να κινηθούμε μέχρι το επιλεγμένο τετράγωνο και άλλα 10 για να κινηθούμε κάθετα στο αμέσως πιο πάνω). Επειδή το 20 είναι μεγαλύτερο από το 14 επιλέγουμε τη διαγώνια διαδρομή. Αν κοιτάξουμε το διάγραμμα αυτό γίνεται προφανές διότι είναι πιο γρήγορο να πάμε σε εκείνο το τετράγωνο (αυτό αμέσως πάνω από το επιλεγμένο) κάνοντας μόνο μια διαγώνια κίνηση παρά κινούμενοι οριζόντια και στη συνέχεια κάθετα.

Όταν επαναλάβουμε αυτή τη διαδικασία και για τα 4 τετράγωνα στην ανοικτή λίστα, βρίσκουμε ότι κανένα από τα μονοπάτια δεν βελτιώνεται πηγαίνοντας μέσω του επιλεγμένου μονοπατιού(παρά μόνο διαγώνια) και συνεπώς δεν κάνουμε κάποια επιπλέον ενέργεια. Τώρα που εξετάσαμε όλα τα διπλανά τετράγωνα τελειώσαμε με το επιλεγμένο τετράγωνο και προχωρούμε στο επόμενο.

Πηγαίνουμε τώρα στην ανοικτή λίστα όπου τώρα έχει 7 τετράγωνα και επιλέγουμε αυτό με το μικρότερο F. Περιέργως σε αυτή την περίπτωση υπάρχουνε 2 τετράγωνα με F=54. Ποιο από τα δύο λοιπόν επιλέγουμε;Δεν έχει ουσιαστική σημασία. Για λόγους ταχύτητας μπορεί να είναι προτιμότερο να επιλέξουμε το τελευταίο που προστέθηκε στην ανοικτή λίστα. Αυτή η επιλογή ίσως επιφέρει μελλοντικές διαφοροποιήσεις αργότερα όταν θα πλησιάζουμε το στόχο αλλά δεν έχει ουσιαστική σημασία(Διαφορετική υλοποίηση του αλγόριθμου σε αυτό το σημείο θα παράγει 2 διαφορετικά μονοπάτια με ίσο μήκος).

Ας επιλέξουμε λοιπόν αυτό αμέσως κάτω και δεξιά από το επιλεγμένο τετράγωνο όπως φαίνεται στην επόμενη εικόνα.

 
[
Εικόνα 5] 

Αυτή τη φορά όταν ελέγχουμε τα διπλανά τετράγωνα βρίσκουμε ότι αυτό αμέσως μετά από το επιλεγμένο είναι τοίχος και το αγνοούμε. Το ίδιο και για το τετράγωνο ακριβώς από πάνω. Επίσης αγνοούμε και το τετράγωνο ακριβώς κάτω από τον τοίχο. Γιατί; Διότι δεν μπορούμε να φτάσουμε κατευθείαν σε εκείνο το τετράγωνο διαμέσου της γωνίας του τοίχου αλλά πρέπει να κινηθούμε γύρω από αυτήν(Σημείωση: Αυτός ο κανόνας για τις γωνίες είναι προαιρετικός. Η χρήση του εξαρτάται πως είναι διατεταγμένοι οι κόμβοι.)

Τώρα μας απομένουν 5 τετράγωνα. Τα άλλα δύο τετράγωνα κάτω από το επιλεγμένο που δεν βρίσκονται στην ανοικτή λίστα τα προστεθούμε και αυτά και κάνουμε το επιλεγμένο τετράγωνο πατέρα αυτών. Από τα άλλα τρία τετράγωνα 2 βρίσκονται στην κλειστή λίστα(το αρχικό τετράγωνο και αυτό ακριβώς πάνω από το επιλεγμένο, και τα δύο με μπλε περίγραμμα) και συνεπώς τα αγνοούμε. Και για το τελευταίο τετράγωνο αμέσως αριστερά από το επιλεγμένο τετράγωνο ελέγχουμε αν το G του είναι μικρότερο αν πάμε εκεί μέσω του επιλεγμένου κάτι που ασφαλώς δεν συμβαίνει. Συνεπώς τελειώσαμε και με αυτό και είμαστε έτοιμοι να ελέγξουμε το επόμενο τετράγωνο από την ανοικτή λίστα.

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

   
[
Εικόνα 6] 

Σημειώστε ότι το τετράγωνο δύο θέσεις κάτω από το αρχικό τετράγωνο έχει αλλάξει σε σχέση με την προηγούμενη εικόνα. Πριν είχε G = 28 και έδειχνε στο τετράγωνο που βρίσκεται διαγώνια πάνω από αυτό. Τώρα έχει G = 20 και δείχνει στο τετράγωνο ακριβώς πάνω από αυτό. Αυτό έγινε κατά τη διάρκεια του ελέγχου, όπου το G ελέγχθηκε και επιλέχτηκε η μικρότερη τιμή G χρησιμοποιώντας ένα νέο μονοπάτι έτσι ο πατέρας άλλαξε και τα G,F υπολογίστηκαν ξανά. Ενώ αυτή η αλλαγή δεν φαίνεται να είναι σημαντική σε αυτό το παράδειγμα, υπάρχουν αρκετές πιθανές περιπτώσεις όπου αυτός ο συνεχής έλεγχος θα κάνει τη διαφορά στον καθορισμό του καλύτερου μονοπατιού προς τον στόχο.

Τελικώς πως προσδιορίζουμε το μονοπάτι;Απλά αρχίζουμε από το κόκκινο τετράγωνο στόχο και κινούμαστε ανάποδα πηγαίνοντας από το ένα τετράγωνο στο άλλο ακολουθώντας τα βέλη. Αυτό τελικά μας πηγαίνει πίσω στο αρχικό τετράγωνο και αυτή η διαδρομή αποτελεί το μονοπάτι. Η διαδρομή φαίνεται στην επόμενη εικόνα. Για να κινηθούμε από το αρχικό τετράγωνο A στο τελικό B πηγαίνουμε από το κέντρο κάθε τετραγώνου(κόμβου) στο κέντρο του επόμενου τετραγώνου στο μονοπάτι, μέχρι να φτάσουμε στον στόχο.

   
[
Εικόνα 7]

Περίληψη του Α* αλγορίθμου

Τώρα που έχουμε εξηγήσει κάποια πράγματα, ας παραθέσουμε βήμα προς βήμα τον ολόκληρο αλγόριθμο:

 

1)Πρόσθεσε το αρχικό τετράγωνο(ή κόμβο) στην ανοικτή λίστα.

2)Επανέλαβε τα ακόλουθα:

Α)Βρες το τετράγωνο με το μικρότερο F στην ανοικτή λίστα. Θα αναφερόμαστε σε αυτό ως το επιλεγμένο τετράγωνο.

Β)Βάλτο στη κλειστή λίστα.

Γ)Για κάθε ένα από τα τετράγωνα που βρίσκονται δίπλα στο επιλεγμένο τετράγωνο…

·         Αν δεν είναι προσπελάσιμο ή αν βρίσκεται στην κλειστή λίστα, αγνόησε το. Διαφορετικά κάνε τα ακόλουθα:

·         Αν δεν βρίσκεται στην ανοικτή λίστα, πρόσθεσε το εκεί. Κάνε το επιλεγμένο τετράγωνο πατέρα αυτού του τετραγώνου. Καταχώρισε τις τιμές των F,G και H του τετραγώνου.

·         Αν βρίσκεται είδη στην ανοικτή λίστα, έλεγξε αν το μονοπάτι αυτού του τετραγώνου είναι καλύτερο χρησιμοποιώντας την τιμή του G. Χαμηλότερο G σημαίνει ότι και καλύτερο μονοπάτι. Αν είναι έτσι κάνε πατέρα αυτού του τετραγώνου το επιλεγμένο τετράγωνο και υπολόγισε ξανά τα G,F του τετραγώνου. Αν η ανοικτή λίστα είναι ταξινομημένη ως προς τα F ταξινομήστε την ξανά.

Δ)Σταμάτησε όταν:

·         Μπει το τετράγωνο στόχος στην κλειστή λίστα, οπότε και το μονοπάτι έχει βρεθεί(δες σημείωση παρακάτω).

·         Αποτύχεις να βρεις τον στόχο και η ανοικτή λίστα είναι κενή. Σε αυτή την περίπτωση δεν υπάρχει μονοπάτι.

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

Σημείωση: Σε προηγούμενες εκδόσεις αυτού του άρθρου είχε προταθεί ότι μπορεί να σταματήσεις όταν το τετράγωνο στόχος(ή κόμβος) μπει στην ανοικτή παρά την κλειστή λίστα. Κάνοντας αυτό θα είναι γρηγορότερο και σχεδόν πάντα θα δώσει το καλύτερο μονοπάτι, αλλά όχι πάντα. Περιπτώσεις όπου πράττοντας θα είχε σημαντική επίπτωση είναι όταν το κόστος της κίνησης από το προτελευταίο προς τον τελευταίο τετράγωνο στόχο μπορεί να διαφοροποιείται σημαντικά για παράδειγμα αν υπάρχει ένα ποτάμι μεταξύ των δύο κόμβων.

Μικρό υστερόγραφο

Συγχωρήστε με για την παρέκκλιση μου από το θέμα αλλά αξίζει να σημειωθεί ότι όταν διαβάζετε διάφορες συζήτησεις για τον αλγόριθμο A* στο διαδίκτυο θα δείτε περιστασιακά κάποιον να αναφέρει κάποιον αλγόριθμο ως Α* ενώ στην πραγματικότητα δεν είναι. Ο αλγόριθμός Α* που συζητήθηκε πρέπει  να περιέχει συγκεκριμένα ανοικτές και κλειστές λίστες και βαθμολόγηση μονοπατιού χρησιμοποιώντας τα F,G και H. Υπάρχουν πλείστοι άλλοι αλγόριθμοι εύρεσης-μονοπατιού(pathfinding) αλλά αυτοί δεν είναι αλγόριθμοι σαν τον Α* ο οποίος θεωρείται γενικά ένας από τους καλύτερους. Ο Bryan Stout αναφέρεται σε αρκετούς από αυτούς σε άρθρο του για το οποίο υπάρχει παραπομπή στο τέλος του παρόντος άρθρου συμπεριλαμβάνοντας τα υπέρ και τα κατά τους. Μερικές φορές οι εναλλακτικές λύσεις είναι καλύτερες, αλλά πρέπει να έχετε πλήρη κατανόηση του τι θέλετε να κάνετε. Αλλά ας συνεχίσουμε…

Σημειώσεις για την υλοποίηση

Τώρα που κατανοείτε τα βασικά παραθέτω κάποια επιπλέον πράγματα που θα πρέπει να έχετε υπόψη όταν γράφεται την εφαρμογή σας. Κάποιο από το ακόλουθο υλικό είναι γραμμένο σε C++ και Blitz Basic αλλά τα βασικά εφαρμόζονται και σε άλλες γλώσσες.

1.Άλλες μονάδες(αποφυγή σύγκρουσης):Αν κοιτάξετε προσεχτικά το δείγμα του κώδικά μου θα παρατηρήσετε ότι αγνοεί εξ’ ολοκλήρου τις άλλες μονάδες στην οθόνη. Οι μονάδες περνούν η μια μέσα από την άλλη. Αυτό μπορεί να είναι αποδεκτό ή όχι και εξαρτάται από το παιχνίδι. Αν θέλετε να εξετάσετε και άλλες κινούμενες μονάδες στον αλγόριθμο προτείνω να εξετάζετε αυτές οι οποίες είναι σταματημένες ή βρίσκονται δίπλα στην μονάδα για την οποία εφαρμόζεται ο αλγόριθμος θεωρώντας τις θέσεις του ως μη προσπελάσιμες. Για διπλανές μονάδες οι οποίες κινούνται μπορείτε να αποφύγετε τις συγκρούσεις δίνοντας πόντος ποινής στους κόμβους που βρίσκονται στα αντίστοιχα μονοπάτια τους και συνεπώς προτρέποντας την μονάδα σας να βρει ένα διαφορετικό δρόμο(περιγράφεται εκτενέστερα στο #2).

Αν επιλέξετε να εξετάσετε και άλλες κινούμενες μονάδες που δεν βρίσκονται δίπλα στην μονάδα σας(αυτή για την οποία εφαρμόζεται ο αλγόριθμος) θα χρειαστεί να αναπτύξετε μια μέθοδο ώστε να προβλέπετε που θα βρίσκονται κάθε στιγμή ώστε να γίνει η αποφυγή τους. Διαφορετικά θα καταλήξετε σε περίεργα μονοπάτια όπου οι μονάδες προσπαθούν να αποφύγουν άλλες μονάδες οι οποίες δεν βρίσκονται εκεί πια κάνοντας zigzag.

Θα χρειαστεί επίσης να αναπτύξετε μια μέθοδο ανίχνευσης συγκρούσεων διότι όσο καλό και να είναι το μονοπάτι τη στιγμή που εξετάζεται, τα πράγματα μπορεί να αλλάξουν αργότερα. Όταν συμβαίνει μια σύγκρουση, μια μονάδα είτε πρέπει να εξετάσει διαφορετικό μονοπάτι είτε να περιμένει την άλλη μονάδα να βγει από το δρόμο της ώστε να συνεχίσει.

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

2. Μεταβλητό βαθμός προσπέλασης: Σε αυτό το άρθρο και στο αντίστοιχο πρόγραμμα, η περιοχή μπορεί να είναι μόνο προσπελάσιμη ή μη προσπελάσιμη. Αλλά τι γίνεται αν έχουμε μια περιοχή όπου είναι προσπελάσιμη αλλά με μεγαλύτερο βαθμό δυσκολίας; Βάλτοι, λόφοι, σκαλοπάτια σε ένα μπουντρούμι κλπ. –αυτά είναι παραδείγματα περιοχής που είναι προσπελάσιμη αλλά με μεγαλύτερο βαθμό δυσκολίας από το επίπεδο έδαφος. Παρομοίως ένας δρόμος μπορεί να έχει μικρότερο βαθμό δυσκολίας στην κίνηση από την περιβάλλουσα περιοχή.

Αυτό το πρόβλημα αντιμετωπίζεται εύκολα προσθέτοντας έναν βαθμό δυσκολίας όταν υπολογίζεται το G ενός δεδομένου κόμβου. Απλά αυξήστε την τιμή του G σε τέτοιους κόμβους. Ο αλγόριθμος Α* είναι φτιαγμένος έτσι ώστε να βρίσκει το συντομότερο μονοπάτι(από άποψη βαθμολογίας) και θα μπορεί να το αντιμετωπίσει αυτό εύκολα. Σε αυτό το απλό παράδειγμα, περιέγραψα μόνο την περίπτωση όπου η περιοχή είναι προσπελάσιμη ή μη και ο Α* θα ψέξει για το συντομότερο κα ποιο ευθύ μονοπάτι. Αλλά σε μια περιοχή με μεταβλητό βαθμό προσπέλασης το συντομότερο μονοπάτι ίσως να μην είναι αυτό με την συντομότερη απόσταση όπως π.χ. το να πάτε γύρω από ένα βάλτο είναι συντομότερο από το να περάσετε από μέσα του.

Ένα επιπλέον ενδιαφέρον ζήτημα είναι αυτό το οποίο οι ειδικοί αναφέρουν ως χαρτογράφηση επιρροής(influence mapping). Έτσι όπως το μεταβλητός βαθμός προσπέλασης που περιγράφηκαν ποιο πάνω, μπορούμε να δημιουργήσουμε ένα επιπλέον σύστημα μονάδων και να το εφαρμόσουμε στα μονοπάτια για λόγους τεχνητής νοημοσύνης. Φανταστείτε ότι έχετε ένα χάρτη όπου κάποιες μονάδες προασπίζονται πάνω σε ένα βουνό ένα πέρασμα . Κάθε φορά όπου ο Υ/Η στέλνει κάποιον σε αυτό το πέρασμα μέσω μιας διαδρομής πέφτει στην ενέδρα. Αν θέλουμε μπορούμε να φτιάξουμε έναν χάρτη επιρροής ο οποίος επιβάλλει ποινή σε αυτούς του κόμβους όπου γίνεται η σφαγή. Αυτό θα μάθαινε τον υπολογιστή να επιλέγει ασφαλέστερα μονοπάτια και θα βοηθούσε στην αποφυγή ανεπιθύμητων καταστάσεων όπου θα έστελνε μονάδες σε από ένα μονοπάτι μόνο επειδή αυτό είναι συντομότερο(αλλά επιπλέον και πολύ πιο επικίνδυνο).

Ακόμα μια πιθανή χρήση της επιβολής ποινής είναι σε κόμβους που βρίσκονται σε μονοπάτια διπλανών κινούμενων μονάδων, Ένα από τα μειονεκτήματα του Α* είναι όταν ένα σύνολο από μονάδες προσπαθεί να βρει μονοπάτια για την ίδια τοποθεσία γίνεται σημαντική επικάλυψη αφού μια ή περισσότερες μονάδες προσπαθούν να πάρουν το ίδιο ή παρόμοιο μονοπάτι για να φτάσουν στον προορισμό τους. Βάζοντας ποινή σε κόμβους που διεκδικούν άλλες μονάδες θα περιορίσει αυτό το φαινόμενο. Μην μεταχειρίζεστε ώμος αυτούς τους κόμβους ως μη προσπελάσιμους διότι ακόμα επιθυμείτε πολλαπλές μονάδες να μπορούν να διαβούν μέσω ενός στενού διαδρόμου. Επιπλέον θα πρέπει να βάζετε ποινή στα μονοπάτια των μονάδων όπου βρίσκονται κοντά στην μονάδα για την οποία εκτελείτε ο αλγόριθμος όχι όλα τα μονοπάτια διότι θα προκύψουν παράξενες zigzag κινήσεις όπου οι μονάδες αποφεύγουν μονοπάτια άλλων μονάδων οι οποίες δεν βρίσκονται εκεί κοντά!!. Ακόμα θα πρέπει να βάζετε ποινή σε κόμβους οι οποίοι βρίσκονται στο κομμάτι του μονοπατιού που υπολείπεται και όχι σε μονοπάτι που η μονάδα έχει είδη επισκεφτεί.

3.Διαχείριση ανεξερεύνητων περιοχών: Έχετε παίξει ποτέ παιχνίδι όπου η Η/Υ πάντα γνωρίζει ακριβώς ποιο μονοπάτι πρέπει να πάρει, ακόμα και αν ο χάρτης δεν έχει εξερευνηθεί ακόμα; Ανάλογα με το παιχνίδι, το pathfinding που είναι πολύ καλό μπορεί να γίνει και μη ρεαλιστικό. Ευτυχώς αυτό το πρόβλημα μπορεί να αντιμετωπιστεί αρκετά εύκολα.

Η απάντηση βρίσκεται στο να δημιουργήσετε ένα πίνακα «γνωστής-προσπελασιμότητας>  για κάθε έναν παίκτη συμπεριλαμβανομένων και αυτών που χειρίζεται ο Υ/Η(και όχι για κάθε μονάδα κάτι που θα κατανάλωνε πολύ μνήμη). Κάθε πίνακας θα περιέχει πληροφορίες για τις περιοχές όπου ο παίκτης έχει εξερευνήσει θεωρώντας τον υπόλοιπο χάρτη ως προσπελάσιμο μέχρι αποδειχτεί διαφορετικά. Χρησιμοποιώντας αυτήν την προσέγγιση οι μονάδες θα περιπλανιόνται και θα κάνουν παρόμοια λάθη μέχρι να μάθουν τον δρόμο. Όταν ο χάρτης εξερευνηθεί το pathfinding θα λειτουργεί κανονικά.

4.Ομαλότερα μονοπάτια: Καθόσον ο Α* θα δίνει αυτόματα το συντομότερο από άποψη κόστους μονοπάτι, δεν θα δίνει και το μονοπάτι που θα φαίνεται ομαλότερο. Δείτε το τελικό μονοπάτι του παραδείγματος μας(Εικόνα 7). Σε εκείνο το μονοπάτι το πρώτο βήμα είναι ακριβώς κάτω και δεξιά από το αρχικό τετράγωνο. Δεν θα ήταν ποιο ομαλό το μονοπάτι μας αν το πρώτο βήμα ήταν το τετράγωνο ακριβώς κάτω από το αρχικό;

Υπάρχουν πολλοί τρόποι για να διορθωθεί αυτό το πρόβλημα. Καθόσον υπολογίζεται το μονοπάτι μπορείτε να επιβάλλετε ποινή στους κόμβους όπου υπάρχει μια μεταβολή στην κατεύθυνση προσθέτοντας έναν βαθμό ποινής στο G. Εναλλακτικά μπορείτε να διασχίσετε το μονοπάτι αφού υπολογιστεί λαμβάνοντας υπόψη τα μέρη όπου αν επιλέγατε έναν διπλανό κόμβο θα σας έδινε ένα ποιο ομαλό μονοπάτι. Για περισσότερα πάνω στο θέμα κοιτάξτε το άρθρο του Marco Pinter στην σελίδα Toward More Realistic Pathfinding(δωρεάν με εγγραφή)

5.Μη-τετραγωνικές περιοχής αναζήτησης: Στο παράδειγμά μας χρησιμοποιήσαμε μια απλή περιοχή 2 διαστάσεων. Μπορείτε να χρησιμοποιήσετε ακανόνιστες περιοχές . Σκεφτείτε το επιτραπέζιο παιχνίδι Risk και τις χώρες του. Μπορείτε να επινοήσετε ένα σενάριο pathfinding για ένα παιχνίδι σαν και αυτό. Για να το κάνετε αυτό πρέπει να φτιάξετε έναν πίνακα για να αποθηκεύετε τις γειτονικές χώρες κάθε χώρας και μια τιμή G συσχετισμένη με την κίνηση από μια χώρα σε μια άλλη. Θα πρέπει ακόμα να βρείτε μια μέθοδο για να υπολογίζετε το H. Όλα τα υπόλοιπα μένουν τα ίδια όπως στο παράδειγμα μας. Αντί να κοιτάτε τα διπλανά τετράγωνα θα κοιτάτε τις διπλανές χώρες στον πίνακα όταν φτιάχνετε την ανοικτή λίστα σας.

Με τον ίδιο τρόπο θα μπορείτε να φτιάξετε ένα σύστημα δ-σημείων για μονοπάτια σε έναν σταθερό χάρτη. Τα δ-σημεία αποτελούν σημεία τα οποία διασχίζονται συχνά σε ένα μονοπάτι, ίσως σε έναν δρόμο ή μια κύρια σήραγγα σε ένα μπουντρούμι. Μπορείτε εκ των προτέρων να προσδιορίσετε αυτά τα δ-σημεία. Δύο δ-σημεία θα θεωρούνται ως «παρακείμενα» το ένα ως προς το άλλο αν δεν υπάρχουν εμπόδια ανάμεσα στην ευθεία γραμμή που τα συνδέει. Όπως και στο Risk μπορείτε να αποθηκέψετε αυτήν την πληροφορία σε κάποιο πίνακα και να την χρησιμοποιήσετε όταν φτιάχνετε την ανοικτή σας λίστα. Θα μπορείτε ύστερα να καταγράψετε τα G(ίσως λαμβάνοντας το μήκος της ευθείας γραμμής μεταξύ των κόμβων ως απόσταση) και τα H(ίσως λαμβάνοντας το μήκος της γραμμής μεταξύ του κόμβου και του στόχου ως απόσταση). Όλα τα υπόλοιπα παραμένουν ίδια.

 

Ο Amit Patel έχει γράψει ένα σύντομο άρθρο για κάποιες εναλλακτικές. Για ένα επιπλέον παράδειγμα αναζήτησης σε έναν ισομετρικό χάρτη RPG χρησιμοποιώντας μια μη-τετράγωνη περιοχή έρευνας δείτε το άρθρο μου Two-Tiered A* Pathfinding.

6.Συμβολές για ταχύτητα: Καθώς θα αναπτύσσετε τον δικό σα αλγόριθμο Α* ή θα προσαρμόζετε αυτόν που έχω φτιάξει θα δείτε ότι το pathfinding χρησιμοποιεί μεγάλο μέρος της CPU ειδικά όταν έχετε έναν μεγάλο αριθμό από μονάδες που βρίσκουν το δρόμο τους σε έναν μεγάλο χάρτη. Αν διαβάσετε τα διάφορα άρθρα στο διαδίκτυο θα δείτε ότι αυτό είναι αλήθεια ακόμα και για επαγγελματίες που σχεδιάζουν παιχνίδια όπως το Starcraft  ή το Age of Empires. Αν δείτε ότι το πράγμα αργεί πολύ εξαιτίας του pathfinding, ορίστε μερικές ιδέες οι οποίες θα επιταχύνουν λίγο τα πράγματα:

 

7.Διατηρώντας την ανοικτή λίστα: Αυτό αποτελεί ένα από τα πιο χρονοβόρα στοιχεία του αλγόριθμου Α*. Κάθε φορά που εξετάζεται την ανοικτή λίστα, πρέπει να βρείτε το τετράγωνο με το μικρότερο F. Υπάρχουν αρκετοί τρόποι για να το κάνετε αυτό. Μπορείτε να σώσετε τα στοιχεία του μονοπατιού και απλά να εξετάσετε όλη τη λίστα κάθε φορά που χρειάζεται να βρείτε το τετράγωνο με το μικρότερο F. Αυτό είναι απλό αλλά πολύ αργό για μεγάλα μονοπάτια. Μπορεί να βελτιωθεί όμως συντηρώντας μια διατεταγμένη λίστα και επιλέγοντας απλά το πρώτο στοιχείο της λίστας κάθε φορά που θέλετε το τετράγωνο με το μικρότερο F. Όταν έγραψα το πρόγραμμα, αυτή ήταν η πρώτη μέθοδος που χρησιμοποίησα.

Αυτό θα δουλέψει αρκετά καλά για μικρούς χάρτες αλλά γενικά δεν είναι γρήγορη λύση. Οι επαγγελματίες προγραμματιστές του Α* που θέλουν μεγάλες ταχύτητες χρησιμοποιούν ένα δυαδικό δέντρο, και αυτό χρησιμοποιώ στον κώδικά μου. Βάσει της εμπειρίας μου αυτή η προσέγγιση είναι 2 με 3 φορές γρηγορότερη στις περισσότερες περιπτώσεις και εκθετικά γρηγορότερη(10 φορές γρηγορότερη) για μεγαλύτερες διαδρομές. Αν θέλετε να μάθετε περισσότερα για δυαδικά δέντρα δείτε το άρθρο μου, Using Binary Heaps in A* Pathfinding.

Μια επιπλέον δυσκολία είναι ο τρόπος που σβήνετε και διατηρείτε τις δομές δεδομένων σας μεταξύ των κλήσεων του αλγορίθμου. Εγώ προσωπικά προτιμώ να τα αποθηκεύω όλα σε πίνακες. Παρότι οι κόμβοι μπορούν να δημιουργηθούν και να διατηρηθούν με δυναμικό αντικειμενοστραφή τρόπο, βρίσκω ότι ο χρόνος που χρειάζεται για να φτιαχτούν και να διαγραφούν τέτοια αντικείμενα είναι μεγάλος και επιβραδύνει τα πράγματα. Αν χρησιμοποιείτε πίνακες όμως θα πρέπει να σβήνετε τα δεδομένα μεταξύ των κλήσεων. Το τελευταίο πράγμα που θα θέλετε να κάνετε σε τέτοιες περιπτώσεις είναι να ξοδεύετε χρόνο μηδενίζοντας τα όλα μετά από την κλήση του αλγορίθμου pathfinding, ιδιαίτερα αν έχετε έναν μεγάλο χάρτη.

Εγώ αποφεύγω αυτό το πρόβλημα φτιάχνοντας έναν 2D πίνακα όπου τον ονομάζω whichList(x,y) ο οποίος για κάθε κόμβο υποδεικνύει αν αυτός βρίσκεται στην ανοικτή ή κλειστή λίστα. Μετά το pathfinding δεν μηδενίζω αυτή τη λίστα. Αντί αυτού μηδενίζω τα onClosedList onOpenList  σε κάθε κλήση του αλγορίθμου pathfinding αυξάνοντας και τα δύο κατά 5 ή κάτι παρόμοιο κάθε φορά που εκτελείτε ο αλγόριθμος.Με αυτόν τον τρόπο ο αλγόριθμος μπορεί με ασφάλεια να αγνοήσει όποια προηγούμενα δεδομένα από προηγούμενες κλήσεις του αλγορίθμου. Επίσης αποθηκεύω τις τιμές των F, G, H σε πίνακες. Σε αυτήν την περίπτωση απλώς γράφω τις καινούργιες τιμές επί των παλαιών χωρίς πριν να καθαρίζω τους πίνακες.

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

8. Ο αλγόριθμος του Dijkstra: Ενώ ο Α* θεωρείται γενικά ο καλύτερος αλγόριθμος για pathfinding, υπάρχει τουλάχιστον ακόμα ένας αλγόριθμος που έχει την χρησιμότητα του – ο αλγόριθμος του Dijkstra. Ο αλγόριθμος του Dijkstra είναι ουσιαστικά ίδιος με τον Α*, με τη διαφορά ότι δεν υπάρχει ευρετική(το H είναι πάντα 0). Επειδή δεν έχει ευρετική, ψάχνει το ίδιο σε κάθε κατεύθυνση. Όπως μπορείτε να φανταστείτε επειδή ο αλγόριθμος του Dijkstra τελικά διερευνάει πολύ μεγαλύτερη περιοχή πριν βρεθεί ο στόχος, αυτό τον κάνει πιο αργό από τον Α*.

Τότε γιατί τον χρησιμοποιούμε;Μερικές φορές δεν ξέρουμε που βρίσκεται ο στόχος μας. Ας πούμε ότι έχετε μια μονάδα περισυλλογής πόρων η οποία χρειάζεται να πάει να μαζέψει πόρους κάποιου είδους. Μπορεί να γνωρίζει που βρίσκονται διάφορες περιοχές πόρων, αλλά θέλει να πάει στην πιο κοντινή περιοχή. Εδώ ο αλγόριθμος του Dijkstra είναι καλύτερος από τον * διότι δεν ξέρουμε την πλησιέστερη. Η μόνη μας εναλλακτική είναι να τρέξουμε επανειλλημένως τον αλγόριθμο A*, να βρούμε την απόσταση για κάθε μια και να επιλέξουμε ανάλογα. Υπάρχουν αμέτρητες παρόμοιες καταστάσεις όπου θέλουμε να ξέρουμε ποια από τις τοποθεσίες που θέλουμε είναι η πλησιέστερη ή που βρίσκεται αυτή η τοποθεσία.

Επιπλέον διάβασμα

Τώρα ξέρετε τα βασικά και έχετε μια αίσθηση και για πιο προχωρημένα πράγματα. Σε αυτό το σημείο προτείνω να μελετήσετε τον κώδικά μου. Το πακέτο περιλαμβάνει 2 εκδόσεις, μια σε C++ και μια σε Blitz Basic. Και οι δύο έχουν αρκετό σχολιασμό και θα είναι σχετικά εύκολο να τις κατανοήσετε. Ορίστε ο σύνδεσμος.

Αν δεν έχετε C++ ή Blitz Basic, δύο αρχεία exe υπάρχουν στην έκδοση C++. Μπορείτε να αποκτήσετε μια demo έκδοση της Blitz Basic 3D(όχι Blitz Plus) στη διεύθυνση Blitz Basic.

Μπορείτε επίσης να επισκεφτείτε τις επόμενες σελίδες. Θα είναι πολύ πιο εύκολο να κατανοήσετε τώρα που έχετε διαβάσει όλα αυτά.

Κάποιοι άλλοι δικτυακοί τόποι που αξίζει να επισκεφτείτε:

Αυτά λοιπόν. Αν τύχει να γράψετε κάποιο πρόγραμμα το οποίο χρησιμοποιεί οτιδήποτε από τα παραπάνω θα ήθελα να το δω. Μπορείτε να με βρείτε στο

Μέχρι τότε καλή τύχη!