Complex Boundaries

Hello!

Here we have a simple system for vehicles to avoid a demarcated boundary.

// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com

// Stay Within Walls
// "Made-up" Steering behavior to stay within walls


Vehicle v;
boolean debug = true;

float d = 25;

void setup() {
  size(640, 360);
  v = new Vehicle(width/2, height/2);
}

void draw() {
  background(255);

  if (debug) {
    stroke(175);
    noFill();
    rectMode(CENTER);
    rect(width/2, height/2, width-d*2, height-d*2);
  }

  v.boundaries();
  v.run();
}

void mousePressed() {
  debug = !debug;
}

// The Nature of Code
// Daniel Shiffman
// http://natureofcode.com

// The "Vehicle" class

class Vehicle {

  PVector position;
  PVector velocity;
  PVector acceleration;
  float r;

  float maxspeed;
  float maxforce;
  
  Vehicle(float x, float y) {
    acceleration = new PVector(0, 0);
    velocity = new PVector(3, -2);
    velocity.mult(5);
    position = new PVector(x, y);
    r = 6;
    maxspeed = 3;
    maxforce = 0.15;
  }

  void run() {
    update();
    display();
  }

  // Method to update position
  void update() {
    // Update velocity
    velocity.add(acceleration);
    // Limit speed
    velocity.limit(maxspeed);
    position.add(velocity);
    // Reset accelertion to 0 each cycle
    acceleration.mult(0);
  }

  void boundaries() {

    PVector desired = null;

    if (position.x < d) {
      desired = new PVector(maxspeed, velocity.y);
    } 
    else if (position.x > width -d) {
      desired = new PVector(-maxspeed, velocity.y);
    } 

    if (position.y < d) {
      desired = new PVector(velocity.x, maxspeed);
    } 
    else if (position.y > height-d) {
      desired = new PVector(velocity.x, -maxspeed);
    } 

    if (desired != null) {
      desired.normalize();
      desired.mult(maxspeed);
      PVector steer = PVector.sub(desired, velocity);
      steer.limit(maxforce);
      applyForce(steer);
    }
  }  

  void applyForce(PVector force) {
    // We could add mass here if we want A = F / M
    acceleration.add(force);
  }


  void display() {
    // Draw a triangle rotated in the direction of velocity
    float theta = velocity.heading2D() + radians(90);
    fill(127);
    stroke(0);
    pushMatrix();
    translate(position.x, position.y);
    rotate(theta);
    beginShape(TRIANGLES);
    vertex(0, -r*2);
    vertex(-r, r*2);
    vertex(r, r*2);
    endShape();
    popMatrix();
  }
}

Now, how could I make this boundary have a complex shape, rather than it being a simple rectangle? I would like the boundary, and the lines that represent it, to bend at arbitrary angles and have an arbitrary number of segments, as in a complex 2D shape with any coordinates as its vertices. How could this be done?

Thanks!

1 Like

Inside the vehicle class’s bondaries() function, is this code:

    if (position.x < d) {
      desired = new PVector(maxspeed, velocity.y);
    } 
    else if (position.x > width -d) {
      desired = new PVector(-maxspeed, velocity.y);
    } 

    if (position.y < d) {
      desired = new PVector(velocity.x, maxspeed);
    } 
    else if (position.y > height-d) {
      desired = new PVector(velocity.x, -maxspeed);
    } 

This sets a desired direction for the Vehicle based on it’s position.
You simple need to increase the complexity here.

One approach would be to define a new type of thing called a ZoneTri. A ZoneTri would be a triangular area defined by its three corner points.

How can you determine if a Vehicle is inside a ZoneTri? That’s triangle-point collision! Look that up!
For now, draw the ZoneTri in a different color if the vehicle is over it.

Then define a new object called a Zone. A Zone has many ZoneTri’s in it, and a desired velocity that any Vehicles in any of its ZoneTri’s should take.

… It’s quite a bit of work. Try it yourself! Post the code of your attempt if you get stuck.

1 Like

You could use geomerative library to create a complex RShape as the boundary I have created such an example in ruby-processing/JRubyArt-examples under external-library/gem folder on github. Unfortunately I have yet to find out how to copy links on my pad, and I,m stranded from my linux box.

2 Likes

Hi @LordCacops,

I think @monkstone 's suggestion is well suited for what you’re trying to achieve.
Here’s a simple example sketch in Python mode based on the (very useful) examples he provided in this thread and on his gist.

(Click the mouse to change mode: enclosing/avoidance)

add_library('geomerative')

# Polygon parameters
N = 10
angle = radians(360) / N
radius = 200

# Enclose Mode (enclosing or repulsing particles)
Enclose = True

def setup():
    size(1000, 600, P2D)
    smooth(8)
    
    global polyshape, balls, center

    # Array of Ball() objects
    balls = [Ball() for i in xrange(30)]
    
    # Instantiating our RPolygon
    RG.init(this)
    rpoly = RPolygon()
    
    # Building polygon from vertices location
    for i in xrange(N):
        r = random(.5, 1.3)
        x = cos(angle * i) * (radius * r)  + width/2
        y = sin(angle * i) * (radius * r)  + height/2
        rpoly.addPoint(RPoint(x, y))
     
    # Converting our RPolygon() to RShape()  
    polyshape = RShape(rpoly.toShape())
    
    # Stores location of its centroid
    center = polyshape.getCentroid()
    
    
def draw():
    pushStyle()
    noStroke()
    fill(255, 100)
    rect(0, 0, width, height)
    popStyle()
    
    # Displaying balls + updating location
    for b in balls:
        b.update()
        b.render()
    
    # Drawing our polygon shape
    pushStyle()
    stroke('#504AFF')
    strokeWeight(2)
    noFill()
    polyshape.draw()
    popStyle()
    

       
class Ball(object):
    def __init__(self):
        self.loc = PVector(random(width), random(height))
        self.vel = PVector.random2D()
        
    def update(self):
        self.loc.add(self.vel) # Updating location
        self.vel.limit(2) # Limiting velocity
        
        dir = PVector(center.x, center.y).sub(self.loc) # Direction
        f = dir.sub(self.vel).normalize().mult(.1) # Force (remove 'mult()' for a hard stop)
        
        if Enclose:
            # If ball not within the boundaries of the polygon:
            # --> divert it back to the center of the poygon
            if not polyshape.contains(RPoint(self.loc.x, self.loc.y)):
                self.vel.add(f)
        
        # Else --> avoidance behavior
        elif polyshape.contains(RPoint(self.loc.x, self.loc.y)):
            self.vel.sub(f)
                
        # Canvas boundaries       
        if self.loc.x > width or self.loc.x < 0: self.vel.x *= -1
        if self.loc.y > height or self.loc.y < 0: self.vel.y *= -1


    def render(self):
        if polyshape.contains(RPoint(self.loc.x, self.loc.y)):
            strokeWeight(10)
            stroke('#FF4A62')
        else:
            strokeWeight(6)
            stroke('#69C375')
            
        point(self.loc.x, self.loc.y, self.loc.z)
        
def mouseClicked():
    global Enclose
    Enclose = not Enclose
    print "Enclose Mode is %s" % Enclose
1 Like

:ok_hand: thanks for creating link I,m pretty incompetent on my FireHD8.mf Fir000000

To avoid collision with a complex shape (‘n’ sided closed polygon) then it is not enough to know whether a point is inside or outside the shape.

If you consider each side of the closed as a wall then for each wall you need to know

  1. the position (XY coordinates of each end)
  2. which side of the wall faces inside and which faces outside the closed polygon

The simplified algorithm then is to

calculate the velocity vector
for each wall in the shape
  see if the wall is intersected by the velocity vector
  calculate the intersection point and the distance to it from the moving object
  remember the nearest wall / intersection point
if we have an intersection then
  calculate the reflection vector based on the velocity vector and the wall normal vector
  calculate the reflection distance (velocity magnitude - intersection distance)
  calculate the destination based on the reflection distance and reflection vector 

This approach is used in the AI for 2D Games library and the technique is called wall avoidance

2 Likes

Thank you. I will try to come up with the code for that.

I did it using Geomerative. Now I am looking to revert the desired vector so that the agents turn around smoothly in the opposite direction when they are outside the boundary rather than simply becoming instantly reversed.

import geomerative.*;

RShape shape;
RShape rect;



Flock flock;

void setup() {
  size(640, 888, P2D);
  RG.init(this);
  RG.setPolygonizer(RG.ADAPTATIVE);
  flock = new Flock();
  // Add an initial set of boids into the system
  for (int i = 0; i < 50; i++) {
    Boid b = new Boid(width/2, height/2);
    flock.addBoid(b);
  }
}

void draw() {
  background(255);
  flock.run();
  flock.respectBounds();

  // Instructions
  fill(0);
  text("Drag the mouse to generate new boids.", 10, height-16);

}

class Flock {
  ArrayList<Boid> boids; // An ArrayList for all the boids

  Flock() {
    boids = new ArrayList<Boid>(); // Initialize the ArrayList
  }

  void run() {
    for (Boid b : boids) {
      b.run(boids);  // Passing the entire list of boids to each boid individually
    }
  }

  void addBoid(Boid b) {
    boids.add(b);
  }

  void respectBounds() { 
    noFill(); 
    RShape wave = new RShape();
    wave.addMoveTo(50, 100);
    wave.addLineTo(300, 100);
    wave.addLineTo(555, 600);
    wave.addLineTo(200, 700);
    wave.addLineTo(50, 100);
    wave.draw();

    for (Boid b : boids) {
      if (wave.contains(b.position.x, b.position.y) == false) {
        b.velocity.mult(-1); //= new PVector(random(width), random(height));
      }
    }
  }
}
class Boid {

  PVector position;
  PVector velocity;
  PVector acceleration;
  float r;
  float maxforce;    // Maximum steering force
  float maxspeed;    // Maximum speed

  Boid(float x, float y) {
    acceleration = new PVector(0, 0);
    velocity = new PVector(random(-1, 1), random(-1, 1));
    position = new PVector(x, y);
    r = 3.0;
    maxspeed = 3;
    maxforce = 0.05;
  }

  void run(ArrayList<Boid> boids) {
    flock(boids);
    update();
    borders();
    render();
  }

  void applyForce(PVector force) {
    // We could add mass here if we want A = F / M
    acceleration.add(force);
  }

  // We accumulate a new acceleration each time based on three rules
  void flock(ArrayList<Boid> boids) {
    PVector sep = separate(boids);   // Separation
    PVector ali = align(boids);      // Alignment
    PVector coh = cohesion(boids);   // Cohesion
    // Arbitrarily weight these forces
    sep.mult(map(mouseX, 0, 640, 0, 4));
    ali.mult(1.0);
    coh.mult(map(mouseY, 0, 888, 0, 4));
    // Add the force vectors to acceleration
    applyForce(sep);
    applyForce(ali);
    applyForce(coh);
  }

  // Method to update position
  void update() {
    // Update velocity
    velocity.add(acceleration);
    // Limit speed
    velocity.limit(maxspeed);
    position.add(velocity);
    // Reset accelertion to 0 each cycle
    acceleration.mult(0);
  }

  // A method that calculates and applies a steering force towards a target
  // STEER = DESIRED MINUS VELOCITY
  PVector seek(PVector target) {
    PVector desired = PVector.sub(target, position);  // A vector pointing from the position to the target
    // Normalize desired and scale to maximum speed
    desired.normalize();
    desired.mult(maxspeed);
    // Steering = Desired minus Velocity
    desired.sub(velocity); //elimine steer. en lugar queda desired. uso un vector menos!
    desired.limit(maxforce);  // Limit to maximum steering force
    return desired;
  }


  void render() {
    // Draw a triangle rotated in the direction of velocity
    float theta = velocity.heading() + radians(90);
    fill(175);
    stroke(0);
    pushMatrix();
    translate(position.x, position.y);
    rotate(theta);
    rect(-3*r, 2*r, r, r); //he aca un gridsito pegado al triangulo que apunta a donde el monstruo quiere 
    rect(-2*r, 2*r, r, r); // el cual sera optado como indicador del fenotipo visual del animalin.
    rect(-1*r, 2*r, r, r);
    rect(0*r, 2*r, r, r);
    rect(1*r, 2*r, r, r);
    rect(2*r, 2*r, r, r);
    rect(-3*r, 3*r, r, r);
    rect(-2*r, 3*r, r, r);
    rect(-1*r, 3*r, r, r);
    rect(0*r, 3*r, r, r);
    rect(1*r, 3*r, r, r);
    rect(2*r, 3*r, r, r);
    rect(-3*r, 4*r, r, r);
    rect(-2*r, 4*r, r, r);
    rect(-1*r, 4*r, r, r);
    rect(0*r, 4*r, r, r);
    rect(1*r, 4*r, r, r);
    rect(2*r, 4*r, r, r);
    popMatrix();
  }

  // Wraparound
  void borders() {
    if (position.x < -r) position.x = width+r;
    if (position.y < -r) position.y = height+r;
    if (position.x > width+r) position.x = -r;
    if (position.y > height+r) position.y = -r;
  }

  // Separation
  // Method checks for nearby boids and steers away
  PVector separate (ArrayList<Boid> boids) {
    float desiredseparation = 25.0f;
    PVector desired = new PVector(0, 0, 0);
    int count = 0;
    // For every boid in the system, check if it's too close
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      // If the distance is greater than 0 and less than an arbitrary amount (0 when you are yourself)
      if ((d > 0) && (d < desiredseparation)) {
        // Calculate vector pointing away from neighbor
        PVector diff = PVector.sub(position, other.position);
        diff.normalize();
        diff.div(d);        // Weight by distance
        desired.add(diff);
        count++;            // Keep track of how many
      }
    }
    // Average -- divide by how many
    if (count > 0) {
      desired.div((float)count);
    }

    // As long as the vector is greater than 0
    if (desired.mag() > 0) {
      // Implement Reynolds: Steering = Desired - Velocity
      desired.normalize();
      desired.mult(maxspeed);
      desired.sub(velocity);
      desired.limit(maxforce);
    }
    return desired;
  }

  // Alignment
  // For every nearby boid in the system, calculate the average velocity
  PVector align (ArrayList<Boid> boids) {
    float neighbordist = 50;
    PVector sum = new PVector(0, 0);
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      if ((d > 0) && (d < neighbordist)) {
        sum.add(other.velocity);
        count++;
      }
    }
    if (count > 0) {
      sum.div((float)count);
      sum.normalize();
      sum.mult(maxspeed);
      PVector desired = PVector.sub(sum, velocity);
      desired.limit(maxforce);
      return desired;
    } else {
      return new PVector(0, 0);
    }
  }

  // Cohesion
  // For the average position (i.e. center) of all nearby boids, calculate steering vector towards that position
  PVector cohesion (ArrayList<Boid> boids) {
    float neighbordist = 50;
    PVector sum = new PVector(0, 0);   // Start with empty vector to accumulate all positions
    int count = 0;
    for (Boid other : boids) {
      float d = PVector.dist(position, other.position);
      if ((d > 0) && (d < neighbordist)) {
        sum.add(other.position); // Add position
        count++;
      }
    }
    if (count > 0) {
      sum.div(count);
      return seek(sum);  // Steer towards the position
    } else {
      return new PVector(0, 0);
    }
  }
}
1 Like