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