2 * Copyright (C) 2005-2009 MaNGOS <http://getmangos.com/>
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.
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.
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
20 creature_movement Table
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';
35 #include "WaypointMovementGenerator.h"
36 #include "ObjectMgr.h"
38 #include "DestinationHolderImp.h"
39 #include "CreatureAI.h"
40 #include "WaypointManager.h"
41 #include "WorldPacket.h"
45 //-----------------------------------------------//
46 void WaypointMovementGenerator
<Creature
>::LoadPath(Creature
&c
)
48 sLog
.outDetail("LoadPath: loading waypoint path for creature %d,%d", c
.GetGUIDLow(), c
.GetDBTableGUIDLow());
50 i_path
= WaypointMgr
.GetPath(c
.GetDBTableGUIDLow());
53 sLog
.outErrorDb("WaypointMovementGenerator::LoadPath: creature %s (Entry: %u GUID: %d) doesn't have waypoint path",
54 c
.GetName(), c
.GetEntry(), c
.GetDBTableGUIDLow());
58 uint32 node_count
= i_path
->size();
59 i_hasDone
.resize(node_count
);
60 for(uint32 i
= 0; i
< node_count
-1; ++i
)
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;
70 void WaypointMovementGenerator
<Creature
>::ClearWaypoints()
75 void WaypointMovementGenerator
<Creature
>::Initialize()
79 bool WaypointMovementGenerator
<Creature
>::Update(Creature
&creature
, const uint32
&diff
)
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
))
89 // prevent a crash at empty waypoint path.
90 if(!i_path
|| i_path
->empty())
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())
99 CreatureTraveller
traveller(creature
);
101 i_nextMoveTime
.Update(diff
);
102 i_destinationHolder
.UpdateTraveller(traveller
, diff
, false, true);
104 // creature has been stopped in middle of the waypoint segment
105 if (!i_destinationHolder
.HasArrived() && creature
.IsStopped())
107 if( i_nextMoveTime
.Passed()) // Timer has elapsed, meaning this part controlled it
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());
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
127 return true; // Abort here this update
130 if( creature
.IsStopped())
132 uint32 idx
= i_currentNode
> 0 ? i_currentNode
-1 : i_path
->size()-1;
136 if (i_path
->at(idx
).orientation
!=100)
137 creature
.SetOrientation(i_path
->at(idx
).orientation
);
139 if(WaypointBehavior
*behavior
= i_path
->at(idx
).behavior
)
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])
149 // Not only one text is set
150 if( behavior
->textid
[1] )
152 // Select one from max 5 texts (0 and 1 laready checked)
154 for( ; i
< MAX_WAYPOINT_TEXT
; ++i
)
155 if( !behavior
->textid
[i
] )
158 creature
.Say(behavior
->textid
[rand() % i
], 0, 0);
161 creature
.Say(behavior
->textid
[0], 0, 0);
163 } // wpBehaviour found
165 i_hasDone
[idx
] = true;
166 MovementInform(creature
);
167 } // HasDone == false
168 } // i_creature.IsStopped()
170 if( i_nextMoveTime
.Passed() ) // This is at the end of waypoint segment or has been stopped by player
172 if( creature
.IsStopped() ) // If stopped then begin a new move segment
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;
182 if (i_path
->at(idx
).orientation
!=100)
183 creature
.SetOrientation(i_path
->at(idx
).orientation
);
185 if(WaypointBehavior
*behavior
= i_path
->at(idx
).behavior
)
187 i_hasDone
[idx
] = false;
188 if(behavior
->model2
!= 0)
189 creature
.SetDisplayId(behavior
->model2
);
191 creature
.SetUInt32Value(UNIT_NPC_EMOTESTATE
, 0);
194 else // If not stopped then stop it and set the reset of TimeTracker to waittime
196 creature
.StopMoving();
197 SetStoppedByPlayer(false);
198 i_nextMoveTime
.Reset(i_path
->at(i_currentNode
).delay
);
200 if( i_currentNode
>= i_path
->size() )
207 void WaypointMovementGenerator
<Creature
>::MovementInform(Creature
&unit
)
210 unit
.AI()->MovementInform(WAYPOINT_MOTION_TYPE
, i_currentNode
);
213 //----------------------------------------------------//
214 void FlightPathMovementGenerator::LoadPath(Player
&)
216 objmgr
.GetTaxiPathNodes(i_pathId
, i_path
,i_mapIds
);
219 uint32
FlightPathMovementGenerator::GetPathAtMapEnd() const
221 if(i_currentNode
>= i_mapIds
.size())
222 return i_mapIds
.size();
224 uint32 curMapId
= i_mapIds
[i_currentNode
];
225 for(uint32 i
= i_currentNode
; i
< i_mapIds
.size(); ++i
)
227 if(i_mapIds
[i
] != curMapId
)
231 return i_mapIds
.size();
234 void FlightPathMovementGenerator::Initialize(Player
&player
)
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
);
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);
244 player
.SendMonsterMoveByPath(GetPath(),GetCurrentNode(),GetPathAtMapEnd(),MONSTER_MOVE_SPLINE_FLY
);
247 void FlightPathMovementGenerator::Finalize(Player
& player
)
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
);
253 i_destinationHolder
.GetLocationNow(player
.GetBaseMap(), x
, y
, z
);
254 player
.SetPosition(x
, y
, z
, player
.GetOrientation());
257 player
.RemoveFlag(UNIT_FIELD_FLAGS
,UNIT_FLAG_DISABLE_MOVE
| UNIT_FLAG_TAXI_FLIGHT
);
259 if(player
.m_taxi
.empty())
261 player
.getHostilRefManager().setOnlineOfflineState(true);
262 if(player
.pvpInfo
.inHostileArea
)
263 player
.CastSpell(&player
, 2479, true);
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
272 bool FlightPathMovementGenerator::Update(Player
&player
, const uint32
&diff
)
274 if( MovementInProgress() )
276 Traveller
<Player
> traveller(player
);
277 if( i_destinationHolder
.UpdateTraveller(traveller
, diff
, false) )
279 i_destinationHolder
.ResetUpdate(FLIGHT_TRAVEL_UPDATE
);
280 if( i_destinationHolder
.HasArrived() )
282 uint32 curMap
= i_mapIds
[i_currentNode
];
284 if( MovementInProgress() )
286 DEBUG_LOG("loading node %u for player %s", i_currentNode
, player
.GetName());
287 if(i_mapIds
[i_currentNode
]==curMap
)
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);
303 // we have arrived at the end of the path
307 void FlightPathMovementGenerator::SetCurrentNodeAfterTeleport()
312 uint32 map0
= i_mapIds
[0];
313 for(int i
= 1; i
< i_mapIds
.size(); ++i
)
315 if(i_mapIds
[i
]!=map0
)
324 // Unique1's ASTAR Pathfinding Code... For future use & reference...
327 #ifdef __PATHFINDING__
329 int GetFCost(int to
, int num
, int parentNum
, float *gcost
); // Below...
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
];
340 for (temp
= number
; temp
>= 0; temp
--)
342 qboolean shortened
= qfalse
;
344 for (temp2
= 0; temp2
< temp
; temp2
++)
346 for (link
= 0; link
< nodes
[pathlist
[temp
]].enodenum
; link
++)
348 if (nodes
[pathlist
[temp
]].links
[link
].flags
& PATH_BLOCKED
)
351 //if ((bot->client->ps.eFlags & EF_TANK) && nodes[bot->current_node].links[link].flags & PATH_NOTANKS) //if this path is blocked, skip it
354 //if (nodes[nodes[pathlist[temp]].links[link].targetNode].origin[2] > nodes[pathlist[temp]].origin[2] + 32)
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))
361 temppathlist
[count
] = pathlist
[temp2
];
372 temppathlist
[count
] = pathlist
[temp
];
379 for (temp
= 0; temp
< count
; temp
++)
381 pathlist
[temp
] = temppathlist
[upto
];
385 G_Printf("ShortenASTARRoute: Path size reduced from %i to %i nodes...n", number
, count
);
390 ===========================================================================
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 ===========================================================================
400 int CreatePathAStar(gentity_t
*bot
, int from
, int to
, short int *pathlist
)
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
];
410 short int numOpen
= 0;
411 short int atNode
, temp
, newnode
=-1;
412 qboolean found
= qfalse
;
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
);
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
))
429 openlist
[1] = from
; //add the starting node to the open list
431 gcost
[from
] = 0; //its f and g costs are obviously 0
436 if (numOpen
!= 0) //if there are still items in the open list
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
443 openlist
[1] = openlist
[numOpen
+1]; //move the last item in the list to the top position
446 //this while loop reorders the list so that the new lowest fcost is at the top again
450 if ((2*u
+1) < numOpen
) //if both children exist
452 if (fcost
[openlist
[u
]] >= fcost
[openlist
[2*u
]])
454 if (fcost
[openlist
[v
]] >= fcost
[openlist
[2*u
+1]])
459 if ((2*u
) < numOpen
) //if only one child exists
461 if (fcost
[openlist
[u
]] >= fcost
[openlist
[2*u
]])
466 if (u
!= v
) //if they're out of order, swap this item with its parent
469 openlist
[u
] = openlist
[v
];
476 for (i
= 0; i
< nodes
[atNode
].enodenum
; ++i
) //loop through all the links for this node
478 newnode
= nodes
[atNode
].links
[i
].targetNode
;
480 //if this path is blocked, skip it
481 if (nodes
[atNode
].links
[i
].flags
& PATH_BLOCKED
)
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
)
486 //skip any unreachable nodes
487 if (bot
->client
&& (nodes
[newnode
].type
& NODE_ALLY_UNREACHABLE
) && (bot
->client
->sess
.sessionTeam
== TEAM_ALLIES
))
489 if (bot
->client
&& (nodes
[newnode
].type
& NODE_AXIS_UNREACHABLE
) && (bot
->client
->sess
.sessionTeam
== TEAM_AXIS
))
492 if (list
[newnode
] == 2) //if this node is on the closed list, skip it
495 if (list
[newnode
] != 1) //if this node is not already on the open list
497 openlist
[++numOpen
] = newnode
; //add the new node to the open list
499 parent
[newnode
] = atNode
; //record the node's parent
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)'
504 //store it's f cost value
505 fcost
[newnode
] = GetFCost(to
, newnode
, parent
[newnode
], gcost
);
507 //this loop re-orders the heap so that the lowest fcost is at the top
509 while (m
!= 1) //while this item isn't at the top of the heap already
511 //if it has a lower fcost than its parent
512 if (fcost
[openlist
[m
]] <= fcost
[openlist
[m
/2]])
514 temp
= openlist
[m
/2];
515 openlist
[m
/2] = openlist
[m
];
516 openlist
[m
] = temp
; //swap them
523 else //if this node is already on the open list
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
529 if (gc
< gcost
[newnode
]) //if the new gcost is less (ie, this path is shorter than what we had before)
531 parent
[newnode
] = atNode
; //set the new parent for this node
532 gcost
[newnode
] = gc
; //and the new g cost
534 for (i
= 1; i
< numOpen
; ++i
) //loop through all the items on the open list
536 if (openlist
[i
] == newnode
) //find this node in the list
538 //calculate the new fcost and store it
539 fcost
[newnode
] = GetFCost(to
, newnode
, parent
[newnode
], gcost
);
541 //reorder the list again, with the lowest fcost item on top
545 //if the item has a lower fcost than it's parent
546 if (fcost
[openlist
[m
]] < fcost
[openlist
[m
/2]])
548 temp
= openlist
[m
/2];
549 openlist
[m
/2] = openlist
[m
];
550 openlist
[m
] = temp
; //swap them
556 break; //exit the 'for' loop because we already changed this node
559 } //if (gc < gcost[newnode])
560 } //if (list[newnode] != 1) --> else
561 } //for (loop through links)
562 } //if (numOpen != 0)
565 found
= qfalse
; //there is no path between these nodes
569 if (list
[to
] == 1) //if the destination node is on the open list, we're done
576 if (found
== qtrue
) //if we found a path
578 //G_Printf("%s - path found!n", bot->client->pers.netname);
581 temp
= to
; //start at the end point
582 while (temp
!= from
) //travel along the path (backwards) until we reach the starting point
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
588 pathlist
[count
++] = from
; //add the beginning node to the end of the pathlist
590 #ifdef __BOT_SHORTEN_ROUTING__
591 count
= ShortenASTARRoute(pathlist
, count
); // This isn't working... Dunno why.. Unique1
592 #endif //__BOT_SHORTEN_ROUTING__
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
);
601 #ifdef __BOT_SHORTEN_ROUTING__
602 count
= ShortenASTARRoute(pathlist
, count
); // This isn't working... Dunno why.. Unique1
603 #endif //__BOT_SHORTEN_ROUTING__
608 return count
; //return the number of nodes in the path, -1 if not found
612 ===========================================================================
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
619 Returned as an int because more precision is unnecessary and it
620 will slightly speed up heap access
621 ===========================================================================
623 int GetFCost(int to
, int num
, int parentNum
, float *gcost
)
629 if (gcost
[num
] == -1)
633 gc
= gcost
[parentNum
];
634 VectorSubtract(nodes
[num
].origin
, nodes
[parentNum
].origin
, v
);
635 gc
+= VectorLength(v
);
642 VectorSubtract(nodes
[to
].origin
, nodes
[num
].origin
, v
);
643 hc
= VectorLength(v
);
645 return (int)(gc
+ hc
);
647 #endif //__PATHFINDING__