Autor:
night_hawk, postat pe 08 Sep 2007 14:28:39
Da, am rezolvat cu pathfinding-ul in Galactica : Corsairs si vreau sa spun tuturor cum! Nu e o metoda prea eficienta, dar e mai rapida decat majoritatea alternativelor. Adaug la final si cod sursa de exemplu.
BTW: Acest algoritm este doar pentru pathfinding in spatiu, fara terrain.
Incepem.
Se stie pozitia unitatii 1. Se stie unde doreste unitatea 1 sa ajunga. Se traseaza 2 linii de la unitatea 1 la tinta in modul urmator: prima linie isi are originea mai sus de pozitia unitatii 1 cu o valoare predefinita sau generata sau unica pentru unitatea respectiva, in timp ce originea celei de a doua linii e mai jos cu aceasi valoare. Capetele liniilor se pozitioneaza analog cu originea pentru a se interesecta.
Figura 1 - Cam cum sunt pozitionate liniile descrise
Pasul 2 este optional, dar este destul de folositor deoarece ar putea mari viteza algoritmului considerabil, desi va consuma mai multa memorie. Unitatile vor fi aranjate intr-o matrice de A x A, unde A depinde de numarul de unitati, unde fiecare element este un array de id-uri sau pointeri catre unitatile reprezentate. In aceasta matrice unitatile sunt aranjate dupa pozitia lor in spatiu 2D (Doar X si Z), cu posibilitatea ca mai multe unitati sa fie in aceasi pozitie in matrice.
Pasul 3 este chiar metoda propriu zisa: daca s-a facut pasul 2, se fac coliziuni intre linii si bounding-box-ul fiecarei unitati din elementele adiacente elementului unitatii pentru care facem pathfinding-ul, iar daca nu s-a facut pasul 2, cu toate unitatile de pe harta. Daca s-a gasit o coliziune, nu se mai verifica in continuare, iar unitatii pentru care am verificat i se spune sa se ridice / coboare / opreasca, asta depinzand de ce aveti nevoie.
Nu e eficient pe distante scurte, dar este rapid si, zic eu, destul de usor de implementat.
Cod sursă:
irr::core::line3df line,line2;
line.start= units[i].node->getPosition()+vector3df(0,40,0);
line2.start= units[i].node->getPosition()+vector3df(0,-40,0);
vector3df targ=units[i].target;
targ.Y=oldy;
line.end=targ+vector3df(0,-40,0);
line2.end=targ+vector3df(0,40,0);
bool colis=0;
vector3df pos22;
for(int i2=1;i2(mai mic)=count;i2++)
{
colis = smgr->getSceneCollisionManager()->getCollisionPoint(line, units[i2].node->getTriangleSelector(), colres, coltri);
if(colis)
{
pos22=units[i2].node->getPosition();
i2=count;
} else {
colis = smgr -> getSceneCollisionManager()->getCollisionPoint(line2,units[i2].node->getTriangleSelector(),colres,coltri);
if(colis)
{
pos22=units[i2].node->getPosition();
i2=count;
}
}
}
if(colis)
{
// Colission has been found, there is something blocking the way, do whatever you need to do in that case.
}
[
1
]
