书名：代码本色：用编程模拟天然体系
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第6章目次
6.9 多段路径跟随
1、多段路径跟随
我们办理了单个线段的路径跟随题目，接下来该怎样办理多个相连线段的路径跟随题目？让我们回首小车沿着屏幕运动的例子，假设我们已经到了步调3。
- 步调3：在路径上探求一个目标位置
- 为了探求目标位置，我们必须找到线段上的法线交点。但现在的路径是由多个线段构成的，法线交点也有多个（如图6-32所示）。
该选择哪个交点？这里有两个选择条件：
（a）选择近来的法线交点；
（b）这个交点必须位于路径内。
- 假如只有一个点和一条无穷长的直线，总能得到位于直线内的法线交点。但假如是一个点和一个线段，则不肯定能找到位于线段内的法线交点。因此，假如法线交点不在线段内，我们就应该将它清除在外。得到符合条件的法线交点后（在上图中，只有两个符合条件的交点），我们须要挑选出近来的点作为目标位置。
2、加入一个ArrayList对象
- 为了实现如许的特性，我们要扩展Path类，加入一个ArrayList对象用于存放路径的极点（代替之前的起点和尽头）。
class Path { // A Path is an arraylist of points (PVector objects) ArrayList< Vector> 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<Vector>(); } // 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 vehiclesVehicle 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); } }}4、运行效果
|
