src/game/WaypointMovementGenerator.cpp

   1 /*
   2  * Copyright (C) 2005-2009 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     // remove flag to prevent send object build movement packets for flight state and crash (movement generator already not at top of stack)
 249     player.clearUnitState(UNIT_STAT_IN_FLIGHT);
 250
 251     float x, y, z;
 252     i_destinationHolder.GetLocationNow(player.GetMapId(), x, y, z);
 253     player.SetPosition(x, y, z, player.GetOrientation());
 254
 255     player.Unmount();
 256     player.RemoveFlag(UNIT_FIELD_FLAGS,UNIT_FLAG_DISABLE_MOVE | UNIT_FLAG_TAXI_FLIGHT);
 257
 258     if(player.m_taxi.empty())
 259     {
 260         player.getHostilRefManager().setOnlineOfflineState(true);
 261         if(player.pvpInfo.inHostileArea)
 262             player.CastSpell(&player, 2479, true);
 263
 264         player.SetUnitMovementFlags(MOVEMENTFLAG_WALK_MODE);
 265         player.StopMoving();
 266     }
 267 }
 268
 269 bool FlightPathMovementGenerator::Update(Player &player, const uint32 &diff)
 270 {
 271     if( MovementInProgress() )
 272     {
 273         Traveller<Player> traveller(player);
 274         if( i_destinationHolder.UpdateTraveller(traveller, diff, false) )
 275         {
 276             i_destinationHolder.ResetUpdate(FLIGHT_TRAVEL_UPDATE);
 277             if( i_destinationHolder.HasArrived() )
 278             {
 279                 uint32 curMap = i_mapIds[i_currentNode];
 280                 ++i_currentNode;
 281                 if( MovementInProgress() )
 282                 {
 283                     DEBUG_LOG("loading node %u for player %s", i_currentNode, player.GetName());
 284                     if(i_mapIds[i_currentNode]==curMap)
 285                     {
 286                         // do not send movement, it was sent already
 287                         i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z, false);
 288                     }
 289                     return true;
 290                 }
 291                 //else HasArrived()
 292             }
 293             else
 294                 return true;
 295         }
 296         else
 297             return true;
 298     }
 299
 300     // we have arrived at the end of the path
 301     return false;
 302 }
 303
 304 void FlightPathMovementGenerator::SetCurrentNodeAfterTeleport()
 305 {
 306     if(i_mapIds.empty())
 307         return;
 308
 309     uint32 map0 = i_mapIds[0];
 310     for(int i = 1; i < i_mapIds.size(); ++i)
 311     {
 312         if(i_mapIds[i]!=map0)
 313         {
 314             i_currentNode = i;
 315             return;
 316         }
 317     }
 318 }
 319
 320 //
 321 // Unique1's ASTAR Pathfinding Code... For future use & reference...
 322 //
 323
 324 #ifdef __PATHFINDING__
 325
 326 int GetFCost(int to, int num, int parentNum, float *gcost); // Below...
 327
 328 int ShortenASTARRoute(short int *pathlist, int number)
 329 {                                                           // Wrote this to make the routes a little smarter (shorter)... No point looping back to the same places... Unique1
 330     short int temppathlist[MAX_PATHLIST_NODES];
 331     int count = 0;
 332     //    int count2 = 0;
 333     int temp, temp2;
 334     int link;
 335     int upto = 0;
 336
 337     for (temp = number; temp >= 0; temp--)
 338     {
 339         qboolean shortened = qfalse;
 340
 341         for (temp2 = 0; temp2 < temp; temp2++)
 342         {
 343             for (link = 0; link < nodes[pathlist[temp]].enodenum; link++)
 344             {
 345                 if (nodes[pathlist[temp]].links[link].flags & PATH_BLOCKED)
 346                     continue;
 347
 348                 //if ((bot->client->ps.eFlags & EF_TANK) && nodes[bot->current_node].links[link].flags & PATH_NOTANKS)    //if this path is blocked, skip it
 349                 //    continue;
 350
 351                 //if (nodes[nodes[pathlist[temp]].links[link].targetNode].origin[2] > nodes[pathlist[temp]].origin[2] + 32)
 352                 //    continue;
 353
 354                 if (nodes[pathlist[temp]].links[link].targetNode == pathlist[temp2])
 355                 {                                           // Found a shorter route...
 356                     //if (OrgVisible(nodes[pathlist[temp2]].origin, nodes[pathlist[temp]].origin, -1))
 357                     {
 358                         temppathlist[count] = pathlist[temp2];
 359                         temp = temp2;
 360                         ++count;
 361                         shortened = qtrue;
 362                     }
 363                 }
 364             }
 365         }
 366
 367         if (!shortened)
 368         {
 369             temppathlist[count] = pathlist[temp];
 370             ++count;
 371         }
 372     }
 373
 374     upto = count;
 375
 376     for (temp = 0; temp < count; temp++)
 377     {
 378         pathlist[temp] = temppathlist[upto];
 379         --upto;
 380     }
 381
 382     G_Printf("ShortenASTARRoute: Path size reduced from %i to %i nodes...n", number, count);
 383     return count;
 384 }
 385
 386 /*
 387 ===========================================================================
 388 CreatePathAStar
 389 This function uses the A* pathfinding algorithm to determine the
 390 shortest path between any two nodes.
 391 It's fairly complex, so I'm not really going to explain it much.
 392 Look up A* and binary heaps for more info.
 393 pathlist stores the ideal path between the nodes, in reverse order,
 394 and the return value is the number of nodes in that path
 395 ===========================================================================
 396 */
 397 int CreatePathAStar(gentity_t *bot, int from, int to, short int *pathlist)
 398 {
 399     //all the data we have to hold...since we can't do dynamic allocation, has to be MAX_NODES
 400     //we can probably lower this later - eg, the open list should never have more than at most a few dozen items on it
 401     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
 402     float gcost[MAX_NODES];
 403     int fcost[MAX_NODES];
 404     char list[MAX_NODES];                                   //0 is neither, 1 is open, 2 is closed - char because it's the smallest data type
 405     short int parent[MAX_NODES];
 406
 407     short int numOpen = 0;
 408     short int atNode, temp, newnode=-1;
 409     qboolean found = qfalse;
 410     int count = -1;
 411     float gc;
 412     int i, u, v, m;
 413     vec3_t vec;
 414
 415     //clear out all the arrays
 416     memset(openlist, 0, sizeof(short int)*(MAX_NODES+1));
 417     memset(fcost, 0, sizeof(int)*MAX_NODES);
 418     memset(list, 0, sizeof(char)*MAX_NODES);
 419     memset(parent, 0, sizeof(short int)*MAX_NODES);
 420     memset(gcost, -1, sizeof(float)*MAX_NODES);
 421
 422     //make sure we have valid data before calculating everything
 423     if ((from == NODE_INVALID) || (to == NODE_INVALID) || (from >= MAX_NODES) || (to >= MAX_NODES) || (from == to))
 424         return -1;
 425
 426     openlist[1] = from;                                     //add the starting node to the open list
 427     ++numOpen;
 428     gcost[from] = 0;                                        //its f and g costs are obviously 0
 429     fcost[from] = 0;
 430
 431     while (1)
 432     {
 433         if (numOpen != 0)                                   //if there are still items in the open list
 434         {
 435             //pop the top item off of the list
 436             atNode = openlist[1];
 437             list[atNode] = 2;                               //put the node on the closed list so we don't check it again
 438             --numOpen;
 439
 440             openlist[1] = openlist[numOpen+1];              //move the last item in the list to the top position
 441             v = 1;
 442
 443             //this while loop reorders the list so that the new lowest fcost is at the top again
 444             while (1)
 445             {
 446                 u = v;
 447                 if ((2*u+1) < numOpen)                      //if both children exist
 448                 {
 449                     if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 450                         v = 2*u;
 451                     if (fcost[openlist[v]] >= fcost[openlist[2*u+1]])
 452                         v = 2*u+1;
 453                 }
 454                 else
 455                 {
 456                     if ((2*u) < numOpen)                    //if only one child exists
 457                     {
 458                         if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 459                             v = 2*u;
 460                     }
 461                 }
 462
 463                 if (u != v)                                 //if they're out of order, swap this item with its parent
 464                 {
 465                     temp = openlist[u];
 466                     openlist[u] = openlist[v];
 467                     openlist[v] = temp;
 468                 }
 469                 else
 470                     break;
 471             }
 472
 473             for (i = 0; i < nodes[atNode].enodenum; ++i)    //loop through all the links for this node
 474             {
 475                 newnode = nodes[atNode].links[i].targetNode;
 476
 477                 //if this path is blocked, skip it
 478                 if (nodes[atNode].links[i].flags & PATH_BLOCKED)
 479                     continue;
 480                 //if this path is blocked, skip it
 481                 if (bot->client && (bot->client->ps.eFlags & EF_TANK) && nodes[atNode].links[i].flags & PATH_NOTANKS)
 482                     continue;
 483                 //skip any unreachable nodes
 484                 if (bot->client && (nodes[newnode].type & NODE_ALLY_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_ALLIES))
 485                     continue;
 486                 if (bot->client && (nodes[newnode].type & NODE_AXIS_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_AXIS))
 487                     continue;
 488
 489                 if (list[newnode] == 2)                     //if this node is on the closed list, skip it
 490                     continue;
 491
 492                 if (list[newnode] != 1)                     //if this node is not already on the open list
 493                 {
 494                     openlist[++numOpen] = newnode;          //add the new node to the open list
 495                     list[newnode] = 1;
 496                     parent[newnode] = atNode;               //record the node's parent
 497
 498                     if (newnode == to)                      //if we've found the goal, don't keep computing paths!
 499                         break;                              //this will break the 'for' and go all the way to 'if (list[to] == 1)'
 500
 501                     //store it's f cost value
 502                     fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 503
 504                     //this loop re-orders the heap so that the lowest fcost is at the top
 505                     m = numOpen;
 506                     while (m != 1)                          //while this item isn't at the top of the heap already
 507                     {
 508                         //if it has a lower fcost than its parent
 509                         if (fcost[openlist[m]] <= fcost[openlist[m/2]])
 510                         {
 511                             temp = openlist[m/2];
 512                             openlist[m/2] = openlist[m];
 513                             openlist[m] = temp;             //swap them
 514                             m /= 2;
 515                         }
 516                         else
 517                             break;
 518                     }
 519                 }
 520                 else                                        //if this node is already on the open list
 521                 {
 522                     gc = gcost[atNode];
 523                     VectorSubtract(nodes[newnode].origin, nodes[atNode].origin, vec);
 524                     gc += VectorLength(vec);                //calculate what the gcost would be if we reached this node along the current path
 525
 526                     if (gc < gcost[newnode])                //if the new gcost is less (ie, this path is shorter than what we had before)
 527                     {
 528                         parent[newnode] = atNode;           //set the new parent for this node
 529                         gcost[newnode] = gc;                //and the new g cost
 530
 531                         for (i = 1; i < numOpen; ++i)       //loop through all the items on the open list
 532                         {
 533                             if (openlist[i] == newnode)     //find this node in the list
 534                             {
 535                                 //calculate the new fcost and store it
 536                                 fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 537
 538                                 //reorder the list again, with the lowest fcost item on top
 539                                 m = i;
 540                                 while (m != 1)
 541                                 {
 542                                     //if the item has a lower fcost than it's parent
 543                                     if (fcost[openlist[m]] < fcost[openlist[m/2]])
 544                                     {
 545                                         temp = openlist[m/2];
 546                                         openlist[m/2] = openlist[m];
 547                                         openlist[m] = temp; //swap them
 548                                         m /= 2;
 549                                     }
 550                                     else
 551                                         break;
 552                                 }
 553                                 break;                      //exit the 'for' loop because we already changed this node
 554                             }                               //if
 555                         }                                   //for
 556                     }                                       //if (gc < gcost[newnode])
 557                 }                                           //if (list[newnode] != 1) --> else
 558             }                                               //for (loop through links)
 559         }                                                   //if (numOpen != 0)
 560         else
 561         {
 562             found = qfalse;                                 //there is no path between these nodes
 563             break;
 564         }
 565
 566         if (list[to] == 1)                                  //if the destination node is on the open list, we're done
 567         {
 568             found = qtrue;
 569             break;
 570         }
 571     }                                                       //while (1)
 572
 573     if (found == qtrue)                                     //if we found a path
 574     {
 575         //G_Printf("%s - path found!n", bot->client->pers.netname);
 576         count = 0;
 577
 578         temp = to;                                          //start at the end point
 579         while (temp != from)                                //travel along the path (backwards) until we reach the starting point
 580         {
 581             pathlist[count++] = temp;                       //add the node to the pathlist and increment the count
 582             temp = parent[temp];                            //move to the parent of this node to continue the path
 583         }
 584
 585         pathlist[count++] = from;                           //add the beginning node to the end of the pathlist
 586
 587         #ifdef __BOT_SHORTEN_ROUTING__
 588         count = ShortenASTARRoute(pathlist, count);         // This isn't working... Dunno why.. Unique1
 589         #endif                                              //__BOT_SHORTEN_ROUTING__
 590     }
 591     else
 592     {
 593         //G_Printf("^1*** ^4BOT DEBUG^5: (CreatePathAStar) There is no route between node ^7%i^5 and node ^7%i^5.n", from, to);
 594         count = CreateDumbRoute(from, to, pathlist);
 595
 596         if (count > 0)
 597         {
 598             #ifdef __BOT_SHORTEN_ROUTING__
 599             count = ShortenASTARRoute(pathlist, count);     // This isn't working... Dunno why.. Unique1
 600             #endif                                          //__BOT_SHORTEN_ROUTING__
 601             return count;
 602         }
 603     }
 604
 605     return count;                                           //return the number of nodes in the path, -1 if not found
 606 }
 607
 608 /*
 609 ===========================================================================
 610 GetFCost
 611 Utility function used by A* pathfinding to calculate the
 612 cost to move between nodes towards a goal.  Using the A*
 613 algorithm F = G + H, G here is the distance along the node
 614 paths the bot must travel, and H is the straight-line distance
 615 to the goal node.
 616 Returned as an int because more precision is unnecessary and it
 617 will slightly speed up heap access
 618 ===========================================================================
 619 */
 620 int GetFCost(int to, int num, int parentNum, float *gcost)
 621 {
 622     float gc = 0;
 623     float hc = 0;
 624     vec3_t v;
 625
 626     if (gcost[num] == -1)
 627     {
 628         if (parentNum != -1)
 629         {
 630             gc = gcost[parentNum];
 631             VectorSubtract(nodes[num].origin, nodes[parentNum].origin, v);
 632             gc += VectorLength(v);
 633         }
 634         gcost[num] = gc;
 635     }
 636     else
 637         gc = gcost[num];
 638
 639     VectorSubtract(nodes[to].origin, nodes[num].origin, v);
 640     hc = VectorLength(v);
 641
 642     return (int)(gc + hc);
 643 }
 644 #endif                                                      //__PATHFINDING__