1 /*
2 * Copyright (C) 2004 Ivo Danihelka (ivo@danihelka.net)
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 #include "FinderAlg.h"
10
11 #include "V2.h"
12 #include "Unit.h"
13 #include "FinderPlace.h"
14
15 //-----------------------------------------------------------------
FinderAlg(int w,int h)16 FinderAlg::FinderAlg(int w, int h)
17 : m_closed(w, h)
18 {
19 m_unit = NULL;
20 }
21 //-----------------------------------------------------------------
22 /**
23 * Finds the best start direction to the destination.
24 * @param unit unit which finds path
25 * @param dest destination, final destination must be under unit
26 * @return direction or DIR_NO
27 */
28 Dir::eDir
findDir(const Unit * unit,const V2 & dest)29 FinderAlg::findDir(const Unit *unit, const V2 &dest)
30 {
31 if (m_unit) {
32 m_closed.reset();
33 m_fifo.clear();
34 }
35 m_unit = unit;
36 V2 uLoc = unit->getLoc();
37 int w = unit->getW();
38 int h = unit->getH();
39 if (isInRect(uLoc, w, h, dest)) {
40 return Dir::DIR_NO;
41 }
42 //TODO: don't compute when dest is on the wall
43
44 m_closed.markClosed(uLoc);
45 m_fifo.push_back(FinderPlace(Dir::DIR_LEFT, uLoc.plus(V2(-1, 0))));
46 m_fifo.push_back(FinderPlace(Dir::DIR_RIGHT, uLoc.plus(V2(+1, 0))));
47 m_fifo.push_back(FinderPlace(Dir::DIR_UP, uLoc.plus(V2(0, -1))));
48 m_fifo.push_back(FinderPlace(Dir::DIR_DOWN, uLoc.plus(V2(0, +1))));
49
50 while (!m_fifo.empty()) {
51 FinderPlace place = m_fifo.front();
52 m_fifo.pop_front();
53 if (tryPlace(place)) {
54 if (isInRect(place.getLoc(), w, h, dest)) {
55 return place.getStartDir();
56 }
57
58 pushNext(place, V2(-1, 0));
59 pushNext(place, V2(+1, 0));
60 pushNext(place, V2(0, -1));
61 pushNext(place, V2(0, +1));
62 }
63 }
64 return Dir::DIR_NO;
65 }
66 //-----------------------------------------------------------------
67 /**
68 * Push neighbour to the fifo.
69 * Only open place is stored.
70 */
71 void
pushNext(const FinderPlace & parent,const V2 & shift)72 FinderAlg::pushNext(const FinderPlace &parent, const V2 &shift)
73 {
74 V2 loc = parent.getLoc().plus(shift);
75 if (!m_closed.isClosed(loc)) {
76 m_closed.markClosed(loc);
77 m_fifo.push_back(FinderPlace(parent.getStartDir(), loc));
78 }
79 }
80 //-----------------------------------------------------------------
81 /**
82 * Whether dest in inside given rectangle.
83 */
84 bool
isInRect(const V2 & rectLoc,int w,int h,const V2 & dest) const85 FinderAlg::isInRect(const V2 &rectLoc, int w, int h, const V2 &dest) const
86 {
87 int rX = rectLoc.getX();
88 int rY = rectLoc.getY();
89 int destX = dest.getX();
90 int destY = dest.getY();
91 return (rX <= destX && destX < rX + w)
92 && (rY <= destY && destY < rY + h);
93 }
94 //-----------------------------------------------------------------
95 bool
tryPlace(const FinderPlace & place) const96 FinderAlg::tryPlace(const FinderPlace &place) const
97 {
98 return m_unit->isFreePlace(place.getLoc());
99 }
100
101