Игра “Космически войни”

Финална задача от конкурса на Telerik и PC Magazine Bulgaria, сезон 2011/2012

Описание на играта “Космически войни”

Играта „Космически войни“ се играе в правоъгълна матрица с размери 40 реда на 50 колони. В нея има 4 вида обекти – бойни кораби (общо 2 на брой), товарни кораби (общо 18 на брой), ракети (изстрелвани от бойните кораби) и астероиди (произволна бройка). Играта се играе от двама играчи. Всеки играч разполага с 1 боен кораб и 9 товарни кораба. Целта е да бъдат унищожени възможно най-много вражески кораби.

Играта се играе на стъпки (ходове). На всеки ход, обектите взаимодействат помежду си, движещите обекти се придвижват, а играчите могат да задават команди на своят боен кораб.

Бойният кораб е олицетворението на играча. Той може да се движи, да сменя ориентацията си, да се блъска в обекти от матрицата и да изстрелва ракети. Ракетите се движат праволинейно, равномерно, като също могат да се блъскат в обекти от матрицата. Играчите ползват бойните си кораби, за да унищожават вражеските товарни кораби и вражеския боен кораб. Унищожаването на вражески боен кораб носи точки на играчите. Загубата на боен кораб отнема точки от играча.

Унищожаването на който и да е кораб е перманентно за играта, т.е. корабите не се „прераждат“ и не се появяват нови кораби в рамките на една игра.

Товарните кораби са вид „ресурс“ за играча. Те не могат да се движат, но могат да бъдат унищожавани. Унищожаването на вражески товарни кораби носи точки на играча. Ако играчът сам унищожи свой товарен кораб, това отнема от неговите точки, но ако товарният кораб бъде унищожен от противника, това не отнема от точките на играча.

Астероидите са неутрални обекти. Те не могат да се движат, но могат да бъдат унищожавани. Унищожаването на астероиди по никакъв начин не влияе на точките на играча.

Всички обекти могат да се сблъскват помежду си, ако в определен момент от време се намират на една и съща позиция. Единствено сблъсък не може да има между две ракети (в този случай ракетите просто се разминават). При сблъсък на два обекта, и двата се унищожават.

Сблъсък на два бойни кораба води до загуба на точки и на двамата играчи, без да се печелят точки за „унищожаване на вражески боен кораб“.

Първоначално, позициите на товарните кораби на първия играч са следните: (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5). Позициите на товарните кораби на втория играч са симетрични на тези на първия играч по редове и колони, съответно в долния десен край на матрицата

Позицията на бойния кораб на първия играч първоначално е (7, 7). Позицията на бойния кораб на втория играч е симетрична на позицията на бойния кораб на първия играч по редове и колони, съответно в долния десен ъгъл.

С две думи, първоначално всеки обект в матрицата си има симетричен обект спрямо центъра на матрицата.

Играта приключва, при първо срещане на едно от следните условия:

• Всички кораби на единия играч са унищожени
• Бойните кораби и на двамата играчи са унищожени
• Стигнато е до хилядната (1000) стъпка (ход) от играта

Движение в играта „Космически войни“

В открития космос, ако едно тяло получи тласък в някаква посока, то ще продължи да се движи в тази посока (праволинейно, равномерно), докато не се появи друг тласък (било то сблъсък с друго тяло, или действие на някаква сила), която да промени движението му.  Ако имаме кораб с двигател и задействаме този двигател за кратко, тялото ще почне да се движи в посока, обратна на посоката в която сочи двигателя, тоест в посоката, в която гледа лицето на кораба. Това ще продължи неопределено дълго. Ако обаче завъртим кораба на 180 градуса около оста му и задействаме двигателя за същото време, за което сме го задействали преди, корабът ще спре в неподвижно състояние. Ако вместо това завъртим само с 90 градуса, и задействаме двигателя, корабът ще започне да се движи по диагонал, защото посоката на движение е сумата от векторите, в които посоки е приложена задвижваща сила. На този принцип работи движението в „Космически войни“.

Бойният кораб може да приема следните команди (съответно да извърши следните действия за един ход):

• Завърти наляво – завърта корабът около оста му на 90 градуса обратно на часовниковата стрелка.
• Завърти надясно – завърта корабът около оста му на 90 градуса по часовниковата стрелка.
• Приложи тяга с двигателите – еднократно (в рамките на хода) включва двигателите, придавайки на кораба фиксирано ускорение в посоката, в която сочи лицето му.
• Изстреляй ракета – изстрелва ракета в посоката, в която сочи лицето на кораба. Освен изстрелването, това има страничен ефект. Излитането на ракетата създава сила, която действа обратно на посоката на движение на ракетата, т.е. обратно на посоката, в която сочи лицето на кораба. Така, изстрелването на ракета действа като прилагане на тяга с двигателите, само че в обратна посока (например изстрелване на  ракета, когато корабът е неподвижен, ще го задвижи назад, а изстрелване, когато се движи напред, ще го спре).

Бойният кораб може за един ход да измине не повече от 1 клетка от матрицата, т.е. новото му местоположение винаги е клетка, съсед на клетката, в която е бил преди (като всяка клетка има точно 8 съседа), или същата клетка (ако няма движение). Бойният кораб може да се движи хоризонтално, вертикално или диагонално в матрицата. Диагоналното движение се постига по следния начин: прилагане на тяга по хоризонтала или вертикала, еднократно завъртане около оста (90 градуса) и отново прилагане на тяга.

Ако бойният кораб излезе от матрицата, той се счита за унищожен.

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

Когато ракетата напусне игралното поле, тя се счита за унищожена.

Точкуване в играта „Космически войни“

Следните точки се причисляват към точките на играч, при съответните ситуации:

• Унищожаване на вражески боен кораб чрез ракета: +1 т.
• Унищожаване на вражески товарен кораб чрез ракета: +1 т.
• Унищожаване на собствен товарен кораб чрез ракета: -1 т.
• Сблъсък с вражески боен кораб: -1 т.
• Сблъсък с вражески товарен кораб: 0 т.
• Сблъсък със собствен товарен кораб: -2 т.
• Сблъсък с астероид: -1 т.

Алгоритмична задача – стратегия за играта “Космически войни”

Напишете програма (алгоритъм), която играе играта “Космически войни”, като се стреми да получава възможно най-много точки в края на играта. На всеки ход, програмата ще бъде стартирана, ще получи информация за това как изглежда матрицата на играта и ще бъде прекратявана след 0.100 секунди. На всеки ход програмата трябва да даде най-много една от 5-те възможни команди на своя кораб:

• L – завъртане наляво
• R – завъртане надясно
• Е – придаване на тяга с двигателите
• S – изстрелване на ракета
• N – празен ход (не се изпълнява никаква команда)

Ако след прекратяване на работата на програмата няма зададена команда се счита, че на този ход играчът просто не задава команда и играта продължава (т.е. няма наказание за пресрочване на позволеното време).

Входни данни

Входните данни се четат от файла “input.txt”.

На първия ред от файла стои числото T – номерът на поредния ход от играта (число от 1 до 999).

На втория ред от файла стоят две числа, R и C, разделени с единствен интервал – съответно редът и колоната, на които се намира корабът на играча (R винаги ще бъде в интервала [0, 39], а C винаги ще бъде в интервала [0, 49]). На следващия ред се намира точно един символ S – символът, с който се означават товарните кораби на играча (може да бъде 1 или 2).

На всеки от следващите 40 реда има по точно 50 символа, описващи съответно клетките от матрицата. Ето означенията на клетките в матрицата:

• ‘ ’ – интервал, (ASCII код 32) – празна клетка
• ‘#’ – диез, (ASCII код 35) – клетка съдържаща астероид
• ‘o’ – малка английска буква о, (ASCII код 111) – клетка, съдържаща ракета
• ‘*’ – звезда (ASCII код 42) – клетка, съдържаща експлозия (не влияе на игровата логика, индикира клетка, където на този ход има сблъсък)
• ‘u’ (ASCII код 117) – клетка, съдържаща боен кораб, лицето на който е ориентирано нагоре
• ‘d’ (ASCII код 100) – клетка, съдържаща боен кораб, лицето на който е ориентирано надолу
• ‘l’ (ASCII код 108) – клетка, съдържаща боен кораб, лицето на който е ориентирано наляво
• ‘r’ (ASCII код 114) – клетка, съдържаща боен кораб, лицето на който е ориентирано надясно
• ‘1’ – единица (ASCII код 49) – клетка, съдържаща товарен кораб на играч 1
• ‘2’ – двойка (ASCII код 50) – клетка, съдържаща товарен кораб на играч 2

Входните данни за алгоритмичната част винаги ще бъдат валидни и в описания формат.

Изходни данни

Изходните данни се печатат във файла “output.txt”

На единствения ред от изхода програмата трябва да отпечата точно един символ (L, R, E, S или N), който индикира командата, която се задава на бойния кораб на играча.

Ограничения

• Числата R и C са цели и са в сила ограниченията 0 ? R ? 39, 0 ? C ? 49.
• Програмата трябва да завършва своята работа за най-много 0.100 секунди.
• Алгоритмите имат право да създават файлове в директорията, в която се намират, стига тези файлове да имат име различно от “input.txt” и “output.txt”.
• Опити за умишлено четене или писане в директория, различна от текущата, ще се считат за нечестна игра и ще се присъждат 0 точки на виновния състезател или отбор.

Примери – код на игровата логика

Ще получите сорс кода на игровата логика, който ще бъде ползван за тестване на алгоритмичната част и можете да адаптирате програмите си така, че да работят оптимално спрямо дадения код.

Сорс кодът може да бъде намерен на адрес:

http://pcmagazine-telerik-contest.googlecode.com/svn/trunk/Round-7-Final-Space-Wars/

Задача по приложно програмиране – симулатор на играта “Космически войни”

Напишете софтуерно приложение, който симулира играта „Космически войни“ и визуализира битката между двама играчи. Можете да ползвате дадения код на игровата логика, както и да я имплементирате сами – по Ваш избор. Функционалностите за имплементиране в този симулатор оставяме на Вас, но ето някои предложения:

• Визуализация на ходовете – кораби, астероиди, експлозии и т.н.
• Визуализация на резултати (точките на двамата играчи)
• Възможност за игра от човек-човек, човек-компютър, компютър-компютър
• „Записване“ на игра и възможност за показване на записаното после.

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

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването ще бъде генерирано едно произволно, симетрично (спрямо центъра на матрицата) игрално поле.

Всеки алгоритъм ще бъде противопоставян на всички останали, и точките от всеки двубой, в който участва, ще бъдат добавяни към общите му точки.

След изиграване на всички двубои, алгоритъмът с най-висок резултат ще получи 10 точки,  а останалите алгоритми – съответната част от тези точки.

Максимални точки в крайното класиране за алгоритмичната част – 10

Критерии за оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

• Коректност (доколко функционалностите работят и са достатъчни за добра симулация) – 2 точки
• Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
• Ползваемост (доколко е удобна и интуитивна работата с приложението) – 2 точки
• UI дизайн (доколко са приятни и удобни интерфейсът и визуализацията) – 2 точки
• Оригинални функции и решения, които да впечатлят журито – 2 точки

Максимални точки в крайното класиране за приложната част – 10

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например PHP, C, C++, C#, Delphi, Python, WPF, XAML, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълният сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

За приложната част се изисква да бъде предаден пълен сорс код. Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може също да бъде web-базирано). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), по-сериозни затруднения при намирането и стартирането на приложението ще намалят неговият краен резултат.

Характеристики на системата, върху която ще бъде проведено тестването на алгоритмичната част

• Intel® Xeon® CPU E31225 @ 3.10 GHz
• 16 GB RAM
• 128 MB Video Memory (dedicated) Intel® HD Graphics video card
• 232 GB HDD
• Microsoft Windows 7 64-bit OS

 

Завърши финалният кръг на състезанието на PC Magazine Bulgaria и Телерик за сезон 2011/2012!

Да, този път заглавието не е „Анализ на нам-кой-си кръг“. Все пак това беше грандиозният финал, заслужава грандиозно заглавие – доколкото сме способни да измислим такова. Сега ще ви разкажем нашите впечатления от състезанието, как то протече, и всичко останало, което ни е на сърце. Естествено резултатите можете да видите накрая на тази статия, а състезателите вече бяха наградени и тайни няма, така че този път сигурно scroll-ването ще е по-малко.

Накратко за формата на финала

Състезанието се проведе в два дни, като по-голямата му тежест беше в първия ден. Идеята беше следната – на първия ден трябваше да се напише всичко, алгоритмичната част да се оцени автоматично вечерта, а на сутринта на следващия ден състезателите да представят приложната част на задачата. Амбициозна цел, предвид, че първият състезателен ден беше дълъг 12 часа. Това обаче не попречи да бъде осъществена идеята. Сега ще дадем и кратко резюме на двата дни.

Задачата и първи ден на състезанието

Първия ден не беше лек за състезателите. Състезанието беше планувано да почне в 8:30 сутринта и да продължи до 20:30 вечерта. Разбира се, благодарение на разнообразно множество от причини/оправдания, започнахме към 9. Което, както повечето състезатели знаят, е на късмет. Дойде и моментът, в който отборите се впуснаха в решаване на задачата. А тя не беше лека.

С няколко думи, в задачата описахме играта „Космически войни“, която се играе в правоъгълна матрица. Във всяка клетка на матрицата може да има или кораб, или ракета, или астероид. Играта се играе от двама играчи, всеки от тях управлява един „боен кораб“ и има 9 товарни кораба (неподвижни), които трябва да защитава. Типичния сценарии на стратегия „унищожи противника и базата му, преди той да те е унищожил“, или иначе казано нещо като DotA / MOBA стил игра.

Дотук не звучи като нещо особено, но като си представим, че отборите трябваше да напишат алгоритъм, който играе тази игра, така че да побеждава, нещата стават по-сложни. И на това отгоре управлението на кораб в космоса не е тривиална задача.

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

Като бонус, който да ги улесни, състезателите получиха „груба“ версия на симулация на играта (заедно със сорс код) – едно конзолно приложение, което беше способно да зареди два алгоритъма, да проиграе играта между тях и да записва резултати. Както се очакваше, в тази симулация имаше грешки (бъгове), за които състезателите можеха да съобщават, както и от които можеха да извлекат полза за алгоритмите си. Ние им дадохме няколко последователни версии, постепенно изчиствайки бъговете.

Така се доближихме максимално до истинския свят – ако една игра има проблеми, когато излезе на пазара, играчите се възползват от тях за да печелят. Съответно производителите оправят тези проблеми и играчите се адаптират и се възползват от нещо друго. Е, при нас изглежда не останаха такива проблеми (или поне не сме ги открили) в крайна сметка, но пък създадохме забавно взаимодействие между жури и състезатели, което едва ли се случва често по други състезания.

Предвид дългия ден, осигурихме на състезателите това-онова за хапване, под формата на нещо като шведска маса. Но, сериозно отдали се на задачата, те бяха оставили половината маса непокътната. Ние обаче сме настоятелни и започнахме да им носим лично. Това имаше по-голям ефект от шведската маса и храната значително намаля. Добре де, накрая и ние си взехме, признаваме си.

В хода на деня започнахме да виждаме изписани въпроси на лицата на участниците от типа на „абе т‘ва що лети накриво“, „тоя if к‘во прави тук“ и подобни, които определено върнаха стари (и не толкова стари) спомени. Естествено, не липсваха и радостни моменти, когато алгоритмите изпълняваха очакванията на състезателите.

Някои отбори се преориентираха към приложната част, други бяха твърдо решени да напишат алгоритмичната, трети писаха по малко и от двете – имаше разнообразие на дейности. Както често става по такива събития, трескавото писане започна към края на състезанието. Трябва да се отбележи, че състезателите показаха желание и повечето от тях останаха до самия край. Дори след предаването на решенията имахме повод да останем малко повечко и да изядем храната –лаптопът на един състезател реши, че е подходящ момент за windows updates.

В крайна сметка денят завърши успешно „и кой откъде е“. Разбира се на журито предстоеше интересна вечер тестване, а на следващия ден на състезателите предстоеше представяне и награждаване.

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

Лека-полека и без много сън, преминахме към втория ден

Втори ден на състезанието, представяния и награждаване

Навлязохме във втория ден с доста желание да видим какво са ни подготвили състезателите в приложната част. Все пак бяхме провокирани от интересните двубои в алгоритмичната. Няма да споменаваме, че изграждането на симулация на игра на тематика космически битки е трудна задача, дори когато е предоставена игровата логика (така де, няма да го споменаваме). Старанията на повечето отбори бяха дали добри резултати, предвид малкото осигурено време. Видяхме приложения, в които се наблягаше на оформлението на контролите в приложението (условно казано UI частта), видяхме и такива, в които се наблягаше повече на визуализацията на самата симулация – имаше от всичко по малко, тук-там и по много.

Журито беше съставено от доста членове, имащи по един или друг начин , всеки от които даде своята оценка. Представянията бяха на ниво, въпреки че състезателите сигурно не бяха прекарали доста време в сън.

Когато седнахме да заседаваме установихме, че оценките ни за отборите се доближават, без да сме комуникирали по време на даването на тези оценки. Това доста улесни заседаването, тъй като нямаше значителни разминавания на мнения. Приключихме бързичко, дадохме оценките и оставаше най-хубавата част – наградите. Е, всъщност дойде частта с чакането да дойде време за наградите, защото свършихме няколко часа преди самото награждаване.

Награждаването се проведе в БТА. Заведохме състезателите дотам (заедно с багажите им, кои каквито си има). Постарахме се да ги вкараме в задоволително нервно състояние, като им разказахме различни едновременно забавни и непечеливши случки на поведение на алгоритмите им (някои от които украсени за артистичен ефект) – естествено стресирахме победителите най-много.

Започна церемонията, казаха се няколко (доста) думи за състезанието и се започна с наградите. Както споменахме, състезателите си имаха достатъчно багажи, но това не попречи да бъдат натоварени допълнително – сред наградите бяха електронни четци за книги, принтер, колонки, чанти за лаптопи, монитори, клавиатури, мишки, модеми, сертификати и така нататък. Разбира се, като доблестни състезатели те приеха голямото натоварване без никакви оплаквания, сигурно им е харесало.

Беше уреден един скромен коктейл в БТА, почерпихме се всички, простихме си взаимно мъченията, стегнахме багажите и… знаете я песента.

Надяваме се, че всички участници на финала си прекараха шеметно, нека всеки сам тълкува думата както намери за добре. За нас определено беше така през целия този конкурс. Поздрави на всички за участието и успехите и понеже и най-големите пожелания са празни приказки, оставяме на вас да ги изпълните!

… Добре де, ето ги и резултатите за призовите места:

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

Това са крайните резултати на отборите, заели призовите места на финала на състезанието на PC Magazine Bulgaria и Telerik.

 

Място	Отбор	Общ резултат	Алгоритъм	Приложение
1	Станислав Гатев и Георги Ангелов	17.8	10	7.8
2	Антон Богданов и Станислава Богданова	15.55	8.43	7.12
3	Марио Стоилов и Ивайло Кирилов	6.6	0	6.6
4	Димитър Иванов	5.03	0	5.03

 

Решенията на участниците от всички кръгове са публично достъпни и могат да бъдат намерени на този адрес:

http://pcmagazine-telerik-contest.googlecode.com/svn/trunk/

Очаквайте на същия адрес публикуван линк с видео на двубой между решения от алгоритмичната част!