Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Provinsgenerering med postprocess
KTH, School of Information and Communication Technology (ICT).
2014 (Swedish)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
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.

Place, publisher, year, edition, pages
2014. , 52 p.
Series
TRITA-ICT-EX, 2014:105
Keyword [en]
algorithm implementation, computational geometry, digital cartography, efficiency, post-processing
Keyword [sv]
algoritmimplementation, beräkningsgeometri, digital kartografi, effektivitet, postprocess
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-177269OAI: oai:DiVA.org:kth-177269DiVA: diva2:872044
Examiners
Available from: 2015-12-01 Created: 2015-11-17 Last updated: 2017-08-01Bibliographically approved

Open Access in DiVA

fulltext(3341 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 3341 kBChecksum SHA-512
fd60b5ad610e921f780774fb13104e6155d2385ed1d32769f4dd98269a794cf77f9d300d0378e61aac414ef3720ac4578710ee4f40305af3200d0f368b4a3910
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 7 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 100 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf