Menu
▾
▴
[Freeorion-programmers] SF.net SVN: freeorion:[4304] trunk/FreeOrion/universe
|
From: <tz...@us...> - 2011-09-29 02:43:17
|
Revision: 4304
http://freeorion.svn.sourceforge.net/freeorion/revision/?rev=4304&view=rev
Author: tzlaine
Date: 2011-09-29 02:43:10 +0000 (Thu, 29 Sep 2011)
Log Message:
-----------
Optimization of some of the turn-processing code in Universe and Condition.
Modified patch from cami.
Modified Paths:
--------------
trunk/FreeOrion/universe/Condition.cpp
trunk/FreeOrion/universe/Universe.cpp
trunk/FreeOrion/universe/Universe.h
Modified: trunk/FreeOrion/universe/Condition.cpp
===================================================================
--- trunk/FreeOrion/universe/Condition.cpp 2011-09-29 01:55:08 UTC (rev 4303)
+++ trunk/FreeOrion/universe/Condition.cpp 2011-09-29 02:43:10 UTC (rev 4304)
@@ -4173,48 +4173,46 @@
namespace {
const int MANY_JUMPS(999999);
-
- int JumpsBetweenObjects(const UniverseObject* one, const UniverseObject* two, int jump_limit = MANY_JUMPS) {
+
+ int JumpsBetweenObjects(const UniverseObject* one, const UniverseObject* two) {
ObjectMap& objects = GetUniverse().Objects();
if (!one || !two)
return MANY_JUMPS;
- // determine if objects are systems
const System* system_one = objects.Object<System>(one->SystemID());
const System* system_two = objects.Object<System>(two->SystemID());
- // need various special cases for whether the condition-matching object
- // and candidate objects are or are in systems.
if (system_one && system_two) {
// both condition-matching object and candidate are / in systems.
// can just find the shortest path between the two systems
- std::pair<std::list<int>, double> path = GetUniverse().LeastJumpsPath(system_one->ID(), system_two->ID(), ALL_EMPIRES, jump_limit);
- if (!path.first.empty()) // if path.first is empty, no path exists between the systems
- return static_cast<int>(path.first.size() - 1);
-
+ short jumps = GetUniverse().JumpDistance(system_one->ID(), system_two->ID());
+ if (jumps != -1) // if jumps is -1, no path exists between the systems
+ return static_cast<int>(jumps);
+
} else if (system_one) {
// just object one is / in a system.
if (const Fleet* fleet = FleetFromObject(two)) {
// other object is a fleet that is between systems
// need to check shortest path from systems on either side of starlane fleet is on
- std::pair<std::list<int>, double> path1 = GetUniverse().LeastJumpsPath(system_one->ID(), fleet->PreviousSystemID(), ALL_EMPIRES, jump_limit);
- std::pair<std::list<int>, double> path2 = GetUniverse().LeastJumpsPath(system_one->ID(), fleet->NextSystemID(), ALL_EMPIRES, jump_limit);
- if (int jumps = static_cast<int>(std::max(path1.first.size(), path2.first.size())))
+ short jumps1 = GetUniverse().JumpDistance(system_one->ID(), fleet->PreviousSystemID());
+ short jumps2 = GetUniverse().JumpDistance(system_one->ID(), fleet->NextSystemID());
+ int jumps = static_cast<int>(std::max(jumps1, jumps2));
+ if (jumps != -1)
return jumps - 1;
}
-
+
} else if (system_two) {
// just object two is a system.
- if (const Fleet* fleet = FleetFromObject(two)) {
+ if (const Fleet* fleet = FleetFromObject(one)) {
// other object is a fleet that is between systems
// need to check shortest path from systems on either side of starlane fleet is on
- std::pair<std::list<int>, double> path1 = GetUniverse().LeastJumpsPath(system_two->ID(), fleet->PreviousSystemID(), ALL_EMPIRES, jump_limit);
- std::pair<std::list<int>, double> path2 = GetUniverse().LeastJumpsPath(system_two->ID(), fleet->NextSystemID(), ALL_EMPIRES, jump_limit);
- if (int jumps = static_cast<int>(std::max(path1.first.size(), path2.first.size())))
+ short jumps1 = GetUniverse().JumpDistance(system_two->ID(), fleet->PreviousSystemID());
+ short jumps2 = GetUniverse().JumpDistance(system_two->ID(), fleet->NextSystemID());
+ int jumps = static_cast<int>(std::max(jumps1, jumps2));
+ if (jumps != -1)
return jumps - 1;
}
-
} else {
// neither object is / in a system
@@ -4231,19 +4229,19 @@
int fleet_two_prev_system_id = fleet_two->PreviousSystemID();
int fleet_two_next_system_id = fleet_two->NextSystemID();
- std::pair<std::list<int>, int> path1 = GetUniverse().LeastJumpsPath(fleet_one_prev_system_id, fleet_two_prev_system_id, ALL_EMPIRES, jump_limit);
- std::pair<std::list<int>, int> path2 = GetUniverse().LeastJumpsPath(fleet_one_prev_system_id, fleet_two_next_system_id, ALL_EMPIRES, jump_limit);
- std::pair<std::list<int>, int> path3 = GetUniverse().LeastJumpsPath(fleet_one_next_system_id, fleet_two_prev_system_id, ALL_EMPIRES, jump_limit);
- std::pair<std::list<int>, int> path4 = GetUniverse().LeastJumpsPath(fleet_one_next_system_id, fleet_two_next_system_id, ALL_EMPIRES, jump_limit);
- if (int jumps = static_cast<int>(std::max(std::max(path1.second, path2.second),
- std::max(path3.second, path4.second))))
+ short jumps1 = GetUniverse().JumpDistance(fleet_one_prev_system_id, fleet_two_prev_system_id);
+ short jumps2 = GetUniverse().JumpDistance(fleet_one_prev_system_id, fleet_two_next_system_id);
+ short jumps3 = GetUniverse().JumpDistance(fleet_one_next_system_id, fleet_two_prev_system_id);
+ short jumps4 = GetUniverse().JumpDistance(fleet_one_next_system_id, fleet_two_next_system_id);
+ int jumps = static_cast<int>(std::max(jumps1, std::max(jumps2, std::max(jumps3, jumps4))));
+ if (jumps != -1)
return jumps - 1;
}
}
return MANY_JUMPS;
}
-
+
bool WithinStarlaneJumpsSimpleMatch(const UniverseObject* candidate, const Condition::ObjectSet& from_objects, int jump_limit)
{
if (!candidate)
@@ -4254,7 +4252,7 @@
return false;
// is candidate object close enough to any subcondition matches?
- for (Condition::ObjectSet::const_iterator it = from_objects.begin(); it != from_objects.end(); ++it) {
+ for (Condition::ObjectSet::const_iterator it = from_objects.begin(), end_it = from_objects.end(); it != end_it; ++it) {
if (jump_limit == 0) {
// special case, since LeastJumpsPath() doesn't expect the start point to be the end point
double delta_x = (*it)->X() - candidate->X();
@@ -4262,7 +4260,7 @@
if (delta_x*delta_x + delta_y*delta_y == 0)
return true;
} else {
- int jumps = JumpsBetweenObjects(*it, candidate, jump_limit);
+ int jumps = JumpsBetweenObjects(*it, candidate);
if (jumps <= jump_limit)
return true;
}
Modified: trunk/FreeOrion/universe/Universe.cpp
===================================================================
--- trunk/FreeOrion/universe/Universe.cpp 2011-09-29 01:55:08 UTC (rev 4303)
+++ trunk/FreeOrion/universe/Universe.cpp 2011-09-29 02:43:10 UTC (rev 4304)
@@ -30,6 +30,7 @@
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/timer.hpp>
#include <cmath>
@@ -42,9 +43,7 @@
db.Add("verbose-logging", "OPTIONS_DB_VERBOSE_LOGGING_DESC", false, Validator<bool>());
}
bool temp_bool = RegisterOptions(&AddOptions);
-}
-namespace {
/** Wrapper for boost::timer that outputs time during which this object
* existed. Created in the scope of a function, and passed the appropriate
* name, it will output to Logger().debugStream() the time elapsed while
@@ -64,9 +63,7 @@
boost::timer m_timer;
std::string m_name;
};
-}
-namespace {
const double OFFROAD_SLOWDOWN_FACTOR = 1000000000.0; // the factor by which non-starlane travel is slower than starlane travel
DataTableMap& UniverseDataTables() {
@@ -95,8 +92,27 @@
names.push_back(latest_name.substr(0, latest_name.find_last_not_of(" \t") + 1)); // strip off trailing whitespace
}
}
+
+ struct constant_property
+ {
+ short m_value;
+ };
+
+ short get(const constant_property& pmap, const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long>&) { return pmap.m_value; }
+
}
+namespace boost {
+
+ template <>
+ struct property_traits<constant_property> {
+ typedef short value_type;
+ typedef boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long> key_type;
+ typedef readable_property_map_tag category;
+ };
+
+}
+
namespace SystemPathing {
/** Used to short-circuit the use of BFS (breadth-first search) or
* Dijkstra's algorithm for pathfinding when it finds the desired
@@ -137,7 +153,7 @@
bool m_level_complete;
public:
- BFSVisitorImpl(const Graph& g, const Vertex& start, const Vertex& stop, Vertex predecessors[], int max_depth)
+ BFSVisitorImpl(const Vertex& start, const Vertex& stop, Vertex predecessors[], int max_depth)
: m_marker(start),
m_stop(stop),
m_source(start),
@@ -191,24 +207,7 @@
// templated implementations of Universe graph search methods //
////////////////////////////////////////////////////////////////
struct vertex_system_id_t {typedef boost::vertex_property_tag kind;}; ///< a system graph property map type
-
- // returns the \a graph index for system with \a system_id
- template <class Graph>
- int SystemGraphIndex(const Graph& graph, int system_id)
- {
- typedef typename boost::property_map<Graph, vertex_system_id_t>::const_type ConstSystemIDPropertyMap;
- ConstSystemIDPropertyMap sys_id_property_map = boost::get(vertex_system_id_t(), graph);
-
- for (unsigned int i = 0; i < boost::num_vertices(graph); ++i) {
- const int loop_sys_id = sys_id_property_map[i]; // get system ID of this vertex
- if (loop_sys_id == system_id)
- return i;
- }
-
- throw std::out_of_range("SystemGraphIndex cannot be found due to invalid system ID " + boost::lexical_cast<std::string>(system_id));
- return -1;
- }
-
+
/** Returns the path between vertices \a system1_id and \a system2_id of
* \a graph that travels the shorest distance on starlanes, and the path
* length. If system1_id is the same vertex as system2_id, the path has
@@ -216,7 +215,7 @@
* between the two vertices, then the list is empty and the path length
* is -1.0 */
template <class Graph>
- std::pair<std::list<int>, double> ShortestPathImpl(const Graph& graph, int system1_id, int system2_id, double linear_distance)
+ std::pair<std::list<int>, double> ShortestPathImpl(const Graph& graph, int system1_id, int system2_id, double linear_distance, const boost::unordered_map<int, int>& id_to_graph_index)
{
typedef typename boost::property_map<Graph, vertex_system_id_t>::const_type ConstSystemIDPropertyMap;
typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type ConstIndexPropertyMap;
@@ -227,8 +226,8 @@
ConstSystemIDPropertyMap sys_id_property_map = boost::get(vertex_system_id_t(), graph);
- int system1_index = SystemGraphIndex(graph, system1_id);
- int system2_index = SystemGraphIndex(graph, system2_id);
+ int system1_index = id_to_graph_index.at(system1_id);
+ int system2_index = id_to_graph_index.at(system2_id);
// early exit if systems are the same
@@ -291,15 +290,15 @@
* is 0. If there is no path between the two vertices, then the list is
* empty and the path length is -1 */
template <class Graph>
- std::pair<std::list<int>, int> LeastJumpsPathImpl(const Graph& graph, int system1_id, int system2_id, int max_jumps = INT_MAX)
+ std::pair<std::list<int>, int> LeastJumpsPathImpl(const Graph& graph, int system1_id, int system2_id, const boost::unordered_map<int, int>& id_to_graph_index, int max_jumps = INT_MAX)
{
typedef typename boost::property_map<Graph, vertex_system_id_t>::const_type ConstSystemIDPropertyMap;
ConstSystemIDPropertyMap sys_id_property_map = boost::get(vertex_system_id_t(), graph);
std::pair<std::list<int>, int> retval;
- int system1_index = SystemGraphIndex(graph, system1_id);
- int system2_index = SystemGraphIndex(graph, system2_id);
+ int system1_index = id_to_graph_index.at(system1_id);
+ int system2_index = id_to_graph_index.at(system2_id);
// early exit if systems are the same
if (system1_id == system2_id) {
@@ -324,7 +323,7 @@
boost::queue<int> buf;
std::vector<int> colors(boost::num_vertices(graph));
- BFSVisitor bfsVisitor(graph, system1_index, system2_index, &predecessors[0], max_jumps);
+ BFSVisitor bfsVisitor(system1_index, system2_index, &predecessors[0], max_jumps);
boost::breadth_first_search(graph, system1_index, buf, bfsVisitor, &colors[0]);
} catch (const typename BFSVisitor::ReachedDepthLimit&) {
// catching this means the algorithm explored the neighborhood until max_jumps and didn't find anything
@@ -351,9 +350,9 @@
return retval;
}
-
+
template <class Graph>
- std::map<double, int> ImmediateNeighborsImpl(const Graph& graph, int system_id)
+ std::map<double, int> ImmediateNeighborsImpl(const Graph& graph, int system_id, const boost::unordered_map<int, int>& id_to_graph_index)
{
typedef typename Graph::out_edge_iterator OutEdgeIterator;
typedef typename boost::property_map<Graph, vertex_system_id_t>::const_type ConstSystemIDPropertyMap;
@@ -362,7 +361,7 @@
std::map<double, int> retval;
ConstEdgeWeightPropertyMap edge_weight_map = boost::get(boost::edge_weight, graph);
ConstSystemIDPropertyMap sys_id_property_map = boost::get(vertex_system_id_t(), graph);
- std::pair<OutEdgeIterator, OutEdgeIterator> edges = boost::out_edges(SystemGraphIndex(graph, system_id), graph);
+ std::pair<OutEdgeIterator, OutEdgeIterator> edges = boost::out_edges(id_to_graph_index.at(system_id), graph);
for (OutEdgeIterator it = edges.first; it != edges.second; ++it) {
retval[edge_weight_map[*it]] = sys_id_property_map[boost::target(*it, graph)];
}
@@ -939,22 +938,20 @@
}
double Universe::LinearDistance(int system1_id, int system2_id) const
-{
- //Logger().debugStream() << "LinearDistance(" << system1_id << ", " << system2_id << ")";
- int system1_index = SystemGraphIndex(m_graph_impl->system_graph, system1_id);
- int system2_index = SystemGraphIndex(m_graph_impl->system_graph, system2_id);
- return m_system_distances.at(std::max(system1_index, system2_index)).at(std::min(system1_index, system2_index));
-}
+{ return m_system_distances[m_system_id_to_graph_index.at(system1_id)][m_system_id_to_graph_index.at(system2_id)]; }
+short Universe::JumpDistance(int system1_id, int system2_id) const
+{ return m_system_jumps[m_system_id_to_graph_index.at(system1_id)][m_system_id_to_graph_index.at(system2_id)] - 1; }
+
std::pair<std::list<int>, double> Universe::ShortestPath(int system1_id, int system2_id, int empire_id/* = ALL_EMPIRES*/) const
{
double linear_distance = LinearDistance(system1_id, system2_id);
if (empire_id == ALL_EMPIRES) {
- return ShortestPathImpl(m_graph_impl->system_graph, system1_id, system2_id, linear_distance);
+ return ShortestPathImpl(m_graph_impl->system_graph, system1_id, system2_id, linear_distance, m_system_id_to_graph_index);
} else {
GraphImpl::EmpireViewSystemGraphMap::const_iterator graph_it = m_graph_impl->empire_system_graph_views.find(empire_id);
if (graph_it != m_graph_impl->empire_system_graph_views.end())
- return ShortestPathImpl(*graph_it->second, system1_id, system2_id, linear_distance);
+ return ShortestPathImpl(*graph_it->second, system1_id, system2_id, linear_distance, m_system_id_to_graph_index);
}
return std::pair<std::list<int>, double>();
}
@@ -962,11 +959,11 @@
std::pair<std::list<int>, int> Universe::LeastJumpsPath(int system1_id, int system2_id, int empire_id/* = ALL_EMPIRES*/, int max_jumps/* = INT_MAX*/) const
{
if (empire_id == ALL_EMPIRES) {
- return LeastJumpsPathImpl(m_graph_impl->system_graph, system1_id, system2_id, max_jumps);
+ return LeastJumpsPathImpl(m_graph_impl->system_graph, system1_id, system2_id, m_system_id_to_graph_index, max_jumps);
} else {
GraphImpl::EmpireViewSystemGraphMap::const_iterator graph_it = m_graph_impl->empire_system_graph_views.find(empire_id);
if (graph_it != m_graph_impl->empire_system_graph_views.end())
- return LeastJumpsPathImpl(*graph_it->second, system1_id, system2_id, max_jumps);
+ return LeastJumpsPathImpl(*graph_it->second, system1_id, system2_id, m_system_id_to_graph_index, max_jumps);
}
return std::pair<std::list<int>, int>();
}
@@ -988,11 +985,11 @@
std::map<double, int> Universe::ImmediateNeighbors(int system_id, int empire_id/* = ALL_EMPIRES*/) const
{
if (empire_id == ALL_EMPIRES) {
- return ImmediateNeighborsImpl(m_graph_impl->system_graph, system_id);
+ return ImmediateNeighborsImpl(m_graph_impl->system_graph, system_id, m_system_id_to_graph_index);
} else {
GraphImpl::EmpireViewSystemGraphMap::const_iterator graph_it = m_graph_impl->empire_system_graph_views.find(empire_id);
if (graph_it != m_graph_impl->empire_system_graph_views.end())
- return ImmediateNeighborsImpl(*graph_it->second, system_id);
+ return ImmediateNeighborsImpl(*graph_it->second, system_id, m_system_id_to_graph_index);
}
return std::map<double, int>();
}
@@ -1396,6 +1393,11 @@
void Universe::GetEffectsAndTargets(EffectsTargetsCausesMap& targets_causes_map, const std::vector<int>& target_objects)
{
+ // transfer target objects from input vector to a set
+ Effect::TargetSet all_potential_targets;
+ for (std::vector<int>::const_iterator it = target_objects.begin(); it != target_objects.end(); ++it)
+ all_potential_targets.insert(m_objects.Object(*it));
+
Logger().debugStream() << "Universe::GetEffectsAndTargets";
// 0) EffectsGroups from Species
Logger().debugStream() << "Universe::GetEffectsAndTargets for SPECIES";
@@ -1413,7 +1415,7 @@
continue;
}
StoreTargetsAndCausesOfEffectsGroups(species->Effects(), it->first, ECT_SPECIES, species_name,
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
}
// 1) EffectsGroups from Specials
@@ -1429,7 +1431,7 @@
}
StoreTargetsAndCausesOfEffectsGroups(special->Effects(), source_object_id, ECT_SPECIAL, special->Name(),
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
}
}
@@ -1442,7 +1444,7 @@
if (!tech) continue;
StoreTargetsAndCausesOfEffectsGroups(tech->Effects(), empire->CapitalID(), ECT_TECH, tech->Name(),
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
}
}
@@ -1462,7 +1464,7 @@
}
StoreTargetsAndCausesOfEffectsGroups(building_type->Effects(), building->ID(), ECT_BUILDING, building_type->Name(),
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
}
// 4) EffectsGroups from Ship Hull and Ship Parts
@@ -1486,7 +1488,7 @@
}
StoreTargetsAndCausesOfEffectsGroups(hull_type->Effects(), ship->ID(), ECT_SHIP_HULL, hull_type->Name(),
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
const std::vector<std::string>& parts = ship_design->Parts();
for (std::vector<std::string>::const_iterator part_it = parts.begin(); part_it != parts.end(); ++part_it) {
@@ -1499,7 +1501,7 @@
continue;
}
StoreTargetsAndCausesOfEffectsGroups(part_type->Effects(), ship->ID(), ECT_SHIP_PART, part_type->Name(),
- target_objects, targets_causes_map);
+ all_potential_targets, targets_causes_map);
}
}
}
@@ -1507,17 +1509,12 @@
void Universe::StoreTargetsAndCausesOfEffectsGroups(const std::vector<boost::shared_ptr<const Effect::EffectsGroup> >& effects_groups,
int source_object_id, EffectsCauseType effect_cause_type,
const std::string& specific_cause_name,
- const std::vector<int>& target_objects, EffectsTargetsCausesMap& targets_causes_map)
+ Effect::TargetSet& target_objects, EffectsTargetsCausesMap& targets_causes_map)
{
if (GetOptionsDB().Get<bool>("verbose-logging")) {
Logger().debugStream() << "Universe::StoreTargetsAndCausesOfEffectsGroups( , source id: " << source_object_id << ", , specific cause: " << specific_cause_name << ", , )";
}
- // transfer target objects from input vector to a set
- Effect::TargetSet all_potential_targets;
- for (std::vector<int>::const_iterator it = target_objects.begin(); it != target_objects.end(); ++it)
- all_potential_targets.insert(m_objects.Object(*it));
-
// process all effects groups in set provided
int eg_count = 1;
std::vector<boost::shared_ptr<const Effect::EffectsGroup> >::const_iterator effects_it;
@@ -1526,7 +1523,6 @@
// create non_targets and targets sets for current effects group
Effect::TargetSet target_set; // initially empty
- Effect::TargetSet potential_target_set = all_potential_targets; // copy again each iteration, so previous iterations don't affect starting potential targets of next iteration
// get effects group to process for this iteration
boost::shared_ptr<const Effect::EffectsGroup> effects_group = *effects_it;
@@ -1534,7 +1530,7 @@
{
ScopedTimer update_timer2("... ... Universe::StoreTargetsAndCausesOfEffectsGroups get target set");
// get set of target objects for this effects group from potential targets specified
- effects_group->GetTargetSet(source_object_id, target_set, potential_target_set); // transfers objects from potential_target_set to target_set if they meet the condition
+ effects_group->GetTargetSet(source_object_id, target_set, target_objects); // transfers objects from target_objects to target_set if they meet the condition
}
//effects_group->GetTargetSet(source_object_id, target_set, potential_target_set); // transfers objects from potential_target_set to target_set if they meet the condition
@@ -1553,6 +1549,10 @@
// store effect cause and targets info in map, indexed by sourced effects group
targets_causes_map.insert(std::make_pair(sourced_effects_group, target_and_cause));
+
+ // restore target_objects by moving objects back from targets to target_objects
+ // this should be cheaper than doing a full copy because target_set is usually small
+ target_objects.insert(target_set.begin(), target_set.end());
}
}
@@ -2297,10 +2297,13 @@
system_id_graph_index_reverse_lookup_map[system_id] = i;
}
+ m_system_distances.resize(system_ids.size(), system_ids.size());
for (int i = 0; i < static_cast<int>(system_ids.size()); ++i) {
int system1_id = system_ids[i];
const System* system1 = objects.Object<System>(system1_id);
+ m_system_id_to_graph_index[system1_id] = i;
+
// add edges and edge weights
for (System::const_lane_iterator it = system1->begin_lanes(); it != system1->end_lanes(); ++it) {
// get id in universe of system at other end of lane
@@ -2333,19 +2336,20 @@
}
// define the straight-line system distances for this system
- m_system_distances.resize(system_ids.size());
- m_system_distances[i].clear();
for (int j = 0; j < i; ++j) {
int system2_id = system_ids[j];
const UniverseObject* system2 = objects.Object(system2_id);
double x_dist = system2->X() - system1->X();
double y_dist = system2->Y() - system1->Y();
- m_system_distances[i].push_back(std::sqrt(x_dist*x_dist + y_dist*y_dist));
- //std::cout << "m_system_distances: " << system1_id << " to " << system2_id << ": " << m_system_distances[i].back() << std::endl;
+ m_system_distances[i][j] = std::sqrt(x_dist*x_dist + y_dist*y_dist);
}
- m_system_distances[i].push_back(0.0); // distance from system to itself
+ m_system_distances[i][i] = 0.0;
}
+ m_system_jumps.resize(system_ids.size(), system_ids.size());
+ constant_property jump_weight = { 1 };
+ boost::johnson_all_pairs_shortest_paths(m_graph_impl->system_graph, m_system_jumps, boost::weight_map(jump_weight));
+
RebuildEmpireViewSystemGraphs(for_empire_id);
}
Modified: trunk/FreeOrion/universe/Universe.h
===================================================================
--- trunk/FreeOrion/universe/Universe.h 2011-09-29 01:55:08 UTC (rev 4303)
+++ trunk/FreeOrion/universe/Universe.h 2011-09-29 02:43:10 UTC (rev 4304)
@@ -7,7 +7,9 @@
#include "../util/AppInterface.h"
#include <boost/signal.hpp>
+#include <boost/unordered_map.hpp>
#include <boost/iostreams/filtering_stream.hpp>
+#include <boost/numeric/ublas/symmetric.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/shared_ptr.hpp>
@@ -323,6 +325,8 @@
double LinearDistance(int system1_id, int system2_id) const; ///< returns the straight-line distance between the systems with the given IDs. \throw std::out_of_range This function will throw if either system ID is out of range.
+ short JumpDistance(int system1_id, int system2_id) const; ///< returns the number of starlane jumps between the systems with the given IDs. \throw std::out_of_range This function will throw if either system ID is out of range.
+
/** Returns the sequence of systems, including \a system1_id and
* \a system2_id, that defines the shortest path from \a system1 to
* \a system2, and the distance travelled to get there. If no such path
@@ -344,7 +348,7 @@
* will throw if either system ID is out of range. */
std::pair<std::list<int>, int>
LeastJumpsPath(int system1_id, int system2_id, int empire_id = ALL_EMPIRES, int max_jumps = INT_MAX) const;
-
+
/** Returns whether there is a path known to empire \a empire_id between
* system \a system1 and system \a system2. The path is calculated using
* the visibility for empire \a empire_id, or without regard to visibility
@@ -560,8 +564,53 @@
static int s_encoding_empire;
private:
- typedef std::vector< std::vector<double> > DistanceMatrix;
+ template <typename T>
+ class distance_matrix
+ {
+ public:
+ typedef boost::numeric::ublas::symmetric_matrix<
+ T,
+ boost::numeric::ublas::lower
+ > storage_type;
+
+ struct const_row_ref
+ {
+ const_row_ref(std::size_t i, const storage_type& m) : m_i(i), m_m(m) {}
+ T operator[](std::size_t j) const { return m_m(m_i, j); }
+ private:
+ std::size_t m_i;
+ const storage_type& m_m;
+ };
+ struct row_ref
+ {
+ row_ref(std::size_t i, storage_type& m) : m_i(i), m_m(m) {}
+ T& operator[](std::size_t j) { return m_m(m_i, j); }
+ private:
+ std::size_t m_i;
+ storage_type& m_m;
+ };
+
+ distance_matrix() :
+ m_m()
+ {}
+
+ const_row_ref operator[](std::size_t i) const
+ { return const_row_ref(i, m_m); }
+
+ row_ref operator[](std::size_t i)
+ { return row_ref(i, m_m); }
+
+ void resize(std::size_t rows, std::size_t columns)
+ { m_m.resize(rows, columns); }
+
+ private:
+ storage_type m_m;
+ };
+
+ typedef distance_matrix<double> DistanceMatrix;
+ typedef distance_matrix<short> JumpsMatrix;
+
/** Discrepancy between meter's value at start of turn, and the value that
* this client calculate that the meter should have with the knowledge
* available -> the unknown factor affecting the meter. This is used
@@ -582,11 +631,13 @@
/** Used by GetEffectsAndTargets to process a vector of effects groups.
* Stores target set of specified \a effects_groups and \a source_object_id
- * in \a targets_causes_map */
+ * in \a targets_causes_map
+ * NOTE: this method will modify target_objects temporarily, but restore
+ * its contents before returning. */
void StoreTargetsAndCausesOfEffectsGroups(const std::vector<boost::shared_ptr<const Effect::EffectsGroup> >& effects_groups,
int source_object_id, EffectsCauseType effect_cause_type,
const std::string& specific_cause_name,
- const std::vector<int>& target_objects, EffectsTargetsCausesMap& targets_causes_map);
+ Effect::TargetSet& target_objects, EffectsTargetsCausesMap& targets_causes_map);
/** Executes all effects. For use on server when processing turns. */
void ExecuteEffects(const EffectsTargetsCausesMap& targets_causes_map);
@@ -649,8 +700,10 @@
ShipDesignMap m_ship_designs; ///< ship designs in the universe
std::map<int, std::set<int> > m_empire_known_ship_design_ids; ///< ship designs known to each empire
- DistanceMatrix m_system_distances; ///< the straight-line distances between all the systems; this is an lower-triangular matrix, so only access the elements in (highID, lowID) order
+ DistanceMatrix m_system_distances; ///< the straight-line distances between all the systems
+ JumpsMatrix m_system_jumps; ///< the least-jumps distances between all the systems
GraphImpl* m_graph_impl; ///< a graph in which the systems are vertices and the starlanes are edges
+ boost::unordered_map<int, int> m_system_id_to_graph_index;
EffectAccountingMap m_effect_accounting_map; ///< map from target object id, to map from target meter, to orderered list of structs with details of an effect and what it does to the meter
EffectDiscrepancyMap m_effect_discrepancy_map; ///< map from target object id, to map from target meter, to discrepancy between meter's actual initial value, and the initial value that this meter should have as far as the client can tell: the unknown factor affecting the meter
|