javascript - HTML5 Canvas Pathfinding for an object within a drawn polygon -

javascript - HTML5 Canvas Pathfinding for an object within a drawn polygon -

good afternoon all,

i come yet request lesson/example/answers. while messing around canvas in html5, have learned how manipulate depth(z-buffer) , several other neat things. however, trying find way perform pathfinding canvas. of examples on net little hard comprehend me due fact handling pathfinding far differently trying achieve(which utilize tile based pathfinding). other examples seem deal in boxes or rectangles well.

this code used illustration draw polygon: var canvas = document.getelementbyid('canvaspath'); var context = canvas.getcontext('2d');

// begin custom shape context.beginpath(); context.moveto(170, 80); context.beziercurveto(1, 200, 125, 230, 230, 150); context.beziercurveto(250, 180, 320, 200, 340, 200); context.beziercurveto(420, 150, 420, 120, 390, 100); context.beziercurveto(430, 40, 370, 30, 340, 50); context.beziercurveto(320, 5, 250, 20, 250, 50); context.beziercurveto(200, 5, 150, 20, 170, 80); context.closepath(); context.linewidth = 2; context.strokestyle = 'gray'; context.stroke();

lets have little box want move around in polygon(i creating polygon line points rather bezier curvers. wantd show illustration here) when click @ goal position want at... how can create pathfinding algorithm find way around , yet not have bottom points of box touch outside polygon? assuming need pixels in polygon create path from? thinking bezier curves , points may need created , pushed array instead , find path???

any suggestions on approach , can provide illustration how go this? please gentle... while have been experienced scripter , programmer, have not been 1 mess much games, or graphics , still learning manipulate canvas in html5. help in advance.

the key part of asking how shrink polygon box can travel along shrunken polygon without extending outside original polygon.

the illustration below shows original black polygon, shrunken reddish polygon , bluish traveling box.

precisely shrinking polygon

the code exactly shrink polygon quite complex. involves repositioning original polygon vertices based on whether each particular vertex forms convex or concave angle.

here's illustration code derived hans muller's blog on webkits shape-padding. illustration requires polygon vertices defined in clockwise order.

class="snippet-code-js lang-js prettyprint-override">var canvas=document.getelementbyid("canvas"); var ctx=canvas.getcontext("2d"); var cw=canvas.width; var ch=canvas.height; var shapepadding = 10; var dragvertexindex = null; var hoverlocation = null; var polygonvertexradius = 9; var polygon, marginpolygon, paddingpolygon; var polygonvertices = [{x: 143, y: 327}, {x: 80, y: 236}, {x: 151, y: 148}, {x: 454, y: 69}, {x: 560, y: 320}]; var polygon = createpolygon(polygonvertices); var paddingpolygon = createpaddingpolygon(polygon); drawall(); ///////////////////////////////// // polygon creation , drawing function drawall(){ draw(polygon,'black'); draw(paddingpolygon,'red'); } function draw(p,stroke){ var v=p.vertices; ctx.beginpath(); ctx.moveto(v[0].x,v[0].y); for(var i=0;i<v.length;i++){ ctx.lineto(v[i].x,v[i].y); } ctx.closepath(); ctx.strokestyle=stroke; ctx.stroke(); } function createpolygon(vertices){ var polygon = {vertices: vertices}; var edges = []; var minx = (vertices.length > 0) ? vertices[0].x : undefined; var miny = (vertices.length > 0) ? vertices[0].y : undefined; var maxx = minx; var maxy = miny; (var = 0; < polygon.vertices.length; i++) { vertices[i].label = string(i); vertices[i].isreflex = isreflexvertex(polygon, i); var border = { vertex1: vertices[i], vertex2: vertices[(i + 1) % vertices.length], polygon: polygon, index: }; edge.outwardnormal = outwardedgenormal(edge); edge.inwardnormal = inwardedgenormal(edge); edges.push(edge); var x = vertices[i].x; var y = vertices[i].y; minx = math.min(x, minx); miny = math.min(y, miny); maxx = math.max(x, maxx); maxy = math.max(y, maxy); } polygon.edges = edges; polygon.minx = minx; polygon.miny = miny; polygon.maxx = maxx; polygon.maxy = maxy; polygon.closed = true; homecoming polygon; } function createpaddingpolygon(polygon){ var offsetedges = []; (var = 0; < polygon.edges.length; i++) { var border = polygon.edges[i]; var dx = edge.inwardnormal.x * shapepadding; var dy = edge.inwardnormal.y * shapepadding; offsetedges.push(createoffsetedge(edge, dx, dy)); } var vertices = []; (var = 0; < offsetedges.length; i++) { var thisedge = offsetedges[i]; var prevedge = offsetedges[(i + offsetedges.length - 1) % offsetedges.length]; var vertex = edgesintersection(prevedge, thisedge); if (vertex) vertices.push(vertex); else { var arccenter = polygon.edges[i].vertex1; appendarc(vertices, arccenter, shapepadding, prevedge.vertex2, thisedge.vertex1, true); } } var paddingpolygon = createpolygon(vertices); paddingpolygon.offsetedges = offsetedges; homecoming paddingpolygon; } ////////////////////// // back upwards functions function isreflexvertex(polygon, vertexindex){ // assuming polygon vertices in clockwise order var thisvertex = polygon.vertices[vertexindex]; var nextvertex = polygon.vertices[(vertexindex + 1) % polygon.vertices.length]; var prevvertex = polygon.vertices[(vertexindex + polygon.vertices.length - 1) % polygon.vertices.length]; if (leftside(prevvertex, nextvertex, thisvertex) < 0){return true;} // tbd: homecoming true if thisvertex within polygon when thisvertex isn't included homecoming false; } function inwardedgenormal(edge){ // assuming polygon vertices in clockwise order var dx = edge.vertex2.x - edge.vertex1.x; var dy = edge.vertex2.y - edge.vertex1.y; var edgelength = math.sqrt(dx*dx + dy*dy); homecoming {x: -dy/edgelength, y: dx/edgelength}; } function outwardedgenormal(edge){ var n = inwardedgenormal(edge); homecoming {x: -n.x, y: -n.y}; } // if slope of line vertex1,vertex2 greater slope of vertex1,p p on left side of vertex1,vertex2 , homecoming value > 0. // if p colinear vertex1,vertex2 homecoming 0, otherwise homecoming value < 0. function leftside(vertex1, vertex2, p){ homecoming ((p.x - vertex1.x) * (vertex2.y - vertex1.y)) - ((vertex2.x - vertex1.x) * (p.y - vertex1.y)); } function createoffsetedge(edge, dx, dy){ homecoming { vertex1: {x: edge.vertex1.x + dx, y: edge.vertex1.y + dy}, vertex2: {x: edge.vertex2.x + dx, y: edge.vertex2.y + dy} }; } // based on http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/, edgea => "line a", edgeb => "line b" function edgesintersection(edgea, edgeb){ var den = (edgeb.vertex2.y - edgeb.vertex1.y) * (edgea.vertex2.x - edgea.vertex1.x) - (edgeb.vertex2.x - edgeb.vertex1.x) * (edgea.vertex2.y - edgea.vertex1.y); if (den == 0){return null;} // lines parallel or conincident var ua = ((edgeb.vertex2.x - edgeb.vertex1.x) * (edgea.vertex1.y - edgeb.vertex1.y) - (edgeb.vertex2.y - edgeb.vertex1.y) * (edgea.vertex1.x - edgeb.vertex1.x)) / den; var ub = ((edgea.vertex2.x - edgea.vertex1.x) * (edgea.vertex1.y - edgeb.vertex1.y) - (edgea.vertex2.y - edgea.vertex1.y) * (edgea.vertex1.x - edgeb.vertex1.x)) / den; if (ua < 0 || ub < 0 || ua > 1 || ub > 1){ homecoming null; } homecoming {x: edgea.vertex1.x + ua * (edgea.vertex2.x - edgea.vertex1.x), y: edgea.vertex1.y + ua * (edgea.vertex2.y - edgea.vertex1.y)}; } function appendarc(vertices, center, radius, startvertex, endvertex, ispaddingboundary){ const twopi = math.pi * 2; var startangle = math.atan2(startvertex.y - center.y, startvertex.x - center.x); var endangle = math.atan2(endvertex.y - center.y, endvertex.x - center.x); if (startangle < 0) startangle += twopi; if (endangle < 0) endangle += twopi; var arcsegmentcount = 5; // odd number 1 arc vertex eactly arcradius center. var angle = ((startangle > endangle) ? (startangle - endangle) : (startangle + twopi - endangle)); var angle5 = ((ispaddingboundary) ? -angle : twopi - angle) / arcsegmentcount; vertices.push(startvertex); (var = 1; < arcsegmentcount; ++i) { var angle = startangle + angle5 * i; var vertex = { x: center.x + math.cos(angle) * radius, y: center.y + math.sin(angle) * radius, }; vertices.push(vertex); } vertices.push(endvertex); } class="snippet-code-css lang-css prettyprint-override">body{ background-color: ivory; } #canvas{border:1px solid red;} class="snippet-code-html lang-html prettyprint-override"><h4>original black polygon , shrunken reddish polygon</h4> <canvas id="canvas" width=650 height=400></canvas>

calculating waypoints along polygon traveling box

to have box travel along within of polygon, need array containing points along each line of polygon. can calculate these points using linear interpolation.

given object defining line this:

var line={ x0:50, y0:50, x1:200, y1:50};

you can utilize linear interpolation calculate points along line every 1px this:

var allpoints = alllinepoints(line); function alllinepoints(line){ var raw=[]; var dx = line.x1-line.x0; var dy = line.y1-line.y0; var length=math.sqrt(dx*dx+dy*dy); var segments=parseint(length+1); for(var i=0;i<segments;i++){ var percent=i/segments; if(i==segments-1){ raw.push({x:line.x1,y:line.y1}); // forcefulness lastly point == p1 }else{ raw.push({ x:line.x0+dx*percent, y:line.y0+dy*percent}); } } return(raw); }

get point on polygon closest mouse click

you can utilize distance formula (derived pythagorean theorem) calculate of calculated waypoints closest mouse click position:

// index in of waypoint closest mouse var indexofclosestpoint; // iterate waypoints , find closest mouse var minlengthsquared=1000000*1000000; for(var i=0;i<allpoints.length;i++){ var p=allpoints[i]; var dx=mousex-p.x; var dy=mousey-p.y; var dxy=dx*dx+dy*dy if(dxy<minlengthsquared){ minlengthsquared=dxy; indexofclosestpoint=i; } }

animate box along each waypoint calculated ending waypoint

the thing left set animation loop redraws traveling box @ each waypoint along polygon until reaches ending waypoint:

// start animating @ first waypoint var animationindex=0; // utilize requestanimationframe redraw traveling box // along each waypoint function animate(time){ // redraw line , box @ current (percent) position var pt=allpoints[animationindex]; // redraw polygon , traveling box ctx.strokestyle='black'; ctx.linewidth=1; ctx.clearrect(0,0,cw,ch); ctx.strokestyle='black'; drawlines(linepoints); ctx.strokestyle='red'; drawlines(insidelinepoints); ctx.fillstyle='skyblue'; ctx.fillrect(pt.x-boxwidth/2,pt.y-boxheight/2,boxwidth,boxheight); // increment percentage next frame loop animationindex++; // done? if(animationindex<=indexofclosestpoint){ // request frame loop requestanimationframe(animate); }else{ // set flag indicating animation finish isanimating=false; } }

here's looks when set together

class="snippet-code-js lang-js prettyprint-override">var canvas=document.getelementbyid("canvas"); var ctx=canvas.getcontext("2d"); var cw=canvas.width; var ch=canvas.height; function reoffset(){ var bb=canvas.getboundingclientrect(); offsetx=bb.left; offsety=bb.top; } var offsetx,offsety; reoffset(); window.onscroll=function(e){ reoffset(); } // polygon vertices var polygonvertices=[ {x:143,y:327}, {x:80,y:236}, {x:151,y:148}, {x:454,y:69}, {x:560,y:320}, ]; var shrunkenvertices=getshrunkenvertices(polygonvertices,10); var polypoints=getpolygonpoints(shrunkenvertices) //log(shrunkenvertices); // animation variables var isanimating=false; var animationindex=0; // var indexofclosestpoint=-99; // define movable box var boxwidth=12; var boxheight=10; var boxradius=math.sqrt(boxwidth*boxwidth+boxheight*boxheight); var boxfill='skyblue'; // hear mouse events $("#canvas").mousedown(function(e){handlemousedown(e);}); $("#canvas").mousemove(function(e){handlemousemove(e);}); drawpolys(polygonvertices,shrunkenvertices); //////////////////////////// // animate box endpoint //////////////////////////// function animate(time){ ctx.clearrect(0,0,cw,ch); drawpolys(polygonvertices,shrunkenvertices); // redraw line , box @ current (percent) position var pt=polypoints[animationindex]; ctx.fillstyle=boxfill; ctx.fillrect(pt.x-boxwidth/2,pt.y-boxheight/2,boxwidth,boxheight); // increment percentage next frame loop animationindex++; // request frame loop if(animationindex<=indexofclosestpoint){ requestanimationframe(animate); }else{ isanimating=false; } } //////////////////////////////////// // select box endpoint click //////////////////////////////////// function handlemousedown(e){ // homecoming if we're animating if(isanimating){return;} // tell browser we're handling event e.preventdefault(); e.stoppropagation(); // start animating animationindex=0; isanimating=true; requestanimationframe(animate); } function handlemousemove(e){ // homecoming if we're animating if(isanimating){return;} // tell browser we're handling event e.preventdefault(); e.stoppropagation(); // mouse position mousex=parseint(e.clientx-offsetx); mousey=parseint(e.clienty-offsety); // find nearest waypoint indexofclosestpoint=findnearestpointtomouse(mousex,mousey); // redraw ctx.clearrect(0,0,cw,ch); drawpolys(polygonvertices,shrunkenvertices); // draw reddish dot @ nearest waypoint drawdot(polypoints[indexofclosestpoint],'red'); } function findnearestpointtomouse(mx,my){ // find nearest waypoint var minlengthsquared=1000000*1000000; for(var i=0;i<polypoints.length;i++){ var p=polypoints[i]; var dx=mousex-p.x; var dy=mousey-p.y; var dxy=dx*dx+dy*dy if(dxy<minlengthsquared){ minlengthsquared=dxy; indexofclosestpoint=i; } } return(indexofclosestpoint); } //////////////////////////////// // drawing functions //////////////////////////////// function drawpolys(polygon,shrunken){ drawpoly(polygon,'black'); drawpoly(shrunken,'blue'); } function drawpoly(v,stroke){ ctx.beginpath(); ctx.moveto(v[0].x,v[0].y); for(var i=0;i<v.length;i++){ ctx.lineto(v[i].x,v[i].y); } ctx.closepath(); ctx.strokestyle=stroke; ctx.stroke(); } function drawdot(pt,color){ ctx.beginpath(); ctx.arc(pt.x,pt.y,3,0,math.pi*2); ctx.closepath(); ctx.fillstyle=color; ctx.fill(); } //////////////////////////////// // points along polygon //////////////////////////////// function getpolygonpoints(vertices){ // purpose, sure close polygon var v=vertices.slice(0); var v0=v[0]; var vx=v[v.length-1]; if(v0.x!==vx.x || v0.y!==vx.y){v.push(v[0]);} // var points=[]; for(var i=1;i<v.length;i++){ var p0=v[i-1]; var p1=v[i]; var line={x0:p0.x,y0:p0.y,x1:p1.x,y1:p1.y}; points=points.concat(getlinepoints(line)); } return(points); } function getlinepoints(line){ var raw=[]; var dx = line.x1-line.x0; var dy = line.y1-line.y0; var length=math.sqrt(dx*dx+dy*dy); var segments=parseint(length+1); for(var i=0;i<segments;i++){ var percent=i/segments; if(i==segments-1){ raw.push({x:line.x1,y:line.y1}); // forcefulness lastly point == p1 }else{ raw.push({ x:line.x0+dx*percent, y:line.y0+dy*percent}); } } return(raw); } ///////////////////////// // "shrink" polygon ///////////////////////// function getshrunkenvertices(vertices,shapepadding){ var polygon = createpolygon(polygonvertices); var paddingpolygon = createpaddingpolygon(polygon,shapepadding); return(paddingpolygon.vertices); } function createpolygon(vertices){ var polygon = {vertices: vertices}; var edges = []; var minx = (vertices.length > 0) ? vertices[0].x : undefined; var miny = (vertices.length > 0) ? vertices[0].y : undefined; var maxx = minx; var maxy = miny; (var = 0; < polygon.vertices.length; i++) { vertices[i].label = string(i); vertices[i].isreflex = isreflexvertex(polygon, i); var border = { vertex1: vertices[i], vertex2: vertices[(i + 1) % vertices.length], polygon: polygon, index: }; edge.outwardnormal = outwardedgenormal(edge); edge.inwardnormal = inwardedgenormal(edge); edges.push(edge); var x = vertices[i].x; var y = vertices[i].y; minx = math.min(x, minx); miny = math.min(y, miny); maxx = math.max(x, maxx); maxy = math.max(y, maxy); } polygon.edges = edges; polygon.minx = minx; polygon.miny = miny; polygon.maxx = maxx; polygon.maxy = maxy; polygon.closed = true; homecoming polygon; } function createpaddingpolygon(polygon,shapepadding){ var offsetedges = []; (var = 0; < polygon.edges.length; i++) { var border = polygon.edges[i]; var dx = edge.inwardnormal.x * shapepadding; var dy = edge.inwardnormal.y * shapepadding; offsetedges.push(createoffsetedge(edge, dx, dy)); } var vertices = []; (var = 0; < offsetedges.length; i++) { var thisedge = offsetedges[i]; var prevedge = offsetedges[(i + offsetedges.length - 1) % offsetedges.length]; var vertex = edgesintersection(prevedge, thisedge); if (vertex) vertices.push(vertex); else { var arccenter = polygon.edges[i].vertex1; appendarc(vertices, arccenter, shapepadding, prevedge.vertex2, thisedge.vertex1, true); } } var paddingpolygon = createpolygon(vertices); paddingpolygon.offsetedges = offsetedges; homecoming paddingpolygon; } function isreflexvertex(polygon, vertexindex){ // assuming polygon vertices in clockwise order var thisvertex = polygon.vertices[vertexindex]; var nextvertex = polygon.vertices[(vertexindex + 1) % polygon.vertices.length]; var prevvertex = polygon.vertices[(vertexindex + polygon.vertices.length - 1) % polygon.vertices.length]; if (leftside(prevvertex, nextvertex, thisvertex) < 0){return true;} // tbd: homecoming true if thisvertex within polygon when thisvertex isn't included homecoming false; } function inwardedgenormal(edge){ // assuming polygon vertices in clockwise order var dx = edge.vertex2.x - edge.vertex1.x; var dy = edge.vertex2.y - edge.vertex1.y; var edgelength = math.sqrt(dx*dx + dy*dy); homecoming {x: -dy/edgelength, y: dx/edgelength}; } function outwardedgenormal(edge){ var n = inwardedgenormal(edge); homecoming {x: -n.x, y: -n.y}; } // if slope of line vertex1,vertex2 greater slope of vertex1,p p on left side of vertex1,vertex2 , homecoming value > 0. // if p colinear vertex1,vertex2 homecoming 0, otherwise homecoming value < 0. function leftside(vertex1, vertex2, p){ homecoming ((p.x - vertex1.x) * (vertex2.y - vertex1.y)) - ((vertex2.x - vertex1.x) * (p.y - vertex1.y)); } function createoffsetedge(edge, dx, dy){ homecoming { vertex1: {x: edge.vertex1.x + dx, y: edge.vertex1.y + dy}, vertex2: {x: edge.vertex2.x + dx, y: edge.vertex2.y + dy} }; } // based on http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/, edgea => "line a", edgeb => "line b" function edgesintersection(edgea, edgeb){ var den = (edgeb.vertex2.y - edgeb.vertex1.y) * (edgea.vertex2.x - edgea.vertex1.x) - (edgeb.vertex2.x - edgeb.vertex1.x) * (edgea.vertex2.y - edgea.vertex1.y); if (den == 0){return null;} // lines parallel or conincident var ua = ((edgeb.vertex2.x - edgeb.vertex1.x) * (edgea.vertex1.y - edgeb.vertex1.y) - (edgeb.vertex2.y - edgeb.vertex1.y) * (edgea.vertex1.x - edgeb.vertex1.x)) / den; var ub = ((edgea.vertex2.x - edgea.vertex1.x) * (edgea.vertex1.y - edgeb.vertex1.y) - (edgea.vertex2.y - edgea.vertex1.y) * (edgea.vertex1.x - edgeb.vertex1.x)) / den; if (ua < 0 || ub < 0 || ua > 1 || ub > 1){ homecoming null; } homecoming {x: edgea.vertex1.x + ua * (edgea.vertex2.x - edgea.vertex1.x), y: edgea.vertex1.y + ua * (edgea.vertex2.y - edgea.vertex1.y)}; } function appendarc(vertices, center, radius, startvertex, endvertex, ispaddingboundary){ const twopi = math.pi * 2; var startangle = math.atan2(startvertex.y - center.y, startvertex.x - center.x); var endangle = math.atan2(endvertex.y - center.y, endvertex.x - center.x); if (startangle < 0) startangle += twopi; if (endangle < 0) endangle += twopi; var arcsegmentcount = 5; // odd number 1 arc vertex eactly arcradius center. var angle = ((startangle > endangle) ? (startangle - endangle) : (startangle + twopi - endangle)); var angle5 = ((ispaddingboundary) ? -angle : twopi - angle) / arcsegmentcount; vertices.push(startvertex); (var = 1; < arcsegmentcount; ++i) { var angle = startangle + angle5 * i; var vertex = { x: center.x + math.cos(angle) * radius, y: center.y + math.sin(angle) * radius, }; vertices.push(vertex); } vertices.push(endvertex); } ///////////////////////// // end "shrink polygon" ///////////////////////// class="snippet-code-css lang-css prettyprint-override">body{ background-color: ivory; } #canvas{border:1px solid red;} class="snippet-code-html lang-html prettyprint-override"><script src="https://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script> <h4>move mouse want box end up<br>then click start box animating start end.<br>note: starting point on bottom left of polygon</h4> <canvas id="canvas" width=650 height=400></canvas>

using curved paths

if want create closed path bezier curves, have calculate waypoints along curves using de casteljau's algorithm. want over-sample number of points--maybe 500 values of t between 0.00 , 1.00. here javascript version of algorithm calculates x,y points @ interval t along cubic bezier curve:

// de casteljau's algorithm calculates points along cubic bezier curve // plot point @ interval t along bezier curve // t==0.00 @ origin of curve. t==1.00 @ ending of curve // calculating 300 t's between 0-1 define curve sufficiently function getcubicbezierxyatt(startpt,controlpt1,controlpt2,endpt,t){ var x=cubicn(t,startpt.x,controlpt1.x,controlpt2.x,endpt.x); var y=cubicn(t,startpt.y,controlpt1.y,controlpt2.y,endpt.y); return({x:x,y:y}); } // cubic helper formula @ t distance function cubicn(t, a,b,c,d) { var t2 = t * t; var t3 = t2 * t; homecoming + (-a * 3 + t * (3 * - * t)) * t + (3 * b + t * (-6 * b + b * 3 * t)) * t + (c * 3 - c * 3 * t) * t2 + d * t3; }

javascript html5 canvas graphics