AStar Pathfinding

[impixiParticipant]

The following example calculates paths through a 2d integer array using the AStar search algorithm.

Monkey

'AStar pathfinding example. #Import "<std>" #Import "<mojo>" Using std.. Using mojo.. Function Main() New AppInstance New MyWindow App.Run() End '------------ Class MyWindow Extends Window Field _grid:Int[,] '0 = No Wall, 1 = Wall. Field _start:Vec2i 'Path starting coordinate. Field _goal:Vec2i 'Path goal coordinate. Field _pathFinder:PathFinder Field _path:Stack<Vec2i> 'All path's coordinates. Field _diagnals:Bool 'Include diagnals in potential path (cut corners). Field _cellWidth:Int 'Cell render width. Field _cellHeight:Int 'Cell render height. Method New(title:String = "AStar Example", width:Int = 800, height:Int = 600, flags:WindowFlags = Null) Super.New( title,width,height,flags ) Local cols := 40 Local rows := 20 _grid = New Int[cols, rows] _cellWidth = Width / cols _cellHeight = Height / rows _diagnals = False _start = New Vec2i(1, 1) _goal = New Vec2i(1, 10) _path = New Stack<Vec2i>() _pathFinder = New PathFinder(_grid) Generate() End Method Generate:Void() 'Randomly place some walls. For Local c :=0 Until _grid.GetSize(0) 'Columns. For Local r := 0 Until _grid.GetSize(1) 'Rows. If Floor(Rnd(0, 100)) < 33 '33% chance of wall. _grid[c, r] = 1 'Wall. Else _grid[c, r] = 0 'Empty. Endif Next Next CalculatePath() End Method CalculatePath:Void() _pathFinder.FindPath(_start, _goal, _path, _diagnals) End Method OnRender( canvas:Canvas ) Override App.RequestRender() For Local c := 0 Until _grid.GetSize(0) For Local r := 0 Until _grid.GetSize(1) If _grid[c, r] canvas.Color = Color.DarkGrey 'Wall. Else canvas.Color = Color.Black 'Empty. Endif canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next 'Start. canvas.Color = Color.Green canvas.DrawEllipse(_start.X * _cellWidth + (_cellWidth / 2), (_start.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) 'Path coordinates (if any). canvas.Color = Color.Yellow For Local coord := Eachin _path canvas.DrawRect(coord.X * _cellWidth, coord.Y * _cellHeight, _cellWidth, _cellHeight) Next 'Goal. canvas.Color = Color.Red canvas.DrawEllipse(_goal.X * _cellWidth + (_cellWidth / 2), (_goal.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) canvas.Color = Color.White canvas.DrawText("[Enter]: Generate new grid, [Left Click]: Place start, [Right Click] Place goal, [Tab] Toggle diagnals.", 0, 0) canvas.Flush() End Method OnKeyEvent:Void(event:KeyEvent) Override If event.Type = EventType.KeyDown If event.Key = Key.Escape App.Terminate() Elseif event.Key = Key.Tab 'Toggle "corner cutting" on/off. _diagnals = Not _diagnals CalculatePath() Elseif event.Key = Key.Enter 'Generate a new grid. Generate() Endif Endif End Method OnMouseEvent:Void(event:MouseEvent) Override If event.Type = EventType.MouseClick 'Set starting coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] = 0 _start = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseRightClick 'Set goal coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] = 0 _goal = New Vec2i(c, r) CalculatePath() Endif Endif End End '========================================= Class PathNode Public Field Pos:Vec2i 'Position Field H:Int 'Heuristic: movement cost to goal. Field G:Int 'Movement cost of entire path. Field F:Int 'Estimated cost for full path (G + H). Field Parent:PathNode 'Node to reach this node. Method New(pos:Vec2i) Pos = pos Reset() End Method Reset:Void() H = 0 G = 0 F = 0 Parent = Null End End '----- Class PathFinder Public Method New(grid:Int[,]) 'grid: An existing 2d array of integers with dimensions Columns x Rows Grid = grid _openStack = New Stack<PathNode>() _closedStack = New Stack<PathNode>() _pathStack = New Stack<PathNode>() _adjacentNodeStack = New Stack<PathNode>() End Property Grid:Int[,]() Return _grid Setter (value:Int[,]) If Not value Then Return _grid = value _cols = _grid.GetSize(0) _rows = _grid.GetSize(1) 'Only create a new nodeGrid if the new dimensions differ from the old dimensions. If Not _nodeGrid Or _nodeGrid.GetSize(0) <> _cols Or _nodeGrid.GetSize(1) <> _rows _nodeGrid = New PathNode[_cols, _rows] For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r] = New PathNode(New Vec2i(c, r)) Next Next Endif End Method FindPath:Void(start:Vec2i, goal:Vec2i, results:Stack<Vec2i>, includeDiagnals:Bool = False) 'start: Starting coordinate: column, row. 'goal: Goal coordinate: column, row. 'results: An existing Stack on which to place the path coordinates. If Not results Then Return results.Clear() If start = goal Then Return 'No path necessary 'Check for invalid start or goal coordinates. If start.X < 0 Or start.Y < 0 Or goal.X < 0 Or goal.Y < 0 Then Return If start.X >= _cols Or start.Y >= _rows Or goal.X >= _cols Or goal.Y >= _rows Then Return CalculateHeuristicCosts(goal) Local startNode := _nodeGrid[start.X, start.Y] Local goalNode := _nodeGrid[goal.X, goal.Y] _openStack.Clear() _closedStack.Clear() _pathStack.Clear() Local currentNode := startNode _openStack.Push(currentNode) _adjacentNodeStack.Clear() While Not _openStack.Empty 'Initially set the minimum full path cost high. Local minF := 4000000 For Local node:= Eachin _openStack If node.F < minF minF = node.F currentNode = node Endif Next _openStack.Remove(currentNode) _closedStack.Push(currentNode) GetAdjacentNodes(currentNode, _adjacentNodeStack, includeDiagnals) For Local node:= Eachin _adjacentNodeStack If node = goalNode node.Parent = currentNode While node.Parent _pathStack.Push(node) node = node.Parent Wend _openStack.Clear() Exit Else Local idx:=_closedStack.FindIndex(node) If idx < 0 'Node is not in closed stack. Local idx2:=_openStack.FindIndex(node) If idx2 < 0 'node is not in open stack. _openStack.Push(node) node.Parent = currentNode node.G = currentNode.G + 10 node.F = node.G + node.H Else If (currentNode.G + 10 < node.G) 'Faster. node.Parent = currentNode Endif Endif Endif Endif Next Wend For Local node:=Eachin _pathStack results.Push(node.Pos) Next End 'The CalculateHeuristicCosts method is implemented based on the game type. 'This example uses the Manhattan technique of calculating 'the distance between two points (suitable for grid-based, rogue-like games). Method CalculateHeuristicCosts:Void(goal:Vec2i) Local Distance := Lambda:Int(vecA:Vec2i, vecB:Vec2i) 'Manhattan technique of calculating the distance between two points. Local result := vecA - vecB Return Abs(result.X) + Abs(result.Y) End For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r].Reset() _nodeGrid[c, r].H = Distance(_nodeGrid[c, r].Pos, goal) Next Next End 'The GetAdjacentNodes method is implemented based on the game type. 'In this example the nodes North, East, South and West of the currentNode 'are considered adjacent. And also NE, SE, SW, NE, if includeDiagnals is True. Method GetAdjacentNodes:Void(currentNode:PathNode, results:Stack<PathNode>, includeDiagnals:Bool) If Not results Then Return results.Clear() Local PushIfValid := Lambda:void(c:Int, r:Int) If c < 0 Or c >= _cols Then Return If r < 0 Or r >= _rows Then Return If _grid[c, r] = 0 Then results.Push(_nodeGrid[c, r]) 'Cell is empty, so it's valid to use in a potential path. End PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y) 'West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y) 'East. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y-1) 'North. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y+1) 'South. If includeDiagnals PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y-1) 'North West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y-1) 'North East. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y+1) 'South East. PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y+1) 'South West. Endif End Private Field _grid:Int[,] 'Grid to calculate a path through. Field _cols:Int, _rows:Int 'Grid dimensions. 'Data structures used in calculations. Field _nodeGrid:PathNode[,] Field _openStack:Stack<PathNode> Field _closedStack:Stack<PathNode> Field _pathStack:Stack<PathNode> Field _adjacentNodeStack:Stack<PathNode> End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362

'AStar pathfinding example.   #Import "<std>" #Import "<mojo>"   Using std.. Using mojo..   Function Main() New AppInstance New MyWindow App.Run() End   '------------   Class MyWindow Extends Window   Field _grid:Int[,] '0 = No Wall, 1 = Wall. Field _start:Vec2i 'Path starting coordinate. Field _goal:Vec2i 'Path goal coordinate. Field _pathFinder:PathFinder Field _path:Stack<Vec2i> 'All path's coordinates. Field _diagnals:Bool 'Include diagnals in potential path (cut corners).   Field _cellWidth:Int 'Cell render width. Field _cellHeight:Int 'Cell render height.   Method New(title:String = "AStar Example", width:Int = 800, height:Int = 600, flags:WindowFlags = Null) Super.New( title,width,height,flags )   Local cols := 40 Local rows := 20 _grid = New Int[cols, rows] _cellWidth = Width / cols _cellHeight = Height / rows _diagnals = False _start = New Vec2i(1, 1) _goal = New Vec2i(1, 10) _path = New Stack<Vec2i>() _pathFinder = New PathFinder(_grid) Generate()   End   Method Generate:Void() 'Randomly place some walls. For Local c :=0 Until _grid.GetSize(0) 'Columns. For Local r := 0 Until _grid.GetSize(1) 'Rows. If Floor(Rnd(0, 100)) < 33 '33% chance of wall. _grid[c, r] = 1 'Wall. Else _grid[c, r] = 0 'Empty. Endif Next Next CalculatePath() End Method CalculatePath:Void() _pathFinder.FindPath(_start, _goal, _path, _diagnals) End   Method OnRender( canvas:Canvas ) Override App.RequestRender() For Local c := 0 Until _grid.GetSize(0) For Local r := 0 Until _grid.GetSize(1) If _grid[c, r] canvas.Color = Color.DarkGrey 'Wall. Else canvas.Color = Color.Black 'Empty. Endif canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next 'Start. canvas.Color = Color.Green canvas.DrawEllipse(_start.X * _cellWidth + (_cellWidth / 2), (_start.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) 'Path coordinates (if any). canvas.Color = Color.Yellow For Local coord := Eachin _path canvas.DrawRect(coord.X * _cellWidth, coord.Y * _cellHeight, _cellWidth, _cellHeight) Next 'Goal. canvas.Color = Color.Red canvas.DrawEllipse(_goal.X * _cellWidth + (_cellWidth / 2), (_goal.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) canvas.Color = Color.White canvas.DrawText("[Enter]: Generate new grid, [Left Click]: Place start, [Right Click] Place goal, [Tab] Toggle diagnals.", 0, 0) canvas.Flush() End Method OnKeyEvent:Void(event:KeyEvent) Override If event.Type = EventType.KeyDown If event.Key = Key.Escape App.Terminate() Elseif event.Key = Key.Tab 'Toggle "corner cutting" on/off. _diagnals = Not _diagnals CalculatePath() Elseif event.Key = Key.Enter 'Generate a new grid. Generate() Endif Endif End Method OnMouseEvent:Void(event:MouseEvent) Override If event.Type = EventType.MouseClick 'Set starting coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] = 0 _start = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseRightClick 'Set goal coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] = 0 _goal = New Vec2i(c, r) CalculatePath() Endif Endif End End     '=========================================     Class PathNode Public Field Pos:Vec2i 'Position Field H:Int 'Heuristic: movement cost to goal. Field G:Int 'Movement cost of entire path. Field F:Int 'Estimated cost for full path (G + H). Field Parent:PathNode 'Node to reach this node.   Method New(pos:Vec2i) Pos = pos Reset() End Method Reset:Void() H = 0 G = 0 F = 0 Parent = Null End   End   '-----   Class PathFinder Public Method New(grid:Int[,]) 'grid: An existing 2d array of integers with dimensions Columns x Rows   Grid = grid _openStack = New Stack<PathNode>() _closedStack = New Stack<PathNode>() _pathStack = New Stack<PathNode>() _adjacentNodeStack = New Stack<PathNode>() End Property Grid:Int[,]() Return _grid Setter (value:Int[,]) If Not value Then Return _grid = value _cols = _grid.GetSize(0) _rows = _grid.GetSize(1) 'Only create a new nodeGrid if the new dimensions differ from the old dimensions. If Not _nodeGrid Or _nodeGrid.GetSize(0) <> _cols Or _nodeGrid.GetSize(1) <> _rows _nodeGrid = New PathNode[_cols, _rows] For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r] = New PathNode(New Vec2i(c, r)) Next Next Endif End Method FindPath:Void(start:Vec2i, goal:Vec2i, results:Stack<Vec2i>, includeDiagnals:Bool = False) 'start: Starting coordinate: column, row. 'goal: Goal coordinate: column, row. 'results: An existing Stack on which to place the path coordinates. If Not results Then Return results.Clear() If start = goal Then Return 'No path necessary 'Check for invalid start or goal coordinates. If start.X < 0 Or start.Y < 0 Or goal.X < 0 Or goal.Y < 0 Then Return If start.X >= _cols Or start.Y >= _rows Or goal.X >= _cols Or goal.Y >= _rows Then Return CalculateHeuristicCosts(goal) Local startNode := _nodeGrid[start.X, start.Y] Local goalNode := _nodeGrid[goal.X, goal.Y] _openStack.Clear() _closedStack.Clear() _pathStack.Clear() Local currentNode := startNode _openStack.Push(currentNode) _adjacentNodeStack.Clear() While Not _openStack.Empty 'Initially set the minimum full path cost high. Local minF := 4000000 For Local node:= Eachin _openStack If node.F < minF minF = node.F currentNode = node Endif Next _openStack.Remove(currentNode) _closedStack.Push(currentNode) GetAdjacentNodes(currentNode, _adjacentNodeStack, includeDiagnals) For Local node:= Eachin _adjacentNodeStack If node = goalNode node.Parent = currentNode While node.Parent _pathStack.Push(node) node = node.Parent Wend _openStack.Clear() Exit Else Local idx:=_closedStack.FindIndex(node) If idx < 0 'Node is not in closed stack. Local idx2:=_openStack.FindIndex(node) If idx2 < 0 'node is not in open stack. _openStack.Push(node) node.Parent = currentNode node.G = currentNode.G + 10 node.F = node.G + node.H Else If (currentNode.G + 10 < node.G) 'Faster. node.Parent = currentNode Endif Endif Endif Endif Next Wend For Local node:=Eachin _pathStack results.Push(node.Pos) Next End 'The CalculateHeuristicCosts method is implemented based on the game type. 'This example uses the Manhattan technique of calculating 'the distance between two points (suitable for grid-based, rogue-like games). Method CalculateHeuristicCosts:Void(goal:Vec2i) Local Distance := Lambda:Int(vecA:Vec2i, vecB:Vec2i) 'Manhattan technique of calculating the distance between two points. Local result := vecA - vecB Return Abs(result.X) + Abs(result.Y) End   For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r].Reset() _nodeGrid[c, r].H = Distance(_nodeGrid[c, r].Pos, goal) Next Next End 'The GetAdjacentNodes method is implemented based on the game type. 'In this example the nodes North, East, South and West of the currentNode 'are considered adjacent. And also NE, SE, SW, NE, if includeDiagnals is True. Method GetAdjacentNodes:Void(currentNode:PathNode, results:Stack<PathNode>, includeDiagnals:Bool) If Not results Then Return   results.Clear() Local PushIfValid := Lambda:void(c:Int, r:Int) If c < 0 Or c >= _cols Then Return If r < 0 Or r >= _rows Then Return If _grid[c, r] = 0 Then results.Push(_nodeGrid[c, r]) 'Cell is empty, so it's valid to use in a potential path. End PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y) 'West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y) 'East. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y-1) 'North. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y+1) 'South. If includeDiagnals PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y-1) 'North West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y-1) 'North East. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y+1) 'South East. PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y+1) 'South West. Endif End Private Field _grid:Int[,] 'Grid to calculate a path through. Field _cols:Int, _rows:Int 'Grid dimensions. 'Data structures used in calculations. Field _nodeGrid:PathNode[,] Field _openStack:Stack<PathNode> Field _closedStack:Stack<PathNode> Field _pathStack:Stack<PathNode> Field _adjacentNodeStack:Stack<PathNode> End

Theory:

https://en.wikipedia.org/wiki/A*_search_algorithm

[PakzParticipant]

Nice!

I looked through the code and noticed it does not do terrain cost. It does handle diagonal and non diagonal.

I discovered that the simple flood or seed fill is also a good and simpler way to make pathfinding. I think I remember a gdc video where this was also tipped.

[HezkoreParticipant]

I’m no good at math or algorithms, but this is my modified version with tile ‘cost’.
Use the mouse wheel to change the cost of the tile under the mouse.

Monkey

'AStar pathfinding example. #Import "<std>" #Import "<mojo>" Using std.. Using mojo.. Function Main() New AppInstance New MyWindow App.Run() End '------------ Class MyWindow Extends Window Field _grid:Float[,] '0 = No Wall, 1 = Wall. Field _start:Vec2i 'Path starting coordinate. Field _goal:Vec2i 'Path goal coordinate. Field _pathFinder:PathFinder Field _path:Stack<Vec2i> 'All path's coordinates. Field _diagnals:Bool 'Include diagnals in potential path (cut corners). Field _cellWidth:Int 'Cell render width. Field _cellHeight:Int 'Cell render height. Method New(title:String = "AStar Example", width:Int = 800, height:Int = 600, flags:WindowFlags = Null) Super.New( title,width,height,flags ) Local cols := 40 Local rows := 20 _grid = New Float[cols, rows] _cellWidth = Width / cols _cellHeight = Height / rows _diagnals = False _start = New Vec2i(38, 10) _goal = New Vec2i(1, 10) _path = New Stack<Vec2i>() _pathFinder = New PathFinder(_grid) 'Multiply the cost of each tile _pathFinder.CostMulti=50 'Default is 50, just cause it seemed 'correct'? Generate() End Method Generate:Void() 'Randomly place some walls. For Local c :=0 Until _grid.GetSize(0) 'Columns. For Local r := 0 Until _grid.GetSize(1) 'Rows. _grid[c, r] = Rnd( -0.5, 1 ) 'Never a solid wall If _grid[c, r]<0 Then _grid[c, r]=0 Next Next CalculatePath() End Method CalculatePath:Void() _pathFinder.FindPath(_start, _goal, _path, _diagnals) End Method OnRender( canvas:Canvas ) Override App.RequestRender() Local w:Float For Local c := 0 Until _grid.GetSize(0) For Local r := 0 Until _grid.GetSize(1) w=_grid[c, r] If w>=1 canvas.Color = Color.Red 'Wall. Else canvas.Color = New Color( w*0.5, w*0.5, w*0.5 ) 'Walkable Endif canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next 'Start. canvas.Color = Color.Green canvas.DrawEllipse(_start.X * _cellWidth + (_cellWidth / 2), (_start.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) 'Path coordinates (if any). canvas.Color = Color.Yellow For Local coord := Eachin _path canvas.DrawRect(coord.X * _cellWidth, coord.Y * _cellHeight, _cellWidth, _cellHeight) Next 'Goal. canvas.Color = Color.Red canvas.DrawEllipse(_goal.X * _cellWidth + (_cellWidth / 2), (_goal.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) canvas.Color = Color.White canvas.DrawText("[Enter]: Generate new grid, [Left Click]: Place start, [Right Click] Place goal, [Tab] Toggle diagnals.", 0, 0) canvas.Flush() End Method OnKeyEvent:Void(event:KeyEvent) Override If event.Type = EventType.KeyDown If event.Key = Key.Escape App.Terminate() Elseif event.Key = Key.Tab 'Toggle "corner cutting" on/off. _diagnals = Not _diagnals CalculatePath() Elseif event.Key = Key.Enter 'Generate a new grid. Generate() Endif Endif End Method OnMouseEvent:Void(event:MouseEvent) Override If event.Type = EventType.MouseClick 'Set starting coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] < 1 _start = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseRightClick 'Set goal coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] < 1 _goal = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseWheel 'Change tile cost Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) _grid[c, r] += event.Wheel.Y*0.1 If _grid[c, r]<0 Then _grid[c, r]=0 If _grid[c, r]>1 Then _grid[c, r]=1 CalculatePath() Endif End End '========================================= Class PathNode Public Field Pos:Vec2i 'Position Field H:Int 'Heuristic: movement cost to goal. Field G:Int 'Movement cost of entire path. Field F:Int 'Estimated cost for full path (G + H). Field Parent:PathNode 'Node to reach this node. Method New(pos:Vec2i) Pos = pos Reset() End Method Reset:Void() H = 0 G = 0 F = 0 Parent = Null End End '----- Class PathFinder Public Method New(grid:Float[,]) 'grid: An existing 2d array of integers with dimensions Columns x Rows Grid = grid _openStack = New Stack<PathNode>() _closedStack = New Stack<PathNode>() _pathStack = New Stack<PathNode>() _adjacentNodeStack = New Stack<PathNode>() End Property Grid:Float[,]() Return _grid Setter (value:Float[,]) If Not value Then Return _grid = value _cols = _grid.GetSize(0) _rows = _grid.GetSize(1) 'Only create a new nodeGrid if the new dimensions differ from the old dimensions. If Not _nodeGrid Or _nodeGrid.GetSize(0) <> _cols Or _nodeGrid.GetSize(1) <> _rows _nodeGrid = New PathNode[_cols, _rows] For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r] = New PathNode(New Vec2i(c, r)) Next Next Endif End Property CostMulti:Float() Return _costMulti Setter (value:Float) _costMulti=value End Method FindPath:Void(start:Vec2i, goal:Vec2i, results:Stack<Vec2i>, includeDiagnals:Bool = False) 'start: Starting coordinate: column, row. 'goal: Goal coordinate: column, row. 'results: An existing Stack on which to place the path coordinates. If Not results Then Return results.Clear() If start = goal Then Return 'No path necessary 'Check for invalid start or goal coordinates. If start.X < 0 Or start.Y < 0 Or goal.X < 0 Or goal.Y < 0 Then Return If start.X >= _cols Or start.Y >= _rows Or goal.X >= _cols Or goal.Y >= _rows Then Return CalculateHeuristicCosts(goal) Local startNode := _nodeGrid[start.X, start.Y] Local goalNode := _nodeGrid[goal.X, goal.Y] _openStack.Clear() _closedStack.Clear() _pathStack.Clear() Local currentNode := startNode _openStack.Push(currentNode) _adjacentNodeStack.Clear() While Not _openStack.Empty 'Initially set the minimum full path cost high. Local minF := 4000000 For Local node:= Eachin _openStack If node.F < minF minF = node.F currentNode = node Endif Next _openStack.Remove(currentNode) _closedStack.Push(currentNode) GetAdjacentNodes(currentNode, _adjacentNodeStack, includeDiagnals) For Local node:= Eachin _adjacentNodeStack If node = goalNode node.Parent = currentNode While node.Parent _pathStack.Push(node) node = node.Parent Wend _openStack.Clear() Exit Else Local idx:=_closedStack.FindIndex(node) If idx < 0 'Node is not in closed stack. Local idx2:=_openStack.FindIndex(node) If idx2 < 0 'node is not in open stack. _openStack.Push(node) node.Parent = currentNode node.G = currentNode.G + 10 node.F = node.G + node.H Else If (currentNode.G + 10 < node.G) 'Faster. node.Parent = currentNode Endif Endif Endif Endif Next Wend For Local node:=Eachin _pathStack results.Push(node.Pos) Next End 'The CalculateHeuristicCosts method is implemented based on the game type. 'This example uses the Manhattan technique of calculating 'the distance between two points (suitable for grid-based, rogue-like games). Method CalculateHeuristicCosts:Void(goal:Vec2i) Local Distance := Lambda:Int(vecA:Vec2i, vecB:Vec2i) 'Manhattan technique of calculating the distance between two points. Local result := vecA - vecB Return Abs(result.X) + Abs(result.Y) End For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r].Reset() _nodeGrid[c, r].H = Distance(_nodeGrid[c, r].Pos, goal) _nodeGrid[c, r].H += Clamp( _grid[c, r], 0.0, 1.0 ) * _costMulti Next Next End 'The GetAdjacentNodes method is implemented based on the game type. 'In this example the nodes North, East, South and West of the currentNode 'are considered adjacent. And also NE, SE, SW, NE, if includeDiagnals is True. Method GetAdjacentNodes:Void(currentNode:PathNode, results:Stack<PathNode>, includeDiagnals:Bool) If Not results Then Return results.Clear() Local PushIfValid := Lambda:void(c:Int, r:Int) If c < 0 Or c >= _cols Then Return If r < 0 Or r >= _rows Then Return If _grid[c, r] < 1 Then results.Push(_nodeGrid[c, r]) 'Cell is empty, so it's valid to use in a potential path. End PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y) 'West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y) 'East. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y-1) 'North. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y+1) 'South. If includeDiagnals PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y-1) 'North West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y-1) 'North East. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y+1) 'South East. PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y+1) 'South West. Endif End Private Field _grid:Float[,] 'Grid to calculate a path through. Field _cols:Int, _rows:Int 'Grid dimensions. Field _costMulti:Float = 50 'Cost multiplier. 'Data structures used in calculations. Field _nodeGrid:PathNode[,] Field _openStack:Stack<PathNode> Field _closedStack:Stack<PathNode> Field _pathStack:Stack<PathNode> Field _adjacentNodeStack:Stack<PathNode> End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379

'AStar pathfinding example.   #Import "<std>" #Import "<mojo>"   Using std.. Using mojo..   Function Main() New AppInstance New MyWindow App.Run() End   '------------   Class MyWindow Extends Window Field _grid:Float[,] '0 = No Wall, 1 = Wall. Field _start:Vec2i 'Path starting coordinate. Field _goal:Vec2i 'Path goal coordinate. Field _pathFinder:PathFinder Field _path:Stack<Vec2i> 'All path's coordinates. Field _diagnals:Bool 'Include diagnals in potential path (cut corners). Field _cellWidth:Int 'Cell render width. Field _cellHeight:Int 'Cell render height.   Method New(title:String = "AStar Example", width:Int = 800, height:Int = 600, flags:WindowFlags = Null) Super.New( title,width,height,flags ) Local cols := 40 Local rows := 20 _grid = New Float[cols, rows] _cellWidth = Width / cols _cellHeight = Height / rows _diagnals = False _start = New Vec2i(38, 10) _goal = New Vec2i(1, 10) _path = New Stack<Vec2i>() _pathFinder = New PathFinder(_grid) 'Multiply the cost of each tile _pathFinder.CostMulti=50 'Default is 50, just cause it seemed 'correct'? Generate() End   Method Generate:Void() 'Randomly place some walls. For Local c :=0 Until _grid.GetSize(0) 'Columns. For Local r := 0 Until _grid.GetSize(1) 'Rows. _grid[c, r] = Rnd( -0.5, 1 ) 'Never a solid wall If _grid[c, r]<0 Then _grid[c, r]=0 Next Next CalculatePath() End Method CalculatePath:Void() _pathFinder.FindPath(_start, _goal, _path, _diagnals) End   Method OnRender( canvas:Canvas ) Override App.RequestRender() Local w:Float For Local c := 0 Until _grid.GetSize(0) For Local r := 0 Until _grid.GetSize(1) w=_grid[c, r] If w>=1 canvas.Color = Color.Red 'Wall. Else canvas.Color = New Color( w*0.5, w*0.5, w*0.5 ) 'Walkable Endif canvas.DrawRect(c * _cellWidth, r * _cellHeight, _cellWidth, _cellHeight) Next Next 'Start. canvas.Color = Color.Green canvas.DrawEllipse(_start.X * _cellWidth + (_cellWidth / 2), (_start.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) 'Path coordinates (if any). canvas.Color = Color.Yellow For Local coord := Eachin _path canvas.DrawRect(coord.X * _cellWidth, coord.Y * _cellHeight, _cellWidth, _cellHeight) Next 'Goal. canvas.Color = Color.Red canvas.DrawEllipse(_goal.X * _cellWidth + (_cellWidth / 2), (_goal.Y * _cellHeight) + (_cellHeight / 2), _cellWidth / 4, _cellHeight / 4) canvas.Color = Color.White canvas.DrawText("[Enter]: Generate new grid, [Left Click]: Place start, [Right Click] Place goal, [Tab] Toggle diagnals.", 0, 0) canvas.Flush() End Method OnKeyEvent:Void(event:KeyEvent) Override If event.Type = EventType.KeyDown If event.Key = Key.Escape App.Terminate() Elseif event.Key = Key.Tab 'Toggle "corner cutting" on/off. _diagnals = Not _diagnals CalculatePath() Elseif event.Key = Key.Enter 'Generate a new grid. Generate() Endif Endif End Method OnMouseEvent:Void(event:MouseEvent) Override If event.Type = EventType.MouseClick 'Set starting coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] < 1 _start = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseRightClick 'Set goal coordinate. Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) If _grid[c, r] < 1 _goal = New Vec2i(c, r) CalculatePath() Endif Elseif event.Type = EventType.MouseWheel 'Change tile cost Local c:= Floor(Mouse.Location.X / _cellWidth) Local r:= Floor(Mouse.Location.Y / _cellHeight) _grid[c, r] += event.Wheel.Y*0.1 If _grid[c, r]<0 Then _grid[c, r]=0 If _grid[c, r]>1 Then _grid[c, r]=1 CalculatePath() Endif End End     '=========================================     Class PathNode Public Field Pos:Vec2i 'Position Field H:Int 'Heuristic: movement cost to goal. Field G:Int 'Movement cost of entire path. Field F:Int 'Estimated cost for full path (G + H). Field Parent:PathNode 'Node to reach this node.   Method New(pos:Vec2i) Pos = pos Reset() End Method Reset:Void() H = 0 G = 0 F = 0 Parent = Null End   End   '-----   Class PathFinder Public Method New(grid:Float[,]) 'grid: An existing 2d array of integers with dimensions Columns x Rows   Grid = grid _openStack = New Stack<PathNode>() _closedStack = New Stack<PathNode>() _pathStack = New Stack<PathNode>() _adjacentNodeStack = New Stack<PathNode>() End Property Grid:Float[,]() Return _grid Setter (value:Float[,]) If Not value Then Return _grid = value _cols = _grid.GetSize(0) _rows = _grid.GetSize(1) 'Only create a new nodeGrid if the new dimensions differ from the old dimensions. If Not _nodeGrid Or _nodeGrid.GetSize(0) <> _cols Or _nodeGrid.GetSize(1) <> _rows _nodeGrid = New PathNode[_cols, _rows] For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r] = New PathNode(New Vec2i(c, r)) Next Next Endif End Property CostMulti:Float() Return _costMulti Setter (value:Float) _costMulti=value End Method FindPath:Void(start:Vec2i, goal:Vec2i, results:Stack<Vec2i>, includeDiagnals:Bool = False) 'start: Starting coordinate: column, row. 'goal: Goal coordinate: column, row. 'results: An existing Stack on which to place the path coordinates. If Not results Then Return results.Clear() If start = goal Then Return 'No path necessary 'Check for invalid start or goal coordinates. If start.X < 0 Or start.Y < 0 Or goal.X < 0 Or goal.Y < 0 Then Return If start.X >= _cols Or start.Y >= _rows Or goal.X >= _cols Or goal.Y >= _rows Then Return CalculateHeuristicCosts(goal) Local startNode := _nodeGrid[start.X, start.Y] Local goalNode := _nodeGrid[goal.X, goal.Y] _openStack.Clear() _closedStack.Clear() _pathStack.Clear() Local currentNode := startNode _openStack.Push(currentNode) _adjacentNodeStack.Clear() While Not _openStack.Empty 'Initially set the minimum full path cost high. Local minF := 4000000 For Local node:= Eachin _openStack If node.F < minF minF = node.F currentNode = node Endif Next _openStack.Remove(currentNode) _closedStack.Push(currentNode) GetAdjacentNodes(currentNode, _adjacentNodeStack, includeDiagnals) For Local node:= Eachin _adjacentNodeStack If node = goalNode node.Parent = currentNode While node.Parent _pathStack.Push(node) node = node.Parent Wend _openStack.Clear() Exit Else Local idx:=_closedStack.FindIndex(node) If idx < 0 'Node is not in closed stack. Local idx2:=_openStack.FindIndex(node) If idx2 < 0 'node is not in open stack. _openStack.Push(node) node.Parent = currentNode node.G = currentNode.G + 10 node.F = node.G + node.H Else If (currentNode.G + 10 < node.G) 'Faster. node.Parent = currentNode Endif Endif Endif Endif Next Wend For Local node:=Eachin _pathStack results.Push(node.Pos) Next End 'The CalculateHeuristicCosts method is implemented based on the game type. 'This example uses the Manhattan technique of calculating 'the distance between two points (suitable for grid-based, rogue-like games). Method CalculateHeuristicCosts:Void(goal:Vec2i) Local Distance := Lambda:Int(vecA:Vec2i, vecB:Vec2i) 'Manhattan technique of calculating the distance between two points. Local result := vecA - vecB Return Abs(result.X) + Abs(result.Y) End For Local c := 0 Until _cols For Local r := 0 Until _rows _nodeGrid[c, r].Reset() _nodeGrid[c, r].H = Distance(_nodeGrid[c, r].Pos, goal) _nodeGrid[c, r].H += Clamp( _grid[c, r], 0.0, 1.0 ) * _costMulti Next Next End 'The GetAdjacentNodes method is implemented based on the game type. 'In this example the nodes North, East, South and West of the currentNode 'are considered adjacent. And also NE, SE, SW, NE, if includeDiagnals is True. Method GetAdjacentNodes:Void(currentNode:PathNode, results:Stack<PathNode>, includeDiagnals:Bool) If Not results Then Return   results.Clear() Local PushIfValid := Lambda:void(c:Int, r:Int) If c < 0 Or c >= _cols Then Return If r < 0 Or r >= _rows Then Return If _grid[c, r] < 1 Then results.Push(_nodeGrid[c, r]) 'Cell is empty, so it's valid to use in a potential path. End PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y) 'West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y) 'East. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y-1) 'North. PushIfValid(currentNode.Pos.X, currentNode.Pos.Y+1) 'South. If includeDiagnals PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y-1) 'North West. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y-1) 'North East. PushIfValid(currentNode.Pos.X+1, currentNode.Pos.Y+1) 'South East. PushIfValid(currentNode.Pos.X-1, currentNode.Pos.Y+1) 'South West. Endif End Private Field _grid:Float[,] 'Grid to calculate a path through. Field _cols:Int, _rows:Int 'Grid dimensions. Field _costMulti:Float = 50 'Cost multiplier. 'Data structures used in calculations. Field _nodeGrid:PathNode[,] Field _openStack:Stack<PathNode> Field _closedStack:Stack<PathNode> Field _pathStack:Stack<PathNode> Field _adjacentNodeStack:Stack<PathNode> End

[Author]

Posts