API tools faq
paste
Advertisement
nzisaacnz

Dijkstra dynamic map

nzisaacnz
Sep 17th, 2013
138
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 5 12.82 KB | None | 0 0
raw download clone embed print report
  1. <html>
  2. <head>
  3. <script>
  4. var Template = {};
  5. var requestAnimationFrame =
  6. window.requestAnimationFrame||
  7. window.webkitRequestAnimationFrame||
  8. window.mozRequestAnimationFrame||
  9. window.oRequestAnimationFrame||
  10. window.msRequestAnimationFrame;
  11.  
  12. var cancelAnimationFrame =
  13. window.cancelAnimationFrame||
  14. window.webkitCancelRequestAnimationFrame||
  15. window.webkitCancelAnimationFrame||
  16. window.mozCancelRequestAnimationFrame||
  17. window.mozCancelAnimationFrame||
  18. window.oCancelRequestAnimationFrame||
  19. window.oCancelAnimationFrame||
  20. window.msCancelRequestAnimationFrame||
  21. window.msCancelAnimationFrame;
  22.  
  23. Template.newTime = Date.now();
  24. Template.time = 0;
  25. Template.animation = function()
  26. {
  27.  if(!Template.stopped)
  28.  {
  29.   Template.oldTime = Template.newTime;
  30.   if(!Template.paused)
  31.   {
  32.    Template.calculate();
  33.   }
  34.   Template.draw();
  35.   Template.newTime = Date.now();
  36.   Template.time=Template.newTime-Template.oldTime;
  37.   Template.animationFrame = requestAnimationFrame(Template.animation);
  38.  }
  39. }
  40. Template.start = function(d,c)
  41. {
  42.  Template.draw = d;
  43.  Template.calculate = c;
  44.  Template.paused = false;
  45.  Template.animationFrame = requestAnimationFrame(Template.animation);
  46. }
  47. Template.stop = function()
  48. {
  49.  cancelAnimationFrame(Template.animationFrame);
  50. }
  51. function Transition(start,end,period,loops,func)
  52. {
  53.  this.start = start;
  54.  this.end = end;
  55.  this.period = period;
  56.  if(!func)this.func = function(a){return a;};
  57.  else this.func = func;
  58.  this.pos = 0;
  59.  this.reversed;
  60.  this.loop = loops;
  61.  this.res = 0;
  62.  this.calc=function()
  63.  {
  64.   if(this.reversed) this.pos -= Template.time/this.period;
  65.   else this.pos += Template.time/this.period;
  66.   if(this.loop===0)
  67.   {
  68.    this.pos = (this.pos+1)%1;
  69.   }
  70.   else
  71.   {
  72.    this.pos = Math.min(this.loop,Math.max(this.pos,0));
  73.   }
  74.   this.res = this.func(this.pos)*(end-start)+start;
  75.  }
  76.  this.get = function()
  77.  {
  78.   return this.res;
  79.  }
  80.  this.reverse = function()
  81.  {
  82.   this.reversed = !this.reversed;
  83.  }
  84. }
  85. </script>
  86. <script>
  87.  
  88. function Point(x,y)
  89. {
  90.     this.x = x;
  91.     this.y = y;
  92.     this.draw = function(G)
  93.     {
  94.         G.beginPath();
  95.         G.moveTo(this.x+10,this.y);
  96.         G.arc(this.x,this.y,10,0,2*Math.PI);
  97.         G.stroke();
  98.     }
  99. }
  100. function Line(xs,ys,xe,ye)
  101. {
  102.     this.start = new Point(xs,ys);
  103.     this.end = new Point(xe,ye);
  104.     this.Intersects = function(line,x,y,x1,y1)
  105.     {
  106.         x = +x|0;
  107.         y = +y|0;
  108.         x1 = +x1|0;
  109.         y1 = +y1|0;
  110.         return get_line_intersection(this.start.x+x,this.start.y+y,
  111.                                      this.end.x+x,this.end.y+y,
  112.                                      line.start.x+x1,line.start.y+y1,
  113.                                      line.end.x+x1,line.end.y+y1);
  114.     }
  115. }
  116. function Mesh(x,y,strokeStyle,fillStyle)
  117. {
  118.     this.prevPoint = null;
  119.     this.lines = [];
  120.     this.x = x;
  121.     this.y = y;
  122.     this.strokeStyle = strokeStyle;
  123.     this.fillStyle = fillStyle;
  124.     this.add = function(point,index)
  125.     {
  126.         if(this.prevPoint)
  127.         {
  128.             index = +index|this.lines.length;
  129.             this.lines.splice(index,0,new Line(this.prevPoint.x,this.prevPoint.y,point.x,point.y));
  130.         }
  131.         this.prevPoint = new Point(point.x,point.y);
  132.     }
  133.     this.collides = function(thing)
  134.     {
  135.         var collisions = [];
  136.         if(thing.constructor == Mesh)
  137.         {
  138.             var mesh = thing;
  139.             for(var a=0,aa=this.lines.length; a<aa; a++)
  140.            {
  141.                for(var b=0,bb=mesh.lines.length; b<bb; b++)
  142.                {
  143.                    var collision = this.lines[a].Intersects(mesh.lines[b],this.x,this.y,mesh.x,mesh.y);
  144.                    if(collision)collisions[collisions.length] = collision;
  145.                }
  146.            }
  147.        }
  148.        else if(thing.constructor == Line)
  149.        {
  150.            var line = thing;
  151.            for(var a=0,aa=this.lines.length; a<aa; a++)
  152.            {
  153.                var collision = this.lines[a].Intersects(line,this.x,this.y);
  154.                if(collision)collisions[collisions.length] = collision;
  155.            }
  156.        }
  157.        return collisions;
  158.    }
  159.    this.FinishMesh = function()
  160.    {
  161.        if(this.lines.length==0)return false;
  162.        this.add(new Point(this.lines[0].start.x,this.lines[0].start.y));
  163.        this.finished = true;
  164.        return true;
  165.    }
  166.    this.draw = function(G)
  167.    {
  168.        G.strokeStyle = this.strokeStyle;
  169.        G.fillStyle = this.fillStyle;
  170.        if(this.lines.length==0)return false;
  171.        G.beginPath();
  172.        G.moveTo(this.lines[0].start.x+this.x,this.lines[0].start.y+this.y);
  173.        for(var a=0; a<this.lines.length; a++)
  174.        {
  175.            G.lineTo(this.lines[a].end.x+this.x,this.lines[a].end.y+this.y);
  176.        }
  177.        if(this.finished)G.fill();
  178.        G.stroke();
  179.        return true;
  180.    }
  181. }
  182. function get_line_intersection(p0_x,p0_y,p1_x,p1_y,p2_x,p2_y,p3_x,p3_y)
  183. {
  184.    var s1_x, s1_y, s2_x, s2_y;
  185.    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
  186.    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;
  187.  
  188.    var cache2=(-s2_x * s1_y + s1_x * s2_y);
  189.  
  190.    if(cache2===0) return false; // Parallel
  191.  
  192.    var s, t;
  193.    var cache0=(p0_y - p2_y);
  194.    var cache1=(p0_x - p2_x);
  195.  
  196.    s = (-s1_y * cache1 + s1_x * cache0) / cache2;
  197.    t = ( s2_x * cache0 - s2_y * cache1) / cache2;
  198.  
  199.    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
  200.    {
  201.        // Collision detected
  202.        return new Point(p0_x + (t * s1_x),p0_y + (t * s1_y));
  203.     }
  204.  
  205.     return false; // No collision
  206. }
  207.  
  208. </script>
  209. <script>
  210. /******************************************************************************
  211.  * Created 2008-08-19.
  212.  *
  213.  * Dijkstra path-finding functions. Adapted from the Dijkstar Python project.
  214.  *
  215.  * Copyright (C) 2008
  216.  *   Wyatt Baldwin <self@wyattbaldwin.com>
  217.  *   All rights reserved
  218.  *
  219.  * Licensed under the MIT license.
  220.  *
  221.  *   http://www.opensource.org/licenses/mit-license.php
  222.  *
  223.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  224.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  225.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  226.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  227.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  228.  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  229.  * THE SOFTWARE.
  230.  *****************************************************************************/
  231. var dijkstra = {
  232.   single_source_shortest_paths: function(graph, s, d) {
  233.     // Predecessor map for each node that has been encountered.
  234.     // node ID => predecessor node ID
  235.     var predecessors = {};
  236.  
  237.     // Costs of shortest paths from s to all nodes encountered.
  238.     // node ID => cost
  239.     var costs = {};
  240.     costs[s] = 0;
  241.  
  242.     // Costs of shortest paths from s to all nodes encountered; differs from
  243.     // `costs` in that it provides easy access to the node that currently has
  244.     // the known shortest path from s.
  245.     // XXX: Do we actually need both `costs` and `open`?
  246.     var open = dijkstra.PriorityQueue.make();
  247.     open.push(s, 0);
  248.  
  249.     var closest,
  250.         u, v,
  251.         cost_of_s_to_u,
  252.         adjacent_nodes,
  253.         cost_of_e,
  254.         cost_of_s_to_u_plus_cost_of_e,
  255.         cost_of_s_to_v,
  256.         first_visit;
  257.     while (!open.empty()) {
  258.       // In the nodes remaining in graph that have a known cost from s,
  259.       // find the node, u, that currently has the shortest path from s.
  260.       closest = open.pop();
  261.       u = closest.value;
  262.       cost_of_s_to_u = closest.cost;
  263.  
  264.       // Get nodes adjacent to u...
  265.       adjacent_nodes = graph[u] || {};
  266.  
  267.       // ...and explore the edges that connect u to those nodes, updating
  268.       // the cost of the shortest paths to any or all of those nodes as
  269.       // necessary. v is the node across the current edge from u.
  270.       for (v in adjacent_nodes) {
  271.         // Get the cost of the edge running from u to v.
  272.         cost_of_e = adjacent_nodes[v];
  273.  
  274.         // Cost of s to u plus the cost of u to v across e--this is *a*
  275.         // cost from s to v that may or may not be less than the current
  276.         // known cost to v.
  277.         cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;
  278.  
  279.         // If we haven't visited v yet OR if the current known cost from s to
  280.         // v is greater than the new cost we just found (cost of s to u plus
  281.         // cost of u to v across e), update v's cost in the cost list and
  282.         // update v's predecessor in the predecessor list (it's now u).
  283.         cost_of_s_to_v = costs[v];
  284.         first_visit = (typeof costs[v] === 'undefined');
  285.         if (first_visit || cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {
  286.           costs[v] = cost_of_s_to_u_plus_cost_of_e;
  287.           open.push(v, cost_of_s_to_u_plus_cost_of_e);
  288.           predecessors[v] = u;
  289.         }
  290.       }
  291.     }
  292.  
  293.     if (typeof d !== 'undefined' && typeof costs[d] === 'undefined') {
  294.      var msg = ['Could not find a path from ', s, ' to ', d, '.'].join('');
  295.       throw new Error(msg);
  296.     }
  297.  
  298.     return predecessors;
  299.   },
  300.  
  301.   extract_shortest_path_from_predecessor_list: function(predecessors, d) {
  302.     var nodes = [];
  303.     var u = d;
  304.     var predecessor;
  305.     while (u) {
  306.       nodes.push(u);
  307.       predecessor = predecessors[u];
  308.       u = predecessors[u];
  309.     }
  310.     nodes.reverse();
  311.     return nodes;
  312.   },
  313.  
  314.   find_path: function(graph, s, d) {
  315.     var predecessors = dijkstra.single_source_shortest_paths(graph, s, d);
  316.     return dijkstra.extract_shortest_path_from_predecessor_list(
  317.       predecessors, d);
  318.   },
  319.  
  320.   /**
  321.    * A very naive priority queue implementation.
  322.    */
  323.   PriorityQueue: {
  324.     make: function (opts) {
  325.       var T = dijkstra.PriorityQueue,
  326.           t = {},
  327.           opts = opts || {},
  328.           key;
  329.       for (key in T) {
  330.         t[key] = T[key];
  331.       }
  332.       t.queue = [];
  333.       t.sorter = opts.sorter || T.default_sorter;
  334.       return t;
  335.     },
  336.  
  337.     default_sorter: function (a, b) {
  338.       return a.cost - b.cost;
  339.     },
  340.  
  341.     /**
  342.      * Add a new item to the queue and ensure the highest priority element
  343.      * is at the front of the queue.
  344.      */
  345.     push: function (value, cost) {
  346.       var item = {value: value, cost: cost};
  347.       this.queue.push(item);
  348.       this.queue.sort(this.sorter);
  349.     },
  350.  
  351.     /**
  352.      * Return the highest priority element in the queue.
  353.      */
  354.     pop: function () {
  355.       return this.queue.shift();
  356.     },
  357.  
  358.     empty: function () {
  359.       return this.queue.length === 0;
  360.     }
  361.   }
  362. };
  363. </script>
  364. <script>
  365. var
  366.     find_path = dijkstra.find_path,
  367.     graph,
  368.     path,
  369.     paths;
  370.  
  371. var Map = {}
  372. var width = 50;
  373. var height = 50;
  374. var Map = [];
  375. for(var a=0; a<width; a++)
  376. {
  377. Map[a] = [];
  378. for(var b=0; b<height; b++)
  379. {
  380.  var h = Map[a][b-1]|parseInt(Math.random()*256);
  381.  if(a>0)h = h/2+Map[a-1][b]/2;
  382.   Map[a][b] = h+(Math.random()*20)-10;
  383.  }
  384. }
  385. var graph = {};
  386. for(var a=0; a<width; a++)
  387. {
  388. for(var b=0; b<height; b++)
  389. {
  390.  var index = a+","+b;
  391.  graph[index] = {};
  392.  var dx = [];
  393.  var dy = [];
  394.  if(a>0)       {dx[dx.length] = a-1;dy[dy.length] = b;  }
  395.   if(a<width-1) {dx[dx.length] = a+1;dy[dy.length] = b;  }
  396.  if(b>0)       {dx[dx.length] = a;  dy[dy.length] = b-1;}
  397.   if(b<height-1){dx[dx.length] = a;  dy[dy.length] = b+1;}
  398.  
  399.  for(var z=0; z<dx.length; z++)
  400.  {
  401.   var di = dx[z]+","+dy[z];
  402.   graph[index][di] = Map[dx[z]][dy[z]]-Map[a][b]+1;
  403.  }
  404. }
  405. }
  406.  
  407.  
  408.  
  409. </script>
  410. </head>
  411. <body>
  412. <canvas id="cvs" width="800" height="600" onmousemove="mouseMove(event)"></canvas>
  413. <script>
  414.  var scale = 5,mouse={x:-1,y:-10};
  415. function init()
  416. {
  417.  Template.start(draw,calc);
  418. }
  419. function mouseMove(e)
  420. {
  421.  mouse = {x:e.offsetX-0.5,y:e.offsetY-0.5};
  422.  
  423. }
  424. function draw()
  425. {
  426.  var G = cvs.getContext("2d");
  427.  G.clearRect(0,0,cvs.width,cvs.height);
  428.  for(var a=0; a<width; a++)
  429. {
  430.  for(var b=0; b<height; b++)
  431.  {
  432.   G.fillStyle = "hsl("+Map[a][b]/5+",50%,50%)";
  433.   G.fillRect(a*scale,b*scale,10,10);
  434.  }
  435. }
  436. G.beginPath();
  437. for(var a=0; a<path.length; a++)
  438. {
  439.  var coord = path[a].split(",");
  440.  G.lineTo(coord[0]*scale+scale/2,coord[1]*scale+scale/2);
  441. }
  442. G.stroke();
  443. }
  444. function calc()
  445. {
  446. if(Map[parseInt(mouse.x/scale).toString()])
  447. Map[parseInt(mouse.x/scale).toString()][parseInt(mouse.y/scale).toString()]+=15;
  448.  
  449. var graph = {};
  450. for(var a=0; a<width; a++)
  451. {
  452. for(var b=0; b<height; b++)
  453. {
  454.  var index = a+","+b;
  455.  graph[index] = {};
  456.  var dx = [];
  457.  var dy = [];
  458.  if(a>0)       {dx[dx.length] = a-1;dy[dy.length] = b;  }
  459.   if(a<width-1) {dx[dx.length] = a+1;dy[dy.length] = b;  }
  460.  if(b>0)       {dx[dx.length] = a;  dy[dy.length] = b-1;}
  461.   if(b<height-1){dx[dx.length] = a;  dy[dy.length] = b+1;}
  462.  
  463.  for(var z=0; z<dx.length; z++)
  464.  {
  465.   var di = dx[z]+","+dy[z];
  466.   graph[index][di] = Map[dx[z]][dy[z]]-Map[a][b]+1;
  467.  }
  468. }
  469. }
  470. path = find_path(graph, '0,0', '49,49');
  471. }
  472. init();
  473. </script>
  474. </body>
  475. </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!