书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第6章目录
6.9 多段路径跟随
1、多段路径跟随
我们解决了单个线段的路径跟随问题，接下来该如何解决多个相连线段的路径跟随问题？让我们回顾小车沿着屏幕运动的例子，假设我们已经到了步骤3。
-
步骤3：在路径上寻找一个目标位置
图6-32
为了寻找目标位置，我们必须找到线段上的法线交点。但现在的路径是由多个线段组成的，法线交点也有多个（如图6-32所示）。
该选择哪个交点？这里有两个选择条件：
（a）选择最近的法线交点；
（b）这个交点必须位于路径内。如果只有一个点和一条无限长的直线，总能得到位于直线内的法线交点。但如果是一个点和一个线段，则不一定能找到位于线段内的法线交点。因此，如果法线交点不在线段内，我们就应该将它排除在外。得到符合条件的法线交点后（在上图中，只有两个符合条件的交点），我们需要挑选出最近的点作为目标位置。
2、加入一个ArrayList对象
- 为了实现这样的特性，我们要扩展Path类，加入一个ArrayList对象用于存放路径的顶点（代替之前的起点和终点）。
class Path {
// A Path is an arraylist of points (PVector objects)
ArrayList<PVector> points;
// A path has a radius, i.e how far is it ok for the boid to wander off
float radius;
Path() {
// Arbitrary radius of 20
radius = 20;
points = new ArrayList<PVector>();
}
// Add a point to the path
void addPoint(float x, float y) {
PVector point = new PVector(x, y);
points.add(point);
}
PVector getStart() {
return points.get(0);
}
PVector getEnd() {
return points.get(points.size()-1);
}
// Draw the path
void display() {
// Draw thick line for radius
stroke(175);
strokeWeight(radius*2);
noFill();
beginShape();
for (PVector v : points) {
vertex(v.x, v.y);
}
endShape();
// Draw thin line for center of path
stroke(0);
strokeWeight(1);
noFill();
beginShape();
for (PVector v : points) {
vertex(v.x, v.y);
}
endShape();
}
}
- 支持多段路径的Path类已经定义好，下面轮到Vehicle类处理多段路径了。之前我们已经学会如何为单个线段寻找法线交点，只需要加入一个循环就能得到所有线段的法线交点。
for (int i = 0; i < p.points.size()-1; i++) {
PVector a = p.points.get(i);
PVector b = p.points.get(i+1);
PVector normalPoint = getNormalPoint(predictLoc,a,b); 为每个线段寻找法线交点
- 接下来，我们应该确保法线交点处在点a和点b之间。在本例中，路径的走向是由左向右，因此只需验证法线交点的x坐标是否位于a和b的x坐标之间。
if (normalPoint.x < a.x || normalPoint.x > b.x) {
normalPoint = b.get(); 如果无法找到法线交点，就把线段的终点当做法线交点
}
- 使用一个小技巧：如果法线交点不在线段内，我们就把线段的终点当做法线交点。这样可以确保小车始终留在路径内，即使它偏离了线段的边界。
- 最后，我们需要选出离小车最近的法线交点。为了完成这个任务，我们从一个很大的“世界记录”距离开始，再一次遍历每个法线交点，看看它的距离是否打破了这个记录（比记录小）。每当某个法线交点打破了记录，我们就更新记录，把这个法线交点赋给target变量。循环结束时，target变量就是最近的法线交点。
3、示例
示例代码6-6 路径跟随
boolean debug = true;
// A path object (series of connected points)
Path path;
// Two vehicles
Vehicle car1;
Vehicle car2;
void setup() {
size(640, 360);
// Call a function to generate new Path object
newPath();
// Each vehicle has different maxspeed and maxforce for demo purposes
car1 = new Vehicle(new PVector(0, height/2), 2, 0.04);
car2 = new Vehicle(new PVector(0, height/2), 3, 0.1);
}
void draw() {
background(255);
// Display the path
path.display();
// The boids follow the path
car1.follow(path);
car2.follow(path);
// Call the generic run method (update, borders, display, etc.)
car1.run();
car2.run();
car1.borders(path);
car2.borders(path);
// Instructions
fill(0);
text("Hit space bar to toggle debugging lines.\nClick the mouse to generate a new path.", 10, height-30);
}
void newPath() {
// A path is a series of connected points
// A more sophisticated path might be a curve
path = new Path();
path.addPoint(-20, height/2);
path.addPoint(random(0, width/2), random(0, height));
path.addPoint(random(width/2, width), random(0, height));
path.addPoint(width+20, height/2);
}
public void keyPressed() {
if (key == ' ') {
debug = !debug;
}
}
public void mousePressed() {
newPath();
}
Vehicle .pde
class Vehicle {
// All the usual stuff
PVector position;
PVector velocity;
PVector acceleration;
float r;
float maxforce; // Maximum steering force
float maxspeed; // Maximum speed
// Constructor initialize all values
Vehicle( PVector l, float ms, float mf) {
position = l.get();
r = 4.0;
maxspeed = ms;
maxforce = mf;
acceleration = new PVector(0, 0);
velocity = new PVector(maxspeed, 0);
}
// Main "run" function
public void run() {
update();
display();
}
// This function implements Craig Reynolds' path following algorithm
// http://www.red3d.com/cwr/steer/PathFollow.html
void follow(Path p) {
// Predict position 50 (arbitrary choice) frames ahead
// This could be based on speed
PVector predict = velocity.get();
predict.normalize();
predict.mult(50);
PVector predictpos = PVector.add(position, predict);
// Now we must find the normal to the path from the predicted position
// We look at the normal for each line segment and pick out the closest one
PVector normal = null;
PVector target = null;
float worldRecord = 1000000; // Start with a very high record distance that can easily be beaten
// Loop through all points of the path
for (int i = 0; i < p.points.size()-1; i++) {
// Look at a line segment
PVector a = p.points.get(i);
PVector b = p.points.get(i+1);
// Get the normal point to that line
PVector normalPoint = getNormalPoint(predictpos, a, b);
// This only works because we know our path goes from left to right
// We could have a more sophisticated test to tell if the point is in the line segment or not
if (normalPoint.x < a.x || normalPoint.x > b.x) {
// This is something of a hacky solution, but if it's not within the line segment
// consider the normal to just be the end of the line segment (point b)
normalPoint = b.get();
}
// How far away are we from the path?
float distance = PVector.dist(predictpos, normalPoint);
// Did we beat the record and find the closest line segment?
if (distance < worldRecord) {
worldRecord = distance;
// If so the target we want to steer towards is the normal
normal = normalPoint;
// Look at the direction of the line segment so we can seek a little bit ahead of the normal
PVector dir = PVector.sub(b, a);
dir.normalize();
// This is an oversimplification
// Should be based on distance to path & velocity
dir.mult(10);
target = normalPoint.get();
target.add(dir);
}
}
// only if the distance is greater than the path's radius do we bother to steer
if (worldRecord > p.radius) {
seek(target);
}
// Draw the debugging stuff
if (debug) {
// Draw predicted future position
stroke(0);
fill(0);
line(position.x, position.y, predictpos.x, predictpos.y);
ellipse(predictpos.x, predictpos.y, 4, 4);
// Draw normal position
stroke(0);
fill(0);
ellipse(normal.x, normal.y, 4, 4);
// Draw actual target (red if steering towards it)
line(predictpos.x, predictpos.y, normal.x, normal.y);
if (worldRecord > p.radius) fill(255, 0, 0);
noStroke();
ellipse(target.x, target.y, 8, 8);
}
}
// A function to get the normal point from a point (p) to a line segment (a-b)
// This function could be optimized to make fewer new Vector objects
PVector getNormalPoint(PVector p, PVector a, PVector b) {
// Vector from a to p
PVector ap = PVector.sub(p, a);
// Vector from a to b
PVector ab = PVector.sub(b, a);
ab.normalize(); // Normalize the line
// Project vector "diff" onto line by using the dot product
ab.mult(ap.dot(ab));
PVector normalPoint = PVector.add(a, ab);
return normalPoint;
}
// 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 applyForce(PVector force) {
// We could add mass here if we want A = F / M
acceleration.add(force);
}
// A method that calculates and applies a steering force towards a target
// STEER = DESIRED MINUS VELOCITY
void seek(PVector target) {
PVector desired = PVector.sub(target, position); // A vector pointing from the position to the target
// If the magnitude of desired equals 0, skip out of here
// (We could optimize this to check if x and y are 0 to avoid mag() square root
if (desired.mag() == 0) return;
// Normalize desired and scale to maximum speed
desired.normalize();
desired.mult(maxspeed);
// Steering = Desired minus Velocity
PVector steer = PVector.sub(desired, velocity);
steer.limit(maxforce); // Limit to maximum steering force
applyForce(steer);
}
void display() {
// Draw a triangle rotated in the direction of velocity
float theta = velocity.heading2D() + radians(90);
fill(175);
stroke(0);
pushMatrix();
translate(position.x, position.y);
rotate(theta);
beginShape(PConstants.TRIANGLES);
vertex(0, -r*2);
vertex(-r, r*2);
vertex(r, r*2);
endShape();
popMatrix();
}
// Wraparound
void borders(Path p) {
if (position.x > p.getEnd().x + r) {
position.x = p.getStart().x - r;
position.y = p.getStart().y + (position.y-p.getEnd().y);
}
}
}
