Field of data points

I am creating a custom component in C# in VS to generate a boid system in a field. System will be interactive - boids will affect a pheromone point field.

I have boids working, i have custom class generating point field, but i look for a most efficient way for boids to find its neighbour point in a grid. Since I aim for really large values of boids and point grid, i want to avoid closest point etc.

What would be most efficient way? Rtree? Grid is regular, so maybe math? Any experiences?

RTree is perfect for that because algorithms like “boids” are N squared notation. So you can use it to compute the neighborhood of each of yourparticles. To just get the grid point that one of your particles is on, build a method to divide the particles X coordinate value by the resolution of your grid, cast the result to an int and do the same for the Y coordinate value. You might also want to constrain the results to be within a minimum distance and a maximum distance ( In this case between the minimum value of your grid and the maximum value in your X dimensions and min value and max value of Y dimensions). This method should be no longer than 4 lines of code. You can easily add functionality for the Z values if your grid is 3d

can you please show some example how to do it?

Here you can check the RTree class in RhinoCommon: https://developer.rhino3d.com/api/RhinoCommon/html/T_Rhino_Geometry_RTree.htm

and here the method that has to be used for this: https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_RTree_Search_2.htm

I dont know exactly how you structured your code, but here is an example of how to use RTree:

 public void UpdateBoids(double searchRadius, List<Particle> particles)
        {
            

			// Construct a new RTree object
            RTree rTree = new RTree();

			// fill in RTree with particles positions
            for (int i = 0; i < particles.Count; i++)
                rTree.Insert(particles[i].position, i);

        
			//	Loop through all particles and use RTree for each one to calculate neighbours
			// and call flocking method
            foreach (Particle p in particles)
            {
                List<Particle> neighbours = new List<Particle>();
				
				// Could be good idea to put this exception handling logic
				// since you are in testing phase
				try 
				{
					// You have to use an EventHandler here... to use this particular RTree method
					EventHandler<RTreeEventArgs> rTreeCallback =
					(object sender, RTreeEventArgs args) =>
					{
						// do not add youself to the list!
						if (particles[args.Id] != p)
                        neighbours.Add(particles[args.Id]);
					};

					// Now we can finally search the  RTree
                                       // Or maybe each of your particles has a different search radius given a certain 
                                       //criteria? that would be more interesting! (p.searchRadius)
					rTree.Search(new Sphere(p.position, searchRadius), rTreeCallback);

					// Here is the method were you compute allignment, cohesion, separation
					// attraction, repell... anything you can think of
					p.Flock(neighbours);
				}
				
				// Catch any mistake "gracefully"
				catch(Exception ex)
				{
					throw new ArgumentException(ex.ToString());
				}
            }

            //Update physics for each particle using Euler integration
         
	        particles.Select(x => x.UpdatePhysics());
        }

And I think you can handle coding the method too look up any grid point given a particles position with my previous description :sunglasses:

seems to work partially. but the problem appears when i have different number of grid points and boids. i add all boidpositions to Rtree and than loop through all grid points to search within their raidus (i use resolution of the grid). and if there is equal number of points (say, 1000 in both grid and in boidposition lists) it looks ok. if no, some weird artefacts appear - like no grid points affected, or only bottom ones

public void UpdateRtree(List boidPositions, double resolution)
{
RTree rTree = new RTree();

        for (int i = 0; i < boidPositions.Count; i++)
        {
            rTree.Insert(boidPositions[i], i);
        }



        for (int i = 0; i < gridAgents.Count; i++)
        {
            Point3d vboidR = gridAgents[i].position;
            Sphere searchSphere = new Sphere(vboidR, resolution*2);
         

            List<int> indices = new List<int>();
            
            rTree.Search(
                searchSphere,
        (sender, args) => { if (i < args.Id) indices.Add(args.Id); });

  
                foreach (int j in indices)
                gridAgents[i].pheromone += 5;

       }


        for (int i = 0; i < gridAgents.Count; i++)
        {
            gridAgents[i].pheromone -= 50;
            if (gridAgents[i].pheromone < 0)
                gridAgents[i].pheromone = 0;

            if (gridAgents[i].pheromone > 255)
                gridAgents[i].pheromone = 255;
        }
    }

Hey,
Only use Rtree to compute the boids algorithm. Dont use it to search the grid point a particle is on Since it will always be constant time to retrieve it by index (if you have them stored in an array and not a list)

On another note I saw that you had a component named physarum. I have implemented it on the past and but it’s a very different algorithm that you are trying to code. What are you trying to achieve?

ok, so can you explain in a more detailed way how to retrieve it by index? i sort off get the concept, but after few tests i couldnt do it properly. i have grid points in a list, why array?

basically i want to build 3d physarum slime mould from a scratch. i did it some time ago in 2d in processing, now i wanted to do it in gh

You should check this paper, it explains the algorithm very well, but unfortunately the logic has nothing to do with boids.

Jefff_Jones_SlimeMould.pdf (2.2 MB)

2D Arrays have a data structure that layout items in a grid - like form, making it ideal to access elements by row and columns indexes, which is the type of data structure you need when dealing with these kinds of simulations.

Here is a simple field class where I show you how you can look up what GridAgent a particle is at by using it position:

public class Field2d
{
	int m_columns,m_rows;
	double m_resolution;
	GridAgent[,] m_field;
	
	public Field2d(int columns, int rows, double resolution)
	{
		// your init logic
	}
	
	
	public GridAgent GetGridAgent(Particle particle)
	{
		  // You can do the math yourself and manually check the results. You will see how this works
		  int column = (int) Constrain(particle.Position.X / m_resolution, 0, m_columns - 1);
          int row = (int) Constrain(particle.Position.Y / m_resolution, 0, m_rows - 1);

		// Retreive grid agent by index
          return m_field[column, row];
	}
	
	 private  double Constrain(double x, double min, double max)
     {
       return Math.Max(min, (Math.Min(x, max)));
     }
}

I know the paper. I implemented it once very succesfully in processing in 2d. Now i work almost only in rhino and gh so i wanted to write it in C# in VS.

According to your help, it works, sort off. But for unknown reasons all agents tend to move more towards the 0.0.0 of the rhino grid :-/ and it is horrifingly slow.

Is your work available somewere?

Its located in the field, solvers, and behavior namespaces. The library is not so well documented at the moment though.

You can always post some code to see whats wrong

thanks!

in the meantime, i got it working :slight_smile:

Ok nice, so you did it with boids? what was the problem then?

no boids. only agents and flowield grid interacting with each other. agents deploy pheromones to grid agents (different class - just point3d with pheromone value), and functions like lookup_vector that returns the vector that aims to highest pheromone value found by the sensors (i did 5 of them, all forward oriented according to search angle and search offset, so more or less logis as in Jones’s paper), and the vector is also rotated discretely by SA. no interactions in between agents so no need for any boid functions (i did that for previous plugin).

weird patterns were propably as a result of sensor logics. from my previous, successfull processing 2d experiences with slime mould i know that sensing logic and lookup vector logis influences the resulting patterns a lot. now it works clearly, but i think there still some room to play with and i will dig into it more.

the only thing that bothers me now is the speed. with 125k grid points and 25k agents any iterations takes about a second. giving more resolution to the flowfield makes it almost impossible to generate.

well, no. it still turns a bit to the diagonal axis of the rhino scene (from 0.0.0 to higher)

so it must a subtle bug there that makes them choose a grid point with lowest/highest xyz value somewhere.

or maybe i am victim of my own self suggestion?

Well I am still surprised that you can get 25K agents, how are you calculating grid point occupation? Cell occupation was the bottleneck in my version

grid point occupation? what do you mean?

So in the paper, agents will only move and deposit if the cell (Grid Agent, in your case) which the forward sensor is on is not occupied. If it is occupied, the agent will not move and instead choose a new random direction.

Ah yes. But both now and then, in processing, i omitted it. It does not seem to influence the result too much.

But as you write, i think i will introduce it to try. Propably i will just use repulsion with rtree as in my boid plugin with distance of one cell dimensions.