Alchemist` Δημοσ. 26 Ιανουαρίου 2010 Δημοσ. 26 Ιανουαρίου 2010 Πάνε πάνω από 2 μήνες που προσπαθώ να φτιάξω έναν τέτοιο αλγόριθμο αλλα δεν μπορώ να καταφέρω... Έχω δοκιμάσει διάφορους τροπους, αλλα για διαφορετικούς λόγους δεν μου κάνουν... Πριν προχωρήσω να εξηγήσω λίγο το περιβάλλον στο οποίο βρίσκομαι... Ο χώρος είναι δυσδιάστατος, χωρίς grid, και έχω το αντικείμενο "enemy_OBJ" (με δεδομένο χ,ψ) που θέλει να πάει στο σημείο (move_decision_x,move_decision_y) αποφεύγοντας τα 32χ32 εμπόδια (wall_OBJ). Η θέση του αντικειμένου wall_OBJ, καθορίζεται από 1χ και 1ψ, τα οποία δείχνουν το κέντρο του 32χ32 τετραγώνου. Το enemy_OBJ έχει επίσης εμβαδόν 32χ32, και το χ και ψ του λειτουργούν όπως του wall_OBJ. Επιπροσθέτως το αντικείμενο enemy έχει την μεταβλητή speed που δείχνει την ταχύτητα του, και την μεταβλητή direction που δείχνει την κατεύθυνσή του σε μοίρες (0-360). Δεν με ενδιαφέρει αν ο αλγόριθμος επιλέγει το συντομότερο δρόμο για το τελικό σημείο, απλά να πηγαίνει εκεί αποφεύγοντας τα εμπόδια. Έχω φτάσει στο εξής μοντέλο, αλλα δε δουλεύει πάντα σωστά: Αρχικά το enemy_OBJ ελέγχει αν μπορεί να πάει άμεσα, κινούμενο ευθεία απευθείας στον στόχο (move_decision_x,move_decision_y). Αν δλδ δεν υπάρχουν εμπόδια στο ενδιάμεσο, με την χρήση της συνάρτησης collision_line. Αν ναι, τοτε πάει απευθείας εκεί. Αν υπάρχουν εμπόδια, τότε ξεκινάει να κινείται προς τα εκεί και ελέγχει συνεχώς αν είναι ελεύθερος ο χώρος σε απόσταση 40 από το σημείο που βρίσκεται τώρα. Όσο είναι ελεύθερος ο χώρος τότε κινείται προς τα εκεί, μέχρι που αναπόφευκτα, συναντά το εν λόγω εμπόδιο. Τότε αλλάζει την κατεύθυνση του, ελέγχει πια είναι η θέση του σε σχέση με το εμπόδιο, και αλλάζει την κατεύθυνσή του ώστε να το αποφύγει. Με πιθανότητα 50% επιλέγει να αποφύγει το εμπόδιο από μια εκ των 2 δυνατών κατευθύνσεων. Μόλις το σημείο που απέχει απόσταση 40 από το enemy_OBJ, και βρίσκεται στην ευθεία από το enemy_OBJ.x, enemy_OBJ.y και move_decision_x, move_decision_y γίνει ξανά ελεύθερο τότε το enemy_OBJ βαδίζει στην ευθεία αυτή προς τον στόχο. Πολλές φορές όμως (όταν υπάρχουν πάνω από 1 εμπόδια) δεν δουλεύει σωστά, είτε περνά μέσα από κάποιο εμπόδιο, είτε κολάει... Ο κώδικας (σε GML) του αλγορίθμου που περιγράφω είναι ο εξής: >if (algorithm_use = 1) then { //pathfinding algorithm (method #3) //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //phase 1, select course type (1: no line object , 2: objects in the way) if (not(((move_decision_x = x))&&((move_decision_y = y)))) then { //check if u can go straight to decision point if (not(collision_line(x,y,move_decision_x,move_decision_y,wall_OBJ,true,all))) then { course = 1 } //if there are objects in the way if (collision_line(x,y,move_decision_x,move_decision_y,wall_OBJ,true,all)) then { course = 2 } } //end of phase 1 //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //phase 2 //course 1 if (course = 1) then { speed = 3 direction = point_direction(x,y,move_decision_x,move_decision_y) } //****************************** //course 2 if (course = 2) then { check_dir = point_direction(x,y,move_decision_x,move_decision_y) rad_check_dir = degtorad(check_dir) //z = 32 check_x = x + 40*cos(rad_check_dir) check_y = y + 40*sin(rad_check_dir) if (place_free(check_x,check_y)=true) then { first_pass = true dir_chosen = 0 } if (place_free(check_x,check_y)=false) then { first_pass = false } } //end of phase 2 //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //phase 3 //first_pass = true (object further than 32) if (first_pass = true) then { speed = 3 direction = check_dir type = 0 } //first_pass = false (object very close (=<32)) if (first_pass = false) then { hurdle_id = collision_line(x,y,move_decision_x,move_decision_y,wall_OBJ,true,all) if (hurdle_id > 0) then { //8 cases for 8 angles of object position //CASE 1 if ((x > hurdle_id.x + 16)&&(y < hurdle_id.y - 16)) then { type = 1 break; } //CASE 2 if ((hurdle_id.x - 16 < x)&&(x < hurdle_id.x + 16)&&(y < hurdle_id.y - 16)) then { type = 2 break; } //CASE 3 if ((x < hurdle_id.x - 16)&&(y < hurdle_id.y - 16)) then { type = 3 break; } //CASE 4 if ((x < hurdle_id.x - 16)&&(y > hurdle_id.y -16)&&(y < hurdle_id.y +16)) then { type = 4 break; } //CASE 5 if ((x < hurdle_id.x - 16)&&(y > hurdle_id.y +16)) then { type = 5 break; } //CASE 6 if ((hurdle_id.x -16 <x)&&(x < hurdle_id.y +16)&&(y > hurdle_id.y +16)) then { type = 6 break; } //CASE 7 if ((x > hurdle_id.x +16)&&(y > hurdle_id.y +16)) then { type = 7 break; } //CASE 8 if ((x > hurdle_id.x +16)&&(y > hurdle_id.y -16)&&(y < hurdle_id.y +16)) then { type = 8 break; } } } //end of phase 3 //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ //Phase 4 (final action) if (type = 1) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 180 } if (dir_choose = 2) then { speed = 3 direction = 270 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 2) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 180 } if (dir_choose = 2) then { speed = 3 direction = 0 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 3) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 0 } if (dir_choose = 2) then { speed = 3 direction = 270 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 4) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 90 } if (dir_choose = 2) then { speed = 3 direction = 270 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 5) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 0 } if (dir_choose = 2) then { speed = 3 direction = 90 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 6) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 180 } if (dir_choose = 2) then { speed = 3 direction = 0 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 7) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 180 } if (dir_choose = 2) then { speed = 3 direction = 90 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ if (type = 8) then { if (dir_chosen = 0) then { dir_choose = choose(1,2) dir_chosen = 1 if (dir_choose = 1) then { speed = 3 direction = 90 } if (dir_choose = 2) then { speed = 3 direction = 270 } } } //^^^^^^^^^^^^^^^^^^^^^^^^^^^ //end of phase 4 //########################################### } //end of algorithm Μπορεί κανείς να βοηθήσει βελτιώνοντας τον παρόν αλγόριθμο, ή προτείνοντας κάτι καλύτερο? Εχω είδι δοκιμάσει 2 παραλλαγές του αλγορίθμου best FS, και μια του A*... Ο best FS δεν δούλευε επίσης σωστά, ενώ ο Α* δούλευε τέλεια αλλά είναι παρα πολύ αργός και χρησιμοποεί grids. (ο αλγόριθμος χρησιμοποιείται για το παιχνίδι της υπογραφής, αν θέλτε δείτε τα screens για να πάρετε μια εικόνα του περιβάλλοντος) ΕΥχαριστώ προκαταβολικά ΣΗΜΑΝΤΙΚΗ ΣΗΜΕΙΩΣΗ: Ο αλγόριθμος εκτελείται σε κάθε step του επεξεγαστή, και εν τω μεταξύ μπορεί να αλλάζει ο στόχος της κατεύθυνσης... Δεν θέλω αλγόριθμο ο οποίος έχει την μορφή συνάρτησεις που μου επιστρέφει ως αποτέλεσμα την διαδρομή... Η διαδρομή υπολογίζεται δλδ "real-time" εκείνη την στιγμή. _________________________________________________ Y.Γ. είχα αυτόν τον τίτλο στο θέμα "Fast,non-grid,2D Pathfinding script... Βοήθεια!" και μου βγάζει αυτό Δε μπορείτε να χρησιμοποιήσετε τη λέξη "Βοήθεια" στο τίτλο του θέματος σας. Παρακαλούμε χρησιμοποιήστε πιο περιγραφικό τίτλο. ΕΛΕΟΣ???
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.