[C#/WINFORM] A* (AStar) 길 찾기 알고리즘 사용하기

TestProject.zip

다운로드

▶ Tile.cs

using System;
using System.Drawing;

namespace TestProject
{
    /// <summary>
    /// 타일
    /// </summary>
    public class Tile
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region X 좌표 - X

        /// <summary>
        /// X 좌표
        /// </summary>
        public int X { get; set; }

        #endregion
        #region Y 좌표 - Y

        /// <summary>
        /// Y 좌표
        /// </summary>
        public int Y { get; set; }

        #endregion
        #region 벽 여부 - IsWall

        /// <summary>
        /// 벽 여부
        /// </summary>
        public bool IsWall { get; set; }

        #endregion
        #region 테두리 사각형 - BoundRectangle

        /// <summary>
        /// 테두리 사각형
        /// </summary>
        public Rectangle BoundRectangle { get; set; }

        #endregion
        #region 레이블 - Label

        /// <summary>
        /// 레이블
        /// </summary>
        public string Label { get; set; }

        #endregion

        #region 현재 거리 - CurrentDistance

        /// <summary>
        /// 현재 거리
        /// </summary>
        /// <remarks>출발지에서 현재 위치까지의 거리</remarks>
        public int CurrentDistance { get; private set; }

        #endregion
        #region 잔여 거리 - RemainDistance

        /// <summary>
        /// 잔여 거리
        /// </summary>
        /// <remarks>현재 위치에서 도착지까지의 거리</remarks>
        public int RemainDistance { get; private set; }

        #endregion
        #region 전체 거리 - TotalDistance

        /// <summary>
        /// 전체 거리
        /// </summary>
        public int TotalDistance
        {
            get
            {
                return CurrentDistance + RemainDistance;
            }
        }

        #endregion

        #region 부모 타일 - ParentTile

        /// <summary>
        /// 부모 타일
        /// </summary>
        public Tile ParentTile { get; private set; }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Static
        //////////////////////////////////////////////////////////////////////////////// Public

        #region 현재 거리 구하기 - GetCurrentDistance(parentTile, currentTile)

        /// <summary>
        /// 현재 거리 구하기
        /// </summary>
        /// <param name="parentTile">부모 타일</param>
        /// <param name="currentTile">현재 타일</param>
        /// <returns>현재 거리</returns>
        /// <remarks>
        /// 상하좌우 이동값 : 10
        /// 대각선 이동값   : 14
        /// </remarks>
        public static int GetCurrentDistance(Tile parentTile, Tile currentTile)
        {
            int deltaX = Math.Abs(parentTile.X - currentTile.X);
            int deltaY = Math.Abs(parentTile.Y - currentTile.Y);

            int value = 10;

            if(deltaX == 1 && deltaY == 0)
            {
                value = 10;
            }
            else if(deltaX == 0 && deltaY == 1)
            {
                value = 10;
            }
            else if(deltaX == 1 && deltaY == 1)
            {
                value = 14;
            }

            return parentTile.CurrentDistance + value;
        }

        #endregion

        ////////////////////////////////////////////////////////////////////////////////////////// Instance
        //////////////////////////////////////////////////////////////////////////////// Public

        #region 실행하기 - Execute(parentTile, destinationTile)

        /// <summary>
        /// 실행하기
        /// </summary>
        /// <param name="parentTile">부모 타일</param>
        /// <param name="destinationTile">도착지 타일</param>
        public void Execute(Tile parentTile, Tile destinationTile)
        {
            ParentTile = parentTile;

            CurrentDistance = GetCurrentDistance(parentTile, this);

            int deltaX = Math.Abs(destinationTile.X - X);
            int deltaY = Math.Abs(destinationTile.Y - Y);

            RemainDistance = (deltaX + deltaY) * 10;
        }

        #endregion
    }
}

 

728x90

 

▶ MainForm.cs

using System;
using System.Collections.Generic;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;

namespace TestProject
{
    /// <summary>
    /// 메인 폼
    /// </summary>
    public partial class MainForm : Form
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Enumeration
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region 업데이트 타입 - UpdateType

        /// <summary>
        /// 업데이트 타입
        /// </summary>
        private enum UpdateType
        {
            /// <summary>
            /// 해당 무
            /// </summary>
            None,
            
            /// <summary>
            /// 생성
            /// </summary>
            Create,
            
            /// <summary>
            /// 구축
            /// </summary>
            Build,
            
            /// <summary>
            /// 이동
            /// </summary>
            Move
        };

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region Field

        /// <summary>
        /// 배경 브러시
        /// </summary>
        private Brush backgroundBrush;

        /// <summary>
        /// 길 브러시
        /// </summary>
        private Brush roadBrush;

        /// <summary>
        /// 벽 브러시
        /// </summary>
        private Brush wallBrush;

        /// <summary>
        /// 경로 브러시
        /// </summary>
        private Brush pathBrush;

        /// <summary>
        /// 레이블 브러시
        /// </summary>
        private Brush labelBrush;

        /// <summary>
        /// 펜
        /// </summary>
        private Pen pen;

        /// <summary>
        /// 폰트
        /// </summary>
        private Font font;


        /// <summary>
        /// 맵 크기 X
        /// </summary>
        private int mapSizeX;

        /// <summary>
        /// 맵 크기 Y
        /// </summary>
        private int mapSizeY;


        /// <summary>
        /// 타일 리스트
        /// </summary>
        private List<Tile> tileList;

        /// <summary>
        /// 경로 타일 리스트
        /// </summary>
        private List<Tile> pathTileList;

        /// <summary>
        /// 개방 타일 리스트
        /// </summary>
        private List<Tile> openTileList;

        /// <summary>
        /// 폐쇄 타일 리스트
        /// </summary>
        private List<Tile> closeTileList;

        /// <summary>
        /// 업데이트 타입
        /// </summary>
        private UpdateType updateType;


        /// <summary>
        /// 맵 클리어 여부
        /// </summary>
        private bool isMapCleared;

        /// <summary>
        /// 시작 여부
        /// </summary>
        private bool isStarting;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - MainForm()

        /// <summary>
        /// 생성자
        /// </summary>
        public MainForm()
        {
            InitializeComponent();

            Load                             += Form_Load;
            this.xNumericUpDown.ValueChanged += xNumericUpDown_ValueChanged;
            this.yNumericUpDown.ValueChanged += yNumericUpDown_ValueChanged;
            this.clearMapButton.Click        += clearMapButton_Click;
            this.findPathButton.Click        += findPathButton_Click;
            this.mapPictureBox.MouseDown     += mapPictureBox_MouseDown;
            this.mapPictureBox.Paint         += mapPictureBox_Paint;
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Private
        //////////////////////////////////////////////////////////////////////////////// Event

        #region 폼 로드시 처리하기 - Form_Load(sender, e)

        /// <summary>
        /// 폼 로드시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void Form_Load(object sender, EventArgs e)
        {
            if(DesignMode)
            {
                return;
            }

            this.backgroundBrush = new SolidBrush(Color.Black);
            this.roadBrush       = new SolidBrush(Color.LightGray);
            this.wallBrush       = new SolidBrush(Color.Black);
            this.pathBrush       = new SolidBrush(Color.Blue);
            this.labelBrush      = new SolidBrush(Color.Yellow);
            this.pen             = new Pen(Color.Black);
            this.font            = new Font("나눔고딕코딩", 10);

            this.mapSizeX = (int)this.xNumericUpDown.Value;
            this.mapSizeY = (int)this.yNumericUpDown.Value;

            this.tileList      = new List<Tile>();
            this.pathTileList  = new List<Tile>();
            this.openTileList  = new List<Tile>();
            this.closeTileList = new List<Tile>();

            UpdateMap(UpdateType.None);
        }

        #endregion
        #region X 숫자 UP/DOWN 값 변경시 처리하기 - xNumericUpDown_ValueChanged(sender, e)

        /// <summary>
        /// X 숫자 UP/DOWN 값 변경시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void xNumericUpDown_ValueChanged(object sender, EventArgs e)
        {
            if(this.isStarting)
            {
                this.xNumericUpDown.Value = this.mapSizeX;
            }
            else
            {
                this.mapSizeX = (int)this.xNumericUpDown.Value;
            }
        }

        #endregion
        #region Y 숫자 UP/DOWN 값 변경시 처리하기 - yNumericUpDown_ValueChanged(sender, e)

        /// <summary>
        /// Y 숫자 UP/DOWN 값 변경시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void yNumericUpDown_ValueChanged(object sender, EventArgs e)
        {
            if(this.isStarting)
            {
                this.yNumericUpDown.Value = this.mapSizeY;
            }
            else
            {
                this.mapSizeY = (int)this.yNumericUpDown.Value;
            }
        }

        #endregion
        #region 맵 지우기 버튼 클릭시 처리하기 - clearMapButton_Click(sender, e)

        /// <summary>
        /// 맵 지우기 버튼 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void clearMapButton_Click(object sender, EventArgs e)
        {
            if(this.isStarting)
            {
                return;
            }

            this.isMapCleared = false;

            int width  = (this.mapPictureBox.Size.Width  - 10) / this.mapSizeX;
            int height = (this.mapPictureBox.Size.Height - 10) / this.mapSizeY;

            if(width < height)
            {
                height = width;
            }
            else if(height < width)
            {
                width = height;
            }

            this.tileList.Clear();

            for(int x = 0; x < this.mapSizeX; x++)
            {
                for(int y = 0; y < this.mapSizeY; y++)
                {
                    Tile tile = new Tile()
                    {
                        X = x,
                        Y = y,
                        BoundRectangle = new Rectangle
                        (
                            new Point(x * width, y * height),
                            new Size(width, height)
                        ),
                    };

                    this.tileList.Add(tile);
                }
            }

            UpdateMap(UpdateType.Create);
        }

        #endregion
        #region 경로 찾기 버튼 클릭시 처리하기 - findPathButton_Click(sender, e)

        /// <summary>
        /// 경로 찾기 버튼 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void findPathButton_Click(object sender, EventArgs e)
        {
            if(!this.isMapCleared)
            {
                return;
            }

            this.tileList.ForEach(t => t.Label = null);

            this.openTileList.Clear();
            this.closeTileList.Clear();
            this.pathTileList.Clear();

            Tile departureTile   = tileList[0];
            Tile destinationTile = tileList[tileList.Count - 1];

            this.openTileList.Add(departureTile);

            Tile currentTile = null;

            do
            {
                if(this.openTileList.Count == 0)
                {
                    break;
                }

                currentTile = this.openTileList.OrderBy(t => t.TotalDistance).First();

                this.openTileList.Remove(currentTile);
                this.closeTileList.Add(currentTile);

                if(currentTile == destinationTile)
                {
                    break;
                }

                foreach(Tile tile in tileList)
                {
                    if(tile.IsWall)
                    {
                        continue;
                    }

                    if(this.closeTileList.Contains(tile))
                    {
                        continue;
                    }

                    if(!IsNearTile(currentTile, tile))
                    {
                        continue;
                    }

                    if(!this.openTileList.Contains(tile))
                    {
                        this.openTileList.Add(tile);

                        tile.Execute(currentTile, destinationTile);
                    }
                    else
                    {
                        if(Tile.GetCurrentDistance(currentTile, tile) < tile.CurrentDistance)
                        {
                            tile.Execute(currentTile, destinationTile);
                        }
                    }
                }
            }
            while(currentTile != null);

            if(currentTile != destinationTile)
            {
                MessageBox.Show("길이 막혀 있습니다.");

                return;
            }

            do
            {
                this.pathTileList.Add(currentTile);

                currentTile = currentTile.ParentTile;
            }
            while(currentTile != null);

            this.pathTileList.Reverse();

            for(int i = 0; i < this.pathTileList.Count; i++)
            {
                if(i == 0)
                {
                    pathTileList[i].Label = "출발";
                }
                else if(i == pathTileList.Count - 1)
                {
                    pathTileList[i].Label = "도착";
                }
                else
                {
                    pathTileList[i].Label = i.ToString();
                }
            }

            this.isStarting = true;

            UpdateMap(UpdateType.Move);
        }

        #endregion
        #region 맵 픽처 박스 마우스 DOWN 처리하기 - mapPictureBox_MouseDown(sender, e)

        /// <summary>
        /// 맵 픽처 박스 마우스 DOWN 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void mapPictureBox_MouseDown(object sender, MouseEventArgs e)
        {
            if(!this.isMapCleared || this.isStarting)
            {
                return;
            }

            int mouseX = e.Location.X;
            int mouseY = e.Location.Y;

            foreach(Tile tile in tileList)
            {
                int minimumX = tile.BoundRectangle.X;
                int maximumX = tile.BoundRectangle.X + tile.BoundRectangle.Width;
                int minimumY = tile.BoundRectangle.Y;
                int maximumY = tile.BoundRectangle.Y + tile.BoundRectangle.Height;

                if(mouseX >= minimumX && mouseX <= maximumX && mouseY >= minimumY && mouseY <= maximumY)
                {
                    tile.IsWall = !tile.IsWall;

                    break;
                }
            }

            UpdateMap(UpdateType.Build);
        }

        #endregion
        #region 맵 픽처 박스 페인트시 처리하기 - mapPictureBox_Paint(sender, e)

        /// <summary>
        /// 맵 픽처 박스 페인트시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void mapPictureBox_Paint(object sender, PaintEventArgs e)
        {
            if(this.updateType == UpdateType.None)
            {
                return;
            }

            switch(this.updateType)
            {
                case UpdateType.Create :

                    foreach(Tile tile in this.tileList)
                    {
                        e.Graphics.FillRectangle(roadBrush, tile.BoundRectangle);

                        e.Graphics.DrawRectangle(pen, tile.BoundRectangle);
                    }

                    this.isMapCleared = true;

                    break;

                case UpdateType.Build :

                    foreach(Tile tile in this.tileList)
                    {
                        if(tile.IsWall)
                        {
                            e.Graphics.FillRectangle(wallBrush, tile.BoundRectangle);
                        }
                        else
                        {
                            e.Graphics.FillRectangle(roadBrush, tile.BoundRectangle);
                        }

                        e.Graphics.DrawRectangle(pen, tile.BoundRectangle);
                    }

                    break;

                case UpdateType.Move :

                    foreach(Tile tile in this.tileList)
                    {
                        if(tile.IsWall)
                        {
                            e.Graphics.FillRectangle(wallBrush, tile.BoundRectangle);
                        }
                        else
                        {
                            e.Graphics.FillRectangle(roadBrush, tile.BoundRectangle);
                        }

                        e.Graphics.DrawRectangle(pen, tile.BoundRectangle);

                        if(!string.IsNullOrWhiteSpace(tile.Label))
                        {
                            e.Graphics.DrawString(tile.Label, font, labelBrush, tile.BoundRectangle.X, tile.BoundRectangle.Y);
                        }
                    }

                    foreach(Tile tile in this.pathTileList)
                    {
                        e.Graphics.FillRectangle(pathBrush, tile.BoundRectangle);

                        e.Graphics.DrawRectangle(pen, tile.BoundRectangle);

                        if(!string.IsNullOrWhiteSpace(tile.Label))
                        {
                            e.Graphics.DrawString(tile.Label, font, labelBrush, tile.BoundRectangle.X, tile.BoundRectangle.Y);
                        }
                    }

                    this.isStarting = false;

                    break;
            }

            this.updateType = UpdateType.None;
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////// Function

        #region 맵 업데이트 하기 - UpdateMap(type)

        /// <summary>
        /// 맵 업데이트 하기
        /// </summary>
        /// <param name="type">업데이트 타입</param>
        private void UpdateMap(UpdateType type)
        {
            this.updateType = type;

            this.mapPictureBox.Invalidate();
        }

        #endregion
        #region 이웃 타일 여부 구하기 - IsNearTile(sourceTile, targetTile)

        /// <summary>
        /// 이웃 타일 여부 구하기
        /// </summary>
        /// <param name="sourceTile">소스 타일</param>
        /// <param name="targetTile">타겟 타일</param>
        /// <returns>이웃 타일 여부</returns>
        private bool IsNearTile(Tile sourceTile, Tile targetTile)
        {
            int deltaX = Math.Abs(sourceTile.X - targetTile.X);
            int deltaY = Math.Abs(sourceTile.Y - targetTile.Y);

            return deltaX <= 1 && deltaY <= 1;
        }

        #endregion
    }
}