Skip to content

Instantly share code, notes, and snippets.

@DotNetCoreTutorials

DotNetCoreTutorials/ASearchPathfindingInCSharp

Last active January 9, 2024 15:31
Show Gist options
  • Save DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 to your computer and use it in GitHub Desktop.
Save DotNetCoreTutorials/08b0210616769e81034f53a6a420a6d9 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. DotNetCoreTutorials revised this gist Jul 25, 2020. No changes.
  2. DotNetCoreTutorials revised this gist Jul 25, 2020. No changes.
  3. DotNetCoreTutorials created this gist Jul 25, 2020.
    137 changes: 137 additions & 0 deletions ASearchPathfindingInCSharp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,137 @@
    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);
    }
    }
    }