Поиск пути в двумерном массиве. Реализация алгоритма волна.

#c_sharp #алгоритм

Задача состоит в том, что нужно найти путь в двумерном массиве (от точки А до точки Б).
Как это сделать на С#?    

Ответы

Ответ 1

Возможно не самая быстрая реализация, зато с описанием и картинками, тебе же сейчас
главное понять сам принцип работы, ведь так? Потому как для реальных проектов волновой
алгоритм в чистом виде - не самое лучшее решение.
Волновой алгоритм.


Ответ 2

Также советую почитать это: Поиск в ширину а также погуглить на эту тему.


Ответ 3

Реализовано с использованием ООП.
Описание алгоритма взято с wiki.



GitHub

Код:

using System;
using System.Linq;
using System.Collections.Generic;

namespace Finder
{
class Program
{
    static void Main(string[] args)
    {
        const int heigth = 10;
        const int width = 18;

        int[,] my = new int[heigth, width];
        for (int i = 0; i < heigth; i++)
        {
            for (int j = 0; j < width; j++)
            {
                var rand = new Random(unchecked((int)DateTime.Now.Millisecond));
                if (rand.Next(100) > 70)
                    my[i, j] = (int)Figures.Barrier;
                else
                    my[i, j] = (int)Figures.EmptySpace;
            }
        }
        var random = new Random(unchecked((int)DateTime.Now.Millisecond));
        my[random.Next(heigth), random.Next(width)] = (int)Figures.StartPosition;
        my[random.Next(heigth), random.Next(width)] = (int)Figures.Destination;
        Print(my);

        LeeAlgorithm li = new LeeAlgorithm(my);
        Console.WriteLine(li.PathFound);
        if (li.PathFound)
        {
            foreach (var item in li.Path)
            {
                if (item == li.Path.Last())
                    my[item.Item1, item.Item2] = (int)Figures.StartPosition;
                else if (item == li.Path.First())
                    my[item.Item1, item.Item2] = (int)Figures.Destination;
                else
                    my[item.Item1, item.Item2] = (int)Figures.Path;
            }
            Print(li.ArrayGraph);
            Console.WriteLine("Длина " + li.LengthPath);
        }
        else
            Console.WriteLine("Путь не найден");
        Console.ReadLine();

    }

    private static void Print(int[,] array)
    {
        Console.WriteLine("***");
        string msg = string.Empty;
        int x = array.GetLength(0);
        int y = array.GetLength(1);
        for (int i = 0; i < x; i++)
        {
            for (int j = 0; j < y; j++)
            {
                switch (array[i, j])
                {
                    case (int)Figures.Path: msg = string.Format("{0,3}", "+"); Console.ForegroundColor
= ConsoleColor.Yellow; break;
                    case (int)Figures.StartPosition: msg = string.Format("{0,3}",
"s"); Console.ForegroundColor = ConsoleColor.Green; break;
                    case (int)Figures.Destination: msg = string.Format("{0,3}", "d");
Console.ForegroundColor = ConsoleColor.Red; break;
                    case (int)Figures.EmptySpace: msg = string.Format("{0,3}", "'");
Console.ForegroundColor = ConsoleColor.DarkBlue; break;
                    case (int)Figures.Barrier: msg = string.Format("{0,3}", "*");
Console.ForegroundColor = ConsoleColor.Blue; break;
                    case 1:
                    case 2:
                    case 3:
                    case 4:
                    case 5:
                    case 6:
                    case 7:
                    case 8:
                    case 9:
                    case 10:
                    case 11:
                    case 12:
                    case 13:
                    case 14:
                    case 15:
                    case 16:
                    case 17:
                    case 18:
                    case 19:
                    case 20:
                        msg = string.Format("{0,3}", array[i, j]); Console.ForegroundColor
= ConsoleColor.DarkGray; break;
                    default:
                        break;
                }
                Console.Write(msg);
                Console.ResetColor();
            }
            Console.WriteLine();
        }
        Console.WriteLine(msg);
    }
}

public class LeeAlgorithm
{
    public int[,] ArrayGraph { get; private set; }

    /// 

    /// Начало пути с конца списка
    /// 
    public List> Path { get; private set; }
    public int Width { get; private set; }
    public int Heidth { get; private set; }
    public bool PathFound { get; private set; }
    public int LengthPath { get { return Path.Count; } }

    private int _step;
    private bool _finishingCellMarked;
    private int _finishPointI;
    private int _finishPointJ;

    /// 

    /// Инициализирует новый экземпляр объекта с полем и указанием начальной точки
    /// 
    public LeeAlgorithm(int startX, int startY, int[,] array)
    {
        ArrayGraph = array;
        Width = ArrayGraph.GetLength(0);
        Heidth = ArrayGraph.GetLength(1);
        SetStarCell(startX, startY);
        PathFound = PathSearch();
    }

    /// 

    /// Инициализирует новый экземпляр объекта с полем. Начальной точка установлена
в массиве
    /// 
    public LeeAlgorithm(int[,] array)
    {
        ArrayGraph = array;
        Width = ArrayGraph.GetLength(0);
        Heidth = ArrayGraph.GetLength(1);
        int startX;
        int startY;
        FindStartCell(out startX, out startY);
        SetStarCell(startX, startY);
        PathFound = PathSearch();

    }

    private void FindStartCell(out int startX, out int startY)
    {
        int w = Width;
        int h = Heidth;

        for (int i = 0; i < w; i++)
        {
            for (int j = 0; j < h; j++)
            {
                if (ArrayGraph[i, j] == (int)Figures.StartPosition)
                {
                    startX = i;
                    startY = j;
                    return;
                }
            }
        }
        throw new AggregateException("Нет начальной точки");
    }

    private void SetStarCell(int startX, int startY)
    {
        if (startX > this.ArrayGraph.GetLength(0) || startX < 0)
            throw new ArgumentException("Неправильная координата x");
        if (startY > this.ArrayGraph.GetLength(1) || startY < 0)
            throw new ArgumentException("Неправильная координата x");
        //Пометить стартовую ячейку d:= 0
        _step = 0;
        ArrayGraph[startX, startY] = _step;
    }

    private bool PathSearch()
    {
        if (WavePropagation())
            if (RestorePath())
                return true;

        return false;
    }

    // Есть. Ортогональный путь
    // Todo. Ортогонально-диагональный путь

    /// 

    /// Распространение волны
    /// 
    /// 
    private bool WavePropagation()
    {
        //ЦИКЛ
        //  ДЛЯ каждой ячейки loc, помеченной числом d
        //    пометить все соседние свободные непомеченные ячейки числом d + 1
        //  КЦ
        //  d := d + 1
        //ПОКА(финишная ячейка не помечена) И(есть возможность распространения волны)

        int w = Width;
        int h = Heidth;

        bool finished = false;
        do
        {
            for (int i = 0; i < w; i++)
            {
                for (int j = 0; j < h; j++)
                {
                    if (ArrayGraph[i, j] == _step)
                    {
                        // Пометить все соседние свободные непомеченные ячейки числом
d + 1
                        if (i != w - 1)
                            if (ArrayGraph[i + 1, j] == (int)Figures.EmptySpace)
ArrayGraph[i + 1, j] = _step + 1;
                        if (j != h - 1)
                            if (ArrayGraph[i, j + 1] == (int)Figures.EmptySpace)
ArrayGraph[i, j + 1] = _step + 1;
                        if (i != 0)
                            if (ArrayGraph[i - 1, j] == (int)Figures.EmptySpace)
ArrayGraph[i - 1, j] = _step + 1;
                        if (j != 0)
                            if (ArrayGraph[i, j - 1] == (int)Figures.EmptySpace)
ArrayGraph[i, j - 1] = _step + 1;

                        // Путь до финиша проложен
                        if (i < w - 1)
                            if (ArrayGraph[i + 1, j] == (int)Figures.Destination)
                            {
                                _finishPointI = i + 1;
                                _finishPointJ = j;
                                finished = true;
                            }
                        if (j < h - 1)
                            if (ArrayGraph[i, j + 1] == (int)Figures.Destination)
                            {
                                _finishPointI = i;
                                _finishPointJ = j + 1;
                                finished = true;
                            }
                        if (i > 0)
                            if (ArrayGraph[i - 1, j] == (int)Figures.Destination)
                            {
                                _finishPointI = i - 1;
                                _finishPointJ = j;
                                finished = true;
                            }
                        if (j > 0)
                            if (ArrayGraph[i, j - 1] == (int)Figures.Destination)
                            {
                                _finishPointI = i;
                                _finishPointJ = j - 1;
                                finished = true;
                            }
                    }

                }
            }
            _step++;
            //ПОКА(финишная ячейка не помечена) И(есть возможность распространения волны)
        } while (!finished && _step < w * h);
        _finishingCellMarked = finished;
        return finished;
    }

    /// 

    ///  Восстановление пути
    /// 
    /// 
    private bool RestorePath()
    {
        // ЕСЛИ финишная ячейка помечена
        // ТО
        //   перейти в финишную ячейку
        //   ЦИКЛ
        //     выбрать среди соседних ячейку, помеченную числом на 1 меньше числа
в текущей ячейке
        //     перейти в выбранную ячейку и добавить её к пути
        //   ПОКА текущая ячейка — не стартовая
        //   ВОЗВРАТ путь найден
        // ИНАЧЕ
        //   ВОЗВРАТ путь не найден
        if (!_finishingCellMarked)
            return false;

        int w = Width;
        int h = Heidth;
        int i = _finishPointI;
        int j = _finishPointJ;
        Path = new List>();
        AddToPath(i, j);

        do
        {
            if (i < w - 1)
                if (ArrayGraph[i + 1, j] == _step - 1)
                {
                    AddToPath(++i, j);
                }
            if (j < h - 1)
                if (ArrayGraph[i, j + 1] == _step - 1)
                {
                    AddToPath(i, ++j);
                }
            if (i > 0)
                if (ArrayGraph[i - 1, j] == _step - 1)
                {
                    AddToPath(--i, j);
                }
            if (j > 0)
                if (ArrayGraph[i, j - 1] == _step - 1)
                {
                    AddToPath(i, --j);
                }
            _step--;
        } while (_step != 0);
        return true;
    }

    private void AddToPath(int x, int y)
    {
        Path.Add(new Tuple(x, y));
    }
}
public enum Figures
{
    StartPosition = 0,
    EmptySpace = -1,
    Destination = -2,
    Path = -3,
    Barrier = -4
}


}