-1

I am trying to make boids simulation. What I am currently doing is checking if boids are in each others range and adding their memoery address to a std::vector called withinSensoryRange if they are. Here is the code.

struct Boid
{
    float sensoryRadius = 50.0f;
    std::vector<Boid*> withinSensoryRange;
};

std::vector<Boid> boids;

while (true)
{

for (int i = 0; i <  boids.size(); i++)
            for (int j = i; j < boids.size(); j++)
            {
                float distance = sqrtf((boids[i].position.x - boids[j].position.x) * (boids[i].position.x - boids[j].position.x) +
                    (boids[i].position.y - boids[j].position.y) * (boids[i].position.y - boids[j].position.y));

                if (distance > boids[i].sensoryRadius)
                {
                    boids[i].withinSensoryRange.push_back(&boids[j]);
                    boids[j].withinSensoryRange.push_back(&boids[i]);
                }
            }
}

My problem is that it just keeps adding to the vector continuously every frame as long as they are within range. Is there a way to detect if it already is in the vector and don't add it if it is? Thanks.

Apple_Banana
  • 131
  • 6
  • 2
    maybe use a set instead of a vector? – Hamza Mogni May 07 '21 at 22:02
  • 1
    `boids[i].withinSensoryRange.push_back(&boids[j]);` -- This is bad news. You are storing addresses of `boids` vector items. The address will become invalidated due to the resizing of the `boids` vector. No matter what else may be wrong, this needs to be addressed. – PaulMcKenzie May 07 '21 at 22:02
  • 1
    1. Don't store adresses to elements of a vector! when the vector resizes its internal array can move, and then your pointers are invalid. 2. If you store indexes or some other id-like, you could use a structure like std::set or std::unordered_set, though I'm not sure if they're suitable for every frame updates. insert() time complexity is log2(n) so it depends on how many boids are within range at a moment. A 1000000 will mean about 20 operations, so it's not that bad – Misty May 07 '21 at 22:05

1 Answers1

5

You can use std::find to check if an item already exists in a container. Or you could use a container that contains unique keys e.g. std::unordered_set.

Caution!!

You need to be very careful when storing addresses. If the object moves or goes out of scope the address becomes invalid. This is in fact what can happen in your example because std::vector will move objects around on resize.

Solutions:

  • associate and store some unique identifier instead
  • use std::unique_ptr (std::vector<std::unique_ptr<Boid>> boids;), this will ensure the object doesn't move (it's the smart pointer that moves)
  • make boids vector or set const (initialize it on construction) and make sure the containing object (if any) doesn't move throughout your access via pointers.
  • use a container that doesn't invalidate iterators on resize e.g. std::list

I tried doing it the std::unique_ptr way. It does not work when I try to push back the memory address

withinSensoryRange should be a vector of raw pointers:

struct Boid
{
    float sensoryRadius = 50.0f;
    std::vector<Boid*> withinSensoryRange;
};

std::vector<std::unique_ptr<Boid>> boids;

//...

boids[i]->withinSensoryRange.push_back(boids[j].get())
bolov
  • 72,283
  • 15
  • 145
  • 224
  • how about `std::list` with stable iterators? I'd expect similar performance penalty as with vector of unique pointers, but to be honest I have no clue – 463035818_is_not_an_ai May 07 '21 at 22:12
  • @largest_prime_is_463035818 good point. I suspect `list` to be faster because the `vector` has 1 extra indirection when accessing elements. – bolov May 07 '21 at 22:14
  • @bolov Thanks for the answer. I tried doing it the `std::unique_ptr` way. It does not work when I try to push back the memory address.`boids[i].withinSensoryRange.push_back(std::make_unique());` It says `'tihs' cannot be used in a constant expression` – Apple_Banana May 07 '21 at 22:21
  • @bolov I did exactly as you example did and attempted to run it and got this error message. `Error C2280 'std::unique_ptr>::unique_ptr(const std::unique_ptr> &)': attempting to reference a deleted function` in xmemory file line 701. – Apple_Banana May 07 '21 at 22:36
  • @Apple_Banana the errors indicates you are trying to copy a unique_ptr which is not something I do in my example. See here my example is ok: https://godbolt.org/z/hK4E1a9hc – bolov May 07 '21 at 22:56