Shadows Collide - 2D-törmäyksentunnistusohjelma
Lappalainen, Olli (2019)
2019
All rights reserved. This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-2019052913172
https://urn.fi/URN:NBN:fi:amk-2019052913172
Tiivistelmä
Shadows Collide on 2D-törmäyksentunnistusohjelma, joka kehitettiin toimeksiantona Shadow Gameworks -pelistudiolle. Ohjelman tarkoituksena on olla perusta yrityksen ensimmäisen tietokonepelin fysiikkamoottorille. Ohjelma sisältää komentorivikäyttöliittymän, jolla käyttäjä voi kokeilla vektoreina, eli x ja y, listana syötettyjen monikulmioiden keskinäistä törmäämistä. Törmäämisellä tarkoitetaan kahden monikulmion kohtaamista 2D-avaruudessa.
Ohjelma sisältää kolme erilaista törmäyksentunnistusalgoritmia. AABB-algoritmi vaakasuorille nelikulmioille, ympyräalgoritmi ympyröille ja OBB-algoritmi muille koverille monikulmioille ja edellä mainittujen yhdistelmille. OBB-algoritmin keskeisessä roolissa käytetään SAT-algoritmia. SAT on erottavan akselin lauseen lyhenne, eli Separating Axis Theorem. Lauseen mukaan kaksi kuperaa monikulmiota eivät leikkaa, jos niiden välistä löytyy akseli, joka ei leikkaa kumpaakaan monikulmiota. Kuperalla monikulmiolla tarkoitetaan sulkeutuvaa ja vähintään kolme pistettä sisältävää monikulmiota, joka ei leikkaa itseään ja jonka jokainen sisäkulma on maksimissaan 180-astetta.
Shadows Collide kehitettiin Agile-projektina suunnittelu- ja kehitysvaiheissa. Suunnitteluvaiheessa luotiin matemaattinen selvitys tarvittaville funktioille ja konsepteille. Ohjelman rakenne suunniteltiin, josta syntyi vuo- ja luokkakaaviot. Kaavioiden perusteella GitHub-palvelun projektinhallintaan luotiin tehtäväkortit. Kehitysvaiheessa ohjelma ohjelmoitiin GitHub PMS:n tehtäväkorttien perusteella. Ohjelmoinnin aikana syntyneet lisätarpeet lisättiin tehtäväkortteina projektinhallintaan, jotta ohjelman kehitystä oli mahdollista seurata. Shadows Collide on kehitetty C++:lla ja kehitysohjelmana käytettiin Microsoft Visual Studio 2019 Community IDE:tä.
Hyvästä suunnittelusta huolimatta ohjelman kehityksessä ilmeni odottamattomia haasteita, kuten monissa, ellei kaikissa sovelluskehitysprojekteissa. Matemaattisten funktioiden ohjelmointi algoritmiksi osoittautui yleisimmäksi haasteeksi. Toiseksi yleisimmät ongelmat olivat ohjelmiston loogisia osia, jotka olivat jääneet suunnittelusta sivuun ja esiintyivät vasta ohjelmoidessa. Ongelmista huolimatta Shadows Collide valmistui suunnitellussa aikataulussa tyydyttävin tuloksin ja täyttäen toiminnalliset vaatimukset.
Jatkokehityksenä Shadows Collide optimoidaan vähemmän muistia käyttäväksi. Ohjelman lisäksi ohjelmoidaan renderöintimoottori Vulkan tai DirectX 3D-grafiikkarajapinnoilla, jonka jälkeen fysiikkasimulaatioiden kehitys on mahdollista. Pitkäaikaisena tavoitteena on luoda pelimoottori, jota käytetään Shadow Gameworksin ensimmäisessä tietokonepelissä.
Ohjelma sisältää kolme erilaista törmäyksentunnistusalgoritmia. AABB-algoritmi vaakasuorille nelikulmioille, ympyräalgoritmi ympyröille ja OBB-algoritmi muille koverille monikulmioille ja edellä mainittujen yhdistelmille. OBB-algoritmin keskeisessä roolissa käytetään SAT-algoritmia. SAT on erottavan akselin lauseen lyhenne, eli Separating Axis Theorem. Lauseen mukaan kaksi kuperaa monikulmiota eivät leikkaa, jos niiden välistä löytyy akseli, joka ei leikkaa kumpaakaan monikulmiota. Kuperalla monikulmiolla tarkoitetaan sulkeutuvaa ja vähintään kolme pistettä sisältävää monikulmiota, joka ei leikkaa itseään ja jonka jokainen sisäkulma on maksimissaan 180-astetta.
Shadows Collide kehitettiin Agile-projektina suunnittelu- ja kehitysvaiheissa. Suunnitteluvaiheessa luotiin matemaattinen selvitys tarvittaville funktioille ja konsepteille. Ohjelman rakenne suunniteltiin, josta syntyi vuo- ja luokkakaaviot. Kaavioiden perusteella GitHub-palvelun projektinhallintaan luotiin tehtäväkortit. Kehitysvaiheessa ohjelma ohjelmoitiin GitHub PMS:n tehtäväkorttien perusteella. Ohjelmoinnin aikana syntyneet lisätarpeet lisättiin tehtäväkortteina projektinhallintaan, jotta ohjelman kehitystä oli mahdollista seurata. Shadows Collide on kehitetty C++:lla ja kehitysohjelmana käytettiin Microsoft Visual Studio 2019 Community IDE:tä.
Hyvästä suunnittelusta huolimatta ohjelman kehityksessä ilmeni odottamattomia haasteita, kuten monissa, ellei kaikissa sovelluskehitysprojekteissa. Matemaattisten funktioiden ohjelmointi algoritmiksi osoittautui yleisimmäksi haasteeksi. Toiseksi yleisimmät ongelmat olivat ohjelmiston loogisia osia, jotka olivat jääneet suunnittelusta sivuun ja esiintyivät vasta ohjelmoidessa. Ongelmista huolimatta Shadows Collide valmistui suunnitellussa aikataulussa tyydyttävin tuloksin ja täyttäen toiminnalliset vaatimukset.
Jatkokehityksenä Shadows Collide optimoidaan vähemmän muistia käyttäväksi. Ohjelman lisäksi ohjelmoidaan renderöintimoottori Vulkan tai DirectX 3D-grafiikkarajapinnoilla, jonka jälkeen fysiikkasimulaatioiden kehitys on mahdollista. Pitkäaikaisena tavoitteena on luoda pelimoottori, jota käytetään Shadow Gameworksin ensimmäisessä tietokonepelissä.