Last active
January 9, 2024 15:31
-
-
Save DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 to your computer and use it in GitHub Desktop.
A* Search Pathfinding Example from : https://dotnetcoretutorials.com/2020/07/25/a-search-pathfinding-algorithm-in-c/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } | |
| } | |
| } |
Author
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Read the full breakdown here : https://dotnetcoretutorials.com/2020/07/25/a-search-pathfinding-algorithm-in-c/