FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
instancetree.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2017 by the FIFE team *
3  * http://www.fifengine.net *
4  * This file is part of FIFE. *
5  * *
6  * FIFE is free software; you can redistribute it and/or *
7  * modify it under the terms of the GNU Lesser General Public *
8  * License as published by the Free Software Foundation; either *
9  * version 2.1 of the License, or (at your option) any later version. *
10  * *
11  * This library 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 GNU *
14  * Lesser General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU Lesser General Public *
17  * License along with this library; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20  ***************************************************************************/
21 
22 // Standard C++ library includes
23 
24 // 3rd party library includes
25 
26 
27 // FIFE includes
28 // These includes are split up in two parts, separated by one empty line
29 // First block: files included from the FIFE root src directory
30 // Second block: files included from the same folder
31 #include "util/base/exception.h"
32 #include "util/log/logger.h"
34 #include "util/structures/rect.h"
35 
36 #include "instancetree.h"
37 
38 
39 namespace FIFE {
40  static Logger _log(LM_STRUCTURES);
41 
43  }
44 
46  }
47 
49  ModelCoordinate coords = instance->getLocationRef().getLayerCoordinates();
50  InstanceTreeNode * node = m_tree.find_container(coords.x,coords.y,0,0);
51  InstanceList& list = node->data();
52  list.push_back(instance);
53  if( m_reverse.find(instance) != m_reverse.end() ) {
54  FL_WARN(_log, "InstanceTree::addInstance() - Duplicate Instance. Ignoring.");
55  return;
56  }
57  m_reverse[instance] = node;
58  }
59 
61  InstanceTreeNode * node = m_reverse[instance];
62  if( !node ) {
63  FL_WARN(_log, "InstanceTree::removeInstance() - Instance not part of tree.");
64  return;
65  }
66  m_reverse.erase(instance);
67  InstanceList& list = node->data();
68  for(InstanceList::iterator i = list.begin(); i != list.end(); ++i) {
69  if((*i) == instance) {
70  list.erase(i);
71  return;
72  }
73  }
74  FL_WARN(_log, "InstanceTree::removeInstance() - Instance part of tree but not found in the expected tree node.");
75  }
76 
78  public:
82  : instanceList(a_instanceList), searchRect(rect) {
83  }
84  bool visit(InstanceTree::InstanceTreeNode* node, int32_t d);
85  };
86 
88  InstanceTree::InstanceList& list = node->data();
89  for(InstanceTree::InstanceList::const_iterator it(list.begin()); it != list.end(); ++it) {
90  ModelCoordinate coords = (*it)->getLocationRef().getLayerCoordinates();
91  if( searchRect.contains(Point(coords.x,coords.y)) ) {
92  instanceList.push_back(*it);
93  }
94  }
95  return true;
96  }
97 
98  void InstanceTree::findInstances(const ModelCoordinate& point, int32_t w, int32_t h, InstanceTree::InstanceList& list) {
99  list.clear();
100  InstanceTreeNode * node = m_tree.find_container(point.x, point.y, w, h);
101  Rect rect(point.x, point.y, w, h);
102  InstanceListCollector collector(list,rect);
103 
104  node->apply_visitor(collector);
105 
106  node = node->parent();
107  while( node ) {
108  for(InstanceList::const_iterator it(node->data().begin()); it != node->data().end(); ++it) {
109  ModelCoordinate coords = (*it)->getLocationRef().getLayerCoordinates();
110  if( rect.contains(Point(coords.x,coords.y)) ) {
111  list.push_back(*it);
112  }
113  }
114  node = node->parent();
115  }
116  }
117 
118 }
#define FL_WARN(logger, msg)
Definition: logger.h:72
bool visit(InstanceTree::InstanceTreeNode *node, int32_t d)
std::map< Instance *, InstanceTreeNode * > m_reverse
Definition: instancetree.h:100
Node * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Find a container node for a given rectangle.
Definition: quadtree.h:359
bool contains(const PointType2D< T > &point) const
Checks whether a rectangle contains a Point.
Definition: rect.h:184
Base class for all fife classes Used e.g.
Definition: fifeclass.h:42
static Logger _log(LM_AUDIO)
DataType & data()
Return a reference to the data of the node.
Definition: quadtree.h:116
InstanceListCollector(InstanceTree::InstanceList &a_instanceList, const Rect &rect)
InstanceTree::InstanceList & instanceList
Location & getLocationRef()
Gets reference of current location of instance.
Definition: instance.cpp:318
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
Definition: location.cpp:113
void findInstances(const ModelCoordinate &point, int32_t w, int32_t h, InstanceList &list)
Find all instances in a given area.
virtual ~InstanceTree()
Destructor.
InstanceQuadTree::Node InstanceTreeNode
Definition: instancetree.h:48
void removeInstance(Instance *instance)
Removes an instance from the quad tree.
InstanceQuadTree m_tree
Definition: instancetree.h:99
void addInstance(Instance *instance)
Adds an instance to the quad tree.
QuadTree Node.
Definition: quadtree.h:41
A 3D Point.
Definition: point.h:205
std::list< Instance * > InstanceList
Definition: instancetree.h:46
InstanceTree()
Constructor.
An Instance is an "instantiation" of an Object at a Location.
Definition: instance.h:101