Show simple item record

dc.contributor.authorAvni, Shachar
dc.contributor.otherQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))en
dc.date2010-05-25 14:53:24.375en
dc.date.accessioned2010-05-26T14:48:43Z
dc.date.available2010-05-26T14:48:43Z
dc.date.issued2010-05-26T14:48:43Z
dc.identifier.urihttp://hdl.handle.net/1974/5688
dc.descriptionThesis (Master, Computing) -- Queen's University, 2010-05-25 14:53:24.375en
dc.description.abstractIn current online games, player positions are synchronized by means of continual broadcasts through the server. This solution is expensive, forcing any server to limit its number of clients. With a hybrid networking architecture, player synchronization can be distributed to the clients, bypassing the server bottleneck and decreasing latency as a result. Synchronization in a decentralized fashion is difficult as each player must communicate with every other player. The communication requirements can be reduced by computing and exploiting frontier sets: For a pair of players in an online game, a player's frontier is the region of the game space where the player may move without seeing (and without communicating to) the other player. A pair of frontiers is called a frontier set. This thesis describes the first fast and space-efficient method of computing frontier sets in large terrains. Frontier sets are computed by growing regions in a connected set of quads in a hierarchical decomposition of the terrain. The solution involves the precomputation of a potentially visible set (PVS) for each quad in the decomposition, which stores all the quads potentially visible from any point within the current quad. Since the memory needed to store the PVSs for all the quads is quite large, a compression technique is introduced which controls the size of each PVS. A PVS merging algorithm, with both lossless and lossy variations, is also described which permits adding the PVS of a point or quad to the PVS of a growing region. The new algorithm is compared to a simple region growing approach where frontiers are grown along the individual terrain points. Using similar merging techniques, the new algorithm performs better, producing larger frontier sets with faster execution times.en
dc.languageenen
dc.language.isoenen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.subjectComputer Graphicsen
dc.subjectVisibilityen
dc.subjectPVSen
dc.subjectFrontier Setsen
dc.subjectTerrainsen
dc.subjectGame Programmingen
dc.subjectComputer Scienceen
dc.titleFrontier Sets in Large Terrain Environments with Applications to Decentralized Online Gamesen
dc.typeThesisen
dc.description.degreeMasteren
dc.contributor.supervisorStewart, Jamesen
dc.contributor.departmentComputingen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record