# nurbs and pathfinding optimization

I'm working on a project, and my current milestone is pathfinding. I have a working prototype that consists of several components:

1. a manually drawing of a path, that matches the visual path that the characters are allowed to walk on

2. a grid for A* calculations

3. a ray that pokes through the grid cells neighbors during the A* evaluation, and if it intersects a perfect GREEN pixel, sets the cell as walkable for A* calculations, and if it hits a transparent pixel, leaves the cell as not walkable

4. after the rough A* path is calculated, an algorithm for nurbs makes the turns in the path, more ease in, so to speak

My current issue is that the nurbs path Looks like it can use some optimization, And I can use your help to nudge me in the right direction, either pointing me to some literature or directly brainstorm.. Please see the picture below, it should be clearer what I mean, my goal is to have nurbs in a more straight-line, perhaps using some sort of extrapolation algorithm that is based on the A* result, and simplifies it in such a way that the nurbs curve is straighter from start to end

the project is browser-based Away3D framework(sea3D framework more specific)

its github repository can be found here

Thanks!

below is an example that shows the components described above: in GREEN the path that was draw manually, in RED the A* walkable path, in BLUE shades the nurbs

And another example how it actually looks in game, without all the pathfinding visual representations

If you're feeling adventurous, you could try a simple stochastic hill climbing shortcutter on your path before fitting a NURBS curve. Here's how it would go in pseudocode:

function Path Shortcut(Path path):
// Shortcut the path until a max number of timesteps is reached
for t = 1 to MAX_TIMESTEPS
// Get two random path indices to shortcut between
i = GetRandom(1, path.length());
j = GetRandom(i + 1, path.length());

// Create a straight line between the two path points
linear_segment = InterpolateLine(path(i), path(j));

// The new path is one that is the same up to index i, then linear,
// then the rest of the path
shortcut_path = [path(1 : i), linear_segment, path(j : path.length())]

// Check the linear segment to see if it goes outside of the green region.
// If it does, continue shortcutting. Otherwise, modify the path to contain
// the new segment
if !CollisionCheck(linear_segment)
path = shortcut_path

// When we're done shortcutting, the new path is returned.
return path;

// Creates a straight line between the start and the end with a given step size
function Path InterpolateLine(Node start, Node end, float step = 1):
Path toReturn = [];
Vector dir = (end - start);
float length = dir.Length();
dir.Normalize();
// Just step along a line from the start to the end.
for dPath = 0; dPath < length; dPath += step:

// Returns whether any point in a path is invalid
function bool CollisionCheck(Path path):
foreach node in path:
if (!IsWalkable(node)) return false;
return true;


After a few tens of iterations, the shortcutter will converge to a local optimum that is as straight as possible given the original path found by A*. You can control path quality by increasing MAX_ITERATIONS. You can also do some clever hacking by making sure that the path is not already straight and exiting early if it is.

• I'm looking forward to seeing results from this, if you don't mind posting them! Dec 15 '14 at 22:03

I'm going to copy paste some basic code, I came up with in case it helps anyone

    private function hillClimbing( pathCells: Array): Array
{
var pathVectors: Array = new Array;
for(var k:int=0;k<pathCells.length;k++)
{
pathVectors.push(pathCells[k].position);
}
trace( "path length before", pathVectors.length);

var linear_segment: Array = new Array;
var MAX_TIMESTEPS:int = 25;
// Shortcut the pathVectors until a max number of timesteps is reached
for (var t:int=0;t<MAX_TIMESTEPS;t++)
{
var shortcut: Array = new Array;

// Get two random pathVectors indices to shortcut between, so ignore 0 and pathVectors.length-1,
var i:int = int(Main.STATES.randomNumber(0, pathVectors.length-2));
var j:int = int(Main.STATES.randomNumber(i+1, pathVectors.length-1));
// Create a straight line between the two pathVectors points
if(pathVectors[i] != null && pathVectors[j] != null)
{
trace( "selected cell",i,pathVectors[i], "AND",j,pathVectors[j]);
linear_segment = InterpolateLine(pathVectors[i], pathVectors[j]);
}
else
trace( "a cell is empty",i,j,pathVectors[i],pathVectors[j]);

// The new pathVectors is one that is the same up to index i, then linear,
// then the rest of the pathVectors
//if linear segments returned is not null, then we can create a shortcut using it
if(linear_segment != null)
{
trace("linear_segment length", linear_segment.length);
for(k=0;k<i;k++)
{
shortcut.push(pathVectors[k]);
}
shortcut = shortcut.concat(linear_segment);
for(k=j+1;k<pathVectors.length;k++)
{
shortcut.push(pathVectors[k]);
}

//set the updated path  as the shortcut
trace( "after iteration",t, "The path length is", shortcut.length);
pathVectors = shortcut;
}

}

// Creates a straight line between the start and the end with a given step size
function InterpolateLine(start:Vector3D, end:Vector3D, step:int = 16): Array
{
var toReturn: Array = new Array;
var dir: Vector3D = end.subtract(start);
var ratio: Vector3D = new Vector3D;
var _length:Number = dir.length;
trace("dir length",dir.length);
// Just step along a line from the start to the end.
var max: Number = Math.max(Math.abs(end.x - start.x),Math.abs(end.y - start.y),Math.abs(end.z - start.z));

if(ratio.x == 0 && ratio.y == 0 && ratio.z == 0)
{
ratio.x = (end.x - start.x)/max;
ratio.y = (end.y - start.y)/max;
ratio.z = (end.z - start.z)/max;
}//this is a poor attempt to normalize by 3-D vector, there are better ways/classes

for (var dPath: Number = 0; dPath < _length; dPath += step)
{
var result: Vector3D = start.add(new Vector3D(dPath*ratio.x,dPath*ratio.y,dPath*ratio.z));
//trace( "resulting step", result);
toReturn.push(result);
}

//check to see if the  vectors generated are completely on path or not
if( shortcutter(toReturn))
{
trace( "the return length",toReturn.length);
}
else
{
trace( "shortcutter not valid");
return null;
}
}
// When we're done shortcutting, the new path is returned. ideally it would never have less than 4 vectors
trace( "updated path contains", pathVectors.length, "vectors for nurbs");
return pathVectors;
}

public function shortcutter(vectors: Array): Boolean
{
var ray:Ray = new Ray;
for (var i:int=0;i<vectors.length;i++)
{
var vector: Vector3D = vectors[i];

//create  the corner vectors of the plane, this plane is the image for the path
var lt:Vector3D = new Vector3D;
var rb:Vector3D = new Vector3D;
var lb:Vector3D = new Vector3D;
var rt:Vector3D = new Vector3D;

//this is temporary needed to hold the plane to get the material later on
var planes: Array = new Array;
//trace( "coordinates",vector.x,vector.y, "grid",vector.gridC,vector.gridR);

//check to see which planes is the vector supposed to intersect/be part of
//if found, then set its vector corners for future triangulation
for(var j:int=0;j<Main.mapTilesPath.numChildren;j++)
{
if(Math.abs(vector.x) > Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.x) &&
Math.abs(vector.x) < Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.x) + dim.x &&
Math.abs(vector.y) > Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.y) &&
Math.abs(vector.y) < Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.y) + dim.y &&
Math.abs(vector.z) > Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.z) &&
Math.abs(vector.z) < Math.abs((Main.mapTilesPath.getChildAt(j) as Mesh).position.z) + dim.z)
{
//if((Main.mapTilesPath.getChildAt(j) as Mesh).name)     trace( "intersecting",(Main.mapTilesPath.getChildAt(j) as Mesh).name);
lt = (Main.mapTilesPath.getChildAt(j) as Mesh).position;
rb = (Main.mapTilesPath.getChildAt(j) as Mesh).position.add(new Vector3D(-dim.x,-dim.y,dim.z));
lb = (Main.mapTilesPath.getChildAt(j) as Mesh).position.add(new Vector3D(0,-dim.y,dim.z));
rt = (Main.mapTilesPath.getChildAt(j) as Mesh).position.add(new Vector3D(-dim.x,0,0));
//if a plane is found. Keep a future reference to get the material later on
planes.push((Main.mapTilesPath.getChildAt(j) as Mesh));
}
}
//this is the destination vector when checking the ray intersection, it's a simple line on the Z axis starting from the  vector position
var dest: Vector3D = vector.add(new Vector3D(0,0,Main.cellSize));

/*//draw some lines for visual representation of the  rays, not needed in final production
//be advised that the calculations for path and the lines have a Delta, which is the camera position
//this means that calculations for path are relative to the absolute position  of the vectors and meshes
//the lines are displayed relative to the camera, so they appear to be "under" the actual vectors
var lineSet:SegmentSet = new SegmentSet();

//because we have to check the intersection with a plane, we first split the plane into 2 triangles, if all goes well then either there is no intersection,  or at most there is only one
var intersectL:Vector3D = ray.getRayToTriangleIntersection(vector, dest, lt, lb, rb);
var intersectR:Vector3D = ray.getRayToTriangleIntersection(vector, dest, lt, rt, rb);
var intersect: Vector3D = new Vector3D;
if(intersectL != null)
{
intersect = intersectL;
//trace("LEFT intersect ray: "+intersectL);
}
if(intersectR != null)
{
intersect = intersectR;
//trace("RIGHT intersect ray: "+intersectR);
}

//here, if an intersecting plane is found, we actually take the image path and evaluate the value of the pixel where the vector intersects
//if the value is zero, then the intersection was with a transparent pixel, otherwise it should be GREEN
if(planes.length > 0)
{
var material:TextureMaterial = ((planes[0] as Mesh).material as TextureMaterial);
var texture:BitmapTexture = material.texture as BitmapTexture;
var bitmapData:BitmapData = texture.bitmapData;

//we need to convert global to local and 3-D to 2-D coordinates, and remember the camera Delta. :-)
var local:Vector3D = lt.subtract(intersect);
var _x:int = local.x;
var _y:int = -local.z/caz + Math.round(adjustCamera.y/say);

//If the pixel is GREEN, this means the vector should be made walkable as  it's on  "path"
if(bitmapData.getPixel(_x,_y).toString(16) != "ff00")
{
trace( "invalid shortcutter!");
return false;
}
}
}
return true;
}

public function nurbsCurve(pathCells: Array): void
{
//before nurbs,  do a stochastic hillclimbing
var pathVectors: Array = new Array;
pathVectors = hillClimbing(pathCells);

trace( "hillclimbing done",pathVectors.length);

var i:int;//set it here to be used later in for loops
var controlPoints:Vector.<Vector3D> = new Vector.<Vector3D>();
//evaluate all  cell position in the array path
for(i=0;i<pathVectors.length;i++)
{
var vector:Vector3D = pathVectors[i];
controlPoints.push(vector);
}

trace( "control points length", controlPoints.length);

var result:Vector.<Vector3D> = new Vector.<Vector3D>();
var increment: Number = 0;
while (increment <= 1)
{
var out:Vector3D = new Vector3D;
out = Nurbs.nurbs(increment,controlPoints);//use only with 4 or more control points
//out = Nurbs.nurbs(increment,controlPoints,2,1);//use only with 3 or less control points
result.push(out);
increment+=0.002;
}

trace( "number of nurbs", result.length);

for(i=0;i<result.length;i++)
{