Posted By

LeeProbert on 03/13/10


Tagged

textmate grid pathfinder pacman


Versions (?)

AStarMap pathfinding grid (use with AStar class)


 / Published in: Other
 

  1. package com.game.astar
  2. {
  3. public class AStarMap {
  4.  
  5. //these are the states available for each cell.
  6. public const CELL_FREE:uint = 0;
  7. public const CELL_FILLED:uint = 1;
  8. public const CELL_ORIGIN:uint = 2;
  9. public const CELL_DESTINATION:uint = 3;
  10. public const MAX_ITERATIONS:uint = 2000;
  11.  
  12. public var gridWidth:uint;
  13. public var gridHeight:uint;
  14.  
  15. public var isSolved:Boolean;
  16.  
  17. private var originCell:Object;
  18. private var destinationCell:Object;
  19. private var currentCell:Object;
  20.  
  21. private var openList:Array;
  22. private var closedList:Array;
  23.  
  24. private var mapArray:Array;
  25.  
  26. //------------------------------------------------------------------------------------
  27. //grid sizes refer to the size in units of cell size, not pixel size.
  28. public function AStarMap(_gridWidth:int, _gridHeight:int):void
  29. {
  30. gridWidth = _gridWidth;
  31. gridHeight = _gridHeight;
  32.  
  33. //define map
  34. mapArray = new Array();
  35. var xx:int = 0;
  36. var yy:int = 0;
  37. for(xx = 0; xx < gridWidth; xx++)
  38. {
  39. mapArray[xx] = new Array();
  40. for(yy = 0; yy < gridHeight; yy++)
  41. {
  42. mapArray[xx][yy] = new Object();
  43. mapArray[xx][yy].cellType = CELL_FREE;
  44. mapArray[xx][yy].parentCell = null;
  45. mapArray[xx][yy].g = 0;
  46. mapArray[xx][yy].f = 0;
  47. mapArray[xx][yy].x = xx;
  48. mapArray[xx][yy].y = yy;
  49. }
  50.  
  51. }
  52.  
  53. openList = new Array();
  54. closedList = new Array();
  55. }
  56. //----------------------------------------------------------------------------------
  57. public function solve():Array
  58. {
  59. //count = 0;
  60. reset();
  61. //trace(destinationCell.x, destinationCell.y);
  62. isSolved = false;
  63. var iter:int = 0;
  64.  
  65. isSolved = stepPathfinder();
  66.  
  67. while(!isSolved)
  68. {
  69. isSolved = stepPathfinder();
  70. if(iter++ > MAX_ITERATIONS) return null;
  71. }
  72.  
  73. //set pointer to last cell on list
  74. //if pointer is pointing to originCell, then finish
  75. //if pointer is not pointing at origin cell, then process, and set pointer to parent of current cell
  76. var solutionPath:Array = new Array();
  77. var count:int = 0;
  78. var cellPointer:Object = closedList[closedList.length - 1];
  79. while(cellPointer != originCell)
  80. {
  81. if(count++ > 800) return null; //prevent a hang in case something goes awry
  82. solutionPath.push(cellPointer);
  83. cellPointer = cellPointer.parentCell;
  84. }
  85.  
  86. return solutionPath;
  87.  
  88. }
  89.  
  90. //----------------------------------------------------------------------------------
  91. private function stepPathfinder():Boolean {
  92. //trace(cnt++);
  93. if(currentCell == destinationCell)
  94. {
  95. closedList.push(destinationCell);
  96. return true;
  97. }
  98.  
  99. //place current cell into openList
  100. openList.push(currentCell);
  101.  
  102. //----------------------------------------------------------------------------------------------------
  103. //place all legal adjacent squares into a temporary array
  104. //----------------------------------------------------------------------------------------------------
  105.  
  106. //add legal adjacent cells from above to the open list
  107. var adjacentCell:Array = new Array();
  108. var arryPtr:Object;
  109. var isDiagonal:Boolean;
  110.  
  111. for(var xx:int = -1; xx <= 1; xx++)
  112. {
  113. for(var yy:int = -1; yy <= 1; yy++)
  114. {
  115. /*
  116. Look at all the adjacent cells
  117. */
  118. if(!(xx == 0 && yy == 0)) //this is the current cell, so skip it.
  119. {
  120. /*
  121. is adjacent Cell within the grid bounds?
  122. */
  123. if(currentCell.x+xx >= 0 && currentCell.y+yy >= 0 && currentCell.x+xx < gridWidth && currentCell.y+yy < gridHeight)
  124. {
  125. /*
  126. is adjacent cell NOT diagonal to the currentCell?
  127. */
  128. isDiagonal = ((xx==-1 || xx==1) && (yy==-1 || yy==1));
  129. /*
  130. CurrentCell is in the mapArray?
  131. */
  132. if(mapArray[currentCell.x+xx][currentCell.y+yy])
  133. {
  134. arryPtr = mapArray[currentCell.x+xx][currentCell.y+yy];
  135.  
  136. if(arryPtr.cellType != CELL_FILLED && closedList.indexOf(arryPtr) == -1 && !isDiagonal)
  137. {
  138. //trace(mapArray[currentCell.x + xx][currentCell.y + yy]);
  139. adjacentCell.push(arryPtr);
  140. }
  141. }
  142. }
  143. }
  144. }
  145. }
  146.  
  147.  
  148. var g:int;
  149. var h:int;
  150.  
  151. for(var ii:int = 0; ii < adjacentCell.length; ii++) {
  152.  
  153. g = currentCell.g + 1;
  154.  
  155. h = Math.abs(adjacentCell[ii].x - destinationCell.x) + Math.abs(adjacentCell[ii].y - destinationCell.y);
  156.  
  157. if(openList.indexOf(adjacentCell[ii]) == -1) { //is cell already on the open list? - no
  158.  
  159. adjacentCell[ii].f = g + h;
  160. adjacentCell[ii].parentCell = currentCell;
  161. adjacentCell[ii].g = g;
  162. openList.push(adjacentCell[ii]);
  163.  
  164. } else { //is cell already on the open list? - yes
  165.  
  166. if(adjacentCell[ii].g < currentCell.parentCell.g)
  167. {
  168. currentCell.parentCell = adjacentCell[ii];
  169. currentCell.g = adjacentCell[ii].g + 1;
  170. currentCell.f = adjacentCell[ii].g + h;
  171. }
  172. }
  173. }
  174.  
  175. //Remove current cell from openList and add to closedList.
  176. var indexOfCurrent:int = openList.indexOf(currentCell);
  177. closedList.push(currentCell);
  178. openList.splice(indexOfCurrent, 1);
  179.  
  180. //Take the lowest scoring openList cell and make it the current cell.
  181. openList.sortOn("f", Array.NUMERIC | Array.DESCENDING);
  182.  
  183. if(openList.length == 0) return true;
  184.  
  185. currentCell = openList.pop();
  186.  
  187. return false;
  188. }
  189. //------------------------------------------------------------------------------------
  190. public function getCell(xx:int, yy:int):Object
  191. {
  192. return mapArray[xx][yy];
  193. }
  194. //------------------------------------------------------------------------------------
  195. //Sets individual cell state
  196. public function setCell(xx:int, yy:int, cellType:int):void
  197. {
  198. mapArray[xx][yy].cellType = cellType;
  199. }
  200. //------------------------------------------------------------------------------------
  201. //Toggle cell between "filled" and "free" states
  202. public function toggleCell(cellX:int, cellY:int):void
  203. {
  204. if(mapArray[cellX][cellY].cellType == CELL_FILLED) mapArray[cellX][cellY].cellType = CELL_FREE;
  205. else if(mapArray[cellX][cellY].cellType == CELL_FREE) mapArray[cellX][cellY].cellType = CELL_FILLED;
  206. }
  207. //------------------------------------------------------------------------------------
  208. //Sets origin and destination
  209. public function setEndPoints(originX:int, originY:int, destX:int, destY:int):void
  210. {
  211. originCell = mapArray[originX][originY];
  212. destinationCell = mapArray[destX][destY];
  213.  
  214. originCell.cellType = CELL_ORIGIN;
  215. destinationCell.cellType = CELL_DESTINATION;
  216.  
  217. currentCell = originCell;
  218. closedList.push(originCell);
  219. }
  220. //------------------------------------------------------------------------------------
  221. //Resets algorithm without clearing cells
  222. public function reset():void
  223. {
  224. for(var xx:int = 0; xx < gridWidth; xx++)
  225. {
  226. for(var yy:int = 0; yy < gridHeight; yy++)
  227. {
  228. mapArray[xx][yy].parentCell = null;
  229. mapArray[xx][yy].g = 0;
  230. mapArray[xx][yy].f = 0;
  231. }
  232. }
  233.  
  234. openList = new Array();
  235. closedList = new Array();
  236.  
  237. currentCell = originCell;
  238. closedList.push(originCell);
  239. }
  240. //------------------------------------------------------------------------------------
  241. //Sets all filled cells to free cells (does not affect origin or destination cells)
  242. public function clearMap():void
  243. {
  244. for(var xx:int = 0; xx < gridWidth; xx++) {
  245. //mapArray[xx] = new Array();
  246. for(var yy:int = 0; yy < gridHeight; yy++) {
  247. //mapArray[xx][yy] = new Object();
  248. if(mapArray[xx][yy].cellType == CELL_FILLED) mapArray[xx][yy].cellType = CELL_FREE;
  249. mapArray[xx][yy].parentCell = null;
  250. mapArray[xx][yy].g = 0;
  251. mapArray[xx][yy].f = 0;
  252. mapArray[xx][yy].x = xx;
  253. mapArray[xx][yy].y = yy;
  254. }
  255. }
  256. }
  257. } //end class
  258.  
  259. }
  260.  
  261.  

Report this snippet  

You need to login to post a comment.