Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

game_bsp.cpp

Go to the documentation of this file.
00001 #pragma warning(disable: 4786) 00002 00003 /*------------------------------------ Includes ---------------------------------------------*/ 00004 #include "bsp.h" 00005 #include "game_bsp.h" 00006 #include "bresenham.h" 00007 00008 00009 00010 using namespace std; 00011 00012 00013 class cPositive_Rectangle cGame_World::Ecran = cPositive_Rectangle( cPoint2D(0,0) , cPoint2D(100,100)); 00014 00015 /****************************************************************************************************/ 00016 // class cSquare_Area 00017 /****************************************************************************************************/ 00018 cSquare_Area::~cSquare_Area() 00019 { 00020 std::vector<cHV_Seg*>::iterator walls_itr; 00021 for(walls_itr = List_Walls.begin() ; walls_itr != List_Walls.end() ; walls_itr++) 00022 { 00023 delete( (*walls_itr) ); 00024 } 00025 List_Walls.clear(); 00026 List_Portals.clear(); 00027 00028 } 00029 00030 /*--------------------------------------------------------------------------------------------------*/ 00031 void cSquare_Area::Print() 00032 { 00033 assert( Front == NULL && Back == NULL); 00034 00035 std::vector<cHV_Seg*>::iterator walls_itr; 00036 std::vector<cPortal*>::iterator portals_itr; 00037 00038 cout << "[Leaf:" << Id << "]" ; 00039 cout << "]-> Area " << Bounds << "\n"; 00040 cout << " n_walls ="<<List_Walls.size() << "\n"; 00041 cout << " n_portals ="<<List_Portals.size() << "\n"; 00042 cout << " walls : \n"; 00043 for(walls_itr = List_Walls.begin() ; walls_itr != List_Walls.end() ; walls_itr++) 00044 cout << " -> " << *(*walls_itr) << "\n"; 00045 cout << " portals : \n"; 00046 for(portals_itr = List_Portals.begin() ; portals_itr != List_Portals.end() ; portals_itr++) 00047 cout << " -> " << *(*portals_itr) << "\n"; 00048 } 00049 00050 /*--------------------------------------------------------------------------------------------------*/ 00051 void cSquare_Area::split( cHV_Wall & wall, cSquare_Area ** A1, cSquare_Area** A2) 00052 { 00053 cPoint2D pA; 00054 cPoint2D pB; 00055 00056 if( wall.Is_Horizontal() ) 00057 { 00058 pA = this->Bounds.p0; 00059 pB.Set(this->Bounds.p1.X , wall.p0.Get_Y() ); 00060 (*A1) = new cSquare_Area( cPositive_Rectangle( pA, pB) ); 00061 00062 pA.Set(this->Bounds.p0.X , wall.p0.Get_Y() ); 00063 pB = this->Bounds.p1; 00064 (*A2) = new cSquare_Area(cPositive_Rectangle( pA, pB)); 00065 } 00066 else 00067 { 00068 pA = this->Bounds.p0; 00069 pB.Set( wall.p0.Get_X() , this->Bounds.p1.Y ); 00070 (*A1) = new cSquare_Area(cPositive_Rectangle( pA , pB)); 00071 00072 pA.Set( wall.p0.Get_X() , this->Bounds.p0.Y); 00073 pB = this->Bounds.p1; 00074 (*A2) = new cSquare_Area(cPositive_Rectangle( pA, pB)); 00075 } 00076 } 00077 00078 00079 /*--------------------------------------------------------------------------------------------------*/ 00080 void cSquare_Area::Add_Wall(cHV_Seg & w) 00081 { 00082 // on verifie que le wall appartient bien a la zone 00083 assert( Bounds.In(w.Get_p0() )); 00084 assert( Bounds.In(w.Get_p1() )); 00085 00086 cHV_Seg * wall = new cHV_Seg(w.Get_p0() , w.Get_p1() ); 00087 List_Walls.push_back(wall); 00088 00089 } 00090 00091 00092 /*--------------------------------------------------------------------------------------------------*/ 00093 void cSquare_Area::Manage_Paralell_Portals() 00094 { 00095 00096 cPoint2D pA; 00097 cPoint2D pB; 00098 cPoint2D p1; 00099 cPoint2D p2; 00100 cPoint2D pnew; 00101 cHV_Seg dist; 00102 cSeg door; 00103 cPortal * new_portal = NULL; 00104 00105 00106 std::vector<cPortal*>::iterator portals_itr1; 00107 std::vector<cPortal*>::iterator portals_itr2; 00108 00109 for( portals_itr1 = List_Portals.begin(); portals_itr1 != List_Portals.end(); portals_itr1++) 00110 for( portals_itr2 = List_Portals.begin(); portals_itr2 != List_Portals.end(); portals_itr2++) 00111 { 00112 if( (*portals_itr1) < (*portals_itr2) ) 00113 if( (*portals_itr1)->Segment.On_Same_Line((*portals_itr2)->Segment) ) // portails parallell 00114 { 00115 (*portals_itr1)->Segment.Get_Middle(pA); 00116 (*portals_itr2)->Segment.Get_Middle(pB); 00117 00118 dist.Set( pA,pB); 00119 dist.Get_Middle(p1); 00120 this->Get_Centre(p2); 00121 if( dist.Is_Horizontal() ) 00122 { 00123 if( p2.Get_Y() < p1.Get_Y() ) 00124 pnew.Set(p1.X , p1.Y-40); 00125 else 00126 pnew.Set(p1.X , p1.Y+40); 00127 } 00128 else 00129 { 00130 if( p2.Get_X() < p1.Get_X() ) 00131 pnew.Set(p1.X-40 , p1.Y); 00132 else 00133 pnew.Set(p1.X +40, p1.Y); 00134 } 00135 00136 new_portal = new cParalell_Portal(pnew , -1 , this); 00137 //N_Portals++; 00138 (*portals_itr1)->Add_Voisin( new_portal); 00139 (*portals_itr2)->Add_Voisin( new_portal ); 00140 } 00141 } 00142 } 00143 00144 00145 /*--------------------------------------------------------------------------------------------------*/ 00146 void cSquare_Area::Add_Portal(cPortal * portal) 00147 { 00148 assert( portal != NULL); 00149 assert( Bounds.In(portal->Segment.Get_p0()) ); // on verifie que ce portal appartient bien a la zone 00150 assert( Bounds.In(portal->Segment.Get_p1()) ); 00151 00152 bool paralell=false; 00153 cPoint2D p1; 00154 cPoint2D p2; 00155 cPortal * new_portal = NULL; 00156 00157 // on parcours la liste des portals de cette piece 00158 // et on signale a chacun ce nouveau voisin 'portal' 00159 // on signale a 'portal' qu'il est voisin de chacun 00160 std::vector<cPortal*>::iterator portals_itr; 00161 for( portals_itr = List_Portals.begin(); portals_itr != List_Portals.end(); portals_itr++) 00162 { 00163 // ce sont deux portails non parallelles !! 00164 if( ! portal->Segment.On_Same_Line((*portals_itr)->Segment) ) 00165 { 00166 (*portals_itr)->Add_Voisin( portal); 00167 portal->Add_Voisin( (*portals_itr) ); 00168 } 00169 } 00170 00171 // on ajoute a la liste de portals de cette piece le nouveau portal 'portal' 00172 List_Portals.push_back(portal); 00173 } 00174 00175 00176 /*--------------------------------------------------------------------------------------------------*/ 00177 void cSquare_Area::Add_Paralells_Portals(cPortal * portal1 , cPortal * portal2) 00178 { 00179 assert( portal1 != NULL); 00180 assert( portal2 != NULL); 00181 assert( Bounds.In(portal1->Segment.Get_p0()) ); 00182 assert( Bounds.In(portal1->Segment.Get_p1()) ); 00183 assert( Bounds.In(portal2->Segment.Get_p0()) ); 00184 assert( Bounds.In(portal2->Segment.Get_p1()) ); 00185 00186 // on signale a chaque portal de la piece qu'il a pour nouveau voisin 'portal1' et 'portal2' 00187 std::vector<cPortal*>::iterator portals_itr; 00188 for( portals_itr = List_Portals.begin(); portals_itr != List_Portals.end(); portals_itr++) 00189 { 00190 (*portals_itr)->Add_Voisin( portal1); 00191 (*portals_itr)->Add_Voisin( portal2); 00192 } 00193 00194 // on ajoute 'portal1' et 'portal2' a la liste des portals de la piece 00195 List_Portals.push_back(portal1); 00196 List_Portals.push_back(portal2); 00197 } 00198 00199 00200 00201 00202 /****************************************************************************************************/ 00203 // class cGame_World 00204 /****************************************************************************************************/ 00205 /*--------------------------------------------------------------------------------------------------*/ 00206 cGame_World::cGame_World() 00207 { 00208 N_Leaves=0; 00209 bDecorated_With_Areas=false; 00210 N_Portals=0; 00211 00212 } 00213 00214 /*--------------------------------------------------------------------------------------------------*/ 00215 cGame_World::~cGame_World() 00216 { 00217 cPortal * pToDelete=NULL; 00218 00219 N_Leaves=0; 00220 bDecorated_With_Areas=false; 00221 N_Portals=0; 00222 //delete(Level_Loader); 00223 00224 // on n'a pas a detruire les feuilles, c le destructeur du bsp_tree qui s'en charge 00225 // il faut detruire les portals 00226 std::vector<cPortal*>::iterator Portals_Itr; 00227 for(Portals_Itr = List_Portals.begin() ; Portals_Itr != List_Portals.end() ; Portals_Itr++) 00228 { 00229 pToDelete = (*Portals_Itr); 00230 delete(pToDelete); 00231 } 00232 00233 List_Portals.clear(); 00234 List_Areas.clear(); 00235 00236 00237 } 00238 00239 00240 /*--------------------------------------------------------------------------------------------------*/ 00241 void cGame_World::Decorate_With_Areas() 00242 { 00243 cHV_Node * root = My_BSP.Get_Root(); 00244 cSquare_Area * big_one = new cSquare_Area( cGame_World::Ecran ); 00245 bDecorated_With_Areas = true; 00246 00247 if( root == NULL) 00248 { 00249 root = big_one; 00250 N_Leaves++; 00251 root->Set_Id(-N_Leaves); // les feuilles ont les id negatives 00252 } 00253 else 00254 Decorate_With_Areas(root , big_one); 00255 } 00256 00257 00258 00259 /*--------------------------------------------------------------------------------------------------*/ 00260 void cGame_World::Decorate_With_Areas(cHV_Node * node , cSquare_Area * area ) 00261 { 00262 cSquare_Area * A_Front = NULL; 00263 cSquare_Area * A_Back = NULL; 00264 00265 area->split( node->Divider, &A_Front, &A_Back); 00266 if( node->Front == NULL) 00267 { 00268 node->Front = A_Front; 00269 N_Leaves++; 00270 node->Front->Set_Id(-N_Leaves); 00271 List_Areas.push_back(A_Front); 00272 } 00273 else 00274 { 00275 Decorate_With_Areas( node->Front , A_Front); 00276 if(area != NULL) 00277 { 00278 delete(area); 00279 area = NULL; 00280 } 00281 } 00282 00283 if( node->Back == NULL) 00284 { 00285 node->Back = A_Back; 00286 N_Leaves++; 00287 node->Back->Set_Id(-N_Leaves); 00288 List_Areas.push_back(A_Back); 00289 } 00290 else 00291 { 00292 Decorate_With_Areas( node->Back , A_Back); 00293 if( area != NULL) 00294 { 00295 delete(area); 00296 area = NULL; 00297 } 00298 } 00299 } 00300 00301 00302 00303 /*--------------------------------------------------------------------------------------------------*/ 00304 void cGame_World::Print_Leaves() 00305 { 00306 std::vector<cSquare_Area*>::iterator Areas_Itr; 00307 00308 cout << "####### Liste des zones : ########## \n"; 00309 for(Areas_Itr = List_Areas.begin() ; Areas_Itr != List_Areas.end() ; Areas_Itr++) 00310 (*Areas_Itr)->Print(); 00311 cout << "#################################### \n"; 00312 } 00313 00314 00315 /*--------------------------------------------------------------------------------------------------*/ 00316 void cGame_World::Decorate_With_Walls_And_Portals() 00317 { 00318 cPoint2D pA,pB; 00319 cHV_Seg cote; 00320 00321 if( ! bDecorated_With_Areas ) 00322 { 00323 cout << " ERROR : void cGame_World::Decorate_With_Walls_And_Portals() \n"; 00324 cout << " l'arbre doit d'abord etre décoré avec les cSquarePortals !!! \n"; 00325 return; 00326 } 00327 00328 std::vector<cSquare_Area*>::iterator Areas_Itr; 00329 for(Areas_Itr = List_Areas.begin() ; Areas_Itr != List_Areas.end() ; Areas_Itr++) 00330 { 00331 /*----- cote nord -------------*/ 00332 (*Areas_Itr)->Bounds.Get_Nord_Seg(cote); 00333 Add_Wall_And_Portals( (*Areas_Itr) , cote); 00334 00335 /*------cote est ------------*/ 00336 (*Areas_Itr)->Bounds.Get_Est_Seg(cote); 00337 Add_Wall_And_Portals( (*Areas_Itr) , cote); 00338 00339 /*------- cote sud-----------*/ 00340 (*Areas_Itr)->Bounds.Get_Sud_Seg(cote); 00341 Add_Wall_And_Portals( (*Areas_Itr) , cote); 00342 00343 /*-------- cote ouest ----------*/ 00344 (*Areas_Itr)->Bounds.Get_Ouest_Seg(cote); 00345 Add_Wall_And_Portals( (*Areas_Itr) , cote); 00346 } 00347 } 00348 00349 00350 00351 /*--------------------------------------------------------------------------------------------------*/ 00352 void cGame_World::Manage_Paralell_Portals(void) 00353 { 00354 std::vector<cSquare_Area*>::iterator Areas_Itr; 00355 00356 for(Areas_Itr = List_Areas.begin() ; Areas_Itr != List_Areas.end() ; Areas_Itr++) 00357 { 00358 (*Areas_Itr)->Manage_Paralell_Portals(); 00359 } 00360 } 00361 00362 00363 00364 00365 /*--------------------------------------------------------------------------------------------------*/ 00366 void cGame_World::Creates_And_Add_Portals(cSquare_Area * area , cHV_Seg& seg ,cHV_Seg& wall) 00367 { 00368 cPortal * portal1 = NULL; 00369 cPortal * portal2 = NULL; 00370 //bool portal_1 = false; 00371 //bool portal_2 = false; 00372 cPortal * portal = NULL; 00373 cHV_Seg seg_portal; 00374 cPoint2D p1; 00375 cPoint2D p2; 00376 00377 00378 if( wall.Get_p0() != seg.Get_p0() ) // portal 1 00379 { 00380 seg_portal.Set( seg.Get_p0() ,wall.Get_p0() ); // portal entre le debut du cote et le debut du mur 00381 portal1 = Declare_Portal( area , seg_portal ); // creation ou mise a jour de ce portal 00382 //portal_1 = true; 00383 } 00384 00385 if( wall.Get_p1() != seg.Get_p1() ) // portal2 00386 { 00387 seg_portal.Set( wall.Get_p1() , seg.Get_p1() ); // portal entre la fin du mur et la fin du seg 00388 portal2 = Declare_Portal( area , seg_portal ); // creation ou mise a jour de ce portal 00389 //portal_2 = true; 00390 } 00391 00392 } 00393 00394 /*--------------------------------------------------------------------------------*/ 00395 // on va inserer les murs et portals du coté 'seg' de 'area' au jeu 00396 // on a cinq cas possible : 00397 // 1) seg entier est un portal 00398 // 2) seg entier est un mur de 'area' 00399 // 3) seg est : "MUR---PORTAL" 00400 // 4) seg est : "MUR---PORTAL---MUR" 00401 // 5) seg est : "PORTAL---MUR" 00402 /*--------------------------------------------------------------------------------*/ 00403 void cGame_World::Add_Wall_And_Portals(cSquare_Area * area , cHV_Seg& seg) 00404 { 00405 assert( area != NULL); 00406 00407 cPoint2D p_test; 00408 cHV_Seg wall; 00409 cHV_Seg wall_in_the_room; 00410 cHV_Seg seg_portal; 00411 cPortal * portal = NULL; 00412 cHV_Node * node = NULL; 00413 00414 // on teste un point de seg pour savoir si ce point est sur un divider, on prends le point milieu 00415 seg.Get_Middle(p_test); 00416 node = My_BSP.Where_Is( p_test ); 00417 00418 //si ce n'est pas une feuille, c qu'il s'agit bien d'un mur 00419 if( node->Front == NULL && node->Back==NULL) return; 00420 00421 node->Divider.Get_Wall_Seg(wall); // wall contiendra le segment du mur de ce divider 00422 00423 // si wall ne vient pas jusqu'a la piece, alors seg est un portal entier 00424 // au passage, 'inter' contient la portion de wall qui borde 'area' 00425 if( !seg.Get_Intersection(wall,wall_in_the_room) ) 00426 { 00427 seg_portal.Set( seg.Get_p0() , seg.Get_p1() ); // portal entre le debut du cote et le debut du mur 00428 portal = Declare_Portal( area , seg_portal ); // creation ou mise a jour de ce portal 00429 //area->Add_Portal(portal); 00430 return; 00431 } 00432 else 00433 { 00434 // ce mur peut-etre de taille 1 s'il est ds un coin !! 00435 // si c'est le cas, on evite de le rajouter ! 00436 // sinon on ajoute la portion de mur effective a cette piece 00437 if( wall_in_the_room.Get_p0() != wall_in_the_room.Get_p1() ) 00438 area->Add_Wall(wall_in_the_room); 00439 00440 Creates_And_Add_Portals(area,seg,wall_in_the_room); 00441 } 00442 } 00443 00444 00445 00446 /*--------------------------------------------------------------------------------------------------*/ 00447 cPortal * cGame_World::Declare_Portal( cSquare_Area * area , cHV_Seg& seg) 00448 { 00449 assert( area != NULL); 00450 00451 cPortal * portal = NULL; 00452 cPortal * current_portal = NULL; 00453 cHV_Seg inter; 00454 cHV_Seg comp0; 00455 cHV_Seg comp1; 00456 int type_inter; 00457 bool do_inter; 00458 00459 00460 // on parcours tous les portals pour chercher si le seg qu'on veut ajouter n'est pas deja un portal 00461 // ceci car il est possible que la cSquare_Area de l'autre coté de ce portal est déja ajouté 00462 // ce portal à la liste 'List_Portals' 00463 std::vector<cPortal*>::iterator Portals_Itr; 00464 for(Portals_Itr = List_Portals.begin() ; Portals_Itr != List_Portals.end() ; Portals_Itr++) 00465 { 00466 if( seg == (*Portals_Itr)->Segment ) // le portail voisin est identique, on l'identifie au nouveau 00467 { 00468 // on verifie que ce portal a un coté de non connu 00469 assert( (*Portals_Itr)->Area1 != NULL || (*Portals_Itr)->Area2 != NULL ); 00470 00471 // ce portal existe deja 00472 // on lui signale qu'il est voisin de la piece 'area' 00473 (*Portals_Itr)->Add_Area(area); 00474 area->Add_Portal((*Portals_Itr) ); 00475 return (*Portals_Itr); 00476 } 00477 else 00478 { 00479 do_inter = (*Portals_Itr)->Segment.Get_Intersection(seg,inter); 00480 if( do_inter && (inter.Get_p0() != inter.Get_p1() )) // les deux portails s'intersecte, non reduit en 1 point 00481 { 00482 current_portal = (*Portals_Itr); 00483 00484 if( inter == current_portal->Segment) // si l'inter est pas egale a l'ancien portail 00485 { 00486 //(*Portals_Itr)->Add_Area(area); //on ne fait que lui ajouter l'area 00487 } 00488 else 00489 { 00490 Split_Portal( current_portal , inter ); // sinon, il faut le diviser 00491 assert(current_portal->Segment == inter ); 00492 } 00493 00494 // on rajoute les portail du au segment 00495 type_inter = seg.Get_Complementaires(inter , comp0 , comp1); 00496 00497 switch(type_inter) 00498 { 00499 case 0: 00500 assert(0); 00501 case 1 : 00502 current_portal->Add_Area(area); 00503 area->Add_Portal(current_portal ); 00504 break; 00505 case 2: 00506 Declare_Portal( area , inter); 00507 Declare_Portal( area , comp0); 00508 Declare_Portal( area , comp1); 00509 break; 00510 case 3: 00511 Declare_Portal( area , inter); 00512 Declare_Portal( area , comp0); 00513 break; 00514 case 4: 00515 Declare_Portal( area , inter); 00516 Declare_Portal( area , comp1); 00517 break; 00518 default: 00519 assert(0); 00520 } 00521 return NULL; 00522 } 00523 } 00524 } 00525 00526 // ce portal n'existe pas, il faut le creer, l'ajouter à la liste 'List_Portals' 00527 portal = new cPortal(seg , area , N_Portals); 00528 List_Portals.push_back(portal); 00529 area->Add_Portal( portal ); 00530 N_Portals++; 00531 return portal; 00532 } 00533 00534 00535 /*--------------------------------------------------------------------------------------------------*/ 00536 void cGame_World::Split_Portal(cPortal * p , cHV_Seg& seg) 00537 { 00538 cHV_Seg comp1; 00539 cHV_Seg comp2; 00540 00541 assert( p->Segment.Contient(seg ) ); 00542 00543 cPortal * portal = NULL; 00544 int inter_type; 00545 00546 assert( p->Segment.Contient(seg) ); 00547 00548 inter_type = p->Segment.Get_Complementaires(seg , comp1 , comp2); 00549 00550 00551 switch( inter_type) 00552 { 00553 case 0: 00554 assert(0); 00555 break; 00556 case 1: 00557 assert(0); 00558 break; 00559 case 2: 00560 p->Segment.Set(seg.Get_p0() , seg.Get_p1() ); 00561 p->Segment.Get_Middle(p->Position ); 00562 //p->Add_Area(area); 00563 00564 portal = new cPortal(comp1 , p->Area1 ,N_Portals ); 00565 //portal->Add_Area(area); 00566 List_Portals.push_back(portal); 00567 N_Portals++; 00568 //area->Add_Portal( portal ); 00569 p->Area1->Add_Portal( portal ); 00570 00571 portal = new cPortal(comp2 , p->Area1 ,N_Portals ); 00572 //portal->Add_Area(area); 00573 List_Portals.push_back(portal); 00574 N_Portals++; 00575 //area->Add_Portal( portal ); 00576 p->Area1->Add_Portal( portal ); 00577 break; 00578 case 3: 00579 p->Segment.Set(seg.Get_p0() , seg.Get_p1() ); 00580 p->Segment.Get_Middle(p->Position ); 00581 portal = new cPortal(comp1 , p->Area1 ,N_Portals ); 00582 //portal->Add_Area(area); 00583 List_Portals.push_back(portal); 00584 N_Portals++; 00585 //area->Add_Portal( portal ); 00586 p->Area1->Add_Portal( portal ); 00587 break; 00588 case 4: 00589 p->Segment.Set(seg.Get_p0() , seg.Get_p1() ); 00590 p->Segment.Get_Middle(p->Position ); 00591 portal = new cPortal(comp2 , p->Area1 ,N_Portals ); 00592 //portal->Add_Area(area); 00593 List_Portals.push_back(portal); // modifie la liste des portals !!! 00594 N_Portals++; 00595 //area->Add_Portal( portal ); 00596 p->Area1->Add_Portal( portal ); 00597 break; 00598 default: 00599 assert(0); 00600 break; 00601 } 00602 00603 00604 } 00605 00606 00607 00608 /*--------------------------------------------------------------------------------------------------*/ 00609 bool cGame_World::Find_Path( cPoint2D& pA , cPoint2D& pB, std::vector<cPoint2D> & Path) 00610 { 00611 cSquare_Area * area_start = NULL; 00612 cSquare_Area * area_goal = NULL; 00613 cA_Star_Node * start_node = NULL; 00614 cA_Star_Node * goal_node = NULL; 00615 cPortal * portal = NULL; 00616 bool chemin_trouve = false; 00617 00618 cList_A_Star_Nodes voisinage; 00619 cList_A_Star_Nodes::iterator portals_itr; 00620 cList_A_Star_Nodes nodes_path; 00621 cList_A_Star_Nodes::iterator nodes_itr; 00622 cPoint2D step; 00623 00624 Path.clear(); 00625 00626 // on obtient forcement une feuille, 00627 // si le point est sur un divider, on obtient une feuille adjacente 00628 area_start = (cSquare_Area*) My_BSP.In_Which_Leaf_Is( pA ); 00629 area_goal = (cSquare_Area*) My_BSP.In_Which_Leaf_Is( pB ); 00630 00631 if( area_start == area_goal) 00632 { 00633 step.X= pB.Get_X(); 00634 step.Y= pB.Get_Y(); 00635 Path.push_back( step ); 00636 return true; 00637 } 00638 00639 start_node = new cA_Star_Point( area_start , pA ); 00640 goal_node = new cA_Star_Point( area_goal , pB ); 00641 00642 // ajout du noeud correspondant au point d'arrivée 00643 goal_node->Get_List_Neighbors(voisinage); 00644 for( portals_itr = voisinage.begin(); portals_itr != voisinage.end() ; portals_itr++) 00645 { 00646 portal = (cPortal*) (*portals_itr); 00647 portal->Add_Voisin( goal_node); 00648 } 00649 00650 // recherche du chemin 00651 chemin_trouve = Path_Finder.Find_Path( start_node , goal_node , nodes_path); 00652 if( chemin_trouve) // on transforme la liste de noeuds en chemin 00653 { 00654 for( nodes_itr = nodes_path.begin(); nodes_itr != nodes_path.end() ; nodes_itr++) 00655 { 00656 step.X= (*nodes_itr)->Position.Get_X(); 00657 step.Y= (*nodes_itr)->Position.Get_Y(); 00658 Path.push_back( step ); 00659 } 00660 } 00661 00662 // suppression du noeud correspondant au point d'arrivée 00663 goal_node->Get_List_Neighbors(voisinage); 00664 for( portals_itr = voisinage.begin(); portals_itr != voisinage.end() ; portals_itr++) 00665 { 00666 portal = (cPortal*) (*portals_itr); 00667 portal->Remove_Voisin( goal_node); 00668 } 00669 00670 delete(start_node); 00671 delete(goal_node); 00672 00673 return chemin_trouve; 00674 } 00675 00676 00677 00678 /*--------------------------------------------------------------------------------------------------*/ 00679 bool cGame_World::Do_Ball_Intersect_Walls( int x, int y, int r) 00680 { 00681 cSquare_Area *leaf = NULL; 00682 cPoint2D p(x,y); 00683 00684 leaf = (cSquare_Area*) My_BSP.In_Which_Leaf_Is( p ); 00685 00686 std::vector<cHV_Seg*>::iterator walls_itr; 00687 for(walls_itr = leaf->List_Walls.begin() ; walls_itr != leaf->List_Walls.end() ; walls_itr++) 00688 { 00689 if( (*walls_itr)->Get_Square_Distance_From_Point(p ) < r*r) 00690 return true; 00691 } 00692 00693 00694 return false; 00695 } 00696 00697 00698 /*--------------------------------------------------------------------------------------------------*/ 00699 bool cGame_World::Do_Segment_Intersect_Walls(cSeg& seg, cPoint2D& p_result) 00700 { 00701 return Do_Segment_Intersect_Walls(seg,p_result,seg.Get_Square_Length() ); 00702 } 00703 00704 00705 00706 /*--------------------------------------------------------------------------------------------------*/ 00707 bool cGame_World::Do_Segment_Intersect_Walls(cSeg& seg, cPoint2D& p_result, int square_test_range) 00708 { 00709 cPoint2D p; 00710 cPoint2D p_bis; 00711 cPoint2D p0; 00712 cPoint2D p1; 00713 cHV_Seg hv_seg; 00714 cIncremental_Bresenham bresenham; 00715 bool arrived = false; 00716 cHV_Node * node = NULL; 00717 int current_square_length = 0; 00718 int n_test = 0; 00719 00720 p0.X = seg.Get_p0().Get_X(); 00721 p0.Y = seg.Get_p0().Get_Y(); 00722 00723 p1.X = seg.Get_p1().Get_X(); 00724 p1.Y = seg.Get_p1().Get_Y(); 00725 00726 // si les deux points sont ds la meme area, ils se voient forcement 00727 // car les area sont convexees 00728 if( (cSquare_Area*) My_BSP.In_Which_Leaf_Is( seg.Get_p0() ) == (cSquare_Area*) My_BSP.In_Which_Leaf_Is( seg.Get_p1() ) ) 00729 return false; 00730 00731 // si le segment est de longeur nulle, il n'intesecte rien 00732 if( seg.Get_p0() == seg.Get_p1() ) 00733 return false; 00734 00735 bresenham.Reset(p0 , p1 ); 00736 p = seg.Get_p0(); 00737 while(!arrived && current_square_length<square_test_range) 00738 { 00739 p_bis.X = p.Get_X(); 00740 p_bis.Y = p.Get_Y(); 00741 arrived = bresenham.Step(p_bis); 00742 p = p_bis; 00743 current_square_length = (p.Get_X() - p0.X)*(p.Get_X() - p0.X) + (p.Get_Y() - p0.Y)*(p.Get_Y() - p0.Y); 00744 00745 n_test++; 00746 node = My_BSP.Where_Is( p ); 00747 if( node->Front != NULL && node->Back != NULL) // on est sur un noeud qui divise le world, et pas sur une feuille 00748 { 00749 hv_seg.Set( node->Divider.p0 , node->Divider.p1); 00750 if( hv_seg.Contient_Point(p) ) 00751 { 00752 p_result = p; 00753 return true; 00754 } 00755 } 00756 } 00757 00758 return false; // on a pas trouvé d'intersections 00759 } 00760 00761 00762 00763 /*--------------------------------------------------------------------------------------------------*/ 00764 void cGame_World::Decorate() 00765 { 00766 Decorate_With_Areas(); 00767 Decorate_With_Walls_And_Portals(); 00768 Manage_Paralell_Portals(); 00769 }

Generated on Fri May 21 19:22:36 2004 for LIBELL by doxygen 1.3.7