costmap_queue.cpp
Go to the documentation of this file.
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2017, Locus Robotics
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above
14  * copyright notice, this list of conditions and the following
15  * disclaimer in the documentation and/or other materials provided
16  * with the distribution.
17  * * Neither the name of the copyright holder nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  */
35 #include <algorithm>
36 #include <vector>
37 
38 namespace costmap_queue
39 {
40 
42  MapBasedQueue(false), costmap_(costmap), seen_(0), manhattan_(manhattan), cached_max_distance_(-1)
43 {
44  reset();
45 }
46 
48 {
49  seen_.setInfo(costmap_.getInfo());
50  seen_.reset();
51  computeCache();
53 }
54 
55 void CostmapQueue::enqueueCell(unsigned int x, unsigned int y)
56 {
57  enqueueCell(x, y, x, y);
58 }
59 
60 void CostmapQueue::enqueueCell(unsigned int cur_x, unsigned int cur_y,
61  unsigned int src_x, unsigned int src_y)
62 {
63  if (seen_(cur_x, cur_y)) return;
64 
65  // we compute our distance table one cell further than the inflation radius dictates so we can make the check below
66  double distance = distanceLookup(cur_x, cur_y, src_x, src_y);
67  CellData data(distance, cur_x, cur_y, src_x, src_y);
68  if (validCellToQueue(data))
69  {
70  seen_.setValue(cur_x, cur_y, 1);
71  enqueue(distance, data);
72  }
73 }
74 
76 {
77  // get the highest priority cell and pop it off the priority queue
78  CellData current_cell = front();
79  pop();
80 
81  unsigned int mx = current_cell.x_;
82  unsigned int my = current_cell.y_;
83  unsigned int sx = current_cell.src_x_;
84  unsigned int sy = current_cell.src_y_;
85 
86  // attempt to put the neighbors of the current cell onto the queue
87  if (mx > 0)
88  enqueueCell(mx - 1, my, sx, sy);
89  if (my > 0)
90  enqueueCell(mx, my - 1, sx, sy);
91  if (mx < costmap_.getWidth() - 1)
92  enqueueCell(mx + 1, my, sx, sy);
93  if (my < costmap_.getHeight() - 1)
94  enqueueCell(mx, my + 1, sx, sy);
95 
96  return current_cell;
97 }
98 
100 {
101  int max_distance = getMaxDistance();
102  if (max_distance == cached_max_distance_) return;
103  cached_distances_.clear();
104 
105  cached_distances_.resize(max_distance + 2);
106 
107  for (unsigned int i = 0; i < cached_distances_.size(); ++i)
108  {
109  cached_distances_[i].resize(max_distance + 2);
110  for (unsigned int j = 0; j < cached_distances_[i].size(); ++j)
111  {
112  if (manhattan_)
113  {
114  cached_distances_[i][j] = i + j;
115  }
116  else
117  {
118  cached_distances_[i][j] = hypot(i, j);
119  }
120  }
121  }
122  cached_max_distance_ = max_distance;
123 }
124 
125 } // namespace costmap_queue
double distanceLookup(const unsigned int cur_x, const unsigned int cur_y, const unsigned int src_x, const unsigned int src_y)
Lookup pre-computed distances.
void reset() override
Clear the queue.
CellData & front()
Return the item at the front of the queue.
virtual bool validCellToQueue(const CellData &cell)
Check to see if we should add this cell to the queue. Always true unless overridden.
nav_core2::BasicCostmap costmap
Definition: utest.cpp:43
void enqueue(const double priority, CellDataitem)
Add a new item to the queue with a set priority.
std::vector< std::vector< double > > cached_distances_
CostmapQueue(nav_core2::Costmap &costmap, bool manhattan=false)
constructor
virtual int getMaxDistance() const
Get the maximum x or y distance we&#39;ll need to calculate the distance between.
TFSIMD_FORCE_INLINE tfScalar distance(const Vector3 &v) const
void reset() override
void computeCache()
Compute the cached distances.
void enqueueCell(unsigned int x, unsigned int y)
Add a cell the queue.
void pop()
Remove (and destroy) the item at the front of the queue.
void setInfo(const NavGridInfo &new_info) override
Templatized interface for a priority queue.
nav_grid::VectorNavGrid< unsigned char > seen_
Storage for cell information used during queue expansion.
Definition: costmap_queue.h:52
void setValue(const unsigned int x, const unsigned int y, const T &value) override
virtual void reset()
Clear the queue.
nav_core2::Costmap & costmap_
CellData getNextCell()
Get the next cell to examine, and enqueue its neighbors as needed.


costmap_queue
Author(s):
autogenerated on Sun Jan 10 2021 04:08:29