using System;
using System.Collections.Generic;
using System.Drawing;
using mazes;
using System.Linq;

namespace Flies
{
    public class PathFinder
    {

        static Point[] p = new Point[] { new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0) };
        static Random r = new Random();

        private static IEnumerable<Point> GetNeighbours(Point from, IWorld world, Point[,] map)
        {
            //А если перемешивать всех соседей перед тем как вернуть, то поведение мух визуально будет естественнее.
            var listOfPoint = p.Select(z => new Point(z.X + from.X, z.Y + from.Y))
                .OrderBy(
                .Where(z => CanMove(z.X, z.Y, world, map))

                .ToArray();
            return listOfPoint;
        }

        static bool CanMove(int x, int y, IWorld world, Point[,] map)
        {
            return x >= 0 && y >= 0 && x < world.Size.Width && y < world.Size.Height && !world.Contains<Wall>(new Point(x, y)) && map[x,y] == new Point(0, 0) /*&& !world.Contains<Fly>(new Point(x, y))*/;
        }

        public static Point GetDirectionTo(Point source, Point target, IWorld world)
        {
            if (world.Contains<Wall>(new Point(target.X, target.Y)))
                return Point.Empty;
            var queue = new Queue<Point>();
            var map = new Point[world.Size.Width, world.Size.Height];
            map[source.X, source.Y] = new Point{ X = -1, Y = -1 };
            queue.Enqueue(new Point { X = source.X, Y = source.Y });
            while (queue.Count != 0)
            {
                var point = queue.Dequeue();
                if (point == target)
                {
                    break;
                }
                foreach (var e in GetNeighbours(point, world, map)
                    .ToArray())
                {
                    queue.Enqueue(e);
                    map[e.X, e.Y] = point;
                }
            }
            var currentPoint = new Point { X = target.X, Y = target.Y };
            while (true)
            {
                var Step = GetNeighbours(currentPoint, world, map).Where(z => map[currentPoint.X, currentPoint.Y] == z).ToArray();
                if (Step[0] == source)
                    break;
                currentPoint = Step[0];
            }
            return new Point(currentPoint.X - source.X, currentPoint.Y - source.Y);
            // Реализуйте поиск в ширину. Используйте функцию GetNeighbours для получения всех соседей, в которые можно перейти.
            // Функция должна возвращать направление — смещение относительно source, то есть вектор длины 1.
            //return Point.Empty;
        }
    }
}