10 #ifndef EMP_EVO_WORLD_STRUCTURE_H 11 #define EMP_EVO_WORLD_STRUCTURE_H 13 #include "../base/assert.h" 14 #include "../base/vector.h" 15 #include "../data/Trait.h" 16 #include "../tools/Random.h" 17 #include "../tools/vector_utils.h" 21 template <
typename ORG>
class World;
38 WorldPosition(
size_t _id,
size_t _pop_id=0) : index((uint32_t) _id), pop_id((uint32_t) _pop_id) {
64 const size_t pop_id = pos.
GetPopID();
67 return id < base_t::operator[](pop_id).size();
72 const size_t pop_id = pos.
GetPopID();
75 if (
id >= base_t::operator[](pop_id).size()) {
76 base_t::operator[](pop_id).resize(
id+1);
81 const size_t pop_id = pos.
GetPopID();
83 return base_t::operator[](pop_id)[id];
86 const size_t pop_id = pos.
GetPopID();
88 return base_t::operator[](pop_id)[id];
95 template <
typename ORG>
97 size_t pool_size,
bool synchronous_gen=
false) {
98 world.
Resize(pool_size, num_pools);
105 for (
size_t id = 0;
id < world.
GetSize();
id += pool_size) {
113 const size_t pool_start = (pos.
GetIndex() / pool_size) * pool_size;
123 if (synchronous_gen) {
127 const size_t parent_id = parent_pos.
GetIndex();
128 const size_t pool_id = parent_id / pool_size;
129 const size_t start_id = pool_id * pool_size;
130 for (
size_t id = start_id;
id < start_id+pool_size;
id++) {
163 template <
typename ORG>
166 world.
Resize(trait_counts);
177 size_t id = traits.
EvalBin(*new_org, trait_counts);
199 size_t id = traits.
EvalBin(*new_org, trait_counts);
213 template <
typename ORG>
224 const size_t num_traits = traits.
GetSize();
225 size_t trait_size = 1;
226 while (
Pow(trait_size+1, num_traits) < world.
GetSize()) trait_size++;
227 trait_counts.
resize(num_traits, trait_size);
233 template <
typename ORG>
240 template <
typename ORG>
261 template <
typename ORG>
263 static constexpr
size_t ID_NONE = (size_t) -1;
281 : nearest_id(), distance(), world(in_world), traits(in_traits)
282 , min_vals(traits.
GetSize(),
std::numeric_limits<double>::max())
283 , max_vals(traits.
GetSize(),
std::numeric_limits<double>::min())
284 , bin_width(traits.
GetSize(), 0.00001)
285 , is_setup(false), num_trait_bins(0), num_total_bins(0), bin_ids(), org_bins()
291 for (
double offset : offsets) dist += offset * offset;
298 for (
size_t id2 : bin_ids[target_bin]) {
299 if (id2 == refresh_id)
continue;
300 const double cur_dist = CalcDist(id2, refresh_id);
301 if (cur_dist < distance[refresh_id]) {
302 distance[refresh_id] = cur_dist;
303 nearest_id[refresh_id] = id2;
305 if (cur_dist < distance[id2]) {
306 distance[id2] = cur_dist;
307 nearest_id[id2] = refresh_id;
313 void Refresh(
size_t refresh_id,
size_t start_id = 0) {
315 nearest_id[refresh_id] = ID_NONE;
316 distance[refresh_id] = std::numeric_limits<double>::max();
319 size_t bin_id = org_bins[refresh_id];
320 Refresh_AgainstBin(refresh_id, bin_id);
324 size_t trait_offset = 1;
325 for (
size_t trait_id = 0; trait_id < traits.
GetSize(); trait_id++) {
326 size_t prev_bin_id = bin_id - trait_offset;
327 if (prev_bin_id < num_total_bins) {
328 Refresh_AgainstBin(refresh_id, prev_bin_id);
330 size_t next_bin_id = bin_id + trait_offset;
331 if (next_bin_id < num_total_bins) {
332 Refresh_AgainstBin(refresh_id, next_bin_id);
334 trait_offset *= num_trait_bins;
344 size_t bin_id = (size_t) -1;
345 for (
size_t i = 0; i < traits.
GetSize(); i++) {
346 const size_t cur_bin = (size_t) ((t_vals[i] - min_vals[i]) / bin_width[i]);
348 bin_id += cur_bin * scale;
349 scale *= num_trait_bins;
351 emp_assert(bin_id < num_total_bins, bin_id, num_total_bins, scale);
357 bin_ids.
resize(num_total_bins);
358 for (
auto & bin : bin_ids) bin.clear();
359 for (
size_t trait_id = 0; trait_id < traits.
GetSize(); trait_id++) {
360 bin_width[trait_id] = (max_vals[trait_id] - min_vals[trait_id]) / (
double) num_trait_bins;
363 for (
size_t org_id = 0; org_id < world.
GetSize(); org_id++) {
364 size_t cur_bin = CalcBin(org_id);
365 org_bins[org_id] = cur_bin;
366 bin_ids[cur_bin].
insert(org_id);
371 const size_t num_orgs = world.
GetSize();
373 const size_t num_traits = traits.
GetSize();
376 nearest_id.
resize(num_orgs);
377 distance.
resize(num_orgs);
380 num_trait_bins = (size_t) (std::pow(num_orgs, 1.0 / (
double)num_traits) + 0.5);
381 num_total_bins = (size_t) (std::pow(num_trait_bins, num_traits) + 0.5);
385 for (
size_t id = 0;
id < num_orgs;
id++) { Refresh(
id,
id+1); }
398 if (!is_setup) Setup();
405 min_id, distance[min_id], nearest_id[min_id], distance.
size());
407 else return nearest_id[min_id];
421 bool update_chart =
false;
423 for (
size_t i = 0; i < cur_vals.
size(); i++) {
424 if (cur_vals[i] <= min_vals[i]) {
425 min_vals[i] = cur_vals[i] - bin_width[i]/2.0;
428 if (cur_vals[i] >= max_vals[i]) {
429 max_vals[i] = cur_vals[i] + bin_width[i]/2.0;
435 if (!is_setup)
return;
439 bin_ids[org_bins[pos]].
erase(pos);
442 if (update_chart ==
true) {
444 org_bins[pos] = CalcBin(pos);
445 bin_ids[org_bins[pos]].
insert(pos);
448 for (
size_t id = 0;
id < world.
GetSize();
id++) {
456 org_bins[pos] = CalcBin(pos);
457 bin_ids[org_bins[pos]].
insert(pos);
458 for (
size_t id = 0;
id < world.
GetSize();
id++) {
459 if (nearest_id[
id] == pos) Refresh(
id);
477 const size_t num_orgs = world.
GetSize();
480 for (
size_t i = 0; i < num_orgs; i++) {
481 emp_assert(org_bins[i] < num_total_bins, i, org_bins[i], num_total_bins,
484 size_t org_count = 0;
485 for (
size_t i = 0; i < num_total_bins; i++) {
486 org_count += bin_ids[i].
size();
487 for (
size_t org_id : bin_ids[i]) {
500 template <
typename ORG>
507 world.OnWorldDestruct([info_ptr]()
mutable { info_ptr.
Delete(); });
510 world.OnPlacement( [info_ptr](
size_t pos)
mutable { info_ptr->Update(pos); } );
516 world.SetAddInjectFun( [&world, traits, world_size, info_ptr](
Ptr<ORG> new_org) {
517 size_t pos = info_ptr->GetBirthPos(world_size);
527 world.SetKillOrgFun( [&world, info_ptr](){
528 const size_t last_id = world.GetSize() - 1;
529 world.Swap(info_ptr->FindKill(), last_id);
530 info_ptr->is_setup =
false;
531 world.RemoveOrgAt(last_id);
532 world.Resize(last_id);
537 world.SetAddBirthFun( [&world, traits, world_size, info_ptr](
Ptr<ORG> new_org,
WorldPosition parent_pos) {
539 size_t pos = info_ptr->GetBirthPos(world_size);
543 world.SetAttribute(
"SynchronousGen",
"False");
544 world.SetAttribute(
"PopStruct",
"DiverseElites");
545 world.SetSynchronousSystematics(
false);
549 template <
typename ORG>
void Clear()
Definition: World_structure.h:389
iterator insert(ARGS &&...args)
Definition: vector.h:201
T & operator()(WorldPosition pos)
Definition: World_structure.h:80
bool OK()
A debug function to make sure the internal state is all valid.
Definition: World_structure.h:469
Definition: World_structure.h:29
WorldPosition & SetIndex(size_t _id)
Definition: World_structure.h:52
const emp::TraitSet< ORG > & GetPhenotypes() const
What phenotypic traits is the population tracking?
Definition: World.h:263
double CalcFitnessOrg(ORG &org)
Use the configured fitness function on the specified organism.
Definition: World.h:1181
bool is_setup
Have we initialized the internal data stucture?
Definition: World_structure.h:274
void Delete()
Definition: Ptr.h:737
emp::vector< double > EvalValues(target_t &target) const
Definition: Trait.h:160
void ResetBins()
Reset all of the bins in the multidimensional grid for nearest-neighbor analysis. ...
Definition: World_structure.h:356
Random & GetRandom()
Return a reference to the random number generator currently being used by world.
Definition: World.h:770
void Update(size_t pos)
Assume a position has changed; refresh it AND everything that had it as a closest connection...
Definition: World_structure.h:419
World< ORG > & world
World object being tracked.
Definition: World_structure.h:268
size_t num_trait_bins
How many bins should we use for each trait?
Definition: World_structure.h:275
void SetKillOrgFun(const fun_kill_org_t &_fun)
Definition: World.h:522
void SetSynchronousSystematics(bool synchronous)
Tell systematics managers that this world has synchronous generations.
Definition: World.h:433
uint32_t GetPopID() const
Definition: World_structure.h:45
emp::vector< size_t > org_bins
Which bin is each org currently in?
Definition: World_structure.h:278
uint32_t GetIndex() const
Definition: World_structure.h:44
Definition: BitVector.h:785
emp::vector< size_t > nearest_id
For each individual, whom are they closest to?
Definition: World_structure.h:265
TraitSet< ORG > traits
Traits we are tryng to spread.
Definition: World_structure.h:269
emp::vector< double > distance
And what is their distance?
Definition: World_structure.h:266
void push_back(PB_Ts &&...args)
Definition: vector.h:189
void MakeValid(WorldPosition pos)
Make sure position is valid; if not expand relevant vector.
Definition: World_structure.h:71
void SetGetNeighborFun(const fun_get_neighbor_t &_fun)
Definition: World.h:526
void SetAddInjectFun(const fun_find_inject_pos_t &_fun)
Definition: World.h:513
this_t & MarkSpaceStructured(bool in=true)
Definition: World.h:300
Setup a World with a population of organisms that can evolve or deal with ecological effects...
Definition: World.h:94
size_t size() const
Definition: vector.h:151
WorldPosition GetRandomNeighborPos(WorldPosition pos)
Use the specified function to get a neighbor (if not set, assume well mixed).
Definition: World.h:788
void SetMapElites(World< ORG > &world, TraitSet< ORG > traits, const emp::vector< size_t > &trait_counts)
Definition: World_structure.h:164
WorldPosition & MarkInvalid()
Definition: World_structure.h:53
void Resize(size_t new_size)
Definition: World.h:723
WorldPosition & SetPopID(size_t _id)
Definition: World_structure.h:51
WorldPosition & SetActive(bool _active=true)
Definition: World_structure.h:50
bool IsActive() const
Definition: World_structure.h:47
size_t FindKill()
Definition: World_structure.h:397
Build a class to track distances between organisms.
Definition: World_structure.h:262
size_t GetSize() const
How many organisms can fit in the world?
Definition: World.h:245
WorldPosition(size_t _id, size_t _pop_id=0)
Definition: World_structure.h:38
void Refresh(size_t refresh_id, size_t start_id=0)
Definition: World_structure.h:313
World_MinDistInfo(World< ORG > &in_world, const TraitSet< ORG > &in_traits)
Definition: World_structure.h:280
emp::vector< double > min_vals
Smallest value found for each trait.
Definition: World_structure.h:270
void SetAddBirthFun(const fun_find_birth_pos_t &_fun)
Definition: World.h:518
void SetDiverseElites(World< ORG > &world, TraitSet< ORG > traits, size_t world_size)
This first version will setup a Diverse-Elites world and specify traits to use.
Definition: World_structure.h:501
size_t CalcBin(size_t id)
Calculate which bin an organism should be in.
Definition: World_structure.h:340
size_t GetSize() const
Definition: Trait.h:132
WorldPosition()
Definition: World_structure.h:37
A vector that can be indexed with a WorldPosition.
Definition: World_structure.h:58
emp::vector< double > max_vals
Largest value found for each trait.
Definition: World_structure.h:271
void SetAttribute(const std::string &name, T &&val)
Definition: World.h:636
size_t EvalBin(target_t &target, emp::vector< size_t > bin_counts) const
Definition: Trait.h:167
bool IsValid(WorldPosition pos) const
Test if a position is currently valid.
Definition: World_structure.h:63
static constexpr type_if< T, std::is_integral > Pow(T base, T p)
A fast (O(log p)) integral-power command.
Definition: math.h:150
void resize(size_t new_size)
Definition: vector.h:161
ORG & GetOrg(size_t id)
Definition: World.h:316
static constexpr size_t invalid_id
Definition: World_structure.h:35
double CalcDist(size_t id1, size_t id2)
Definition: World_structure.h:288
If we are in emscripten, make sure to include the header.
Definition: array.h:37
size_t GetRandomCellID()
Get the position a cell, at random.
Definition: World.h:779
double CalcFitnessID(size_t id)
Use the configured fitness function on the organism at the specified position.
Definition: World.h:1187
#define emp_assert(...)
Definition: assert.h:199
emp::vector< double > bin_width
Largest value found for each trait.
Definition: World_structure.h:272
void SetPools(World< ORG > &world, size_t num_pools, size_t pool_size, bool synchronous_gen=false)
Definition: World_structure.h:96
size_t GetBirthPos(size_t world_size)
Return an empty world position. If none are available, return the position of an org to be killed...
Definition: World_structure.h:411
size_t GetNumOrgs() const
How many organisms are currently in the world?
Definition: World.h:248
iterator erase(ARGS &&...args)
Definition: vector.h:207
void RemoveOrgAt(WorldPosition pos)
Definition: World.h:887
size_t FindMinIndex(const T &v)
Find the index with the minimal value (picks first in cases of a tie).
Definition: vector_utils.h:63
bool IsValid() const
Definition: World_structure.h:48
const T & operator()(WorldPosition pos) const
Definition: World_structure.h:85
emp::vector< std::set< size_t > > bin_ids
Which org ids fall into each bin?
Definition: World_structure.h:277
emp::vector< double > CalcOffsets(target_t &target1, target_t &target2) const
Definition: Trait.h:177
void Refresh_AgainstBin(size_t refresh_id, size_t target_bin)
Definition: World_structure.h:296
void Setup()
Definition: World_structure.h:370
constexpr size_t GetSize(T(&)[N])
Determine the size of a built-in array.
Definition: functions.h:81
size_t num_total_bins
How many bins are there overall?
Definition: World_structure.h:276
bool IsOccupied(WorldPosition pos) const
Does the specified cell ID have an organism in it?
Definition: World.h:277
this_t & MarkSynchronous(bool in=true)
Definition: World.h:296