4. 動態路線規劃系統

BFS

namespace Q4
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            Close();
        }

        enum State
        {
            S, E, O
        }

        State?[,] gay = new State?[11, 11];

        private void panel2_Paint(object sender, PaintEventArgs e)
        {
            e.Graphics.FillEllipse(Brushes.Black, 2, 0, 30, 30);
            e.Graphics.DrawString("路障點 O", new Font(FontFamily.GenericSansSerif, 14), Brushes.Black, 35, 5);

            e.Graphics.DrawEllipse(new Pen(Brushes.Blue, 2), 2, 40, 30, 30);
            e.Graphics.DrawString("起點 S", new Font(FontFamily.GenericSansSerif, 14), Brushes.Black, 35, 45);

            e.Graphics.DrawRectangle(new Pen(Brushes.Red, 2), 2, 80, 30, 30);
            e.Graphics.DrawString("終點 T", new Font(FontFamily.GenericSansSerif, 14), Brushes.Black, 35, 85);
        }

        private void panel1_Paint(object sender, PaintEventArgs e)
        {
            for (int i = 0; i < 11; i++)
            {
                e.Graphics.DrawLine(new Pen(Brushes.Black, 2), i * 44 + 15, 15, i * 44 + 15, 440 + 15);
                e.Graphics.DrawLine(new Pen(Brushes.Black, 2), 15, i * 44 + 15, 440 + 15, i * 44 + 15);
            }

            if (finalPath != null)
            {
                var last = finalPath[0];
                foreach (var item in finalPath[1..])
                {
                    e.Graphics.DrawLine(new Pen(Brushes.Blue, 3), last.X * 44 + 15, last.Y * 44 + 15, item.X * 44 + 15, item.Y * 44 + 15);
                    last = item;
                }
            }

            for (int x = 0; x < 11; x++)
                for (int y = 0; y < 11; y++)
                {
                    switch (gay[x, y])
                    {
                        case State.O:
                            e.Graphics.FillEllipse(Brushes.Black, x * 44, y * 44, 30, 30);
                            break;
                        case State.S:
                            e.Graphics.FillEllipse(Brushes.White, x * 44, y * 44, 30, 30);
                            e.Graphics.DrawEllipse(new Pen(Brushes.Blue, 2), x * 44, y * 44, 30, 30);
                            break;
                        case State.E:
                            e.Graphics.FillRectangle(Brushes.White, x * 44, y * 44, 30, 30);
                            e.Graphics.DrawRectangle(new Pen(Brushes.Red, 2), x * 44, y * 44, 30, 30);
                            break;
                    }
                }
        }

        List<Point>? finalPath = null;

        private void button1_Click(object sender, EventArgs e)
        {
            gay = new State?[11, 11];

            for (int i = 0; i < 32; i++) genPoint(State.O);
            genPoint(State.S);
            genPoint(State.E);

            findPath();
            panel1.Refresh();
        }


        void findPath()
        {
            system.Text = "規劃路線失敗";

            finalPath = null;

            Point? start = null;
            Point? end = null;

            for (int x = 0; x < 11; x++)
                for (int y = 0; y < 11; y++)
                {
                    if (gay[x, y] == State.S) start = new Point(x, y);
                    if (gay[x, y] == State.E) end = new Point(x, y);
                }

            if (start == null || end == null) return;

            HashSet<Point> visited = new();
            Queue<(Point, List<Point>)> task = new Queue<(Point, List<Point>)>();
            task.Enqueue((start.Value, new()));
            while (task.Count != 0)
            {
                var (curr, path) = task.Dequeue();
                if (visited.Contains(curr) ||
                    curr.X >= 11 || curr.Y >= 11 ||
                    curr.X <0 || curr.Y < 0 ||
                    gay[curr.X, curr.Y] == State.O)
                {
                    continue;
                }
                visited.Add(curr);
                path.Add(curr);

                if (gay[curr.X, curr.Y] == State.E)
                {
                    finalPath = path;
                    system.Text = "規劃路線成功";
                    return;
                }

                task.Enqueue((new Point(curr.X + 1, curr.Y), [.. path]));
                task.Enqueue((new Point(curr.X - 1, curr.Y), [.. path]));
                task.Enqueue((new Point(curr.X, curr.Y + 1), [.. path]));
                task.Enqueue((new Point(curr.X, curr.Y - 1), [.. path]));
            }
        }

        void genPoint(State s)
        {
            var rd = new Random();
            int x, y;
            do
            {
                x = rd.Next(11);
                y = rd.Next(11);
            } while (gay[x, y] != null);
            gay[x, y] = s;
        }

        State? last;
        private void panel1_MouseClick(object sender, MouseEventArgs e)
        {
            var x = (int)Math.Round((e.X - 15) / 44.0);
            var y = (int)Math.Round((e.Y - 15) / 44.0);
            if (x < 0 || y < 0 || x > 10 | y > 10) return;

            if (last == null && gay[x, y] != null)
            {
                system.Text = "";
                last = gay[x, y];
                gay[x, y] = null;
                finalPath = null;
                panel1.Refresh();
            } else
            if (last != null && gay[x, y] == null)
            {
                gay[x, y] = last;
                last = null;
                findPath();
                panel1.Refresh();
            }
        }
    }
}