 |
The found path from A*, the Yellow tiles are the tiles on the
closed list, the blue tiles are tiles on the open list and
the red arrows are the final path. |
This project applied terrain analysis on to a two dimensional grid that would change the weights differently on certain tiles that could change the path of the A* algorithm. Where ever the user clicked on the grid the agent "Tiny" will use A* to calculate the shortest path to that spot. If no terrain analysis is being used moving to a white square that's directly in front, behind, left or right has a cost of 1 and a diagonal tile has a cost of the square root of 2, while black walls have an infinite cost.
The values for the heuristics used can be toggled between Euclidean, Octile, Chebyshev and Manhattan. These heuristics can be multiplied by a weight, making the weight 0 makes the A* algorithm act like a breadth first search algorithm slowly expanding into a circle, while increasing the weight makes it act more like a Best First algorithm, making more of a beeline to the goal but might not find the optimal path. This weight could be changed to better fit the map. For example a map with small separate obstacles a more direct algorithm could find the path without looking at too many nodes but a maze like path where the optimal path is not in the direction of the goal, a more Dijkstra like algorithm would be better.
The original path found gives nodes that's in the center of all the tiles on the path. Rubber banding could be applied to remove unnecessary nodes by checking three adjacent nodes and if the two outer nodes can be connected without running into an obstacle it will remove the inner node. It will do this with every set of three adjacent nodes until no redundant nodes remain. Additionally smoothing can be applied using Catmull Rom splines to create additional nodes that make the path less jagged and more like how a person might walk.
 |
| Closest Wall |
Terrain analysis will take the current map and based off of certain criteria change the costs of the tiles. With closest wall each tile will weigh more the closer it is to a wall. This causes the A* path to look for more open rooms and steer Tiny away from walls and obstacles.
 |
| Rear Cover |
With rear cover each tile is valued based off of its possible protection it could provide. Not necessarily for used for path finding its would be useful for an AI in a shooter where it would look for good places to shoot from where it can't be attacked from behind.
 |
| Visibility |
Visibility checks to see how many other tiles a tile can see unobstructed and will weigh them more. This causes open areas to cost more and little alleyways to cost less. This would cause the path to prefer smaller nooks and crannies and avoid open areas to move across the map.
 |
| Rear Cover x Visibility |
Rear cover with high visibility multiplies the two previous calculations together to find good protected areas that can see a lot of area.
 |
Visible to Player
|
Visible to player checks to see which tiles are directly visible by the player and which ones are right next to directly visible ones. This could be valuable to an AI that could take cover at a tile right next to a tile next to a visible tile and then occasionally pop out to attack and then take cover again.
 |
| Search |
The search analysis increases the weight of tiles the player can see right now and slowly lowers them again over time. This way it will cause the agent to find paths that it hasn't taken before or in a while. This would be good for a guard AI that has to patrol an area.
 |
Fog of War
|
Fog of war can also be toggled where the Tiny won't 'know' about the walls on the map until she can directly see them. So the path finding will only take known walls into account and will recalculate a new path when new obstructions are discovered. This might cause Tiny to walk into a dead end without knowing it and will have to find a whole new path to get to the goal.
This project was made in a given framework that did all of the graphics and animations. I implemented all of the A* algorithm and terrain analysis' from scratch in C++.
