IT Blog
RSS icon Email icon
  • Битката за гьола – финален кръг

    Posted on June 29th, 2013 Krasi Nikolov No comments

    За начало може би е добре накратко да опиша, каква беше задачата за финалния кръг на конкурса. Даден е един гьол с радиус 100. В този гьол разполагаме две жаби с радиус 3.5, едната жаба я управляваме ние а другата се управлява от чужд алгоритъм. Играта протича на етапи, като на всеки етап размера на гьола намалява с единици. За всеки етап всяка жаба може да скача на разстояние 2. Освен това жабите могат да изстрелват куршуми, които се движат със скорост 10 единици за етап. След всеки изстрел, жабата трябва да презареди, т.е. жабата има право да стреля отново след 7 етапа. Всяка жаба която излезе от гьола или бъде уцелена от куршум умира. Пълните правила може да видите на сайта на конкурса – условие
    След като анализирахме условието на задачата стигнахме до следните изводи:
    1. Жабата може да избяга от куршум, ако разстоянието до него е по- голямо от 23.5.
    2. Във връзка с първото, ако двете жаби се приближават, нашата жаба трябва да спре да стреля на разстояние 53.5. Така ще може да сме презаредили и да стреляме на разстояние по- малко от 23.5
    Следващото нещо което ни направи впечатление, беше че жабата ни може да избяга единствено ако не е близо до ръба на гьола. Когато сме на ръба, може да се окаже, че за да избягаме, трябва да напуснем кръга. Това вече драстично усложняваше задачата на нашата жаба, така стигнахме до извода, че не е много добре да сме близо до ръба и всяка жаба близо до ръба ще бъде затруднена. Така стратегията на нашата жаба се състоеше от няколко много прости правила за нейното поведение:
    1. Жабата върви право към центъра, така стоим максимално далеч от ръба на гьола.
    2. Когато стигнем центъра оставаме там.
    3. Стреляме непрекъснато докато сме на разстояние по- голямо от 56.
    4. Ако разстоянието падне под 56, спираме да стреляме за да може да презаредим до 23.5
    5. Когато разстоянието до противника падне под 23.5 стреляме. Той вече не може да бяга.
    6. Ако забележим противников куршум на разстояние под 33.5 избягваме изстрела, в посока перпендикулярна на треакторията на изстрела. След това продължаваме по посока на центъра.
    Нека да покажа най- важните елементи от нашия код.

            static void Main(string[] args)
            {
                Dangerous = new List<Point>();
                ReadInput();
                if (Dangerous.Count > 0)
                {
                    Point escapePoint = FindEscapeDirection();
                    Console.WriteLine("move " + escapePoint.X + " " + escapePoint.Y);
                }
                else
                {
                    Console.WriteLine("move 0 0");
                }
                double distanceToEnemy = FindDistance(MyFrog.Position, EnemyFrog.Position);
                if ((distanceToEnemy > 56 || distanceToEnemy < 23.5) && MyFrog.CanShootAfter == 0)
                {
                    Console.WriteLine("shoot " + EnemyFrog.Position.X + " " + EnemyFrog.Position.Y);
                }
                else
                {
                    Console.WriteLine();
                }
            }
    

    Това е основната логика по която работи нашия алгоритъм. Нещото което не се вижда тук е, че Dangerous е списък от точките по които биха преминали опасните противникови куршуми. Опасни са куршуми които са на разстояние по малко от 33.5.

                BulletsCount = int.Parse(Console.ReadLine());
                if (BulletsCount > 0)
                {
                    Bullets = new Bullet[BulletsCount];
                    for (int i = 0; i < BulletsCount; i++)
                    {
                        string[] line = Console.ReadLine().Split(' ');
                        Bullets[i] = new Bullet()
                        {
                            From = new Point() { X = double.Parse(line[0]), Y = double.Parse(line[1]) },
                            To = new Point() { X = double.Parse(line[2]), Y = double.Parse(line[3]) }
                        };
                        FindDangerousPoints(Bullets[i]);
                    }
                }
    

    Тук четем куршумите на полето и ги изпращаме във FindDangerousPoints(Bullets[i]); където проверяваме дали има опасни.
    Това е самата проверка за опасни куршуми.

            private static void FindDangerousPoints(Bullet bullet)
            {
                double deltaX = (bullet.To.X - bullet.From.X) / 10;
                double deltaY = (bullet.To.Y - bullet.From.Y) / 10;
                double oldDistance = FindDistance(bullet.From, MyFrog.Position);
                Point point = new Point() { X = bullet.From.X + deltaX, Y = bullet.From.Y + deltaY };
                double currentDistance = FindDistance(point, MyFrog.Position);
                if (oldDistance > currentDistance && currentDistance < 30)
                {
                    bool dangerousAdded = false;
                    while (oldDistance > currentDistance)
                    {
                        var oldPoint = new Point() { X = point.X, Y = point.Y };
                        if (currentDistance < 4.5)
                        {
                            Dangerous.Add(oldPoint);
                            dangerousAdded = true;
                        }
                        oldDistance = currentDistance;
                        point.X += deltaX;
                        point.Y += deltaY;
                        currentDistance = FindDistance(point, MyFrog.Position);
                    }
                    if (dangerousAdded)
                    {
                        Dangerous.Add(point);
                    }              
                }
            }
    

    Двете условия за опасни куршуми са:
    1. oldDistance > currentDistance – проверяваме да ли куршума се приближава.
    2. currentDistance < 30 - проверяваме дали е в опасна близост В общи линии до тук нещата са тривиални, но нещото с което наистина се гордея е начина по които пресмятам посоката за бягство на жабата. За да го сметна вземам две последователни ударни точки на куршум и спрямо тях изчислявам посока за перпендикулярно бягство. [sourcecode language="csharp"] private static Point FindEscapeDirection() { Point escapePoint = new Point(); if (Dangerous.Count == 1) { double deltaX = MyFrog.Position.X - Dangerous[0].X; double deltaY = MyFrog.Position.Y - Dangerous[0].Y; escapePoint.X = MyFrog.Position.X + deltaX; escapePoint.Y = MyFrog.Position.Y + deltaY; } else { double deltaX = Dangerous[0].Y - Dangerous[1].Y; double deltaY = Dangerous[0].X - Dangerous[1].X; escapePoint.X = MyFrog.Position.X - 2*deltaX; escapePoint.Y = MyFrog.Position.Y + 2*deltaY; } return escapePoint; } [/sourcecode] Това е цялата логика по- която работи нашия алгоритъм. Написахме го за не повече то 5-6 часа и смятахме, че ще имаме достатъчно време за приложната част. По голяма част от времето на финалния кръг отделихме за приложната част, която за съжаление не успяхме да завършим. Приложната ни част представлява, MVC 4 приложение, което при всеки ход подава входа към два алгоритъма. Взема техния отговор, обработва го и го подава към UI. Със съвсем леки модификации нашето приложение, може да работи като игра между човек и алгоритъм. За съжаление, отделихме прекалено много време за бек-енда и накрая просто не успяхме да зъвършим фронт-енда. Тук може да намерите целият код, на нашия алгоритъм и приложение. - код
    Тук може да видите резултатите от нашето участие. – резултати

    Leave a reply