Amire én a labeles megoldást találtam a leghatékonyabbnak: Egy rekurzió nélküli fill-ező algoritmus. Adott egy kezdő koordináta és négy kiterjesztési irány sorrendben: fel ( 0 ), jobbra ( 1 ), le ( 2 ) és balra ( 3 ). Veszem a kezdő koordinátát és vizsgálom a kiterjeszthetőséget az adott irányokba, ha kiterjeszthető akkor egy listába felveszem az épp vizsgált elem koordinátáját és kiterjesztem az újat. Hogyha egy adott koordináta nem terjeszthető ki kiveszem a listából az előzőleg félbehagyott elemet és attól az iránytól szeretném folytatni, ahol előzőleg abbahagytam. Ha nincs lehetséges kiterjesztés és vissza kell lépni tárolom 'zsákutca' elem koordinátáját, és a listából kivett folytatandó koordináta, a 'zsákutca' elem koordinátája és a kötött kiterjesztési sorrendből tudom, hogy melyik irányban kell folytatni a kiterjesztést.
Ez kódban így néz ki:
if( back == false ) { //Ha nem vagyunk backtrack-ben, a 0. kiterjesztési iránnyal kezdünk
goto LABEL_EXPANDSTATUS_0;
} else {
//Ha épp backtrack-ben vagyunk meg kell vizsgálni, hogy milyen koordinátáról léptünk vissza és aszerint kell folytatni a kiértékelést
if( _x == prevX ) { // X == PREVX
if( _y < prevY ) { // Y < PREVY
goto LABEL_EXPANDSTATUS_3;
} else { // Y > PREVY
goto LABEL_EXPANDSTATUS_1;
}
} else {
if( _x < prevX ) { // X < PREVX
if( _y == prevY ) { // Y == PREVY
goto LABEL_EXPANDSTATUS_2;
}
} else { // X >PREVX
if( _y == prevY ) { // Y == PREVY
goto LABEL_EXPANDSTATUS_4;
}
}
}
LABEL_EXPANDSTATUS_0:
if( FELFELEkiterjesztheto ) {
backTrack_->push_back( _y * _map->width_ + _x );
[...]
expandStatus = 0;
goto LABEL_EXPANDSTATUS_ENDEXPAND;
}
LABEL_EXPANDSTATUS_1:
if( JOBBRAkiterjesztheto ) {
backTrack_->push_back( _y * _map->width_ + _x );
[...]
expandStatus = 1;
goto LABEL_EXPANDSTATUS_ENDEXPAND;
}
LABEL_EXPANDSTATUS_2:
if( LEFELEkiterjesztheto ) {
backTrack_->push_back( _y * _map->width_ + _x );
[...]
expandStatus = 2;
goto LABEL_EXPANDSTATUS_ENDEXPAND;
}
LABEL_EXPANDSTATUS_3:
if( BALRAkiterjesztheto ) {
backTrack_->push_back( _y * _map->width_ + _x );
[...]
expandStatus = 3;
goto LABEL_EXPANDSTATUS_ENDEXPAND;
}
LABEL_EXPANDSTATUS_4:
expandStatus = 4;
LABEL_EXPANDSTATUS_ENDEXPAND:
if( expandStatus == 4 ) {
//BACK, nincs kiterjesztheto irany
} else {
//VAN kiterjesztheto irany, ennek a lemanagelese
}
Persze meg lehet írni goto nélkül, de akkor ciklus iterációnként kell bele egy switch, vagy egy függvény pointer tömbből való hívás - és ez sajnos egy nagyon kritikus függvény, sokszor fut le így a performance volt az elsődleges. Szerintem ez egy jó példa a goto indokolt használatára.
SZERK.: Sajnos a behúzásaim eltűntek így nagyon csúnya a kód, nem értem, a < c o d e > blokkon belül miért nem maradnak meg a whitespace karakterek....