Queen's University - Utility Bar

QSpace at Queen's University >
Graduate Theses, Dissertations and Projects >
Queen's Graduate Theses and Dissertations >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1974/5688

Title: Frontier Sets in Large Terrain Environments with Applications to Decentralized Online Games
Authors: Avni, Shachar

Files in This Item:

File Description SizeFormat
Avni_Shachar_201005_MSc.pdf1.95 MBAdobe PDFView/Open
Keywords: Computer Graphics
Frontier Sets
Game Programming
Computer Science
Issue Date: 2010
Series/Report no.: Canadian theses
Abstract: In 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.
Description: Thesis (Master, Computing) -- Queen's University, 2010-05-25 14:53:24.375
URI: http://hdl.handle.net/1974/5688
Appears in Collections:Queen's Graduate Theses and Dissertations
School of Computing Graduate Theses

Items in QSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


  DSpace Software Copyright © 2002-2008  The DSpace Foundation - TOP