■ 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

    }

}

 

 

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

    }

}

 

------------------------------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker

댓글을 달아 주세요