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