728x90
반응형
728x170
▶ 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
}
}
728x90
반응형
그리드형(광고전용)
'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] ImageAttributes 클래스 : 이미지 수정하기 (0) | 2020.08.04 |
[C#/WINFORM] 라운드 다각형 그리기 (0) | 2020.08.03 |
[C#/WINFORM] 기준선을 사용해 이미지 회전하기 (0) | 2020.08.03 |
[C#/WINFORM] 마우스 아래 그려진 문자 찾기 (0) | 2020.08.03 |
댓글을 달아 주세요