Може би вече сте запознати с първата задача от съвместното състезание на Телерик и PC Magazine. Може би дори сте взели участие, измисляйки някое хитроумно решение или още по – добре някои красив дизайн към него.

За тези, които още не са запознати с условието на задачата – можете да го намерите наофициалния сайт на конкурса. Пак там можете да разберете, че изискването е изготвяне на алгоритмична и приложна част.

Тук искам да обърна внимание на едно интересно решение от екипа на KeyDown ™ . Приложната част на решението може да се намери на

http://keydown.org

А сега и малко по – подробни разяснения по условията, алгоритъма и приложната част [ще бъдат използвани пасажи от официалната документация на примерното решение].

Условие

Играта се играе в квадратно поле, съставено от N*N квадратни плочки (всяка страна има по N плочки), като на всяка плочка има кули от каменни кубчета, наредени едно върху друго. В играта се въвеждат концепцията на “съседни плочки“, “съседни кули” и “височина на кула“. Височина на кула наричаме броя кубчета, от които се състои една кула върху дадена плочка. Две плочки са съседни, ако имат обща страна, т.е. една плочка може да има най-много 4 съседни плочки (ако е в някой от ъглите има 2, а ако е на някоя от страните, без да е в ъгъл, има 3). Съседни кули съответно ще наричаме всички кули, които са върху съседни плочки.
В началото на играта няма кули, с еднакви височини, които да са съседи. Играчът получава право на точно C на брой хода, като може на всеки ход да прави точно една от следните две операции:
• Да добавя едно кубче върху някоя кула (т. е. увеличаване на височината на една кула);
• Да взема едно кубче от някоя кула (т. е. намаляване на височината на една кула);
За един ход, играчът може да вземе или добави точно едно кубче от някоя от кулите. Съответно сумарно броят кубчета, които играчът може да вземе или добави за цялата игра съответства на броя ходове, на които има право.
В играта има едно интересно правило – ако на някой ход от играта две или повече съседни кули са с еднаква височина, всичките кубчета в тези кули се премахват от полето автоматично, без това допълнително да отнема ход на играча.
На края на играта играчът печели точки, равни на броя премахнати кубчета от полето (т.е. броя първоначални кубчета минус останалите на полето кубчета). Съответно целта на играча е в рамките на позволения брой ходове да играе така, че на игралното поле да останат възможно най-малко кубчета.

Ограничения

• Числата C и N са цели и са в сила ограниченията 1 ? C, N ? 1000;
• В началото никоя кула няма да има височина по-голяма от 1000;
• Програмата трябва да завършва своята работа за най-много 3 секунди. След третата секунда програмата ще бъде спряна автоматично;
• Ако на една плочка не са останали кубчета, ако програмата се опита да вземе кубче от тази плочка, този ход ще се счита за “пропилян”, тоест нищо няма да се случи, но играчът няма да бъде наказан;
• Възможно е крайният резултат да е отрицателен (например ако само добавяме кубчета, без да вземаме и без да се случват изравнявания на височини);
• При невалиден ход (например невалидна команда координати извън игралното поле) играчът може да получи наказание по преценка на журито;

Описание на алгоритъма

Събаряне на максимален брой съседни кули – MaxTowersPerTurnAlgo

Алгоритъмът за събаряне на максимален брой съседни кули е реализиран в класа MaxTowersPerTurnAlgo. Това е първият алгоритъм, за който се досетихме и реализирахме, а целта му е да работи върху 5 съседни кули едновременно докато събори и 5-те, преди да продължи нататък.В алгоритъма се въвежда концепцията за „централна кула“, „група от съседни кули“, „базова височина“, „оценка на група от съседни кули“. Централна кула наричаме кула, която е в центъра на една група от съседни кули. Група от съседни кули може да съдържа 3, 4 или 5 кули в зависимост дали се намира в ъгъл, до стена или в някъде в средата на полето. Базова височина е височината, до която ще приравним всички кули от групата от съседни кули, с цел да ги съборим едновременно. Понякога е невъзможно да съборим всички 5 кули (4 или 3 при стена и ъгъл) и това обикновено се получава когато съседна кула трябва да мине през височината на централната кула, за да достигне базовата. В този случай съседната и централната кула ще бъдат съборени преди останалите кули от групата да достигнат базовата височина. Единствените случаи, когато е възможно да се съборят всички кули в дадена група от съседни кули е когато централната кула е най-голямата или най-малката кула в групата и централната кула да бъде обработена последна от всички кули в групата. За да започне събарянето на групите от съседни кули, алгоритъмът трябва да избере начална група, от която да стартира обработката. За тази цел въвеждаме оценки на групите от съседни кули. Алгоритъмът се ориентира по тези оценки като извлича максималната оценка и работи по съответната група от съседни кули, стига да са налични достатъчно ходове, за да бъдат съборени кулите.

Базова височина – GetBase()

Намираме базовата височина за всяка група от съседни кули като вземем височините на кулите (само тези, които са по-високи от 0), сортираме ги във възходящ ред и извличаме медианата, т.е. числовата стойност от височините на кулите, която се намира в средата на сортиранияред(n+1)при нечетен брой кули (2n+1). В случай че броят на кулите в групата е четен (2n), извличаме височината в позиция n+1. След като извлечем базовата височина вече можем да пресметнем броя необходими ходове за събарянето на съседните кули от групата. Този брой, обаче, не е коректен в абсолютно всички случаи. В случай че при привеждане на височината на дадена кула към базовата височина за групата, кулата се изравни със съседна кула от друга група, се оказва, че нужните ходове за събаряне на кулите в групата драстично намаляват. За този специален случай се грижи GetProblematicSurroundingTowersDifference(). А ходовете, които спестяваме намираме чрез GetMaxTurnsSaved().
В случай, че базовата височина е равна на височината на централната кула извличаме следващата по-голяма височина от реда, тъй като не можем да приравняваме кули към височината на централната кула. Ако височината на централната кула е единствената по-голяма от 0 в групата от съседни кули, то взимаме за базова височина 0.

Оценка на група от съседни кули – UpdateRelatedTowersScore()

Оценката на групата представлява брой съборени кубчета за един изигран ход. Например, ако за да се съборят всички кули от една група са необходими пет хода, а сумата от височините на тези кули е равна на 50, то оценката е 50/5 = 10 съборени кубчета на ход. В случаите когато нямаме достатъчно налични ходове, за да съборим всички кули от групата или когато всички кули от групата са вече съборени записваме отрицателна оценка за съответната група.
При събарянето на група от кули намираме групата с най-висока оценка и с необходим брой ходове по-малък или равен на наличния ни брой ходове. За да спестим обхождането на 1 милион оценки 1000 пъти при най-голямото възможно поле и при 1000 хода сме разработили метод, който обхожда всички оценки един път и връща 5-те най-високи оценки – GetRelativeMaxTowerScore(). Ако в следващите 5 пъти тези оценки не се променят, те се използват директно вместо да се обхождат отново всички оценки и да се търси максималната всеки път.Този метод не ни върши работа, когато ни останат малко ходове в поле с малки размери, тъй като шансът оценките да се изменят с всеки ход нараства. За този случай използваме GetExactMaxTowerScore(), който обхожда всички оценки всеки път и връща най-високата, без компромиси. По този начин алгоритъмът свършва работата си върху поле 1000 на 1000 и 1000 хода за по-малко от 2 секунди на тестовата ни машина.

Събаряне на кулите – MakeTurnSet(), ResetTower()

Събарянето протича като се прави опит да се съборят всички кули от групата съседни кули. Понякога не всички кули от групата могат да бъдат съборени и за това се грижи ResetTower(),който проверява дали при вземане/слагане на блокче върху съседна кула тя няма да мине през централната и да нулира себе си и централната кула. В такъв случай не е особено полезно да връщаме централната кула до базовата височина с цел да съборим останалите съседни кули, така че просто изключваме подобни съседни кули и събаряме само останалите в групата, които отговарят на условията. След всяка обработка на група от съседни кули – MakeTurnSet(),правим актуализация на оценките на групите.

Събаряне на максимален брой блокчета – MaxBlocksPerTurnAlgo

Алгоритъмът за събаряне на максимален брой съседни кули работи, но не дава добри резултати при големи разлики във височините на съседните кули в групата. Ако трябва да сме точни, този алгоритъм дава добри резултати в много специфични случаи, когато имаме група от съседни кули с големи височини, но с разлики от няколко кубчета. За да постигнем добри резултати и при разнообразни височини разработихме втори алгоритъм, който използва различна оценка, базова височина и начин на събаряне. Целта на алгоритъма е да намери тези две съседни кули, при чието изравняване ще съборим най-много блокчета с минимален брой ходове.

Базова височина – GetBase()

Тъй като целта ни е да съборим максимален брой блокчета с минимален брой ходове при изравняването само на две съседни кули, базовата височина ще бъде тази височина на съседна кула, която има най-малка разлика с височината на централната кула. Ако две съседни кули имат еднаква най-малка разлика с централната кула, но едната е по-ниска, а другата по-висока от централната се предпочита по-високата кула за извличане на базова височина.

Оценка на група от съседни кули – UpdateRelatedTowersScore()

Оценката отново представлява броя на съборените кубчета за един изигран ход. Специфичното тук е, че в сумата от височините на кулите, освен централната и съседната, които ще съборим, включваме и всички останали съседни кули, които имат височина равна на базовата. В такъв случай ако две съседни кули са равни при изравняване на централната с тях и трите кули ще бъдат съборени и ние трябва да включим този фактор в оценката.

Финална версия на алгоритъма

В зависимост от спецификата на входните данни, понякога първият алгоритъм получава по-добри резултати, а понякога вторият алгоритъм се представя по-добре. Това, което направихме е да съчетаем двата алгоритъма в нашето решение на задачата „Игра на тролове“. След като пуснем двата алгоритъма да се състезават един срещу друг, избираме по-добре представилия се и отпечатваме само неговите резултати.

Описание на приложната част

Начална идея

Началната идея на приложната част беше чрез използване на приятен дизайн да се визуализират резултатите от алгоритъма. Първата технология към която се насочихме беше използването на canvas със различни приятни анимациики за събаряне на кулите, отчитане на ходовете и т.н. След разработката на прототипа екипа установи, че това не би донесло максимално преживяване за потребителя. След изключително кратък размисъл решихме да скочим на дълбоко и да пробваме да разработим 3d приложение. За целта щяхме да използваме WebGL и Three.js.

Краен резултат

Началния период на работа по приложната част беше изключително труден и се състоеше в изграждането на достатъчно добра абстракция, която след това да обхване всички идеи на екипа. Така след много писане без видим резултат започнаха да се появяват файловете, грижещи се за основата на приложението. Целта беше да се изготвят достатъчно гъвкави класове, които да имат цялата необходима функционалност.

Описание на класовете

Основен клас на приложението е класът Sim (Simple Simulator – 2x sim). Той съдържа класът Sim.App – singleton клас, който след като бъде наследен се грижи за цялостната работа на приложението и интеракцията с него. Sim.Object е базов клас за всички обекти в приложението, a Sim.Publisher основен клас за всички събития.

GameOfTrolls е класът, който наследява Sim.App и съответно държи настройките на цялото приложение и интеракцията с него. Тук имаме методи за добавяне на камъни по полето, премахването им, както и създаване на анимация, необходима за един от модулите на приложението. Още в началото класът инициализира 2 други основни класа – GameArea и Environment. Environment е класът, който се грижи за поставянето на терена на игрището, светлини, начална позиция на камерата. GameArea е класът, където зареждаме игралното поле, различните модели на робот и трол, както и инициализираме класът RockColumn, който се грижи за всяка колона от скалички на игралното поле. По време на разработката беше създаден и класът Rock, който да се грижи за всяко отделно камъче, но в последствие заради performance, този клас беше изключен.

Финална версия

Финалната версия включва използването на няколко допълнителни файла и пренаписване на част от функционалността на three.js, за да може да отговаря на изискванията на проекта. Екипът започна работа по възможността за игра от 2ма души, където единия заема ролята на робота, а другия на трола, като този модул е напълно завършен. Притиснати от времето, недовършени останаха другите 2 модула, които екипа разработи – 2 възможности за самостоятелна игра – Предизвикване на Трол, където играчът задача полето върху, което да играе Трола и Игра срещу Трол, където играчът играе на произволно поле сам, като след това резултатът му се сравнява с този на Трола. Самостоятелната игра изискваше пренаписване на целия алгоритъм от C# на javascript, което също забави изпълнението на финалната част. В крайна сметка в момента частично работещи са 2те възможности за самостоятелна игра, като най – важното, което предстои да се добави е в модула Игра срещу Трол, където след изиграване на собствените си ходове, играчът би трябвало да бъде прехвърлен и да види истинската игра на Трола, а не само неговият резултат.

В момента цялото съдържание на играта се зарежда динамично още при зареждането на началното меню

Основен проблем на крайната версия е невъзможността да влезе в рамките, зададени от конкурса за размери на полето – 1000x1000x1000 което би изисквало зареждането на приблизително 1 милиард обекта в браузъра, което е нещо, с което WebGL все още не може да се справи. Също така приложението не проверява за достоверността на въведените данни, когато това се налага