■ 미로 길 찾기 (애니메이션)
------------------------------------------------------------------------------------------------------------------------
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 } }
|
▶ 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 } }
|
▶ 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 } }
|
------------------------------------------------------------------------------------------------------------------------
'C# > WinForm' 카테고리의 다른 글
| [C#/WINFORM] Graphics 클래스 : FillEllipse 메소드를 사용해 포인트 그리기 (0) | 2020.08.07 |
|---|---|
| [C#/WINFORM] 벡터 각도 구하기 (0) | 2020.08.07 |
| [C#/WINFORM] 확대/축소된 이미지를 특정 크기로 자르기 (0) | 2020.08.07 |
| [C#/WINFORM] Graphics 클래스 : FillPolygon 메소드 사용하기 (0) | 2020.08.07 |
| [C#/WINFORM] 다른 선 아래로 지나가는 것을 보여주기 위해 간격이 있는 선 그리기 (0) | 2020.08.06 |
| [C#/WINFORM] 미로 길 찾기 (애니메이션) (0) | 2020.08.05 |
| [C#/WINFORM] 미로 길 찾기 (0) | 2020.08.05 |
| [C#/WINFORM] ImageAttributes 클래스 : 이미지 수정하기 (0) | 2020.08.04 |
| [C#/WINFORM] 라운드 다각형 그리기 (0) | 2020.08.03 |
| [C#/WINFORM] 기준선을 사용해 이미지 회전하기 (0) | 2020.08.03 |
| [C#/WINFORM] 마우스 아래 그려진 문자 찾기 (0) | 2020.08.03 |
댓글을 달아 주세요