-
-
Save DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 to your computer and use it in GitHub Desktop.
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
//A* Search Pathfinding Example from : https://dotnetcoretutorials.com/2020/07/25/a-search-pathfinding-algorithm-in-c/ | |
namespace PathfindingExample | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
List<string> map = new List<string> | |
{ | |
"A ", | |
"--| |------", | |
" ", | |
" |-----| ", | |
" | | ", | |
"---| |B" | |
}; | |
var start = new Tile(); | |
start.Y = map.FindIndex(x => x.Contains("A")); | |
start.X = map[start.Y].IndexOf("A"); | |
var finish = new Tile(); | |
finish.Y = map.FindIndex(x => x.Contains("B")); | |
finish.X = map[finish.Y].IndexOf("B"); | |
start.SetDistance(finish.X, finish.Y); | |
var activeTiles = new List<Tile>(); | |
activeTiles.Add(start); | |
var visitedTiles = new List<Tile>(); | |
while(activeTiles.Any()) | |
{ | |
var checkTile = activeTiles.OrderBy(x => x.CostDistance).First(); | |
if(checkTile.X == finish.X && checkTile.Y == finish.Y) | |
{ | |
//We found the destination and we can be sure (Because the the OrderBy above) | |
//That it's the most low cost option. | |
var tile = checkTile; | |
Console.WriteLine("Retracing steps backwards..."); | |
while(true) | |
{ | |
Console.WriteLine($"{tile.X} : {tile.Y}"); | |
if(map[tile.Y][tile.X] == ' ') | |
{ | |
var newMapRow = map[tile.Y].ToCharArray(); | |
newMapRow[tile.X] = '*'; | |
map[tile.Y] = new string(newMapRow); | |
} | |
tile = tile.Parent; | |
if(tile == null) | |
{ | |
Console.WriteLine("Map looks like :"); | |
map.ForEach(x => Console.WriteLine(x)); | |
Console.WriteLine("Done!"); | |
return; | |
} | |
} | |
} | |
visitedTiles.Add(checkTile); | |
activeTiles.Remove(checkTile); | |
var walkableTiles = GetWalkableTiles(map, checkTile, finish); | |
foreach(var walkableTile in walkableTiles) | |
{ | |
//We have already visited this tile so we don't need to do so again! | |
if (visitedTiles.Any(x => x.X == walkableTile.X && x.Y == walkableTile.Y)) | |
continue; | |
//It's already in the active list, but that's OK, maybe this new tile has a better value (e.g. We might zigzag earlier but this is now straighter). | |
if(activeTiles.Any(x => x.X == walkableTile.X && x.Y == walkableTile.Y)) | |
{ | |
var existingTile = activeTiles.First(x => x.X == walkableTile.X && x.Y == walkableTile.Y); | |
if(existingTile.CostDistance > checkTile.CostDistance) | |
{ | |
activeTiles.Remove(existingTile); | |
activeTiles.Add(walkableTile); | |
} | |
}else | |
{ | |
//We've never seen this tile before so add it to the list. | |
activeTiles.Add(walkableTile); | |
} | |
} | |
} | |
Console.WriteLine("No Path Found!"); | |
} | |
private static List<Tile> GetWalkableTiles(List<string> map, Tile currentTile, Tile targetTile) | |
{ | |
var possibleTiles = new List<Tile>() | |
{ | |
new Tile { X = currentTile.X, Y = currentTile.Y - 1, Parent = currentTile, Cost = currentTile.Cost + 1 }, | |
new Tile { X = currentTile.X, Y = currentTile.Y + 1, Parent = currentTile, Cost = currentTile.Cost + 1}, | |
new Tile { X = currentTile.X - 1, Y = currentTile.Y, Parent = currentTile, Cost = currentTile.Cost + 1 }, | |
new Tile { X = currentTile.X + 1, Y = currentTile.Y, Parent = currentTile, Cost = currentTile.Cost + 1 }, | |
}; | |
possibleTiles.ForEach(tile => tile.SetDistance(targetTile.X, targetTile.Y)); | |
var maxX = map.First().Length - 1; | |
var maxY = map.Count - 1; | |
return possibleTiles | |
.Where(tile => tile.X >= 0 && tile.X <= maxX) | |
.Where(tile => tile.Y >= 0 && tile.Y <= maxY) | |
.Where(tile => map[tile.Y][tile.X] == ' ' || map[tile.Y][tile.X] == 'B') | |
.ToList(); | |
} | |
} | |
class Tile | |
{ | |
public int X { get; set; } | |
public int Y { get; set; } | |
public int Cost { get; set; } | |
public int Distance { get; set; } | |
public int CostDistance => Cost + Distance; | |
public Tile Parent { get; set; } | |
//The distance is essentially the estimated distance, ignoring walls to our target. | |
//So how many tiles left and right, up and down, ignoring walls, to get there. | |
public void SetDistance(int targetX, int targetY) | |
{ | |
this.Distance = Math.Abs(targetX - X) + Math.Abs(targetY - Y); | |
} | |
} | |
} |
How would you print out a result as a direction that the path took from the start? for example if the next tile is to the right Print E, if the next tile is below print S and W for left and N for above? I'm needing to print out just the direction in compass coordinates. Is this possible?
How would you print out a result as a direction that the path took from the start? for example if the next tile is to the right Print E, if the next tile is below print S and W for left and N for above? I'm needing to print out just the direction in compass coordinates. Is this possible?
I think you can calculate that inline outside the code. Just see the relative position with the x and y values of the next point. (Example: If your point is 2,3 and the next is 2,2, as the Y value for the next point is < than the Y of the current point and X is equal you can say that the direction is W.
Read the full breakdown here : https://dotnetcoretutorials.com/2020/07/25/a-search-pathfinding-algorithm-in-c/