2018년 10월 18일 목요일

C# 간단한 4방향 A*(A Star) 알고리즘 구현 - Simple 4-way A* Algorithm implementation in C#

http://gigi.nullneuron.net/gigilabs/a-pathfinding-example-in-c/#comment-51778

위 링크를 따라가보면 c#을 이용해서 동서남북으로 이동하는 A*(A 스타) 알고리즘을 간단히 구현한 소스가 있는데 버그가 있다.

첫째로 G 값을 계산하는 루틴에서 g++ 과 같이 매 스탭마다 무조건 노드의 G 값을 증가시키는데 이렇게 되면 제대로 최단경로를 찾을 수 없다.

두번째로 GetWalkableAdjacentSquares 함수에서 이웃한 노드를 찾을때 Location 을 무조건 새로 생성하는데 만약 openList 에 해당 노드가 존재한다면 openList 에 존재하는 노드의 값을 비교하는것이 아니라 새로 생성한 노드와 비교하기 때문에(모든값이 0) 역시 엉뚱한 경로를 찾게된다.

따라서 위 코드는 아래와 같이 수정되어야한다.

 
 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 using System.Threading.Tasks;  
   
 namespace AStarPathfinding  
 {  
   class Location  
   {  
     public int X;  
     public int Y;  
     public int F;  
     public int G;  
     public int H;  
     public Location Parent;  
   }  
   
   class Program  
   {  
     static void Main(string[] args)  
     {  
       Console.Title = "A* Pathfinding";  
   
       // draw map  
       string[] map = new string[]  
       {  
                "+------------+",
                "|     X      |",
                "|  X     X  B|",
                "|  X     X   |",
                "|  X     X   |",
                "|A X     X   |",
                "|            |",
                "+------------+",
       };  
       var start = new Location { X = 1, Y = 5 };  
       var target = new Location { X = 12, Y = 2 };  

       int SLEEP_TIME = 100;  
   
       foreach (var line in map)  
         Console.WriteLine(line);  
   
       // algorithm  
       Location current = null;  
       var openList = new List<Location>();  
       var closedList = new List<Location>();  
       int g = 0;  
   
       // start by adding the original position to the open list  
       openList.Add(start);  
   
       while (openList.Count > 0)  
       {  
         // get the square with the lowest F score  
         var lowest = openList.Min(l => l.F);  
         current = openList.First(l => l.F == lowest);  
   
         // add the current square to the closed list  
         closedList.Add(current);  
   
         // show current square on the map  
         Console.SetCursorPosition(current.X, current.Y);  
         Console.Write('.');  
         Console.SetCursorPosition(current.X, current.Y);  
         System.Threading.Thread.Sleep(SLEEP_TIME);  
   
         // remove it from the open list  
         openList.Remove(current);  
   
         // if we added the destination to the closed list, we've found a path  
         if (closedList.FirstOrDefault(l => l.X == target.X && l.Y == target.Y) != null)  
           break;  

         var adjacentSquares = GetWalkableAdjacentSquares(current.X, current.Y, map, openList);  
         g = current.G + 1;  

         foreach(var adjacentSquare in adjacentSquares)  
         {  
           // if this adjacent square is already in the closed list, ignore it  
           if (closedList.FirstOrDefault(l => l.X == adjacentSquare.X  
               && l.Y == adjacentSquare.Y) != null)  
             continue;  
   
           // if it's not in the open list...  
           if (openList.FirstOrDefault(l => l.X == adjacentSquare.X  
               && l.Y == adjacentSquare.Y) == null)  
           {  
             // compute its score, set the parent  
             adjacentSquare.G = g;  
             adjacentSquare.H = ComputeHScore(adjacentSquare.X, adjacentSquare.Y, target.X, target.Y);  
             adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;  
             adjacentSquare.Parent = current;  
   
             // and add it to the open list  
             openList.Insert(0, adjacentSquare);  
           }  
           else  
           {  
             // test if using the current G score makes the adjacent square's F score  
             // lower, if yes update the parent because it means it's a better path  
             if (g + adjacentSquare.H < adjacentSquare.F)  
             {  
               adjacentSquare.G = g;  
               adjacentSquare.F = adjacentSquare.G + adjacentSquare.H;  
               adjacentSquare.Parent = current;  
             }  
           }  
         }  
       }  
   
       Location end = current;  
   
       // assume path was found; let's show it  
       while (current != null)  
       {  
         Console.SetCursorPosition(current.X, current.Y);  
         Console.Write('_');  
         Console.SetCursorPosition(current.X, current.Y);  
         current = current.Parent;  
         System.Threading.Thread.Sleep(SLEEP_TIME);  
       }  
   
       if (end != null)  
       {  
         Console.SetCursorPosition(0, 20);  
         Console.WriteLine("Path : {0}", end.G);  
       }  
   
       // end  
       Console.ReadLine();  
     }  
     
     static List<Location> GetWalkableAdjacentSquares(int x, int y, string[] map, List<Location> openList)  
     {  
       List<Location> list = new List<Location>();  
   
       if (map[y - 1][x] == ' ' || map[y - 1][x] == 'B')  
       {  
         Location node = openList.Find(l => l.X == x && l.Y == y - 1);  
         if (node == null) list.Add(new Location() { X = x, Y = y - 1 });  
         else list.Add(node);  
       }  
   
       if (map[y + 1][x] == ' ' || map[y + 1][x] == 'B')  
       {  
         Location node = openList.Find(l => l.X == x && l.Y == y + 1);  
         if (node == null) list.Add(new Location() { X = x, Y = y + 1 });  
         else list.Add(node);  
       }  
   
       if (map[y][x - 1] == ' ' || map[y][x - 1] == 'B')  
       {  
         Location node = openList.Find(l => l.X == x - 1 && l.Y == y);  
         if (node == null) list.Add(new Location() { X = x - 1, Y = y });  
         else list.Add(node);  
       }  
   
       if (map[y][x + 1] == ' ' || map[y][x + 1] == 'B')  
       {  
         Location node = openList.Find(l => l.X == x + 1 && l.Y == y);  
         if (node == null) list.Add(new Location() { X = x + 1, Y = y });  
         else list.Add(node);  
       }  
   
       return list;  
     }  
   
     static int ComputeHScore(int x, int y, int targetX, int targetY)  
     {  
       return Math.Abs(targetX - x) + Math.Abs(targetY - y);  
     }  
   }  
 }  


위 코드의 결과를 이전 코드와 비교하면 다른것을 확인할 수 있다.

< 이전코드 >



<수정된 코드 >





댓글 1개:

  1. Thank you very much. my pathfinding is working wonderfull now =)

    -Alberto-

    답글삭제