Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Provinsgenerering med postprocess
KTH, Skolan för informations- och kommunikationsteknik (ICT).
2014 (Svenska)Självständigt arbete på avancerad nivå (yrkesexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
Abstract [en]

This bachelor's thesis is a part of a larger project carried out at Paradox Interactive. The project aims to improve a map generator for the strategy game Europa Universalis IV. This work addresses the creation and implementation of a province generator that divides a pregenerated landscape in provinces. The provinces in the game are the regions on the game map that the game mechanics are based upon. The improvements that are expected of the new province generator includes the following properties:

• The provinces that are created have more logically placed boundaries that are affected by the structure of the landscape.

• The program gives the user more control over how the end result should look like by letting the user set the values of input parameters.

• The execution should not exceed an approximate time limit. This time limit is set by Paradox Interactive.

The work began with research on the topics map creation and map division to give enough knowledge to plan the implementation of the program. The programming language that is used is Java. The implementation of the program is based on many well-known algorithms in which the most remarkable one is Fortune's algorithm which performs the main task of the provincial division of the program, the creation of Voronoi diagrams. The Voronoi diagrams are used to divide the map into regions which by using a post-process results in the creation of the provinces.

Other well-known algorithms and methods used or addressed in this report include the Lloyd relaxation, Bresenham's line algorithm, Scan Line Flood Fill, Delaunay triangulation and Bowyer-Watson's algorithm. The result of this work is a Java application that can load a map file containing information of a landscape structure and create a division of provinces with provincial boundaries that depend on the structure of the landscape. The results of the provincial division may be controlled by a number of user defined parameters. The program could not be fully calibrated during the time of the project because the landscape generator was not ready in time to be able to provide a map of a generated landscape. The generated provinces can be saved as an image file on the hard disk.

Abstract [sv]

Kandidatexamensarbetet är en del av ett större projekt som utförs på företaget Paradox Interactive. Projektets mål är att förbättra en kartgenerator för strategispelet Europa Universalis IV. Det här arbetet avser skapandet och implementationen av en provinsgenerator som delar in ett färdiggenererat landskap i provinser. Provinserna i spelet är de landsdelar på kartan som spelmekaniken bygger på.

Förbättringarna som förväntas av den nya provinsgeneratorn är bland annat att:

• Provinserna som skapas ska ha mer logiska gränser som påverkas av landskapets utformning och inte vara alltför orealistiska.

• Ge användaren mer kontroll över hur slutresultatet ska se ut genom användarinmatade parametrar.

• Inte överstiga en ungefärlig tidsgräns vid programmets exekvering. Tidsgränsen sätts av Paradox Interactive.

Arbetet började med forskning kring ämnena kartgenerering och kartindelning vilket gav tillräckligt med kunskap för att planera hur programmet skulle implementeras. Programmeringsspråket som används är Java. Implementationen av programmet bygger på många kända algoritmer där den mest anmärkningsvärda algoritmen är Fortune's algoritm som utför huvuduppgiften för provinsindelningen i programmet, skapandet av Voronoidiagram. Voronoi-diagramen används för att dela in kartan i ytor som med hjälp av en postprocess resulterar i skapandet av provinserna.

Andra kända algoritmer och metoder som används eller tas upp i den här rapporten är bland annat Lloyd relaxation, Bresenham's linjealgoritm, Scanline floodfill, Delaunay triangulering och Bowyer–Watson's algoritm.

Resultatet av arbetet är ett Java-program som kan läsa in en kartfil med information om landskapsstruktur och skapa en indelning av provinser med provinsgränser som beror på landskapets utformning. Resultatet av provinsindelningen kan styras med hjälp av ett antal användarinmatade parametrar. Programmet hann inte kalibreras fullt ut under arbetets gång på grund av att landskapsgeneratorn inte blev färdig i tid för att kunna bidra med en genererad landskapskarta. De genererade provinserna kan sparas som en bildfil på hårddisken.

Ort, förlag, år, upplaga, sidor
2014. , s. 52
Serie
TRITA-ICT-EX ; 2014:105
Nyckelord [en]
algorithm implementation, computational geometry, digital cartography, efficiency, post-processing
Nyckelord [sv]
algoritmimplementation, beräkningsgeometri, digital kartografi, effektivitet, postprocess
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-177269OAI: oai:DiVA.org:kth-177269DiVA, id: diva2:872044
Examinatorer
Tillgänglig från: 2015-12-01 Skapad: 2015-11-17 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

fulltext(3341 kB)50 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 3341 kBChecksumma SHA-512
fd60b5ad610e921f780774fb13104e6155d2385ed1d32769f4dd98269a794cf77f9d300d0378e61aac414ef3720ac4578710ee4f40305af3200d0f368b4a3910
Typ fulltextMimetyp application/pdf

Av organisationen
Skolan för informations- och kommunikationsteknik (ICT)
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 50 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 157 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf