1 /*
2 * Copyright 2011-2012 Arx Libertatis Team (see the AUTHORS file)
3 *
4 * This file is part of Arx Libertatis.
5 *
6 * Arx Libertatis is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * Arx Libertatis is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with Arx Libertatis. If not, see <http://www.gnu.org/licenses/>.
18 */
19 /* Based on:
20 ===========================================================================
21 ARX FATALIS GPL Source Code
22 Copyright (C) 1999-2010 Arkane Studios SA, a ZeniMax Media company.
23
24 This file is part of the Arx Fatalis GPL Source Code ('Arx Fatalis Source Code').
25
26 Arx Fatalis Source Code is free software: you can redistribute it and/or modify it under the terms of the GNU General Public
27 License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
28
29 Arx Fatalis Source Code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
30 warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
31
32 You should have received a copy of the GNU General Public License along with Arx Fatalis Source Code. If not, see
33 <http://www.gnu.org/licenses/>.
34
35 In addition, the Arx Fatalis Source Code is also subject to certain additional terms. You should have received a copy of these
36 additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Arx
37 Fatalis Source Code. If not, please request a copy in writing from Arkane Studios at the address below.
38
39 If you have questions concerning this license or the applicable additional terms, you may contact in writing Arkane Studios, c/o
40 ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
41 ===========================================================================
42 */
43 // Code: Cyril Meynier
44 //
45 // Copyright (c) 1999-2001 ARKANE Studios SA. All rights reserved
46
47 #include "ai/PathFinderManager.h"
48
49 #include <cstring>
50 #include <cstdlib>
51 #include <algorithm>
52
53 #include "ai/PathFinder.h"
54 #include "game/Entity.h"
55 #include "game/NPC.h"
56 #include "graphics/Math.h"
57 #include "platform/Thread.h"
58 #include "platform/Lock.h"
59 #include "physics/Anchors.h"
60 #include "scene/Light.h"
61
62 using std::memcpy;
63
64
65 static const float PATHFINDER_HEURISTIC_MIN = 0.2f;
66 static const float PATHFINDER_HEURISTIC_MAX = PathFinder::HEURISTIC_MAX;
67 static const float PATHFINDER_HEURISTIC_RANGE = PATHFINDER_HEURISTIC_MAX
68 - PATHFINDER_HEURISTIC_MIN;
69 static const float PATHFINDER_DISTANCE_MAX = 5000.0f;
70
71 // Pathfinder Definitions
72 static unsigned long PATHFINDER_UPDATE_INTERVAL = 10;
73
74 PATHFINDER_REQUEST pr;
75 long PATHFINDER_WORKING = 0;
76
77 class PathFinderThread : public StoppableThread {
78
79 void run();
80
81 };
82
83 static PathFinderThread * pathfinder = NULL;
84 static Lock * mutex = NULL;
85
86 struct PATHFINDER_QUEUE_ELEMENT {
87 PATHFINDER_REQUEST req;
88 PATHFINDER_QUEUE_ELEMENT * next;
89 long valid;
90 };
91
92 static PATHFINDER_QUEUE_ELEMENT * pathfinder_queue_start = NULL;
93
94 // An Io can request Pathfinding only once so we insure that it's always the case.
95 // A new pathfinder request from the same IO will overwrite the precedent.
PATHFINDER_Find_ioid(Entity * io)96 static PATHFINDER_QUEUE_ELEMENT * PATHFINDER_Find_ioid(Entity * io) {
97
98 if (!pathfinder_queue_start) return NULL;
99
100 PATHFINDER_QUEUE_ELEMENT * cur = pathfinder_queue_start;
101
102 while(cur) {
103 if (cur->req.ioid == io) return cur->valid ? cur : NULL;
104
105 cur = cur->next;
106 }
107
108 return NULL;
109 }
110
111 // Adds a Pathfinder Search Element to the pathfinder queue.
EERIE_PATHFINDER_Add_To_Queue(PATHFINDER_REQUEST * req)112 bool EERIE_PATHFINDER_Add_To_Queue(PATHFINDER_REQUEST * req) {
113
114 if(!pathfinder) {
115 return false;
116 }
117
118 Autolock lock(mutex);
119
120 PATHFINDER_QUEUE_ELEMENT * cur = pathfinder_queue_start;
121
122 PATHFINDER_QUEUE_ELEMENT * temp;
123
124 // If this NPC is already requesting a Pathfinding then either
125 // try to Override it or add it to queue if it is currently being
126 // processed.
127 temp = PATHFINDER_Find_ioid(req->ioid);
128
129 if(temp && temp->valid && temp != pathfinder_queue_start) {
130 temp->valid = 0;
131 memcpy(&temp->req, req, sizeof(PATHFINDER_REQUEST));
132 temp->valid = 1;
133 return true;
134 }
135
136 // Create a New element for the queue
137 temp = (PATHFINDER_QUEUE_ELEMENT *)malloc(sizeof(PATHFINDER_QUEUE_ELEMENT));
138
139 if(!temp) {
140 return false;
141 }
142
143 // Fill this New element with new request
144 memcpy(&temp->req, req, sizeof(PATHFINDER_REQUEST));
145 temp->valid = 1;
146
147 // No queue start ? then this element becomes the queue start
148 if(!cur) {
149 temp->next = NULL;
150 pathfinder_queue_start = temp;
151
152 } else if((req->ioid->_npcdata->behavior & (BEHAVIOUR_MOVE_TO | BEHAVIOUR_FLEE
153 | BEHAVIOUR_LOOK_FOR)) && cur->next) {
154 // priority: insert as second element of queue
155 temp->next = cur->next;
156 cur->next = temp;
157
158 } else {
159
160 // add to end of queue
161 temp->next = NULL;
162
163 if(!pathfinder_queue_start) {
164 pathfinder_queue_start = temp;
165 return true;
166 } else {
167 while(cur->next) {
168 cur = cur->next;
169 }
170 cur->next = temp;
171 }
172 }
173
174 return true;
175 }
176
EERIE_PATHFINDER_Get_Queued_Number()177 long EERIE_PATHFINDER_Get_Queued_Number() {
178
179 Autolock lock(mutex);
180
181 PATHFINDER_QUEUE_ELEMENT * cur = pathfinder_queue_start;
182
183 long count = 0;
184
185 while (cur) cur = cur->next, count++;
186
187 return count;
188 }
189
EERIE_PATHFINDER_Clear_Private()190 static void EERIE_PATHFINDER_Clear_Private() {
191
192 PATHFINDER_QUEUE_ELEMENT * cur = pathfinder_queue_start;
193 PATHFINDER_QUEUE_ELEMENT * next;
194
195 while(cur) {
196 next = cur->next;
197 free(cur);
198 cur = next;
199 }
200
201 pathfinder_queue_start = NULL;
202
203 }
204
205
EERIE_PATHFINDER_Clear()206 void EERIE_PATHFINDER_Clear() {
207
208 if(!pathfinder) {
209 return;
210 }
211
212 Autolock lock(mutex);
213
214 EERIE_PATHFINDER_Clear_Private();
215
216 }
217
218 // Retrieves & Removes next Pathfind request from queue
EERIE_PATHFINDER_Get_Next_Request(PATHFINDER_REQUEST * request)219 static bool EERIE_PATHFINDER_Get_Next_Request(PATHFINDER_REQUEST * request) {
220
221 if(!request || !pathfinder_queue_start || !pathfinder_queue_start->valid) {
222 return false;
223 }
224
225 PATHFINDER_QUEUE_ELEMENT * cur = pathfinder_queue_start;
226
227 if ((cur->req.ioid)
228 && (cur->req.ioid->ioflags & IO_NPC)
229 && (cur->req.ioid->_npcdata->behavior == BEHAVIOUR_NONE)) {
230 pathfinder_queue_start = cur->next;
231 free(cur);
232 return false;
233 }
234
235 memcpy(request, &cur->req, sizeof(PATHFINDER_REQUEST));
236 pathfinder_queue_start = cur->next;
237 free(cur);
238
239 return true;
240 }
241
242 // Pathfinder Thread
run()243 void PathFinderThread::run() {
244
245 EERIE_BACKGROUND * eb = ACTIVEBKG;
246 PathFinder pathfinder(eb->nbanchors, eb->anchors,
247 MAX_LIGHTS, (EERIE_LIGHT **)GLight);
248
249 while(!isStopRequested()) {
250
251 mutex->lock();
252
253 PATHFINDER_WORKING = 1;
254
255 if (EERIE_PATHFINDER_Get_Next_Request(&pr) && pr.isvalid)
256 {
257
258 PATHFINDER_REQUEST curpr;
259 memcpy(&curpr, &pr, sizeof(PATHFINDER_REQUEST));
260 PATHFINDER_WORKING = 2;
261
262 if (curpr.ioid && curpr.ioid->_npcdata)
263 {
264 float heuristic(PATHFINDER_HEURISTIC_MAX);
265
266 pathfinder.setCylinder(curpr.ioid->physics.cyl.radius, curpr.ioid->physics.cyl.height);
267
268 bool stealth = (curpr.ioid->_npcdata->behavior & (BEHAVIOUR_SNEAK | BEHAVIOUR_HIDE))
269 == (BEHAVIOUR_SNEAK | BEHAVIOUR_HIDE);
270
271
272 PathFinder::Result result;
273
274 if ((curpr.ioid->_npcdata->behavior & BEHAVIOUR_MOVE_TO)
275 || (curpr.ioid->_npcdata->behavior & BEHAVIOUR_GO_HOME))
276 {
277 float distance = fdist(ACTIVEBKG->anchors[curpr.from].pos, ACTIVEBKG->anchors[curpr.to].pos);
278
279 if (distance < PATHFINDER_DISTANCE_MAX)
280 heuristic = PATHFINDER_HEURISTIC_MIN
281 + PATHFINDER_HEURISTIC_RANGE * (distance / PATHFINDER_DISTANCE_MAX);
282
283 pathfinder.setHeuristic(heuristic);
284 pathfinder.move(curpr.from, curpr.to, result, stealth);
285 }
286 else if (curpr.ioid->_npcdata->behavior & BEHAVIOUR_WANDER_AROUND)
287 {
288 if (curpr.ioid->_npcdata->behavior_param < PATHFINDER_DISTANCE_MAX)
289 heuristic = PATHFINDER_HEURISTIC_MIN
290 + PATHFINDER_HEURISTIC_RANGE
291 * (curpr.ioid->_npcdata->behavior_param / PATHFINDER_DISTANCE_MAX);
292
293 pathfinder.setHeuristic(heuristic);
294 pathfinder.wanderAround(curpr.from, curpr.ioid->_npcdata->behavior_param, result, stealth);
295 }
296 else if (curpr.ioid->_npcdata->behavior & (BEHAVIOUR_FLEE | BEHAVIOUR_HIDE))
297 {
298 if (curpr.ioid->_npcdata->behavior_param < PATHFINDER_DISTANCE_MAX)
299 heuristic = PATHFINDER_HEURISTIC_MIN
300 + PATHFINDER_HEURISTIC_RANGE
301 * (curpr.ioid->_npcdata->behavior_param / PATHFINDER_DISTANCE_MAX);
302
303 pathfinder.setHeuristic(heuristic);
304 float safedist = curpr.ioid->_npcdata->behavior_param
305 + fdist(curpr.ioid->target, curpr.ioid->pos);
306
307 pathfinder.flee(curpr.from, curpr.ioid->target, safedist, result, stealth);
308 }
309 else if (curpr.ioid->_npcdata->behavior & BEHAVIOUR_LOOK_FOR)
310 {
311 float distance = fdist(curpr.ioid->pos, curpr.ioid->target);
312
313 if (distance < PATHFINDER_DISTANCE_MAX)
314 heuristic = PATHFINDER_HEURISTIC_MIN
315 + PATHFINDER_HEURISTIC_RANGE * (distance / PATHFINDER_DISTANCE_MAX);
316
317 pathfinder.setHeuristic(heuristic);
318 pathfinder.lookFor(curpr.from, curpr.ioid->target,
319 curpr.ioid->_npcdata->behavior_param, result, stealth);
320 }
321
322 if(!result.empty()) {
323 unsigned short * list = (unsigned short*)malloc(result.size() * sizeof(unsigned short));
324 std::copy(result.begin(), result.end(), list);
325 *(curpr.returnlist) = list;
326 }
327 *(curpr.returnnumber) = result.size();
328
329 }
330 }
331
332 PATHFINDER_WORKING = 0;
333
334 mutex->unlock();
335 sleep(PATHFINDER_UPDATE_INTERVAL);
336 }
337
338 // fix leaks memory but freeze characters
339 // pathfinder.Clean();
340
341 PATHFINDER_WORKING = 0;
342
343 }
344
EERIE_PATHFINDER_Release()345 void EERIE_PATHFINDER_Release() {
346
347 if(!pathfinder) {
348 return;
349 }
350
351 mutex->lock();
352
353 EERIE_PATHFINDER_Clear_Private();
354
355 pathfinder->stop();
356
357 delete pathfinder, pathfinder = NULL;
358
359 mutex->unlock(), delete mutex, mutex = NULL;
360 }
361
EERIE_PATHFINDER_Create()362 void EERIE_PATHFINDER_Create() {
363
364 if(pathfinder) {
365 EERIE_PATHFINDER_Release();
366 }
367
368 if(!mutex) {
369 mutex = new Lock();
370 }
371
372 pathfinder = new PathFinderThread();
373 pathfinder->setThreadName("Pathfinder");
374 pathfinder->start();
375 }
376