# This line ensures that the neighboring cell is part of our walkable cells. # To find the neighbors, we try to move one cell in every possible direction and is ensure that # this cell is walkable and not already connected. func _find_neighbor_indices(cell: Vector2, cell_mappings: Dictionary) -> Array: # Returns an array of the `cell`'s connectable neighbors. connect_points(cell_mappings, neighbor_index) # The nnect_points() function connects two points on the graph by index, *not* # by coordinates. for point in cell_mappings:įor neighbor_index in _find_neighbor_indices(point, cell_mappings): We use # another function to find the neighbors given a cell's coordinates. # Then, we loop over the points again, and we connect them with all their neighbors. # We pass each cell's unique index and the corresponding Vector2 coordinates to the # AStar2D.add_point() function.
First, we register all our points in the AStar graph. func _add_and_connect_points(cell_mappings: Dictionary) -> void: # Adds and connects the walkable cells to the Astar2D object. # The AStar2D object then finds the best path between the two indices. If not, we return an empty # PoolVector2Array() to avoid errors. # We just ensure that the AStar graph has both points defined. # Our Grid.as_index() method does just that. This is why we # need a reliable way to calculate an index given some input coordinates. # With the AStar algorithm, we have to use the points' indices to get a path. func calculate_point_path(start: Vector2, end: Vector2) -> PoolVector2Array: # Returns the path found between `start` and `end` as an array of Vector2 coordinates. # We then add all the cells to our AStar2D instance and connect them to create our pathfinding # graph. # For each cell, we define a key-value pair of cell coordinates: index.Ĭell_mappings = _grid.
Doing so here slightly # simplifies the code and improves performance a bit. Here, # we cache a mapping between cell coordinates and their unique index. # To create our AStar graph, we will need the index value corresponding to each grid cell. # Because we will instantiate the `PathFinder` from our UnitPath's script, we pass it the data it # needs to initialize itself via its constructor function, _init(). func _init(grid: Grid, walkable_cells: Array) -> void:
# Initializes the Astar2D object upon creation. Our script is mostly # here to initialize that object. Var _grid: Resource # This variable holds an AStar2D instance that will do the actual pathfinding. It defines the directions in which we allow a unit # to move in the game: up, left, right, down. # Finds the path between two points among walkable cells using the AStar pathfinding algorithm.Įxtends Reference # We will use that constant in "for" loops later. Here is the code for the PathFinder class. With this method, we can calculate a unique index for each cell coordinates in our grid. This is where our grid class comes in handy with its as_index() method. You can already see the catch: the AStar object works with unique IDs for each point in the graph.
The algorithm outputs a list of coordinates through which you need to navigate to reach the end. Once the graph is set, you call the find_path() function with the indices corresponding to two points: the start and the end. In the case of a grid, you should connect each cell to its unoccupied neighbors.