src/game/WaypointMovementGenerator.cpp

   1 /*
   2  * Copyright (C) 2005,2006,2007 MaNGOS <http://www.mangosproject.org/>
   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 `text1` varchar(255) default NULL;
  23 alter table creature_movement add `text2` varchar(255) default NULL;
  24 alter table creature_movement add `text3` varchar(255) default NULL;
  25 alter table creature_movement add `text4` varchar(255) default NULL;
  26 alter table creature_movement add `text5` varchar(255) default NULL;
  27 alter table creature_movement add `aiscript` varchar(255) default NULL;
  28 alter table creature_movement add `emote` int(10) unsigned default '0';
  29 alter table creature_movement add `spell` int(5) unsigned default '0';
  30 alter table creature_movement add `wpguid` int(11) default '0';
  31
  32 */
  33
  34 #include <ctime>
  35
  36 #include "WaypointMovementGenerator.h"
  37 #include "ObjectMgr.h"
  38 #include "Creature.h"
  39 #include "FlightMaster.h"
  40 #include "DestinationHolderImp.h"
  41
  42 #include <cassert>
  43
  44 //-----------------------------------------------//
  45 void
  46 WaypointMovementGenerator::_load(Creature &c)
  47 {
  48     i_path.Clear();
  49     i_wpBehaviour.clear();
  50
  51     QueryResult *result = NULL;
  52     sLog.outDebug("DEBUG: WaypointMovementGenerator::_load: GUID - %d", c.GetGUIDLow());
  53     // Identify by GUID
  54     result = sDatabase.PQuery("SELECT `position_x`, `position_y`, `position_z`, `orientation`, `model1`, `model2`, `waittime`, `emote`, `spell`, `text1`, `text2`, `text3`, `text4`, `text5`, `aiscript` FROM `creature_movement` WHERE `id` = '%u' ORDER BY `point`", c.GetDBTableGUIDLow());
  55     /*
  56     if( result ) {
  57     sLog.outDebug("DEBUG: Number of hits: %d", result->GetRowCount());
  58     } else {
  59     sLog.outDebug("DEBUG: Nothing found");
  60     }
  61     */
  62
  63     if( result )
  64     {
  65         unsigned int count = 0;
  66         const unsigned int sz = result->GetRowCount();
  67         i_path.Resize( sz );
  68         i_delays.resize( sz );
  69         i_wpBehaviour.resize( sz );
  70
  71         do
  72         {
  73             //sLog.outDebug("DEBUG: _load");
  74             Field *fields = result->Fetch();
  75             i_path[count].x         = fields[0].GetFloat();
  76             i_path[count].y         = fields[1].GetFloat();
  77             i_path[count].z         = fields[2].GetFloat();
  78             float orientation       = fields[3].GetFloat();
  79             uint32 model1           = fields[4].GetUInt32();
  80             uint32 model2           = fields[5].GetUInt32();
  81             i_delays[count]         = fields[6].GetUInt16();
  82             uint32 emote            = fields[7].GetUInt32();
  83             uint32 spell            = fields[8].GetUInt32();
  84             std::string text1       = fields[9].GetCppString();
  85             std::string text2       = fields[10].GetCppString();
  86             std::string text3       = fields[11].GetCppString();
  87             std::string text4       = fields[12].GetCppString();
  88             std::string text5       = fields[13].GetCppString();
  89             std::string aiscript    = fields[14].GetCppString();
  90
  91             if( (emote != 0) || (spell != 0)
  92                 || (text1 != "") || (text2 != "") || (text3 != "") || (text4 != "") || (text5 != "")
  93                 || (aiscript != "")
  94                 || (model1 != 0)  || (model2 != 0) || (orientation != 100))
  95             {
  96                 WaypointBehavior *tmpWPB = new WaypointBehavior;
  97
  98                 // sLog.outDebug("DEBUG: _load  ---  Adding WaypointBehavior");
  99
 100                 tmpWPB->text[0] = text1;
 101                 tmpWPB->text[1] = text2;
 102                 tmpWPB->text[2] = text3;
 103                 tmpWPB->text[3] = text4;
 104                 tmpWPB->text[4] = text5;
 105                 tmpWPB->aiscript = aiscript;
 106                 tmpWPB->orientation = orientation;
 107                 tmpWPB->emote = emote;
 108                 tmpWPB->spell = spell;
 109                 tmpWPB->model1 = model1;
 110                 tmpWPB->model2 = model2;
 111                 tmpWPB->HasDone = false;
 112                 i_wpBehaviour[count] = tmpWPB;
 113             }
 114             else
 115             {
 116                 i_wpBehaviour[count] = NULL;
 117             }
 118
 119             if(!MaNGOS::IsValidMapCoord(i_path[count].x,i_path[count].y))
 120             {
 121                 sLog.outErrorDb("ERROR: Creature (guidlow %d,entry %d) have invalid coordinates in his waypoint %d (X: %d, Y: %d).",
 122                     c.GetGUIDLow(),c.GetEntry(),count,i_path[count].x,i_path[count].y
 123                     );
 124
 125                 // prevent invalid coordinates using
 126                 MaNGOS::NormalizeMapCoord(i_path[count].x);
 127                 MaNGOS::NormalizeMapCoord(i_path[count].y);
 128                 i_path[count].z = MapManager::Instance ().GetMap(c.GetMapId(), &c)->GetHeight(i_path[count].x,i_path[count].y, i_path[count].z);
 129             }
 130             // to prevent a misbehaviour inside "update"
 131             // update is alway called with the next wp - but the wpSys needs the current
 132             // so when the routine is called the first time, wpSys gets the last waypoint
 133             // and this prevents the system from performing text/emote, etc
 134             if( count == (sz-1) )
 135             {
 136                 if( i_wpBehaviour[count] != NULL )
 137                 {
 138                     i_wpBehaviour[count]->HasDone = true;
 139                 }
 140             }
 141             //if( i_delays[count] < 30 /* millisecond */ )
 142             //    i_delays[count] = (rand() % 5000);
 143             ++count;
 144
 145         } while( result->NextRow() );
 146
 147         delete result;
 148
 149         assert( sz == count );
 150     }
 151 }
 152
 153 void
 154 WaypointMovementGenerator::Initialize()
 155 {
 156     QueryResult *result = sDatabase.Query("SELECT distinct(`id`) as uniqueid FROM `creature_movement`");
 157
 158     if( result )
 159     {
 160         do
 161         {
 162             Field *fields = result->Fetch();
 163             si_waypointHolders.insert( fields[0].GetUInt32() );
 164         }
 165         while( result->NextRow() );
 166
 167         delete result;
 168     }
 169 }
 170
 171 int
 172 WaypointMovementGenerator::Permissible(const Creature *c)
 173 {
 174     if (si_waypointHolders.find(c->GetGUIDLow()) != si_waypointHolders.end())
 175     {
 176         DEBUG_LOG("Creature [guid=%u] returns waypoint movement permit.", c->GetGUIDLow());
 177         return WAYPOINT_MOTION_TYPE;
 178     }
 179
 180     return CANNOT_HANDLE_TYPE;
 181 }
 182
 183 bool
 184 WaypointMovementGenerator::Update(Creature &creature, const uint32 &diff)
 185 {
 186     if(!&creature)
 187         return true;
 188     if(i_creature.hasUnitState(UNIT_STAT_ROOT) || i_creature.hasUnitState(UNIT_STAT_STUNDED))
 189         return true;
 190
 191     // prevent crash at empty waypoint path.
 192     if(i_path.Size()==0)
 193     {
 194         return true;
 195     }
 196
 197     CreatureTraveller traveller(creature);
 198
 199     /*
 200     if( npcIsStopped[creature.GetGUID()] )
 201     {
 202         i_nextMoveTime.Update(40000);
 203         i_destinationHolder.UpdateTraveller(traveller, ((diff)-40000), false);
 204         npcIsStopped[creature.GetGUID()] = false;
 205         return true;
 206     }
 207     */
 208     i_nextMoveTime.Update(diff);
 209     i_destinationHolder.UpdateTraveller(traveller, diff, false);
 210
 211     if( i_creature.IsStopped() )
 212     {
 213         uint32 wpB = i_currentNode > 0 ? i_currentNode-1 : i_wpBehaviour.size()-1;
 214
 215         if( i_wpBehaviour[wpB] != NULL )
 216         {
 217             struct WaypointBehavior *tmpBehavior = i_wpBehaviour[wpB];
 218
 219             if (!tmpBehavior->HasDone)
 220             {
 221                 if(tmpBehavior->emote != 0)
 222                 {
 223                     creature.SetUInt32Value(UNIT_NPC_EMOTESTATE,tmpBehavior->emote);
 224                 }
 225                 if(tmpBehavior->aiscript != "")
 226                 {
 227                     WPAIScript(creature, tmpBehavior->aiscript);
 228                 }
 229                 //sLog.outDebug("DEBUG: tmpBehavior->text[0] TEST");
 230                 if(tmpBehavior->text[0] != "")
 231                 {
 232                     //sLog.outDebug("DEBUG: tmpBehavior->text[0] != \"\"");
 233                     // Only one text is set
 234                     if( tmpBehavior->text[1] == "" )
 235                     {
 236                         //sLog.outDebug("DEBUG: tmpBehavior->text[1] == NULL");
 237                         creature.Say(tmpBehavior->text[0].c_str(), 0, 0);
 238                     }
 239                     else
 240                     {
 241                         // Select one from max 5 texts
 242                         int maxText = 4;
 243                         for( int i=0; i<4; i++ )
 244                         {
 245                             if( tmpBehavior->text[i] == "" )
 246                             {
 247                                 //sLog.outDebug("DEBUG: tmpBehavior->text[i] == \"\": %d", i);
 248                                 //sLog.outDebug("DEBUG: rand() % (i): %d", rand() % (i));
 249
 250                                 creature.Say(tmpBehavior->text[rand() % i].c_str(), 0, 0);
 251                                 break;
 252                             }
 253                         }
 254                     }
 255                 }
 256                 if(tmpBehavior->spell != 0)
 257                 {
 258                     //sLog.outDebug("DEBUG: wpSys - spell");
 259                     creature.CastSpell(&creature,tmpBehavior->spell, false);
 260                 }
 261                 if (tmpBehavior->orientation !=100)
 262                 {
 263                     //sLog.outDebug("DEBUG: wpSys - orientation");
 264                     creature.SetOrientation(tmpBehavior->orientation);
 265                 }
 266                 if(tmpBehavior->model1 != 0)
 267                 {
 268                     //sLog.outDebug("DEBUG: wpSys - model1");
 269                     creature.SetUInt32Value(UNIT_FIELD_DISPLAYID, tmpBehavior->model1);
 270                 }
 271                 tmpBehavior->HasDone = true;
 272             }                                               // HasDone == false
 273         }                                                   // wpBehaviour found
 274     }                                                       // i_creature.IsStopped()
 275
 276     if( i_nextMoveTime.Passed() )
 277     {
 278         if( i_creature.IsStopped() )
 279         {
 280             assert( i_currentNode < i_path.Size() );
 281             creature.addUnitState(UNIT_STAT_ROAMING);
 282             const Path::PathNode &node(i_path(i_currentNode));
 283             i_destinationHolder.SetDestination(traveller, node.x, node.y, node.z);
 284             i_nextMoveTime.Reset(i_destinationHolder.GetTotalTravelTime());
 285             uint32 wpB = i_currentNode > 0 ? i_currentNode-1 : i_wpBehaviour.size()-1;
 286
 287             if( i_wpBehaviour[wpB] != NULL )
 288             {
 289                 struct WaypointBehavior *tmpBehavior = i_wpBehaviour[wpB];
 290                 tmpBehavior->HasDone = false;
 291                 if(tmpBehavior->model2 != 0)
 292                 {
 293                     creature.SetUInt32Value(UNIT_FIELD_DISPLAYID, tmpBehavior->model2);
 294                 }
 295                 if (tmpBehavior->orientation !=100)
 296                 {
 297                     creature.SetOrientation(tmpBehavior->orientation);
 298                 }
 299                 creature.SetUInt32Value(UNIT_NPC_EMOTESTATE, 0);
 300             }
 301         }
 302         else
 303         {
 304             creature.StopMoving();
 305             i_nextMoveTime.Reset(i_delays[i_currentNode]);
 306             ++i_currentNode;
 307             if( i_currentNode >= i_path.Size() )
 308                 i_currentNode = 0;
 309         }
 310     }
 311     return true;
 312 }
 313
 314 void
 315 WaypointMovementGenerator::WPAIScript(Creature &pCreature, std::string pAiscript)
 316 {
 317     time_t curr;
 318     tm local;
 319     time(&curr);                                            // get current time_t value
 320     local=*(localtime(&curr));                              //
 321     int cT = ((local.tm_hour*100)+local.tm_min);
 322
 323     sLog.outDebug("WPAIScript: %s", pAiscript.c_str());
 324
 325     if( pAiscript == "guard-sw")                            //demo script for WP-AI System
 326     {
 327         if(pCreature.GetEntry() == 68 || 1423)
 328         {
 329             if(!( (cT < 1800) && (cT > 800) ))              //If time not smaler than 1800 and not bigger than 800 (24 hour format)
 330             {                                               //try to set model of Off-hand (shield) to 0 (imo it doesn't work...)
 331                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_SLOT_DISPLAY+1, 0);
 332                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2, 234948100);
 333                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2 + 1, 4);
 334
 335                 //set new Off-Hand Item as lamp
 336                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_SLOT_DISPLAY+1, 7557);
 337                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2, 385941508);
 338                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2 + 1, 7);
 339             }                                               //else do it in other direction...
 340             else
 341             {
 342                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_SLOT_DISPLAY+1, 0);
 343                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2, 385941508);
 344                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2 + 1, 7);
 345
 346                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_SLOT_DISPLAY+1, 2080);
 347                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2, 234948100);
 348                 pCreature.SetUInt32Value( UNIT_VIRTUAL_ITEM_INFO + 2 + 1, 4);
 349             }
 350         }
 351         sLog.outDebug("guard-sw");
 352     }
 353 }
 354
 355 std::set<uint32> WaypointMovementGenerator::si_waypointHolders;
 356
 357 //----------------------------------------------------//
 358 FlightPathMovementGenerator::FlightPathMovementGenerator(Player &pl, uint32 id) : i_pathId(id), i_player(pl)
 359 {
 360     Initialize();
 361     FlightMaster::Instance().ReportFlight(&i_player, this);
 362 }
 363
 364 void
 365 FlightPathMovementGenerator::LoadPath(Player &pl)
 366 {
 367     objmgr.GetTaxiPathNodes(i_pathId, i_path);
 368 }
 369
 370 void
 371 FlightPathMovementGenerator::Initialize()
 372 {
 373     i_player.MoveToHateOfflineList();
 374     i_player.addUnitState(UNIT_STAT_IN_FLIGHT);
 375     LoadPath(i_player);
 376     i_currentNode = 0;
 377     Traveller<Player> traveller(i_player);
 378     i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z);
 379 }
 380
 381 void
 382 FlightPathMovementGenerator::UpdatePath(Player &player, const uint32 &diff)
 383 {
 384     if( !MovementInProgress() )
 385         return;
 386
 387     Traveller<Player> traveller(player);
 388     if( i_destinationHolder.UpdateTraveller(traveller, diff, false) )
 389     {
 390         i_destinationHolder.ResetUpdate(FLIGHT_TRAVEL_UPDATE);
 391         if( i_destinationHolder.HasArrived() )
 392         {
 393             ++i_currentNode;
 394             if( i_currentNode < i_path.Size() )
 395             {
 396                 DEBUG_LOG("loading node %u for player %s", i_currentNode, i_player.GetName());
 397                 i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z);
 398             }
 399         }
 400     }
 401 }
 402
 403 //
 404 // Unique1's ASTAR Pathfinding Code... For future use & reference...
 405 //
 406
 407 #ifdef __PATHFINDING__
 408
 409 int GetFCost(int to, int num, int parentNum, float *gcost); // Below...
 410
 411 int ShortenASTARRoute(short int *pathlist, int number)
 412 {                                                           // Wrote this to make the routes a little smarter (shorter)... No point looping back to the same places... Unique1
 413     short int temppathlist[MAX_PATHLIST_NODES];
 414     int count = 0;
 415     //    int count2 = 0;
 416     int temp, temp2;
 417     int link;
 418     int upto = 0;
 419
 420     for (temp = number; temp >= 0; temp--)
 421     {
 422         qboolean shortened = qfalse;
 423
 424         for (temp2 = 0; temp2 < temp; temp2++)
 425         {
 426             for (link = 0; link < nodes[pathlist[temp]].enodenum; link++)
 427             {
 428                 if (nodes[pathlist[temp]].links[link].flags & PATH_BLOCKED)
 429                     continue;
 430
 431                 //if ((bot->client->ps.eFlags & EF_TANK) && nodes[bot->current_node].links[link].flags & PATH_NOTANKS)    //if this path is blocked, skip it
 432                 //    continue;
 433
 434                 //if (nodes[nodes[pathlist[temp]].links[link].targetNode].origin[2] > nodes[pathlist[temp]].origin[2] + 32)
 435                 //    continue;
 436
 437                 if (nodes[pathlist[temp]].links[link].targetNode == pathlist[temp2])
 438                 {                                           // Found a shorter route...
 439                     //if (OrgVisible(nodes[pathlist[temp2]].origin, nodes[pathlist[temp]].origin, -1))
 440                     {
 441                         temppathlist[count] = pathlist[temp2];
 442                         temp = temp2;
 443                         count++;
 444                         shortened = qtrue;
 445                     }
 446                 }
 447             }
 448         }
 449
 450         if (!shortened)
 451         {
 452             temppathlist[count] = pathlist[temp];
 453             count++;
 454         }
 455     }
 456
 457     upto = count;
 458
 459     for (temp = 0; temp < count; temp++)
 460     {
 461         pathlist[temp] = temppathlist[upto];
 462         upto--;
 463     }
 464
 465     G_Printf("ShortenASTARRoute: Path size reduced from %i to %i nodes...n", number, count);
 466     return count;
 467 }
 468
 469 /*
 470 ===========================================================================
 471 CreatePathAStar
 472 This function uses the A* pathfinding algorithm to determine the
 473 shortest path between any two nodes.
 474 It's fairly complex, so I'm not really going to explain it much.
 475 Look up A* and binary heaps for more info.
 476 pathlist stores the ideal path between the nodes, in reverse order,
 477 and the return value is the number of nodes in that path
 478 ===========================================================================
 479 */
 480 int CreatePathAStar(gentity_t *bot, int from, int to, short int *pathlist)
 481 {
 482     //all the data we have to hold...since we can't do dynamic allocation, has to be MAX_NODES
 483     //we can probably lower this later - eg, the open list should never have more than at most a few dozen items on it
 484     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
 485     float gcost[MAX_NODES];
 486     int fcost[MAX_NODES];
 487     char list[MAX_NODES];                                   //0 is neither, 1 is open, 2 is closed - char because it's the smallest data type
 488     short int parent[MAX_NODES];
 489
 490     short int numOpen = 0;
 491     short int atNode, temp, newnode=-1;
 492     qboolean found = qfalse;
 493     int count = -1;
 494     float gc;
 495     int i, u, v, m;
 496     vec3_t vec;
 497
 498     //clear out all the arrays
 499     memset(openlist, 0, sizeof(short int)*(MAX_NODES+1));
 500     memset(fcost, 0, sizeof(int)*MAX_NODES);
 501     memset(list, 0, sizeof(char)*MAX_NODES);
 502     memset(parent, 0, sizeof(short int)*MAX_NODES);
 503     memset(gcost, -1, sizeof(float)*MAX_NODES);
 504
 505     //make sure we have valid data before calculating everything
 506     if ((from == NODE_INVALID) || (to == NODE_INVALID) || (from >= MAX_NODES) || (to >= MAX_NODES) || (from == to))
 507         return -1;
 508
 509     openlist[1] = from;                                     //add the starting node to the open list
 510     numOpen++;
 511     gcost[from] = 0;                                        //its f and g costs are obviously 0
 512     fcost[from] = 0;
 513
 514     while (1)
 515     {
 516         if (numOpen != 0)                                   //if there are still items in the open list
 517         {
 518             //pop the top item off of the list
 519             atNode = openlist[1];
 520             list[atNode] = 2;                               //put the node on the closed list so we don't check it again
 521             numOpen--;
 522
 523             openlist[1] = openlist[numOpen+1];              //move the last item in the list to the top position
 524             v = 1;
 525
 526             //this while loop reorders the list so that the new lowest fcost is at the top again
 527             while (1)
 528             {
 529                 u = v;
 530                 if ((2*u+1) < numOpen)                      //if both children exist
 531                 {
 532                     if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 533                         v = 2*u;
 534                     if (fcost[openlist[v]] >= fcost[openlist[2*u+1]])
 535                         v = 2*u+1;
 536                 }
 537                 else
 538                 {
 539                     if ((2*u) < numOpen)                    //if only one child exists
 540                     {
 541                         if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 542                             v = 2*u;
 543                     }
 544                 }
 545
 546                 if (u != v)                                 //if they're out of order, swap this item with its parent
 547                 {
 548                     temp = openlist[u];
 549                     openlist[u] = openlist[v];
 550                     openlist[v] = temp;
 551                 }
 552                 else
 553                     break;
 554             }
 555
 556             for (i = 0; i < nodes[atNode].enodenum; i++)    //loop through all the links for this node
 557             {
 558                 newnode = nodes[atNode].links[i].targetNode;
 559
 560                 //if this path is blocked, skip it
 561                 if (nodes[atNode].links[i].flags & PATH_BLOCKED)
 562                     continue;
 563                 //if this path is blocked, skip it
 564                 if (bot->client && (bot->client->ps.eFlags & EF_TANK) && nodes[atNode].links[i].flags & PATH_NOTANKS)
 565                     continue;
 566                 //skip any unreachable nodes
 567                 if (bot->client && (nodes[newnode].type & NODE_ALLY_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_ALLIES))
 568                     continue;
 569                 if (bot->client && (nodes[newnode].type & NODE_AXIS_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_AXIS))
 570                     continue;
 571
 572                 if (list[newnode] == 2)                     //if this node is on the closed list, skip it
 573                     continue;
 574
 575                 if (list[newnode] != 1)                     //if this node is not already on the open list
 576                 {
 577                     openlist[++numOpen] = newnode;          //add the new node to the open list
 578                     list[newnode] = 1;
 579                     parent[newnode] = atNode;               //record the node's parent
 580
 581                     if (newnode == to)                      //if we've found the goal, don't keep computing paths!
 582                         break;                              //this will break the 'for' and go all the way to 'if (list[to] == 1)'
 583
 584                     //store it's f cost value
 585                     fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 586
 587                     //this loop re-orders the heap so that the lowest fcost is at the top
 588                     m = numOpen;
 589                     while (m != 1)                          //while this item isn't at the top of the heap already
 590                     {
 591                         //if it has a lower fcost than its parent
 592                         if (fcost[openlist[m]] <= fcost[openlist[m/2]])
 593                         {
 594                             temp = openlist[m/2];
 595                             openlist[m/2] = openlist[m];
 596                             openlist[m] = temp;             //swap them
 597                             m /= 2;
 598                         }
 599                         else
 600                             break;
 601                     }
 602                 }
 603                 else                                        //if this node is already on the open list
 604                 {
 605                     gc = gcost[atNode];
 606                     VectorSubtract(nodes[newnode].origin, nodes[atNode].origin, vec);
 607                     gc += VectorLength(vec);                //calculate what the gcost would be if we reached this node along the current path
 608
 609                     if (gc < gcost[newnode])                //if the new gcost is less (ie, this path is shorter than what we had before)
 610                     {
 611                         parent[newnode] = atNode;           //set the new parent for this node
 612                         gcost[newnode] = gc;                //and the new g cost
 613
 614                         for (i = 1; i < numOpen; i++)       //loop through all the items on the open list
 615                         {
 616                             if (openlist[i] == newnode)     //find this node in the list
 617                             {
 618                                 //calculate the new fcost and store it
 619                                 fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 620
 621                                 //reorder the list again, with the lowest fcost item on top
 622                                 m = i;
 623                                 while (m != 1)
 624                                 {
 625                                     //if the item has a lower fcost than it's parent
 626                                     if (fcost[openlist[m]] < fcost[openlist[m/2]])
 627                                     {
 628                                         temp = openlist[m/2];
 629                                         openlist[m/2] = openlist[m];
 630                                         openlist[m] = temp; //swap them
 631                                         m /= 2;
 632                                     }
 633                                     else
 634                                         break;
 635                                 }
 636                                 break;                      //exit the 'for' loop because we already changed this node
 637                             }                               //if
 638                         }                                   //for
 639                     }                                       //if (gc < gcost[newnode])
 640                 }                                           //if (list[newnode] != 1) --> else
 641             }                                               //for (loop through links)
 642         }                                                   //if (numOpen != 0)
 643         else
 644         {
 645             found = qfalse;                                 //there is no path between these nodes
 646             break;
 647         }
 648
 649         if (list[to] == 1)                                  //if the destination node is on the open list, we're done
 650         {
 651             found = qtrue;
 652             break;
 653         }
 654     }                                                       //while (1)
 655
 656     if (found == qtrue)                                     //if we found a path
 657     {
 658         //G_Printf("%s - path found!n", bot->client->pers.netname);
 659         count = 0;
 660
 661         temp = to;                                          //start at the end point
 662         while (temp != from)                                //travel along the path (backwards) until we reach the starting point
 663         {
 664             pathlist[count++] = temp;                       //add the node to the pathlist and increment the count
 665             temp = parent[temp];                            //move to the parent of this node to continue the path
 666         }
 667
 668         pathlist[count++] = from;                           //add the beginning node to the end of the pathlist
 669
 670         #ifdef __BOT_SHORTEN_ROUTING__
 671         count = ShortenASTARRoute(pathlist, count);         // This isn't working... Dunno why.. Unique1
 672         #endif                                              //__BOT_SHORTEN_ROUTING__
 673     }
 674     else
 675     {
 676         //G_Printf("^1*** ^4BOT DEBUG^5: (CreatePathAStar) There is no route between node ^7%i^5 and node ^7%i^5.n", from, to);
 677         count = CreateDumbRoute(from, to, pathlist);
 678
 679         if (count > 0)
 680         {
 681             #ifdef __BOT_SHORTEN_ROUTING__
 682             count = ShortenASTARRoute(pathlist, count);     // This isn't working... Dunno why.. Unique1
 683             #endif                                          //__BOT_SHORTEN_ROUTING__
 684             return count;
 685         }
 686     }
 687
 688     return count;                                           //return the number of nodes in the path, -1 if not found
 689 }
 690
 691 /*
 692 ===========================================================================
 693 GetFCost
 694 Utility function used by A* pathfinding to calculate the
 695 cost to move between nodes towards a goal.  Using the A*
 696 algorithm F = G + H, G here is the distance along the node
 697 paths the bot must travel, and H is the straight-line distance
 698 to the goal node.
 699 Returned as an int because more precision is unnecessary and it
 700 will slightly speed up heap access
 701 ===========================================================================
 702 */
 703 int GetFCost(int to, int num, int parentNum, float *gcost)
 704 {
 705     float gc = 0;
 706     float hc = 0;
 707     vec3_t v;
 708
 709     if (gcost[num] == -1)
 710     {
 711         if (parentNum != -1)
 712         {
 713             gc = gcost[parentNum];
 714             VectorSubtract(nodes[num].origin, nodes[parentNum].origin, v);
 715             gc += VectorLength(v);
 716         }
 717         gcost[num] = gc;
 718     }
 719     else
 720         gc = gcost[num];
 721
 722     VectorSubtract(nodes[to].origin, nodes[num].origin, v);
 723     hc = VectorLength(v);
 724
 725     return (int)(gc + hc);
 726 }
 727 #endif                                                      //__PATHFINDING__