sigma.pathfinding.astar.js 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134
  1. (function() {
  2. 'use strict';
  3. if (typeof sigma === 'undefined') {
  4. throw 'sigma is not declared';
  5. }
  6. // Default function to compute path length between two nodes:
  7. // the euclidian
  8. var defaultPathLengthFunction = function(node1, node2, previousPathLength) {
  9. var isEverythingDefined =
  10. node1 != undefined &&
  11. node2 != undefined &&
  12. node1.x != undefined &&
  13. node1.y != undefined &&
  14. node2.x != undefined &&
  15. node2.y != undefined;
  16. if(!isEverythingDefined) {
  17. return undefined;
  18. }
  19. return (previousPathLength || 0) + Math.sqrt(
  20. Math.pow((node2.y - node1.y), 2) + Math.pow((node2.x - node1.x), 2)
  21. );
  22. };
  23. sigma.classes.graph.addMethod(
  24. 'astar',
  25. function(srcId, destId, settings) {
  26. var currentSettings = new sigma.classes.configurable(
  27. // Default settings
  28. {
  29. // Graph is directed, affects which edges are taken into account
  30. undirected: false,
  31. // Function to compute the distance between two connected node
  32. pathLengthFunction: defaultPathLengthFunction,
  33. // Function to compute an distance between two nodes
  34. // if undefined, uses pathLengthFunction
  35. heuristicLengthFunction: undefined
  36. },
  37. settings || {});
  38. var pathLengthFunction = currentSettings("pathLengthFunction"),
  39. heuristicLengthFunction = currentSettings("heuristicLengthFunction") || pathLengthFunction;
  40. var srcNode = this.nodes(srcId),
  41. destNode = this.nodes(destId);
  42. var closedList = {},
  43. openList = [];
  44. var addToLists = function(node, previousNode, pathLength, heuristicLength) {
  45. var nodeId = node.id;
  46. var newItem = {
  47. pathLength: pathLength,
  48. heuristicLength: heuristicLength,
  49. node: node,
  50. nodeId: nodeId,
  51. previousNode: previousNode
  52. };
  53. if(closedList[nodeId] == undefined || closedList[nodeId].pathLength > pathLength) {
  54. closedList[nodeId] = newItem;
  55. var item;
  56. var i;
  57. for(i = 0; i < openList.length; i++) {
  58. item = openList[i];
  59. if(item.heuristicLength > heuristicLength) {
  60. break;
  61. }
  62. }
  63. openList.splice(i, 0, newItem);
  64. }
  65. };
  66. addToLists(srcNode, null, 0, 0);
  67. var pathFound = false;
  68. // Depending of the type of graph (directed or not),
  69. // the neighbors are either the out neighbors or all.
  70. var allNeighbors;
  71. if(currentSettings("undirected")) {
  72. allNeighbors = this.allNeighborsIndex;
  73. }
  74. else {
  75. allNeighbors = this.outNeighborsIndex;
  76. }
  77. var inspectedItem,
  78. neighbors,
  79. neighbor,
  80. pathLength,
  81. heuristicLength,
  82. i;
  83. while(openList.length > 0) {
  84. inspectedItem = openList.shift();
  85. // We reached the destination node
  86. if(inspectedItem.nodeId == destId) {
  87. pathFound = true;
  88. break;
  89. }
  90. neighbors = Object.keys(allNeighbors[inspectedItem.nodeId]);
  91. for(i = 0; i < neighbors.length; i++) {
  92. neighbor = this.nodes(neighbors[i]);
  93. pathLength = pathLengthFunction(inspectedItem.node, neighbor, inspectedItem.pathLength);
  94. heuristicLength = heuristicLengthFunction(neighbor, destNode);
  95. addToLists(neighbor, inspectedItem.node, pathLength, heuristicLength);
  96. }
  97. }
  98. if(pathFound) {
  99. // Rebuilding path
  100. var path = [],
  101. currentNode = destNode;
  102. while(currentNode) {
  103. path.unshift(currentNode);
  104. currentNode = closedList[currentNode.id].previousNode;
  105. }
  106. return path;
  107. }
  108. else {
  109. return undefined;
  110. }
  111. }
  112. );
  113. }).call(window);