Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Розрахунок витрат на розробку модифікованого алгоритму 77

Розрахунок витрат на розробку модифікованого алгоритму 77




Сторінка11/17
Дата конвертації16.03.2017
Розмір0.82 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   17

3.4 Реалізація алгоритму

У даній дипломній роботі розробляється мультиплеєрна гра в жанрі тактичної стратегії. На ігровому полі розташовані бази, з’єднані між собою шляхами. Загалом ігрове поле можна представити у вигляді графу, в якому вершини – це бази, а ребра – це шляхи. Кожна база має такі характеристики:



  • координати;

  • місткість;

  • швидкість відновлення;

    Та́ктика (від дав.-гр. τακτική taktike - мистецтво шикування) - концептуальна дія, яка здійснюється у вигляді одного або більшої кількості конкретних завдань. Термін використовується у бізнесі та військовій справі, а також у шахах, спорті та акціях протесту.

    Відно́влення (рос. восстановление, англ. reduction; нім. Reduktion f) -- це процес приєднання електронів речовиною, при цьому ступінь окиснення її елементів знижується.



  • власник.

Якщо між базами існує шлях, то по ньому можна відправити контейнер. Якщо контейнер прибув на ворожу базу, і його місткість більша за місткість бази – він захопить її. Якщо його місткість менша за місткість бази – то їх значення віднімаються. Якщо місткості рівні – база стає нейтральною. При попаданні на свою базу їх місткості додаються.

Кожен контейнер має такі характеристики:



  • координати;

  • місткість;

  • швидкість руху;

  • власник.

Якщо на шляху стикаються два контейнери різних власників, то контейнер з меншою місткістю знищується і його місткість віднімається від більшого.

Ціллю гри є захоплення усіх баз противника. Зв’язок між пристроями відбувається через Bluetooth.

В даній грі одною з основних проблем є пошук колізій. Захоплення бази чи зіткнення контейнерів на шлху повинно перевірятись на кожному кроці. Існує велика кількість варіантів вирішення даної проблеми:

Повний перебір – перевірка кожного об’єкту на стикання з іншим об’єктом. Швидкість виконання даного алгоритму n2, тому при збільшенні кількості об’єктів на екрані швидкодія буде знижуватись в квадратичній залежності. У деяких випадках кількість об’єктів на екрані може досягати близько 100, що викликатиме відчутну затримку.

Іншим варіантом вирішення даної проблеми було розбиття екрану на сегменти. Швидкодія даного алгоритму також n2, проте навіть при значній кількості об’єктів на екрані, кількість об’єктів n в кожному окремому секторі не перевищуватиме критичної, при якій створюватиметься надмірне навантаження на процесор.

Я вирішив розбивати екран не на сегменти а на ребра. У кожного ребра є два масива об’єктів з кожного кінця. Для пошуку колізій достатньо перевірити на стикання лише перші елементи цих масивів. Швидкість роботи даного алгоритму m, де m – кількість ребер.

Кожне ребро має такі характеристики:


При запуску програми відбувається перевірка чи підтримує пристрій передачу даних через Bluetooth. Якщо так, то користувачеві пропонується його увімкнути. Екран запиту дозволу на включення Bluetooth наведено на рисунку 3.3.

c:\users\matviy\desktop\диплом\ресурси на диплом\screens\screenshot_2015-06-09-14-48-34.png

Рисунок 3.3 – Запит дозволу на ввімкнення Bluetooth.
Далі потрібно встановити з’єднання між пристроями. Для цього в програмі створено 3 потоки:

  1. AcceptedTread – у цьому потоці приймається запит на встановлення зв’язку;

  2. ConnectingThread – даний потік приймає назву підєднаного пристрою і відкриває слухаючий сокет;

  3. ConnectedThread – в даному потоці відбувається прийом\передавання даних між пристроями.

Вікно пошуку пристроїв наведено на рисунку 3.4.


Рисунок 3.4 – Вікно пошуку пристроїв.
В грі реалізовано 2 екрана – головне меню та ігрове поле. На головному меню можна відправти лише команду старт на інший пристрій, разом з якою також буде передано інформацію з поточними налаштуваннями. При отриманні іншим пристроєм цієї команди автоматично запускається екран ігрового поля. При виході гравцем з програми відсилається відповідна команда, яка сповістить опонента про роз’єднання зв’язку. Вікно головного меню наведено на рисунку 3.5.

В ході розробки даного програмного продукту було перевірено кілька алгоритмів синхронізації даних. Після запуску ігрового поля візуальні дані на кожному з пристроїв повинні бути ідентичними. Вікно ігрового поля зображено на рисунку 3.6.

Спочатку було використано простий алгоритм передачі та обробки даних. На кожному пристрої запускався потік перемальовки забраження. При відправці контейнера на базу на інший пристрій відсилалось повідомлення з номером бази та вагою контейнера. Пристрій який отримував таке повідомлення намагався на своєму екрані відтворити таку ж подію. У такому алгоритмі зразу виявилось кілька недоліків. Першим з них була різна швидкість перемальовки зображення на різних пристроях. При цьому швидші пристрої мали значну перевагу, так як контейнери приходили на інші бази з більшою швидкістю. Також відбувалась розсинхронізація у випадках коли один гравець захоплював базу іншого, а на пвільнішому пристрої це не встигало обробитись і гравець міг встигнути виконати дії з цією базою. Іншою проблемою була втрата повідомлень, якщо час відправки співпадав з часом перемалювання екрану. Повідомлення відправлялись одразу після взаємодії користувача з екраном. У найгіршому випадку на екрані одного пристрою починала відбуватись певна дія, а на іншому ні.

i:\pictures\screenshot\screenshot_2015-06-11-12-01-05.png

Рисунок 3.5 – Головне меню програми.

c:\users\matviy\desktop\диплом\ресурси на диплом\screens\screenshot_2015-06-09-14-51-50.png

Рисунок 3.6 – Вікно ігрового поля
У наступному варіанті реалізації було додано початковий алгоритм синхронізації. Один з пристроїв назначався хостом. Дані на іншому пристрої коректувались відносно головного. При відправці чи прибутті контейнера на головному пристрої відправлялось повідомлення з даними про цю базу. А пристрій-клієнт при відправці контейнера з бази надсилав запит на хост-пристрій про цю операцію.

Опера́ція (лат. operatio - дія, вплив) - дії, заходи, що виконуються за певним планом і спрямовані на вирішення якогось завдання, досягнення якоїсь мети або належить до кола функцій даного підприємства, установи, відділу, окремого працівника, певного обладнання тощо.

Хост перевіряв стан бази, і якщо дані не відрізнялись то виконував її. В іншому випадку він відправляв повідомлення синхронізації.

Щоб запобігти різній швидкості оновлення екранів різних пристроїв, на стороні клієнта було видалено потік оновлення. Натомість хост-пристрій при кожній перемальовці відправляв повідомлення про перемальовку.

Для того щоб вирішити проблему втрати повідомлень при перемалюванні екрану, я додав стек команд, у який записуються усі дії користувача між оновленнями екрану. При наступній перемальовці цей стек перевіряється, і якщо він не пустий, то виконуються дії, а замість повідомлення оновлення відправляється повідомлення з даними про дію користувача.


1   ...   7   8   9   10   11   12   13   14   ...   17



  • Рисунок 3.3 – Запит дозволу на ввімкнення Bluetooth.
  • Рисунок 3.4 – Вікно пошуку пристроїв.
  • Рисунок 3.5 – Головне меню програми.
  • Рисунок 3.6 – Вікно ігрового поля