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
Non-centralized distributed algorithm to locate nearby servers based on player positions for a MMOG server cluster
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

In this thesis a non-centralized algorithm is proposed to locate nearby servers based on their players’ positions in a massive multiplayer online game server cluster. The purpose of this is to enable that players can visually see each other even though they are connected to different servers. By utilizing peer to peer connection between the servers the algorithm is tolerant against possible hardware failures. The algorithm simplifies the data sent over the network with a new concave polygon creation algorithm which works in linear execution time, enabling fast computations for real-time games.

The algorithm works by finding colliding polygons from other servers and the closest polygons based on distance to find nearby servers which information should be shared with. Those two algorithms at this time work in quadratic execution time which is a point of improvement, which could require the concave polygon to be converted into one or several convex polygons.

The algorithm is designed to give the user good access on the amount of network traffic sent over the cluster which gives better control and understanding on how much network traffic that will be sent in the cluster. It shows that the algorithm is dependent on how players in the world are distributed over the servers. By having players nearby each other on the same server improves the result of the algorithm. It is shown that compared to having a centralized server, the network traffic on every single node have reduced network traffic than compared to a centralized server.

Abstract [sv]

In den här uppsatsen presenteras en icke-centraliserad algoritm som hittar närliggande servrar baserat på deras spelares positioner i ett massivt multi-spelare online spel med flera servrar. Syftet är att möjliggöra att spelare från olika servrar kan se varandra visuellt även fast de är uppkopplade till olika servrar. Genom att använda sig av ”peer-to-peer” kommunikation i klustret blir algoritmen tolerant mot hårdvarufel. Algoritmen simplifierar data som skickas genom en ny typ av konkav polygon algoritm vilken fungerar i linjär exekveringstid, vilket möjliggör snabba beräkningar för realtidsspel.

Algoritmen fungerar genom att hitta kolliderande polygoner från andra servrar och även de mest närliggande baserat på distans för att lokalisera närliggande servrar att dela information med. De här två algoritmerna arbetar i kvadratisk tid vilket skulle kunna förbättras. Detta kan kräva att konkava polygonen konverteras till en eller flera konvexa polygoner.

Algoritmen är designad för att ge användaren bra tillgång till hur mycket nätverkstrafik som bör skickas inom klustret vilket ger en bättre kontroll och förståelse över hur mycket data som kommer att skickas totalt. Det visas att algoritmen är beroende av hur spelarna är distribuerade över servrarna. Genom att ha närliggande spelare i världen på samma server förbättras resultatet av algoritmen. Det visas även att jämfört med en centraliserad server så förbättras nätverkstrafiken på varje enskild nod jämfört med trafiken som mottogs av den centraliserade servern.

Place, publisher, year, edition, pages
2015. , 65 p.
Series
TRITA-ICT-EX, 2015:204
Keyword [en]
Distributed algorithm, non-centralized, MMOG, cluster, locate servers, distance based, polygon creation
Keyword [sv]
Distribuerad algorithm, Icke-centraliserad, MMOG, kluster, lokalisera servrar, avståndsbaserad, polygon skapning
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-186714OAI: oai:DiVA.org:kth-186714DiVA: diva2:927850
Educational program
Master of Science in Engineering - Information and Communication Technology
Examiners
Available from: 2016-05-13 Created: 2016-05-13 Last updated: 2016-05-13Bibliographically approved

Open Access in DiVA

fulltext(2082 kB)55 downloads
File information
File name FULLTEXT01.pdfFile size 2082 kBChecksum SHA-512
8018151619b818ea3fc81a0b6ac98b4be42924a9b4f6a71283b20c64d87e3284d180847108cda727583629861c60274d6d16db04c6b97302328997fe16b9fdef
Type fulltextMimetype application/pdf

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 55 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