A* Algorithm
An algorithm for pathfinding.I want to play around with pathfinding using the A* algorithm. Ultimately, I would like to combine pathfinding with vector fields to create a sort of swarming, pathfinding algorithm.
Tile Map
I need to start by creating a tile map to represent our area. Each tile will have one of two states: blocking or non-blocking. Blocking tiles should stop the movement of entities, while non-blocking tiles should allow the movement of entities.
Pathfinding
Now that the tile map has been implemented, I can work on the actual pathfinding algorithm. As the title of this page suggests, I will be using the A* pathfinding algorithm here.
Movement Rules
These movement rules will determine how and when an entity can move through the tiles within this algorithm. The movement rules are as follows:
- Only the eight surrounding tiles will be considered
- Adjacent tiles can be moved to if they are non-blocking
- Diagonal tiles can be moved to if both adjacent tiles in that direction are non-blocking
A* Rules
The A* algorithm is governed by a very simple path scoring rule. Each tile is given a score of F = G + H, where:
- G is the movement cost from the starting tile to the current tile.
- H is the estimated movement cost from the current tile to the destination tile.
Paths are then given a score equal to their cumulative tiles' F values. The path with the lowest score should be shortest path.
The algorithm should follow these basic steps:
- Check all tiles surrounding the current tile.
- Score each valid tile and add them to the list of tiles to be checked.
- Move to the tile with the lowest F score and remove it from the list to be checked.
- Repeat from the first step until the destination is reached or all tiles have been checked.