src/game/WaypointMovementGenerator.cpp

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