[C#/WINFORM] 미로 길 찾기 (애니메이션)

TestProject.zip

다운로드

▶ MazeNode.cs

using System.Collections.Generic;
using System.Drawing;

namespace TestProject
{
    /// <summary>
    /// 미로 노드
    /// </summary>
    public class MazeNode
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region Field

        /// <summary>
        /// 북쪽
        /// </summary>
        public const int North = 0;

        /// <summary>
        /// 남쪽
        /// </summary>
        public const int South = North + 1;

        /// <summary>
        /// 동쪽
        /// </summary>
        public const int East = South + 1;

        /// <summary>
        /// 서쪽
        /// </summary>
        public const int West = East + 1;

        /// <summary>
        /// 인접 노드 배열
        /// </summary>
        public MazeNode[] AdjacentNodeArray = new MazeNode[4];

        /// <summary>
        /// 전임 노드
        /// </summary>
        public MazeNode Predecessor = null;

        /// <summary>
        /// 경계 사각형
        /// </summary>
        public RectangleF BoundRectangle;

        /// <summary>
        /// 경로 내 여부
        /// </summary>
        public bool InPath = false;

        /// <summary>
        /// 이웃 리스트
        /// </summary>
        public List<MazeNode> NeighborList = null;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 중심 포인트 - CenterPoint

        /// <summary>
        /// 중심 포인트
        /// </summary>
        public PointF CenterPoint
        {
            get
            {
                float x = BoundRectangle.Left + BoundRectangle.Width  / 2f;
                float y = BoundRectangle.Top  + BoundRectangle.Height / 2f;

                return new PointF(x, y);
            }
        }

        #endregion

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

        #region 생성자 - MazeNode(x, y, width, height)

        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="x">X</param>
        /// <param name="y">Y</param>
        /// <param name="width">너비</param>
        /// <param name="height">높이</param>
        public MazeNode(float x, float y, float width, float height)
        {
            BoundRectangle = new RectangleF(x, y, width, height);
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 이웃 정의하기 - DefineNeighbor()

        /// <summary>
        /// 이웃 정의하기
        /// </summary>
        public void DefineNeighbor()
        {
            NeighborList = new List<MazeNode>();

            foreach(MazeNode node in AdjacentNodeArray)
            {
                if((node != null) && ((node.Predecessor == this) || (node == this.Predecessor)))
                {
                    NeighborList.Add(node);
                }
            }
        }

        #endregion
        #region 경계 사각형 그리기 - DrawBoundRectangle(graphics, pen)

        /// <summary>
        /// 경계 사각형 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        public void DrawBoundRectangle(Graphics graphics, Pen pen)
        {
            graphics.DrawRectangle
            (
                pen,
                BoundRectangle.Left   + 1,
                BoundRectangle.Y      + 1,
                BoundRectangle.Width  - 2,
                BoundRectangle.Height - 2
            );
        }

        #endregion
        #region 중심 포인트 그리기 - DrawCenterPoint(graphics, brush, radius)

        /// <summary>
        /// 중심 포인트 그리기
        /// </summary>
        /// <param name="graphics"></param>
        /// <param name="brush"></param>
        /// <param name="radius"></param>
        public void DrawCenterPoint(Graphics graphics, Brush brush, float radius)
        {
            float centerX = BoundRectangle.Left + BoundRectangle.Width  / 2;
            float centerY = BoundRectangle.Top  + BoundRectangle.Height / 2;

            graphics.FillEllipse(brush, centerX - radius, centerY - radius, 2 * radius, 2 * radius);
        }

        #endregion
        #region 중심 포인트 그리기 - DrawCenterPoint(graphics, brush)

        /// <summary>
        /// 중심 포인트 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="brush">브러시</param>
        public void DrawCenterPoint(Graphics graphics, Brush brush)
        {
            DrawCenterPoint(graphics, brush, 4);
        }

        #endregion
        #region 전임 링크 그리기 - DrawPredecessorLink(graphics, pen)

        /// <summary>
        /// 전임 링크 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        public void DrawPredecessorLink(Graphics graphics, Pen pen)
        {
            if((Predecessor != null) && (Predecessor != this))
            {
                graphics.DrawLine(pen, CenterPoint, Predecessor.CenterPoint);
            }
        }

        #endregion
        #region 이웃 링크 그리기 - DrawNeighborLink(graphics, pen)

        /// <summary>
        /// 이웃 링크 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        public void DrawNeighborLink(Graphics graphics, Pen pen)
        {
            foreach(MazeNode neighbor in AdjacentNodeArray)
            {
                if(neighbor != null)
                {
                    int deltaX = (int)(0.4 * (neighbor.CenterPoint.X - CenterPoint.X));
                    int deltaY = (int)(0.4 * (neighbor.CenterPoint.Y - CenterPoint.Y));

                    PointF point = new PointF(CenterPoint.X + deltaX, CenterPoint.Y + deltaY);

                    graphics.DrawLine(pen, CenterPoint, point);
                }
            }
        }

        #endregion
        #region 벽 그리기 - DrawWall(graphics, pen)

        /// <summary>
        /// 벽 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        public void DrawWall(Graphics graphics, Pen pen)
        {
            for(int side = 0; side < 4; side++)
            {
                if
                (
                    (AdjacentNodeArray[side] == null) ||
                    ((AdjacentNodeArray[side].Predecessor != this) && (AdjacentNodeArray[side] != this.Predecessor))
                )
                {
                    DrawWall(graphics, pen, side, 0);
                }
            }
        }

        #endregion

        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region 벽 그리기 - DrawWall(graphics, pen, side, offset)

        /// <summary>
        /// 벽 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        /// <param name="side">면</param>
        /// <param name="offset">오프셋</param>
        private void DrawWall(Graphics graphics, Pen pen, int side, int offset)
        {
            switch(side)
            {
                case North :

                    graphics.DrawLine
                    (
                        pen,
                        BoundRectangle.Left  + offset,
                        BoundRectangle.Top   + offset,
                        BoundRectangle.Right - offset,
                        BoundRectangle.Top   + offset
                    );

                    break;

                case South :

                    graphics.DrawLine
                    (
                        pen,
                        BoundRectangle.Left   + offset,
                        BoundRectangle.Bottom - offset,
                        BoundRectangle.Right  - offset,
                        BoundRectangle.Bottom - offset
                    );

                    break;

                case East :

                    graphics.DrawLine
                    (
                        pen,
                        BoundRectangle.Right  - offset,
                        BoundRectangle.Top    + offset,
                        BoundRectangle.Right  - offset,
                        BoundRectangle.Bottom - offset
                    );

                    break;

                case West :

                    graphics.DrawLine
                    (
                        pen,
                        BoundRectangle.Left   + offset,
                        BoundRectangle.Top    + offset,
                        BoundRectangle.Left   + offset,
                        BoundRectangle.Bottom - offset
                    );

                    break;
            }
        }

        #endregion
    }
}

 

728x90

 

▶ MazeLink.cs

namespace TestProject
{
    /// <summary>
    /// 미로 연결
    /// </summary>
    public class MazeLink
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region Field

        /// <summary>
        /// FROM 노드
        /// </summary>
        public MazeNode FromNode;
        
        /// <summary>
        /// TO 노드
        /// </summary>
        public MazeNode ToNode;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - MazeLink(fromNode, toNode)

        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="fromNode">FROM 노드</param>
        /// <param name="toNode">TO 노드</param>
        public MazeLink(MazeNode fromNode, MazeNode toNode)
        {
            FromNode = fromNode;
            ToNode   = toNode;
        }

        #endregion
    }
}

 

300x250

 

▶ MainForm.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Windows.Forms;

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

        #region Field

        /// <summary>
        /// 최소 X
        /// </summary>
        private int minimumX;
        
        /// <summary>
        /// 최소 Y
        /// </summary>
        private int minimumY;
        
        /// <summary>
        /// 셀 너비
        /// </summary>
        private int cellWidth;
        
        /// <summary>
        /// 셀 높이
        /// </summary>
        private int cellHeight;
        
        /// <summary>
        /// 행 카운트
        /// </summary>
        private int rowCount;
        
        /// <summary>
        /// 컬럼 카운트
        /// </summary>
        private int columnCount;

        /// <summary>
        /// 노드 배열
        /// </summary>
        private MazeNode[,] nodeArray = null;

        /// <summary>
        /// 시작 노드
        /// </summary>
        private MazeNode startNode = null;
        
        /// <summary>
        /// 종료 노드
        /// </summary>
        private MazeNode endNode = null;

        /// <summary>
        /// 경로 노드 리스트
        /// </summary>
        private List<MazeNode> pathNodeList = null;

        /// <summary>
        /// 마지막 사용 이웃 리스트
        /// </summary>
        private List<int> lastUsedNeighborList = null;

        /// <summary>
        /// 솔루션 발견 여부
        /// </summary>
        private bool solutionFound = false;

        #endregion

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

        #region 생성자 - MainForm()

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

            this.createButton.Click    += createButton_Click;
            this.pictureBox.MouseClick += pictureBox_MouseClick;
            this.pictureBox.Paint      += pictureBox_Paint;
            this.timer.Tick            += timer_Tick;
        }

        #endregion

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

        #region 생성하기 버튼 클릭시 처리하기 - createButton_Click(sender, e)

        /// <summary>
        /// 생성하기 버튼 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void createButton_Click(object sender, EventArgs e)
        {
            this.timer.Enabled = false;

            this.columnCount = int.Parse(this.widthTextBox.Text);
            this.rowCount    = int.Parse(this.heightTextBox.Text);

            this.cellWidth  = this.pictureBox.ClientSize.Width  / (this.columnCount + 2);
            this.cellHeight = this.pictureBox.ClientSize.Height / (this.rowCount    + 2);

            if(this.cellWidth > this.cellHeight)
            {
                this.cellWidth = this.cellHeight;
            }
            else
            {
                this.cellHeight = this.cellWidth;
            }

            this.minimumX = (this.pictureBox.ClientSize.Width  - this.columnCount * this.cellWidth ) / 2;
            this.minimumY = (this.pictureBox.ClientSize.Height - this.rowCount    * this.cellHeight) / 2;

            this.nodeArray = GetNodeArray(this.columnCount, this.rowCount);

            this.pathNodeList         = null;
            this.lastUsedNeighborList = null;
            this.startNode            = null;
            this.endNode              = null;

            FindSpanningTree(this.nodeArray[0, 0]);

            DisplayMaze(this.nodeArray);
        }

        #endregion
        #region 픽처 박스 마우스 클릭시 처리하기 - pictureBox_MouseClick(sender, e)

        /// <summary>
        /// 픽처 박스 마우스 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void pictureBox_MouseClick(object sender, MouseEventArgs e)
        {
            this.timer.Enabled = false;

            if(this.nodeArray == null)
            {
                return;
            }

            if(e.Button == MouseButtons.Left)
            {
                this.startNode = FindNode(e.Location);
            }
            else if(e.Button == MouseButtons.Right)
            {
                this.endNode = FindNode(e.Location);
            }

            if((this.startNode != null) && (this.endNode != null))
            {
                StartSolving();
            }

            this.pictureBox.Refresh();
        }

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

        /// <summary>
        /// 픽처 박스 페인트시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void pictureBox_Paint(object sender, PaintEventArgs e)
        {
            e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

            if(this.startNode != null)
            {
                this.startNode.DrawCenterPoint(e.Graphics, Brushes.Red);
            }

            if(this.endNode != null)
            {
                this.endNode.DrawCenterPoint(e.Graphics, Brushes.Green);
            }

            if((this.pathNodeList != null) && (this.pathNodeList.Count > 1))
            {
                List<PointF> pointList = new List<PointF>();

                foreach(MazeNode node in this.pathNodeList)
                {
                    pointList.Add(node.CenterPoint);
                }

                if(this.solutionFound)
                {
                    e.Graphics.DrawLines(Pens.Red, pointList.ToArray());
                }
                else
                {
                    e.Graphics.DrawLines(Pens.Blue, pointList.ToArray());
                }
            }
        }

        #endregion
        #region FPS 스크롤바 스크롤시 처리하기 - fpsScrollBar_Scroll(sender, e)

        /// <summary>
        /// FPS 스크롤바 스크롤시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void fpsScrollBar_Scroll(object sender, ScrollEventArgs e)
        {
            int fps = this.fpsScrollBar.Value;

            this.fpsLabel.Text = fps.ToString();

            this.timer.Interval = 1000 / fps;
        }

        #endregion
        #region 타이머 틱 처리하기 - timer_Tick(sender, e)

        /// <summary>
        /// 타이머 틱 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void timer_Tick(object sender, EventArgs e)
        {
            Solve();
 
            this.pictureBox.Refresh();
        }

        #endregion

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

        #region 노드 배열 구하기 - GetNodeArray(width, height)

        /// <summary>
        /// 노드 배열 구하기
        /// </summary>
        /// <param name="width">너비</param>
        /// <param name="height">높이</param>
        /// <returns>노드 배열</returns>
        private MazeNode[,] GetNodeArray(int width, int height)
        {
            MazeNode[,] nodeArray = new MazeNode[height, width];

            for(int row = 0; row < height; row++)
            {
                int y = this.minimumY + this.cellHeight * row;

                for(int column = 0; column < width; column++)
                {
                    int x = this.minimumX + this.cellWidth * column;

                    nodeArray[row, column] = new MazeNode(x, y, this.cellWidth, this.cellHeight);
                }
            }

            for(int row = 0; row < height; row++)
            {
                for(int column = 0; column < width; column++)
                {
                    if(row > 0)
                    {
                        nodeArray[row, column].AdjacentNodeArray[MazeNode.North] = nodeArray[row - 1, column];
                    }

                    if(row < height - 1)
                    {
                        nodeArray[row, column].AdjacentNodeArray[MazeNode.South] = nodeArray[row + 1, column];
                    }

                    if(column > 0)
                    {
                        nodeArray[row, column].AdjacentNodeArray[MazeNode.West] = nodeArray[row, column - 1];
                    }

                    if(column < width - 1)
                    {
                        nodeArray[row, column].AdjacentNodeArray[MazeNode.East] = nodeArray[row, column + 1];
                    }
                }
            }

            return nodeArray;
        }

        #endregion
        #region 신장 트리 찾기 - FindSpanningTree(rootNode)

        /// <summary>
        /// 신장 트리 찾기
        /// </summary>
        /// <param name="rootNode">루트 노드</param>
        private void FindSpanningTree(MazeNode rootNode)
        {
            Random random = new Random();

            rootNode.Predecessor = rootNode;

            List<MazeLink> linkList = new List<MazeLink>();

            foreach(MazeNode neighborNode in rootNode.AdjacentNodeArray)
            {
                if(neighborNode != null)
                {
                    linkList.Add(new MazeLink(rootNode, neighborNode));
                }
            }

            while(linkList.Count > 0)
            {
                int linkCount = random.Next(0, linkList.Count);

                MazeLink link = linkList[linkCount];

                linkList.RemoveAt(linkCount);

                MazeNode toNode = link.ToNode;

                link.ToNode.Predecessor = link.FromNode;

                for(int i = linkList.Count - 1; i >= 0; i--)
                {
                    if(linkList[i].ToNode.Predecessor != null)
                    {
                        linkList.RemoveAt(i);
                    }
                }

                foreach(MazeNode neighborNode in toNode.AdjacentNodeArray)
                {
                    if((neighborNode != null) && (neighborNode.Predecessor == null))
                    {
                        linkList.Add(new MazeLink(toNode, neighborNode));
                    }
                }
            }
        }

        #endregion
        #region 미로 표시하기 - DisplayMaze(nodeArray)

        /// <summary>
        /// 미로 표시하기
        /// </summary>
        /// <param name="nodeArray">노드 배열</param>
        private void DisplayMaze(MazeNode[,] nodeArray)
        {
            int width  = nodeArray.GetUpperBound(1) + 1;
            int height = nodeArray.GetUpperBound(0) + 1;

            Bitmap bitmap = new Bitmap
            (
                this.pictureBox.ClientSize.Width,
                this.pictureBox.ClientSize.Height
            );

            using(Graphics graphics = Graphics.FromImage(bitmap))
            {
                graphics.SmoothingMode = SmoothingMode.AntiAlias;

                for(int y = 0; y < height; y++)
                {
                    for(int x = 0; x < width; x++)
                    {
                        nodeArray[y, x].DrawWall(graphics, Pens.Black);
                    }
                }
            }

            this.pictureBox.Image = bitmap;
        }

        #endregion
        #region 노드 찾기 - FindNode(point)

        /// <summary>
        /// 노드 찾기
        /// </summary>
        /// <param name="point">포인트</param>
        /// <returns>노드</returns>
        private MazeNode FindNode(Point point)
        {
            if(point.X < this.minimumX)
            {
                return null;
            }

            if(point.Y < this.minimumY)
            {
                return null;
            }

            int row = (point.Y - this.minimumY) / this.cellHeight;

            if(row >= this.rowCount)
            {
                return null;
            }

            int column = (point.X - this.minimumX) / this.cellWidth;

            if(column >= this.columnCount)
            {
                return null;
            }

            return this.nodeArray[row, column];
        }

        #endregion
        #region 해결 시작하기 - StartSolving()

        /// <summary>
        /// 해결 시작하기
        /// </summary>
        private void StartSolving()
        {
            this.pathNodeList = new List<MazeNode>();

            this.lastUsedNeighborList = new List<int>();

            foreach(MazeNode node in this.nodeArray)
            {
                node.InPath = false;
            }

            foreach(MazeNode node in this.nodeArray)
            {
                node.DefineNeighbor();
            }

            this.pathNodeList.Add(this.startNode);

            this.lastUsedNeighborList.Add(-1);

            this.startNode.InPath = true;

            this.solutionFound = false;

            this.timer.Enabled = true;
        }

        #endregion
        #region 해결하기 - Solve()

        /// <summary>
        /// 해결하기
        /// </summary>
        private void Solve()
        {
            int lastNodeIndex = this.pathNodeList.Count - 1;

            MazeNode lastNode = this.pathNodeList[lastNodeIndex];

            if(lastNode == this.endNode)
            {
                this.solutionFound = true;

                this.timer.Enabled = false;

                return;
            }

            bool neighborFound = false;

            int neighborIndex = this.lastUsedNeighborList[lastNodeIndex];

            MazeNode neighborNode = null;

            for(;;)
            {
                neighborIndex++;

                if(neighborIndex >= lastNode.NeighborList.Count)
                {
                    break;
                }

                neighborNode = lastNode.NeighborList[neighborIndex];

                if(!neighborNode.InPath)
                {
                    neighborFound = true;

                    this.lastUsedNeighborList[lastNodeIndex] = neighborIndex;

                    break;
                }
            }

            if(neighborFound)
            {
                this.pathNodeList.Add(neighborNode);

                this.lastUsedNeighborList.Add(-1);

                neighborNode.InPath = true;
            }
            else
            {
                lastNode.InPath = false;

                this.pathNodeList.RemoveAt(lastNodeIndex);

                this.lastUsedNeighborList.RemoveAt(lastNodeIndex);
            }
        }

        #endregion
    }
}