Supporting Scalable Peer to Peer Virtual Environments Using Frontier Sets
Anthony J. Steed, Cameron Angus · 2006
We present a scalable implementation of a network partitioning scheme that we have called frontier sets. Frontier sets build on the notion of a potentially visible set (PVS) [1][22]. In a PVS, a world is sub-divided into cells and for each cell all the other cells that can be seen are computed. In contrast, a frontier set considers pairs of cells, A and B. For eac`h pair, it lists two sets of cells, FAB and FBA. By definition, from no cell in FAB is any cell in FBA visible and vice-versa. Our initial use of frontier sets has been to enable scalability in distributed networking. In this paper we build on previous work by showing how to avoid pre-computing frontier sets. Our previous algorithm, required O(N 3) space in the number of cells, to store pre-computed frontier sets. Our new algorithm precomputes an enhanced potentially visible set that requires only O(N 2) space and then computes frontiers only as needed. Network simulations using code based on the Quake II engine show that frontiers have significant promise and may allow a new class of scalable peer-to-peer game infrastructures to emerge.