1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
/*
* Copyright (C) 2008-2010 by the Widelands Development Team
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
*/
#ifndef WL_LOGIC_PATHFIELD_H
#define WL_LOGIC_PATHFIELD_H
#include <memory>
#include <vector>
#include <boost/shared_ptr.hpp>
#include <stdint.h>
#include "logic/cookie_priority_queue.h"
namespace Widelands {
/**
* Used in pathfinding. For better encapsulation, pathfinding structures
* are separate from normal fields
*
* Costs are in milliseconds to walk.
*
* Note: member sizes chosen so that we get a 16byte (=nicely aligned)
* structure
*/
struct Pathfield {
struct LessCost {
bool operator()(const Pathfield& a, const Pathfield& b) const {
return a.cost() < b.cost();
}
};
using Queue = CookiePriorityQueue<Pathfield, LessCost>;
Queue::Cookie heap_cookie;
int32_t real_cost; // true cost up to this field
int32_t estim_cost; // estimated cost till goal
uint16_t cycle;
uint8_t backlink; // how we got here (WALK_*)
int32_t cost() const {
return real_cost + estim_cost;
}
Queue::Cookie& cookie() {
return heap_cookie;
}
};
struct Pathfields {
std::unique_ptr<Pathfield[]> fields;
uint16_t cycle;
Pathfields(uint32_t nrfields);
};
/**
* Efficiently manages \ref Pathfields instances.
*
* This allows the use of more than one such structure at once,
* which is required for pathfinding reentrancy.
*/
struct PathfieldManager {
PathfieldManager();
void set_size(uint32_t nrfields);
boost::shared_ptr<Pathfields> allocate();
private:
void clear(const boost::shared_ptr<Pathfields>& pf);
using List = std::vector<boost::shared_ptr<Pathfields>>;
uint32_t nrfields_;
List list_;
};
}
#endif // end of include guard: WL_LOGIC_PATHFIELD_H
|