위 링크를 따라가보면 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);
}
}
}
위 코드의 결과를 이전 코드와 비교하면 다른것을 확인할 수 있다.
< 이전코드 >
<수정된 코드 >
