ScummVM API documentation
AIAStar.h
1/* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
19 *
20 */
21
22//K-D Lab / Balmer
23#pragma once
24
25#include "common/multimap.h"
26
27
29//AIAStar::FindPath поиск пути из точки from
30//в точку IsEndPoint.
31//Боле-менее оптимизированный на случай квадратной сетки
32
33/*
34class Heuristic
35{
36 float getH(int x,int y);//Предполагаемые затраты на продвижение из pos1 к окончанию
37 float getG(int x1,int y1,int x2,int y2);//Затраты на продвижение из pos1 в pos2
38 bool IsEndPoint(int x,int y);//Рекурсия должна окончиться здесь
39 //то есть класс AIAStar позволяет задавать несколько точек окончания поиска пути
40};
41*/
42
43namespace QDEngine {
44
45template<class Heuristic, class TypeH = float>
46class AIAStar {
47public:
49
50 struct OnePoint {
51 TypeH g;//Затраты на продвижение до этой точки
52 TypeH h;//Предполагаемые затраты на продвижение до финиша
53 int used;
54 OnePoint *parent;
55 bool is_open;
56
57 inline TypeH f() {
58 return g + h;
59 }
60 };
61protected:
62 int _dx, _dy;
63 OnePoint *_chart;
64 type_point_map _open_map;
65
66 int _is_used_num;//Если _is_used_num==used, то ячейка используется
67
68 int _num_point_examine;//количество посещённых ячеек
69 int _num_find_erase;//Сколько суммарно искали ячейки для удаления
70 Heuristic *_heuristic;
71public:
72 AIAStar();
73 ~AIAStar();
74
75 void init(int dx, int dy);
76 bool findPath(Vect2i from, Heuristic *h, Std::vector<Vect2i> &path, int directions_count = 8);
77 void getStatistic(int *num_point_examine, int *num_find_erase);
78
79 //Debug
80 OnePoint *getInternalBuffer() {
81 return _chart;
82 };
83 int getUsedNum() {
84 return _is_used_num;
85 }
86protected:
87 void clear();
88 inline Vect2i posBy(OnePoint *p) {
89 int offset = p - _chart;
90 Vect2i pos;
91 pos.x = offset % _dx;
92 pos.y = offset / _dx;
93 return pos;
94 }
95};
96
97template<class Heuristic, class TypeH>
98AIAStar<Heuristic, TypeH>::AIAStar() {
99 _chart = NULL;
100 _heuristic = NULL;
101 _num_find_erase = 0;
102 _dx = _dy = 0;
103 _is_used_num = 0;
104 _num_point_examine = 0;
105}
106
107template<class Heuristic, class TypeH>
108void AIAStar<Heuristic, TypeH>::init(int dx_, int dy_) {
109 _dx = dx_;
110 _dy = dy_;
111
112 int size = _dx * _dy;
113 _chart = new OnePoint[size];
114 clear();
115}
116
117template<class Heuristic, class TypeH>
118void AIAStar<Heuristic, TypeH>::clear() {
119 int size = _dx * _dy;
120 _is_used_num = 0;
121 for (int i = 0; i < size; i++)
122 _chart[i].used = 0;
123}
124
125template<class Heuristic, class TypeH>
126AIAStar<Heuristic, TypeH>::~AIAStar() {
127 delete[] _chart;
128}
129
130template<class Heuristic, class TypeH>
131bool AIAStar<Heuristic, TypeH>::findPath(Vect2i from, Heuristic *hr, Std::vector<Vect2i> &path, int directions_count) {
132 _num_point_examine = 0;
133 _num_find_erase = 0;
134
135 _is_used_num++;
136 _open_map.clear();
137 path.clear();
138 if (_is_used_num == 0)
139 clear();//Для того, чтобы вызвалась эта строчка, необходимо гиганское время
140 assert(from.x >= 0 && from.x < _dx && from.y >= 0 && from.y < _dy);
141 _heuristic = hr;
142
143 OnePoint *p = _chart + from.y * _dx + from.x;
144 p->g = 0;
145 p->h = _heuristic->getH(from.x, from.y);
146 p->used = _is_used_num;
147 p->is_open = true;
148 p->parent = NULL;
149
150 _open_map.insert(typename type_point_map::value_type(p->f(), from));
151
152 const int sx[8] = { 0, -1, 0, +1, -1, +1, +1, -1,};
153 const int sy[8] = {-1, 0, +1, 0, -1, -1, +1, +1 };
154
155// const int sx[size_child]={ 0,-1, 0,+1};
156// const int sy[size_child]={-1, 0,+1, 0};
157
158 const int size_child = directions_count;
159
160 while (!_open_map.empty()) {
161 typename type_point_map::iterator low = _open_map.begin();
162 Vect2i pt = (*low).second;
163 OnePoint *parent = _chart + pt.y * _dx + pt.x;
164
165 parent->is_open = false;
166 _open_map.erase(low);
167
168 if (_heuristic->isEndPoint(pt.x, pt.y)) {
169 //сконструировать путь
170 Vect2i vp;
171 while (parent) {
172 vp = posBy(parent);
173 path.push_back(vp);
174
175 if (parent->parent) {
176 Vect2i pp;
177 pp = posBy(parent->parent);
178 assert(abs(vp.x - pp.x) <= 1 &&
179 abs(vp.y - pp.y) <= 1);
180 }
181
182 parent = parent->parent;
183 }
184 assert(vp.x == from.x && vp.y == from.y);
185 Common::reverse(path.begin(), path.end());
186 return true;
187 }
188
189 //для каждого наследника child узла parent
190 for (int i = 0; i < size_child; i++) {
191 Vect2i child = Vect2i(pt.x + sx[i], pt.y + sy[i]);
192 _num_point_examine++;
193
194 if (child.x < 0 || child.y < 0 ||
195 child.x >= _dx || child.y >= _dy)continue;
196 p = _chart + child.y * _dx + child.x;
197
198
199 TypeH addg = _heuristic->getG(pt.x, pt.y, child.x, child.y);
200 TypeH newg = parent->g + addg;
201
202 if (p->used == _is_used_num) {
203 if (!p->is_open)continue;
204 if (p->g <= newg)continue;
205
206 //Удаляем элемент из _open_map
207 TypeH f = p->f();
208 typename type_point_map::iterator cur = _open_map.find(p->f());
209 bool erase = false;
210 while (cur != _open_map.end()) {
211 if ((*cur).first != f)break;
212 if ((*cur).second.x == child.x && (*cur).second.y == child.y) {
213 _open_map.erase(cur);
214 erase = true;
215 break;
216 }
217 _num_find_erase++;
218 cur++;
219 }
220 _num_find_erase++;
221 //assert(erase);
222 if (!erase)
223 continue;
224 }
225
226 p->parent = parent;
227 /*
228 {
229 Vect2i pp=posBy(parent);
230 Vect2i pc=posBy(p);
231 assert(abs(pc.x-pp.x)<=1 &&
232 abs(pc.y-pp.y)<=1);
233 }
234 */
235 p->g = newg;
236 p->h = _heuristic->getH(child.x, child.y);
237
238 _open_map.insert(typename type_point_map::value_type(p->f(), child));
239
240 p->is_open = true;
241 p->used = _is_used_num;
242 }
243 }
244
245 return false;
246}
247
248template<class Heuristic, class TypeH>
249void AIAStar<Heuristic, TypeH>::getStatistic(
250 int *p_num_point_examine, int *p_num_find_erase) {
251 if (p_num_point_examine)
252 *p_num_point_examine = _num_point_examine;
253 if (p_num_find_erase)
254 *p_num_find_erase = _num_find_erase;
255}
256
258//AIAStarGraph - Так-же поиск пути, но ориентированный на поиск в произвольном графе
259/*
260class Node
261{
262 typedef ... iterator;
263 iterator begin();//Работа со списком связанных с этой Node нод.
264 iterator end();
265
266 void* AIAStarPointer;//Используется в AIAStarGraph
267};
268
269class Heuristic
270{
271 float getH(Node* pos);//Предполагаемые затраты на продвижение из pos1 к окончанию
272 float getG(Node* pos1,Node* pos2);//Затраты на продвижение из pos1 в pos2
273 bool IsEndPoint(Node* pos);//Рекурсия должна окончиться здесь
274 //то есть класс AIAStar позволяет задавать несколько точек окончания поиска пути
275};
276*/
277
278template<class Heuristic, class Node, class TypeH = float>
280public:
281 struct OnePoint;
283
284 struct OnePoint {
285 TypeH g;//Затраты на продвижение до этой точки
286 TypeH h;//Предполагаемые затраты на продвижение до финиша
287 int used;
288 OnePoint *parent;
289 bool is_open;
290
291 Node *node;
292 typename type_point_map::iterator self_it;
293
294 inline TypeH f() {
295 return g + h;
296 }
297 };
298protected:
300 type_point_map _open_map;
301
302 int _is_used_num;//Если _is_used_num==used, то ячейка используется
303
304 int _num_point_examine;//количество посещённых ячеек
305 int _num_find_erase;//Сколько суммарно искали ячейки для удаления
306 Heuristic *_heuristic;
307public:
308 AIAStarGraph();
310
311 //Общее количество узлов. Константа, которая не должна меняться,
312 //пока существует класс, указывающий на неё.
313 void init(Std::vector<Node> &all_node);
314
315 bool findPath(Node *from, Heuristic *h, Std::vector<Node *> &path);
316 void getStatistic(int *num_point_examine, int *num_find_erase);
317
318 //Debug
319 OnePoint *getInternalBuffer() {
320 return _chart;
321 };
322 int getUsedNum() {
323 return _is_used_num;
324 }
325protected:
326 void clear();
327 inline Node *posBy(OnePoint *p) {
328 return p->node;
329 }
330};
331
332template<class Heuristic, class Node, class TypeH>
333AIAStarGraph<Heuristic, Node, TypeH>::AIAStarGraph() {
334 _heuristic = NULL;
335 _is_used_num = 0;
336 _num_point_examine = 0;
337 _num_find_erase = 0;
338}
339
340template<class Heuristic, class Node, class TypeH>
341void AIAStarGraph<Heuristic, Node, TypeH>::init(Std::vector<Node> &all_node) {
342 int size = all_node.size();
343 _chart.resize(size);
344
345 for (int i = 0; i < size; i++) {
346 OnePoint *c = &_chart[i];
347 c->node = &all_node[i];
348 c->node->AIAStarPointer = (void *)c;
349 }
350 clear();
351}
352
353template<class Heuristic, class Node, class TypeH>
354void AIAStarGraph<Heuristic, Node, TypeH>::clear() {
355 _is_used_num = 0;
356 for (auto &it : _chart) {
357 it.used = 0;
358 }
359}
360
361template<class Heuristic, class Node, class TypeH>
362AIAStarGraph<Heuristic, Node, TypeH>::~AIAStarGraph() {
363}
364
365template<class Heuristic, class Node, class TypeH>
366bool AIAStarGraph<Heuristic, Node, TypeH>::findPath(Node *from, Heuristic *hr, Std::vector<Node *> &path) {
367 _num_point_examine = 0;
368 _num_find_erase = 0;
369
370 _is_used_num++;
371 _open_map.clear();
372 path.clear();
373 if (_is_used_num == 0)
374 clear();//Для того, чтобы вызвалась эта строчка, необходимо гиганское время
375 _heuristic = hr;
376
377 OnePoint *p = (OnePoint *)from->AIAStarPointer;
378 Node *from_node = p->node;
379 p->g = 0;
380 p->h = _heuristic->getH(p->node);
381 p->used = _is_used_num;
382 p->is_open = true;
383 p->parent = NULL;
384
385 p->self_it = _open_map.insert(type_point_map::value_type(p->f(), p));
386
387 while (!_open_map.empty()) {
388 typename type_point_map::iterator low = _open_map.begin();
389
390 OnePoint *parent = low->second;
391 Node *node = parent->node;
392
393 parent->is_open = false;
394 _open_map.erase(low);
395
396 if (_heuristic->IsEndPoint(node)) {
397 //сконструировать путь
398 Node *np;
399 while (parent) {
400 np = PosBy(parent);
401 assert(parent->used == _is_used_num);
402
403 path.push_back(np);
404 parent = parent->parent;
405 }
406 assert(np == from_node);
407 reverse(path.begin(), path.end());
408 return true;
409 }
410
411 //для каждого наследника child узла parent
412 for (auto &it : *node) {
413 Node *cur_node = *it;
414 OnePoint *op = (OnePoint *)cur_node->AIAStarPointer;
415 _num_point_examine++;
416
417 TypeH addg = _heuristic->getG(node, cur_node);
418 TypeH newg = parent->g + addg;
419
420 if (op->used == _is_used_num) {
421 if (!op->is_open)continue;
422 if (op->g <= newg)continue;
423
424 _open_map.erase(op->self_it);
425 _num_find_erase++;
426 }
427
428 op->parent = parent;
429 op->g = newg;
430 op->h = _heuristic->getH(cur_node);
431
432 op->self_it = _open_map.insert(type_point_map::value_type(op->f(), op));
433
434 op->is_open = true;
435 op->used = _is_used_num;
436 }
437 }
438
439 return false;
440}
441
442template<class Heuristic, class Node, class TypeH>
443void AIAStarGraph<Heuristic, Node, TypeH>::getStatistic(
444 int *p_num_point_examine, int *p_num_find_erase) {
445 if (p_num_point_examine)
446 *p_num_point_examine = _num_point_examine;
447 if (p_num_find_erase)
448 *p_num_find_erase = _num_find_erase;
449}
450
452
453/*
454struct Maps
455{
456 //Значение чего нибудь в точке (x,y)
457 TypeH get(int x,int y);
458
459 //Дальнейшие поиски можно прекратить
460 bool IsOptiumGood(TypeH optium,int x,int y);
461};
462*/
463
464//Ищет минимальное значение, но не по всей карте
465template<class Maps>
466Vect2i AIFindMinium(int x, int y,
467 Maps &maps,
468 int dx, int dy) {
469 typename Maps::TypeH optium = maps.get(x, y);
470 int optiumx = x, optiumy = y;
471
472 int maxi = MAX(MAX(x, dx - x), MAX(y, dy - y));
473 for (int i = 1; i < maxi; i++) {
474 int curx, cury;
475 int xmin = MAX(0, x - i), xmax = MIN(dx - 1, x + i);
476 int ymin = MAX(0, y - i), ymax = MIN(dy - 1, y + i);
477 //up
478 cury = y - i;
479 if (cury >= 0)
480 for (curx = xmin; curx <= xmax; curx++) {
481 typename Maps::TypeH o = maps.get(curx, cury);
482 if (o < optium) {
483 optium = o;
484 optiumx = curx;
485 optiumy = cury;
486 }
487 }
488
489 //down
490 cury = y + i;
491 if (cury < dy)
492 for (curx = xmin; curx <= xmax; curx++) {
493 typename Maps::TypeH o = maps.get(curx, cury);
494 if (o < optium) {
495 optium = o;
496 optiumx = curx;
497 optiumy = cury;
498 }
499 }
500
501 //left
502 curx = x - i;
503 if (curx >= 0)
504 for (cury = ymin; cury <= ymax; cury++) {
505 typename Maps::TypeH o = maps.get(curx, cury);
506 if (o < optium) {
507 optium = o;
508 optiumx = curx;
509 optiumy = cury;
510 }
511 }
512
513 //right
514 curx = x + i;
515 if (curx < dx)
516 for (cury = ymin; cury <= ymax; cury++) {
517 typename Maps::TypeH o = maps.get(curx, cury);
518 if (o < optium) {
519 optium = o;
520 optiumx = curx;
521 optiumy = cury;
522 }
523 }
524
525 if (maps.IsOptiumGood(optium, optiumx, optiumy))
526 break;
527 }
528
529 Vect2i p = {optiumx, optiumy};
530 return p;
531}
532} // namespace QDEngine
iterator end()
Definition: array.h:380
size_type size() const
Definition: array.h:316
void clear()
Definition: array.h:321
void push_back(const T &element)
Definition: array.h:181
iterator begin()
Definition: array.h:375
Definition: multimap.h:34
Definition: AIAStar.h:279
Definition: AIAStar.h:46
Definition: xmath.h:268
Definition: vector.h:39
T MIN(T a, T b)
Definition: util.h:63
T MAX(T a, T b)
Definition: util.h:66
Базовый класс для игровых ресурсов.
Definition: console.h:28
Definition: lobject.h:332
Definition: AIAStar.h:50
Definition: AIAStar.h:284