src/game/WaypointMovementGenerator.cpp

   1 /*
   2  * Copyright (C) 2005-2008 MaNGOS <http://getmangos.com/>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 /*
  20 creature_movement Table
  21
  22 alter table creature_movement add `textid1` int(11) NOT NULL default '0';
  23 alter table creature_movement add `textid2` int(11) NOT NULL default '0';
  24 alter table creature_movement add `textid3` int(11) NOT NULL default '0';
  25 alter table creature_movement add `textid4` int(11) NOT NULL default '0';
  26 alter table creature_movement add `textid5` int(11) NOT NULL default '0';
  27 alter table creature_movement add `emote` int(10) unsigned default '0';
  28 alter table creature_movement add `spell` int(5) unsigned default '0';
  29 alter table creature_movement add `wpguid` int(11) default '0';
  30
  31 */
  32
  33 #include <ctime>
  34
  35 #include "WaypointMovementGenerator.h"
  36 #include "ObjectMgr.h"
  37 #include "Creature.h"
  38 #include "DestinationHolderImp.h"
  39 #include "CreatureAI.h"
  40 #include "WaypointManager.h"
  41
  42 #include <cassert>
  43
  44 //-----------------------------------------------//
  45 void WaypointMovementGenerator<Creature>::LoadPath(Creature &c)
  46 {
  47     sLog.outDetail("LoadPath: loading waypoint path for creature %d,%d", c.GetGUIDLow(), c.GetDBTableGUIDLow());
  48
  49     i_path = WaypointMgr.GetPath(c.GetDBTableGUIDLow());
  50     if(!i_path)
  51     {
  52         sLog.outErrorDb("WaypointMovementGenerator::LoadPath: creature %s (Entry: %u GUID: %d) doesn't have waypoint path",
  53             c.GetName(), c.GetEntry(), c.GetDBTableGUIDLow());
  54         return;
  55     }
  56
  57     uint32 node_count = i_path->size();
  58     i_hasDone.resize(node_count);
  59     for(uint32 i = 0; i < node_count-1; i++)
  60         i_hasDone[i] = false;
  61
  62     // to prevent a misbehavior inside "update"
  63     // update is always called with the next wp - but the wpSys needs the current
  64     // so when the routine is called the first time, wpSys gets the last waypoint
  65     // and this prevents the system from performing text/emote, etc
  66     i_hasDone[node_count - 1] = true;
  67 }
  68
  69 void WaypointMovementGenerator<Creature>::ClearWaypoints()
  70 {
  71     i_path = NULL;
  72 }
  73
  74 void WaypointMovementGenerator<Creature>::Initialize()
  75 {
  76 }
  77
  78 bool WaypointMovementGenerator<Creature>::Update(Creature &creature, const uint32 &diff)
  79 {
  80     if(!&creature)
  81         return true;
  82
  83     // Waypoint movement can be switched on/off
  84     // This is quite handy for escort quests and other stuff
  85     if(creature.hasUnitState(UNIT_STAT_ROOT | UNIT_STAT_STUNNED | UNIT_STAT_DISTRACTED))
  86         return true;
  87
  88     // prevent a crash at empty waypoint path.
  89     if(!i_path || i_path->empty())
  90         return true;
  91
  92     // i_path was modified by chat commands for example
  93     if(i_path->size() != i_hasDone.size())
  94         i_hasDone.resize(i_path->size());
  95     if(i_currentNode >= i_path->size())
  96         i_currentNode = 0;
  97
  98     CreatureTraveller traveller(creature);
  99
 100     i_nextMoveTime.Update(diff);
 101     i_destinationHolder.UpdateTraveller(traveller, diff, false, true);
 102
 103     // creature has been stopped in middle of the waypoint segment
 104     if (!i_destinationHolder.HasArrived() && creature.IsStopped())
 105     {
 106         if( i_nextMoveTime.Passed()) // Timer has elapsed, meaning this part controlled it
 107         {
 108             SetStopedByPlayer(false);
 109             // Now we re-set destination to same node and start travel
 110             creature.addUnitState(UNIT_STAT_ROAMING);
 111             if (creature.canFly())
 112                 creature.AddUnitMovementFlag(MOVEMENTFLAG_FLYING2);
 113             const WaypointNode &node = i_path->at(i_currentNode);
 114             i_destinationHolder.SetDestination(traveller, node.x, node.y, node.z);
 115             i_nextMoveTime.Reset(i_destinationHolder.GetTotalTravelTime());
 116         }
 117         else // if( !i_nextMoveTime.Passed())
 118         { // unexpected end of timer && creature stopped && not at end of segment
 119             if (!IsStopedByPlayer())
 120             {                                                   // Put 30 seconds delay
 121                 i_destinationHolder.IncreaseTravelTime(STOP_TIME_FOR_PLAYER);
 122                 i_nextMoveTime.Reset(STOP_TIME_FOR_PLAYER);
 123                 SetStopedByPlayer(true);                        // Mark we did it
 124             }
 125         }
 126         return true;    // Abort here this update
 127     }
 128
 129     if( creature.IsStopped())
 130     {
 131         uint32 idx = i_currentNode > 0 ? i_currentNode-1 : i_path->size()-1;
 132
 133         if (!i_hasDone[idx])
 134         {
 135             if (i_path->at(idx).orientation !=100)
 136                 creature.SetOrientation(i_path->at(idx).orientation);
 137
 138             if(WaypointBehavior *behavior = i_path->at(idx).behavior)
 139             {
 140                 if(behavior->emote != 0)
 141                     creature.SetUInt32Value(UNIT_NPC_EMOTESTATE,behavior->emote);
 142                 if(behavior->spell != 0)
 143                     creature.CastSpell(&creature,behavior->spell, false);
 144                 if(behavior->model1 != 0)
 145                     creature.SetDisplayId(behavior->model1);
 146                 if(behavior->textid[0])
 147                 {
 148                     // Not only one text is set
 149                     if( behavior->textid[1] )
 150                     {
 151                         // Select one from max 5 texts (0 and 1 laready checked)
 152                         int i = 2;
 153                         for( ; i < MAX_WAYPOINT_TEXT; ++i )
 154                             if( !behavior->textid[i] )
 155                                 break;
 156
 157                         creature.Say(behavior->textid[rand() % i], 0, 0);
 158                     }
 159                     else
 160                         creature.Say(behavior->textid[0], 0, 0);
 161                 }
 162
 163                 i_hasDone[idx] = true;
 164                 MovementInform(creature);
 165             }                                               // wpBehaviour found
 166         }                                                   // HasDone == false
 167     }                                                       // i_creature.IsStopped()
 168
 169     if( i_nextMoveTime.Passed() ) // This is at the end of waypoint segment or has been stopped by player
 170     {
 171         if( creature.IsStopped() ) // If stopped then begin a new move segment
 172         {
 173             creature.addUnitState(UNIT_STAT_ROAMING);
 174             if (creature.canFly())
 175                 creature.AddUnitMovementFlag(MOVEMENTFLAG_FLYING2);
 176             const WaypointNode &node = i_path->at(i_currentNode);
 177             i_destinationHolder.SetDestination(traveller, node.x, node.y, node.z);
 178             i_nextMoveTime.Reset(i_destinationHolder.GetTotalTravelTime());
 179             uint32 idx = i_currentNode > 0 ? i_currentNode-1 : i_path->size()-1;
 180
 181             if (i_path->at(idx).orientation !=100)
 182                 creature.SetOrientation(i_path->at(idx).orientation);
 183
 184             if(WaypointBehavior *behavior = i_path->at(idx).behavior )
 185             {
 186                 i_hasDone[idx] = false;
 187                 if(behavior->model2 != 0)
 188                     creature.SetDisplayId(behavior->model2);
 189
 190                 creature.SetUInt32Value(UNIT_NPC_EMOTESTATE, 0);
 191             }
 192         }
 193         else // If not stopped then stop it and set the reset of TimeTracker to waittime
 194         {
 195             creature.StopMoving();
 196             SetStopedByPlayer(false);
 197             i_nextMoveTime.Reset(i_path->at(i_currentNode).delay);
 198             ++i_currentNode;
 199             if( i_currentNode >= i_path->size() )
 200                 i_currentNode = 0;
 201         }
 202     }
 203     return true;
 204 }
 205
 206 void WaypointMovementGenerator<Creature>::MovementInform(Creature &unit)
 207 {
 208     if(unit.AI())
 209         unit.AI()->MovementInform(WAYPOINT_MOTION_TYPE, i_currentNode);
 210 }
 211
 212 //----------------------------------------------------//
 213 void FlightPathMovementGenerator::LoadPath(Player &)
 214 {
 215     objmgr.GetTaxiPathNodes(i_pathId, i_path,i_mapIds);
 216 }
 217
 218 uint32 FlightPathMovementGenerator::GetPathAtMapEnd() const
 219 {
 220     if(i_currentNode >= i_mapIds.size())
 221         return i_mapIds.size();
 222
 223     uint32 curMapId = i_mapIds[i_currentNode];
 224     for(uint32 i = i_currentNode; i < i_mapIds.size(); ++i)
 225     {
 226         if(i_mapIds[i] != curMapId)
 227             return i;
 228     }
 229
 230     return i_mapIds.size();
 231 }
 232
 233 void FlightPathMovementGenerator::Initialize(Player &player)
 234 {
 235     player.getHostilRefManager().setOnlineOfflineState(false);
 236     player.addUnitState(UNIT_STAT_IN_FLIGHT);
 237     player.SetFlag(UNIT_FIELD_FLAGS,UNIT_FLAG_DISABLE_MOVE | UNIT_FLAG_TAXI_FLIGHT);
 238     LoadPath(player);
 239     Traveller<Player> traveller(player);
 240     // do not send movement, it was sent already
 241     i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z, false);
 242
 243     player.SendMonsterMoveByPath(GetPath(),GetCurrentNode(),GetPathAtMapEnd(),MOVEMENTFLAG_WALK_MODE|MOVEMENTFLAG_ONTRANSPORT);
 244 }
 245
 246 void FlightPathMovementGenerator::Finalize(Player & player)
 247 {
 248     float x, y, z;
 249     i_destinationHolder.GetLocationNow(player.GetMapId(), x, y, z);
 250     player.SetPosition(x, y, z, player.GetOrientation());
 251
 252     player.clearUnitState(UNIT_STAT_IN_FLIGHT);
 253     player.Unmount();
 254     player.RemoveFlag(UNIT_FIELD_FLAGS,UNIT_FLAG_DISABLE_MOVE | UNIT_FLAG_TAXI_FLIGHT);
 255
 256     if(player.m_taxi.empty())
 257     {
 258         player.getHostilRefManager().setOnlineOfflineState(true);
 259         if(player.pvpInfo.inHostileArea)
 260             player.CastSpell(&player, 2479, true);
 261
 262         player.SetUnitMovementFlags(MOVEMENTFLAG_WALK_MODE);
 263         player.StopMoving();
 264     }
 265 }
 266
 267 bool FlightPathMovementGenerator::Update(Player &player, const uint32 &diff)
 268 {
 269     if( MovementInProgress() )
 270     {
 271         Traveller<Player> traveller(player);
 272         if( i_destinationHolder.UpdateTraveller(traveller, diff, false) )
 273         {
 274             i_destinationHolder.ResetUpdate(FLIGHT_TRAVEL_UPDATE);
 275             if( i_destinationHolder.HasArrived() )
 276             {
 277                 uint32 curMap = i_mapIds[i_currentNode];
 278                 ++i_currentNode;
 279                 if( MovementInProgress() )
 280                 {
 281                     DEBUG_LOG("loading node %u for player %s", i_currentNode, player.GetName());
 282                     if(i_mapIds[i_currentNode]==curMap)
 283                     {
 284                         // do not send movement, it was sent already
 285                         i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z, false);
 286                     }
 287                     return true;
 288                 }
 289                 //else HasArrived()
 290             }
 291             else
 292                 return true;
 293         }
 294         else
 295             return true;
 296     }
 297
 298     // we have arrived at the end of the path
 299     return false;
 300 }
 301
 302 void FlightPathMovementGenerator::SetCurrentNodeAfterTeleport()
 303 {
 304     if(i_mapIds.empty())
 305         return;
 306
 307     uint32 map0 = i_mapIds[0];
 308     for(int i = 1; i < i_mapIds.size(); ++i)
 309     {
 310         if(i_mapIds[i]!=map0)
 311         {
 312             i_currentNode = i;
 313             return;
 314         }
 315     }
 316 }
 317
 318 //
 319 // Unique1's ASTAR Pathfinding Code... For future use & reference...
 320 //
 321
 322 #ifdef __PATHFINDING__
 323
 324 int GetFCost(int to, int num, int parentNum, float *gcost); // Below...
 325
 326 int ShortenASTARRoute(short int *pathlist, int number)
 327 {                                                           // Wrote this to make the routes a little smarter (shorter)... No point looping back to the same places... Unique1
 328     short int temppathlist[MAX_PATHLIST_NODES];
 329     int count = 0;
 330     //    int count2 = 0;
 331     int temp, temp2;
 332     int link;
 333     int upto = 0;
 334
 335     for (temp = number; temp >= 0; temp--)
 336     {
 337         qboolean shortened = qfalse;
 338
 339         for (temp2 = 0; temp2 < temp; temp2++)
 340         {
 341             for (link = 0; link < nodes[pathlist[temp]].enodenum; link++)
 342             {
 343                 if (nodes[pathlist[temp]].links[link].flags & PATH_BLOCKED)
 344                     continue;
 345
 346                 //if ((bot->client->ps.eFlags & EF_TANK) && nodes[bot->current_node].links[link].flags & PATH_NOTANKS)    //if this path is blocked, skip it
 347                 //    continue;
 348
 349                 //if (nodes[nodes[pathlist[temp]].links[link].targetNode].origin[2] > nodes[pathlist[temp]].origin[2] + 32)
 350                 //    continue;
 351
 352                 if (nodes[pathlist[temp]].links[link].targetNode == pathlist[temp2])
 353                 {                                           // Found a shorter route...
 354                     //if (OrgVisible(nodes[pathlist[temp2]].origin, nodes[pathlist[temp]].origin, -1))
 355                     {
 356                         temppathlist[count] = pathlist[temp2];
 357                         temp = temp2;
 358                         ++count;
 359                         shortened = qtrue;
 360                     }
 361                 }
 362             }
 363         }
 364
 365         if (!shortened)
 366         {
 367             temppathlist[count] = pathlist[temp];
 368             ++count;
 369         }
 370     }
 371
 372     upto = count;
 373
 374     for (temp = 0; temp < count; temp++)
 375     {
 376         pathlist[temp] = temppathlist[upto];
 377         --upto;
 378     }
 379
 380     G_Printf("ShortenASTARRoute: Path size reduced from %i to %i nodes...n", number, count);
 381     return count;
 382 }
 383
 384 /*
 385 ===========================================================================
 386 CreatePathAStar
 387 This function uses the A* pathfinding algorithm to determine the
 388 shortest path between any two nodes.
 389 It's fairly complex, so I'm not really going to explain it much.
 390 Look up A* and binary heaps for more info.
 391 pathlist stores the ideal path between the nodes, in reverse order,
 392 and the return value is the number of nodes in that path
 393 ===========================================================================
 394 */
 395 int CreatePathAStar(gentity_t *bot, int from, int to, short int *pathlist)
 396 {
 397     //all the data we have to hold...since we can't do dynamic allocation, has to be MAX_NODES
 398     //we can probably lower this later - eg, the open list should never have more than at most a few dozen items on it
 399     short int openlist[MAX_NODES+1];                        //add 1 because it's a binary heap, and they don't use 0 - 1 is the first used index
 400     float gcost[MAX_NODES];
 401     int fcost[MAX_NODES];
 402     char list[MAX_NODES];                                   //0 is neither, 1 is open, 2 is closed - char because it's the smallest data type
 403     short int parent[MAX_NODES];
 404
 405     short int numOpen = 0;
 406     short int atNode, temp, newnode=-1;
 407     qboolean found = qfalse;
 408     int count = -1;
 409     float gc;
 410     int i, u, v, m;
 411     vec3_t vec;
 412
 413     //clear out all the arrays
 414     memset(openlist, 0, sizeof(short int)*(MAX_NODES+1));
 415     memset(fcost, 0, sizeof(int)*MAX_NODES);
 416     memset(list, 0, sizeof(char)*MAX_NODES);
 417     memset(parent, 0, sizeof(short int)*MAX_NODES);
 418     memset(gcost, -1, sizeof(float)*MAX_NODES);
 419
 420     //make sure we have valid data before calculating everything
 421     if ((from == NODE_INVALID) || (to == NODE_INVALID) || (from >= MAX_NODES) || (to >= MAX_NODES) || (from == to))
 422         return -1;
 423
 424     openlist[1] = from;                                     //add the starting node to the open list
 425     ++numOpen;
 426     gcost[from] = 0;                                        //its f and g costs are obviously 0
 427     fcost[from] = 0;
 428
 429     while (1)
 430     {
 431         if (numOpen != 0)                                   //if there are still items in the open list
 432         {
 433             //pop the top item off of the list
 434             atNode = openlist[1];
 435             list[atNode] = 2;                               //put the node on the closed list so we don't check it again
 436             --numOpen;
 437
 438             openlist[1] = openlist[numOpen+1];              //move the last item in the list to the top position
 439             v = 1;
 440
 441             //this while loop reorders the list so that the new lowest fcost is at the top again
 442             while (1)
 443             {
 444                 u = v;
 445                 if ((2*u+1) < numOpen)                      //if both children exist
 446                 {
 447                     if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 448                         v = 2*u;
 449                     if (fcost[openlist[v]] >= fcost[openlist[2*u+1]])
 450                         v = 2*u+1;
 451                 }
 452                 else
 453                 {
 454                     if ((2*u) < numOpen)                    //if only one child exists
 455                     {
 456                         if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 457                             v = 2*u;
 458                     }
 459                 }
 460
 461                 if (u != v)                                 //if they're out of order, swap this item with its parent
 462                 {
 463                     temp = openlist[u];
 464                     openlist[u] = openlist[v];
 465                     openlist[v] = temp;
 466                 }
 467                 else
 468                     break;
 469             }
 470
 471             for (i = 0; i < nodes[atNode].enodenum; i++)    //loop through all the links for this node
 472             {
 473                 newnode = nodes[atNode].links[i].targetNode;
 474
 475                 //if this path is blocked, skip it
 476                 if (nodes[atNode].links[i].flags & PATH_BLOCKED)
 477                     continue;
 478                 //if this path is blocked, skip it
 479                 if (bot->client && (bot->client->ps.eFlags & EF_TANK) && nodes[atNode].links[i].flags & PATH_NOTANKS)
 480                     continue;
 481                 //skip any unreachable nodes
 482                 if (bot->client && (nodes[newnode].type & NODE_ALLY_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_ALLIES))
 483                     continue;
 484                 if (bot->client && (nodes[newnode].type & NODE_AXIS_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_AXIS))
 485                     continue;
 486
 487                 if (list[newnode] == 2)                     //if this node is on the closed list, skip it
 488                     continue;
 489
 490                 if (list[newnode] != 1)                     //if this node is not already on the open list
 491                 {
 492                     openlist[++numOpen] = newnode;          //add the new node to the open list
 493                     list[newnode] = 1;
 494                     parent[newnode] = atNode;               //record the node's parent
 495
 496                     if (newnode == to)                      //if we've found the goal, don't keep computing paths!
 497                         break;                              //this will break the 'for' and go all the way to 'if (list[to] == 1)'
 498
 499                     //store it's f cost value
 500                     fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 501
 502                     //this loop re-orders the heap so that the lowest fcost is at the top
 503                     m = numOpen;
 504                     while (m != 1)                          //while this item isn't at the top of the heap already
 505                     {
 506                         //if it has a lower fcost than its parent
 507                         if (fcost[openlist[m]] <= fcost[openlist[m/2]])
 508                         {
 509                             temp = openlist[m/2];
 510                             openlist[m/2] = openlist[m];
 511                             openlist[m] = temp;             //swap them
 512                             m /= 2;
 513                         }
 514                         else
 515                             break;
 516                     }
 517                 }
 518                 else                                        //if this node is already on the open list
 519                 {
 520                     gc = gcost[atNode];
 521                     VectorSubtract(nodes[newnode].origin, nodes[atNode].origin, vec);
 522                     gc += VectorLength(vec);                //calculate what the gcost would be if we reached this node along the current path
 523
 524                     if (gc < gcost[newnode])                //if the new gcost is less (ie, this path is shorter than what we had before)
 525                     {
 526                         parent[newnode] = atNode;           //set the new parent for this node
 527                         gcost[newnode] = gc;                //and the new g cost
 528
 529                         for (i = 1; i < numOpen; i++)       //loop through all the items on the open list
 530                         {
 531                             if (openlist[i] == newnode)     //find this node in the list
 532                             {
 533                                 //calculate the new fcost and store it
 534                                 fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 535
 536                                 //reorder the list again, with the lowest fcost item on top
 537                                 m = i;
 538                                 while (m != 1)
 539                                 {
 540                                     //if the item has a lower fcost than it's parent
 541                                     if (fcost[openlist[m]] < fcost[openlist[m/2]])
 542                                     {
 543                                         temp = openlist[m/2];
 544                                         openlist[m/2] = openlist[m];
 545                                         openlist[m] = temp; //swap them
 546                                         m /= 2;
 547                                     }
 548                                     else
 549                                         break;
 550                                 }
 551                                 break;                      //exit the 'for' loop because we already changed this node
 552                             }                               //if
 553                         }                                   //for
 554                     }                                       //if (gc < gcost[newnode])
 555                 }                                           //if (list[newnode] != 1) --> else
 556             }                                               //for (loop through links)
 557         }                                                   //if (numOpen != 0)
 558         else
 559         {
 560             found = qfalse;                                 //there is no path between these nodes
 561             break;
 562         }
 563
 564         if (list[to] == 1)                                  //if the destination node is on the open list, we're done
 565         {
 566             found = qtrue;
 567             break;
 568         }
 569     }                                                       //while (1)
 570
 571     if (found == qtrue)                                     //if we found a path
 572     {
 573         //G_Printf("%s - path found!n", bot->client->pers.netname);
 574         count = 0;
 575
 576         temp = to;                                          //start at the end point
 577         while (temp != from)                                //travel along the path (backwards) until we reach the starting point
 578         {
 579             pathlist[count++] = temp;                       //add the node to the pathlist and increment the count
 580             temp = parent[temp];                            //move to the parent of this node to continue the path
 581         }
 582
 583         pathlist[count++] = from;                           //add the beginning node to the end of the pathlist
 584
 585         #ifdef __BOT_SHORTEN_ROUTING__
 586         count = ShortenASTARRoute(pathlist, count);         // This isn't working... Dunno why.. Unique1
 587         #endif                                              //__BOT_SHORTEN_ROUTING__
 588     }
 589     else
 590     {
 591         //G_Printf("^1*** ^4BOT DEBUG^5: (CreatePathAStar) There is no route between node ^7%i^5 and node ^7%i^5.n", from, to);
 592         count = CreateDumbRoute(from, to, pathlist);
 593
 594         if (count > 0)
 595         {
 596             #ifdef __BOT_SHORTEN_ROUTING__
 597             count = ShortenASTARRoute(pathlist, count);     // This isn't working... Dunno why.. Unique1
 598             #endif                                          //__BOT_SHORTEN_ROUTING__
 599             return count;
 600         }
 601     }
 602
 603     return count;                                           //return the number of nodes in the path, -1 if not found
 604 }
 605
 606 /*
 607 ===========================================================================
 608 GetFCost
 609 Utility function used by A* pathfinding to calculate the
 610 cost to move between nodes towards a goal.  Using the A*
 611 algorithm F = G + H, G here is the distance along the node
 612 paths the bot must travel, and H is the straight-line distance
 613 to the goal node.
 614 Returned as an int because more precision is unnecessary and it
 615 will slightly speed up heap access
 616 ===========================================================================
 617 */
 618 int GetFCost(int to, int num, int parentNum, float *gcost)
 619 {
 620     float gc = 0;
 621     float hc = 0;
 622     vec3_t v;
 623
 624     if (gcost[num] == -1)
 625     {
 626         if (parentNum != -1)
 627         {
 628             gc = gcost[parentNum];
 629             VectorSubtract(nodes[num].origin, nodes[parentNum].origin, v);
 630             gc += VectorLength(v);
 631         }
 632         gcost[num] = gc;
 633     }
 634     else
 635         gc = gcost[num];
 636
 637     VectorSubtract(nodes[to].origin, nodes[num].origin, v);
 638     hc = VectorLength(v);
 639
 640     return (int)(gc + hc);
 641 }
 642 #endif                                                      //__PATHFINDING__