25#include "common/multimap.h"
45template<
class Heuristic,
class TypeH =
float>
68 int _num_point_examine;
70 Heuristic *_heuristic;
75 void init(
int dx,
int dy);
77 void getStatistic(
int *num_point_examine,
int *num_find_erase);
88 inline Vect2i posBy(OnePoint *p) {
89 int offset = p - _chart;
97template<
class Heuristic,
class TypeH>
98AIAStar<Heuristic, TypeH>::AIAStar() {
104 _num_point_examine = 0;
107template<
class Heuristic,
class TypeH>
108void AIAStar<Heuristic, TypeH>::init(
int dx_,
int dy_) {
112 int size = _dx * _dy;
113 _chart =
new OnePoint[size];
117template<
class Heuristic,
class TypeH>
118void AIAStar<Heuristic, TypeH>::clear() {
119 int size = _dx * _dy;
121 for (
int i = 0; i < size; i++)
125template<
class Heuristic,
class TypeH>
126AIAStar<Heuristic, TypeH>::~AIAStar() {
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;
138 if (_is_used_num == 0)
140 assert(from.x >= 0 && from.x < _dx && from.y >= 0 && from.y < _dy);
143 OnePoint *p = _chart + from.y * _dx + from.x;
145 p->h = _heuristic->getH(from.x, from.y);
146 p->used = _is_used_num;
150 _open_map.insert(
typename type_point_map::value_type(p->f(), from));
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 };
158 const int size_child = directions_count;
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;
165 parent->is_open =
false;
166 _open_map.erase(low);
168 if (_heuristic->isEndPoint(pt.x, pt.y)) {
175 if (parent->parent) {
177 pp = posBy(parent->parent);
178 assert(abs(vp.x - pp.x) <= 1 &&
179 abs(vp.y - pp.y) <= 1);
182 parent = parent->parent;
184 assert(vp.x == from.x && vp.y == from.y);
185 Common::reverse(path.
begin(), path.
end());
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++;
194 if (child.x < 0 || child.y < 0 ||
195 child.x >= _dx || child.y >= _dy)
continue;
196 p = _chart + child.y * _dx + child.x;
199 TypeH addg = _heuristic->getG(pt.x, pt.y, child.x, child.y);
200 TypeH newg = parent->g + addg;
202 if (p->used == _is_used_num) {
203 if (!p->is_open)
continue;
204 if (p->g <= newg)
continue;
208 typename type_point_map::iterator cur = _open_map.find(p->f());
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);
236 p->h = _heuristic->getH(child.x, child.y);
238 _open_map.insert(
typename type_point_map::value_type(p->f(), child));
241 p->used = _is_used_num;
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;
278template<
class Heuristic,
class Node,
class TypeH =
float>
292 typename type_point_map::iterator self_it;
304 int _num_point_examine;
306 Heuristic *_heuristic;
316 void getStatistic(
int *num_point_examine,
int *num_find_erase);
327 inline Node *posBy(OnePoint *p) {
332template<
class Heuristic,
class Node,
class TypeH>
333AIAStarGraph<Heuristic, Node, TypeH>::AIAStarGraph() {
336 _num_point_examine = 0;
340template<
class Heuristic,
class Node,
class TypeH>
342 int size = all_node.
size();
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;
353template<
class Heuristic,
class Node,
class TypeH>
354void AIAStarGraph<Heuristic, Node, TypeH>::clear() {
356 for (
auto &it : _chart) {
361template<
class Heuristic,
class Node,
class TypeH>
362AIAStarGraph<Heuristic, Node, TypeH>::~AIAStarGraph() {
365template<
class Heuristic,
class Node,
class TypeH>
367 _num_point_examine = 0;
373 if (_is_used_num == 0)
377 OnePoint *p = (OnePoint *)from->AIAStarPointer;
378 Node *from_node = p->node;
380 p->h = _heuristic->getH(p->node);
381 p->used = _is_used_num;
385 p->self_it = _open_map.insert(type_point_map::value_type(p->f(), p));
387 while (!_open_map.empty()) {
388 typename type_point_map::iterator low = _open_map.begin();
390 OnePoint *parent = low->second;
391 Node *node = parent->node;
393 parent->is_open =
false;
394 _open_map.erase(low);
396 if (_heuristic->IsEndPoint(node)) {
401 assert(parent->used == _is_used_num);
404 parent = parent->parent;
406 assert(np == from_node);
412 for (
auto &it : *node) {
413 Node *cur_node = *it;
414 OnePoint *op = (OnePoint *)cur_node->AIAStarPointer;
415 _num_point_examine++;
417 TypeH addg = _heuristic->getG(node, cur_node);
418 TypeH newg = parent->g + addg;
420 if (op->used == _is_used_num) {
421 if (!op->is_open)
continue;
422 if (op->g <= newg)
continue;
424 _open_map.erase(op->self_it);
430 op->h = _heuristic->getH(cur_node);
432 op->self_it = _open_map.insert(type_point_map::value_type(op->f(), op));
435 op->used = _is_used_num;
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;
466Vect2i AIFindMinium(
int x,
int y,
469 typename Maps::TypeH optium = maps.get(x, y);
470 int optiumx = x, optiumy = y;
472 int maxi =
MAX(
MAX(x, dx - x),
MAX(y, dy - y));
473 for (
int i = 1; i < maxi; i++) {
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);
480 for (curx = xmin; curx <= xmax; curx++) {
481 typename Maps::TypeH o = maps.get(curx, cury);
492 for (curx = xmin; curx <= xmax; curx++) {
493 typename Maps::TypeH o = maps.get(curx, cury);
504 for (cury = ymin; cury <= ymax; cury++) {
505 typename Maps::TypeH o = maps.get(curx, cury);
516 for (cury = ymin; cury <= ymax; cury++) {
517 typename Maps::TypeH o = maps.get(curx, cury);
525 if (maps.IsOptiumGood(optium, optiumx, optiumy))
529 Vect2i p = {optiumx, optiumy};
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
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:284