src/game/WaypointMovementGenerator.cpp

   1 /*
   2  * Copyright (C) 2005,2006 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 #include "WaypointMovementGenerator.h"
  20 #include "ObjectMgr.h"
  21 #include "Creature.h"
  22 #include "FlightMaster.h"
  23
  24 #include <cassert>
  25
  26 //-----------------------------------------------//
  27 void
  28 WaypointMovementGenerator::_load(Creature &c)
  29 {
  30     i_path.Clear();
  31
  32     QueryResult *result = sDatabase.PQuery("SELECT `position_x`, `position_y`, `position_z`, `waittime` FROM `creature_movement` WHERE `id` = '%d' ORDER BY `point`;", c.GetGUIDLow());
  33
  34     if( result )
  35     {
  36         unsigned int count = 0;
  37         const unsigned int sz = result->GetRowCount();
  38         i_path.Resize( sz );
  39         i_delays.resize( sz );
  40
  41         do
  42         {
  43             Field *fields = result->Fetch();
  44             i_path[count].x = fields[0].GetFloat();
  45             i_path[count].y = fields[1].GetFloat();
  46             i_path[count].z = fields[2].GetFloat();
  47             i_delays[count] = fields[3].GetUInt16();
  48
  49             if( i_delays[count] < 30 /* millisecond */ )
  50                 i_delays[count] = (rand() % 5000);
  51             ++count;
  52
  53         } while( result->NextRow() );
  54
  55         assert( sz == count );
  56     }
  57 }
  58
  59 void
  60 WaypointMovementGenerator::Initialize()
  61 {
  62     QueryResult *result = sDatabase.PQuery("SELECT `id` FROM `creature_movement`;");
  63
  64     if( result )
  65     {
  66         do
  67         {
  68             Field *fields = result->Fetch();
  69             si_waypointHolders.insert( fields[0].GetUInt32() );
  70         }
  71         while( result->NextRow() );
  72     }
  73 }
  74
  75 int
  76 WaypointMovementGenerator::Permissible(const Creature *c)
  77 {
  78     if (si_waypointHolders.find(c->GetGUIDLow()) != si_waypointHolders.end())
  79     {
  80         DEBUG_LOG("Creature [guid=%d] returns waypoint movement permit.", c->GetGUIDLow());
  81         return CUSTOM_MOTION_TYPE;
  82     }
  83
  84     return CANNOT_HANDLE_TYPE;
  85 }
  86
  87 void
  88 WaypointMovementGenerator::Update(Creature &creature, const uint32 &diff)
  89 {
  90     i_nextMoveTime.Update(diff);
  91     if( i_nextMoveTime.Passed() )
  92     {
  93         if( i_creature.IsStopped() )
  94         {
  95             assert( i_currentNode < i_path.Size() );
  96             creature.addUnitState(UNIT_STAT_ROAMING);
  97             const Path::PathNode &node(i_path(i_currentNode));
  98             Traveller<Creature> traveller(creature);
  99             i_destinationHolder.SetDestination(traveller, node.x, node.y, node.z);
 100             i_nextMoveTime.Reset(i_destinationHolder.GetTotalTravelTime());
 101         }
 102         else
 103         {
 104             Traveller<Creature> traveller(creature);
 105             i_destinationHolder.UpdateTraveller(traveller, diff, true);
 106             creature.StopMoving();
 107             i_nextMoveTime.Reset(i_delays[i_currentNode]);
 108             ++i_currentNode;
 109             if( i_currentNode >= i_path.Size() )
 110                 i_currentNode = 0;
 111         }
 112     }
 113 }
 114
 115 std::set<uint32> WaypointMovementGenerator::si_waypointHolders;
 116
 117 //----------------------------------------------------//
 118 FlightPathMovementGenerator::FlightPathMovementGenerator(Player &pl, uint32 id) : i_pathId(id), i_player(pl)
 119 {
 120     Initialize();
 121     FlightMaster::Instance().ReportFlight(&i_player, this);
 122 }
 123
 124 void
 125 FlightPathMovementGenerator::LoadPath(Player &pl)
 126 {
 127     objmgr.GetTaxiPathNodes(i_pathId, i_path);
 128 }
 129
 130 void
 131 FlightPathMovementGenerator::Initialize()
 132 {
 133     i_player.addUnitState(UNIT_STAT_IN_FLIGHT);
 134     LoadPath(i_player);
 135     i_currentNode = 0;
 136     Traveller<Player> traveller(i_player);
 137     i_destinationHolder.SetDestination(traveller, i_path[i_currentNode].x, i_path[i_currentNode].y, i_path[i_currentNode].z);
 138 }
 139
 140 //
 141 // Unique1's ASTAR Pathfinding Code... For future use & reference...
 142 //
 143
 144 #ifdef __PATHFINDING__
 145
 146 int GetFCost(int to, int num, int parentNum, float *gcost); // Below...
 147
 148 int ShortenASTARRoute(short int *pathlist, int number)
 149 {                                                           // Wrote this to make the routes a little smarter (shorter)... No point looping back to the same places... Unique1
 150     short int temppathlist[MAX_PATHLIST_NODES];
 151     int count = 0;
 152     //  int count2 = 0;
 153     int temp, temp2;
 154     int link;
 155     int upto = 0;
 156
 157     for (temp = number; temp >= 0; temp--)
 158     {
 159         qboolean shortened = qfalse;
 160
 161         for (temp2 = 0; temp2 < temp; temp2++)
 162         {
 163             for (link = 0; link < nodes[pathlist[temp]].enodenum; link++)
 164             {
 165                 if (nodes[pathlist[temp]].links[link].flags & PATH_BLOCKED)
 166                     continue;
 167
 168                 //if ((bot->client->ps.eFlags & EF_TANK) && nodes[bot->current_node].links[link].flags & PATH_NOTANKS)  //if this path is blocked, skip it
 169                 //      continue;
 170
 171                 //if (nodes[nodes[pathlist[temp]].links[link].targetNode].origin[2] > nodes[pathlist[temp]].origin[2] + 32)
 172                 //      continue;
 173
 174                 if (nodes[pathlist[temp]].links[link].targetNode == pathlist[temp2])
 175                 {                                           // Found a shorter route...
 176                     //if (OrgVisible(nodes[pathlist[temp2]].origin, nodes[pathlist[temp]].origin, -1))
 177                     {
 178                         temppathlist[count] = pathlist[temp2];
 179                         temp = temp2;
 180                         count++;
 181                         shortened = qtrue;
 182                     }
 183                 }
 184             }
 185         }
 186
 187         if (!shortened)
 188         {
 189             temppathlist[count] = pathlist[temp];
 190             count++;
 191         }
 192     }
 193
 194     upto = count;
 195
 196     for (temp = 0; temp < count; temp++)
 197     {
 198         pathlist[temp] = temppathlist[upto];
 199         upto--;
 200     }
 201
 202     G_Printf("ShortenASTARRoute: Path size reduced from %i to %i nodes...\n", number, count);
 203     return count;
 204 }
 205
 206 /*
 207 ===========================================================================
 208 CreatePathAStar
 209 This function uses the A* pathfinding algorithm to determine the
 210 shortest path between any two nodes.
 211 It's fairly complex, so I'm not really going to explain it much.
 212 Look up A* and binary heaps for more info.
 213 pathlist stores the ideal path between the nodes, in reverse order,
 214 and the return value is the number of nodes in that path
 215 ===========================================================================
 216 */
 217 int CreatePathAStar(gentity_t *bot, int from, int to, short int *pathlist)
 218 {
 219     //all the data we have to hold...since we can't do dynamic allocation, has to be MAX_NODES
 220     //we can probably lower this later - eg, the open list should never have more than at most a few dozen items on it
 221     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
 222     float gcost[MAX_NODES];
 223     int fcost[MAX_NODES];
 224     char list[MAX_NODES];                                   //0 is neither, 1 is open, 2 is closed - char because it's the smallest data type
 225     short int parent[MAX_NODES];
 226
 227     short int numOpen = 0;
 228     short int atNode, temp, newnode=-1;
 229     qboolean found = qfalse;
 230     int count = -1;
 231     float gc;
 232     int i, u, v, m;
 233     vec3_t vec;
 234
 235     //clear out all the arrays
 236     memset(openlist, 0, sizeof(short int)*(MAX_NODES+1));
 237     memset(fcost, 0, sizeof(int)*MAX_NODES);
 238     memset(list, 0, sizeof(char)*MAX_NODES);
 239     memset(parent, 0, sizeof(short int)*MAX_NODES);
 240     memset(gcost, -1, sizeof(float)*MAX_NODES);
 241
 242     //make sure we have valid data before calculating everything
 243     if ((from == NODE_INVALID) || (to == NODE_INVALID) || (from >= MAX_NODES) || (to >= MAX_NODES) || (from == to))
 244         return -1;
 245
 246     openlist[1] = from;                                     //add the starting node to the open list
 247     numOpen++;
 248     gcost[from] = 0;                                        //its f and g costs are obviously 0
 249     fcost[from] = 0;
 250
 251     while (1)
 252     {
 253         if (numOpen != 0)                                   //if there are still items in the open list
 254         {
 255             //pop the top item off of the list
 256             atNode = openlist[1];
 257             list[atNode] = 2;                               //put the node on the closed list so we don't check it again
 258             numOpen--;
 259
 260             openlist[1] = openlist[numOpen+1];              //move the last item in the list to the top position
 261             v = 1;
 262
 263             //this while loop reorders the list so that the new lowest fcost is at the top again
 264             while (1)
 265             {
 266                 u = v;
 267                 if ((2*u+1) < numOpen)                      //if both children exist
 268                 {
 269                     if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 270                         v = 2*u;
 271                     if (fcost[openlist[v]] >= fcost[openlist[2*u+1]])
 272                         v = 2*u+1;
 273                 }
 274                 else
 275                 {
 276                     if ((2*u) < numOpen)                    //if only one child exists
 277                     {
 278                         if (fcost[openlist[u]] >= fcost[openlist[2*u]])
 279                             v = 2*u;
 280                     }
 281                 }
 282
 283                 if (u != v)                                 //if they're out of order, swap this item with its parent
 284                 {
 285                     temp = openlist[u];
 286                     openlist[u] = openlist[v];
 287                     openlist[v] = temp;
 288                 }
 289                 else
 290                     break;
 291             }
 292
 293             for (i = 0; i < nodes[atNode].enodenum; i++)    //loop through all the links for this node
 294             {
 295                 newnode = nodes[atNode].links[i].targetNode;
 296
 297                                                             //if this path is blocked, skip it
 298                 if (nodes[atNode].links[i].flags & PATH_BLOCKED)
 299                     continue;
 300                                                             //if this path is blocked, skip it
 301                 if (bot->client && (bot->client->ps.eFlags & EF_TANK) && nodes[atNode].links[i].flags & PATH_NOTANKS)
 302                     continue;
 303                 //skip any unreachable nodes
 304                 if (bot->client && (nodes[newnode].type & NODE_ALLY_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_ALLIES))
 305                     continue;
 306                 if (bot->client && (nodes[newnode].type & NODE_AXIS_UNREACHABLE) && (bot->client->sess.sessionTeam == TEAM_AXIS))
 307                     continue;
 308
 309                 if (list[newnode] == 2)                     //if this node is on the closed list, skip it
 310                     continue;
 311
 312                 if (list[newnode] != 1)                     //if this node is not already on the open list
 313                 {
 314                     openlist[++numOpen] = newnode;          //add the new node to the open list
 315                     list[newnode] = 1;
 316                     parent[newnode] = atNode;               //record the node's parent
 317
 318                     if (newnode == to)                      //if we've found the goal, don't keep computing paths!
 319                         break;                              //this will break the 'for' and go all the way to 'if (list[to] == 1)'
 320
 321                                                             //store it's f cost value
 322                     fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 323
 324                     //this loop re-orders the heap so that the lowest fcost is at the top
 325                     m = numOpen;
 326                     while (m != 1)                          //while this item isn't at the top of the heap already
 327                     {
 328                                                             //if it has a lower fcost than its parent
 329                         if (fcost[openlist[m]] <= fcost[openlist[m/2]])
 330                         {
 331                             temp = openlist[m/2];
 332                             openlist[m/2] = openlist[m];
 333                             openlist[m] = temp;             //swap them
 334                             m /= 2;
 335                         }
 336                         else
 337                             break;
 338                     }
 339                 }
 340                 else                                        //if this node is already on the open list
 341                 {
 342                     gc = gcost[atNode];
 343                     VectorSubtract(nodes[newnode].origin, nodes[atNode].origin, vec);
 344                     gc += VectorLength(vec);                //calculate what the gcost would be if we reached this node along the current path
 345
 346                     if (gc < gcost[newnode])                //if the new gcost is less (ie, this path is shorter than what we had before)
 347                     {
 348                         parent[newnode] = atNode;           //set the new parent for this node
 349                         gcost[newnode] = gc;                //and the new g cost
 350
 351                         for (i = 1; i < numOpen; i++)       //loop through all the items on the open list
 352                         {
 353                             if (openlist[i] == newnode)     //find this node in the list
 354                             {
 355                                 //calculate the new fcost and store it
 356                                 fcost[newnode] = GetFCost(to, newnode, parent[newnode], gcost);
 357
 358                                 //reorder the list again, with the lowest fcost item on top
 359                                 m = i;
 360                                 while (m != 1)
 361                                 {
 362                                                             //if the item has a lower fcost than it's parent
 363                                     if (fcost[openlist[m]] < fcost[openlist[m/2]])
 364                                     {
 365                                         temp = openlist[m/2];
 366                                         openlist[m/2] = openlist[m];
 367                                         openlist[m] = temp; //swap them
 368                                         m /= 2;
 369                                     }
 370                                     else
 371                                         break;
 372                                 }
 373                                 break;                      //exit the 'for' loop because we already changed this node
 374                             }                               //if
 375                         }                                   //for
 376                     }                                       //if (gc < gcost[newnode])
 377                 }                                           //if (list[newnode] != 1) --> else
 378             }                                               //for (loop through links)
 379         }                                                   //if (numOpen != 0)
 380         else
 381         {
 382             found = qfalse;                                 //there is no path between these nodes
 383             break;
 384         }
 385
 386         if (list[to] == 1)                                  //if the destination node is on the open list, we're done
 387         {
 388             found = qtrue;
 389             break;
 390         }
 391     }                                                       //while (1)
 392
 393     if (found == qtrue)                                     //if we found a path
 394     {
 395         //G_Printf("%s - path found!\n", bot->client->pers.netname);
 396         count = 0;
 397
 398         temp = to;                                          //start at the end point
 399         while (temp != from)                                //travel along the path (backwards) until we reach the starting point
 400         {
 401             pathlist[count++] = temp;                       //add the node to the pathlist and increment the count
 402             temp = parent[temp];                            //move to the parent of this node to continue the path
 403         }
 404
 405         pathlist[count++] = from;                           //add the beginning node to the end of the pathlist
 406
 407         #ifdef __BOT_SHORTEN_ROUTING__
 408         count = ShortenASTARRoute(pathlist, count);         // This isn't working... Dunno why.. Unique1
 409         #endif                                              //__BOT_SHORTEN_ROUTING__
 410     }
 411     else
 412     {
 413         //G_Printf("^1*** ^4BOT DEBUG^5: (CreatePathAStar) There is no route between node ^7%i^5 and node ^7%i^5.\n", from, to);
 414         count = CreateDumbRoute(from, to, pathlist);
 415
 416         if (count > 0)
 417         {
 418             #ifdef __BOT_SHORTEN_ROUTING__
 419             count = ShortenASTARRoute(pathlist, count);     // This isn't working... Dunno why.. Unique1
 420             #endif                                          //__BOT_SHORTEN_ROUTING__
 421             return count;
 422         }
 423     }
 424
 425     return count;                                           //return the number of nodes in the path, -1 if not found
 426 }
 427
 428 /*
 429 ===========================================================================
 430 GetFCost
 431 Utility function used by A* pathfinding to calculate the
 432 cost to move between nodes towards a goal.  Using the A*
 433 algorithm F = G + H, G here is the distance along the node
 434 paths the bot must travel, and H is the straight-line distance
 435 to the goal node.
 436 Returned as an int because more precision is unnecessary and it
 437 will slightly speed up heap access
 438 ===========================================================================
 439 */
 440 int GetFCost(int to, int num, int parentNum, float *gcost)
 441 {
 442     float gc = 0;
 443     float hc = 0;
 444     vec3_t v;
 445
 446     if (gcost[num] == -1)
 447     {
 448         if (parentNum != -1)
 449         {
 450             gc = gcost[parentNum];
 451             VectorSubtract(nodes[num].origin, nodes[parentNum].origin, v);
 452             gc += VectorLength(v);
 453         }
 454         gcost[num] = gc;
 455     }
 456     else
 457         gc = gcost[num];
 458
 459     VectorSubtract(nodes[to].origin, nodes[num].origin, v);
 460     hc = VectorLength(v);
 461
 462     return (int)(gc + hc);
 463 }
 464 #endif                                                      //__PATHFINDING__