Home   LARC   News   Publication List   Publications by Subject   Procedural Content Generation   Game Programming Education

Game Programming


The following research includes anything related to game programming that doesn't involve Procedural Content Generation.

The 15-Puzzle (2015)


Ian Parberry, "A Memory-Efficient Method for Fast Computation of Short 15-Puzzle Solutions", IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 2, June 2015. [pdf from IEEEXplore, more information]


While the 15-puzzle has a long and interesting history dating back to the 1870s, it still continues to appear as apps on mobile devices and as minigames inside larger video games. We demonstrate a method for solving the 15-puzzle using only 4.7MB of tables that on a million random instances was able to find solutions of 65 moves on average and 95 moves in the worst case in under a tenth of a millisecond per solution on current desktop computing hardware. These numbers compare favorably to the worst-case upper bound of 80 moves and to the greedy algorithm published in 1995, which required 118 moves on average and 195 moves in the worst case.

The $(n^2-1)$-Puzzle (2015)


Ian Parberry, "Solving the $(n^2-1)$-Puzzle with $\tfrac{8}{3}n^3$ Expected Moves", Algorithms, Vol. 8, No. 3, pp. 459-465, 2015. [more information]


It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{8}{3}n^3 +O(n^2)\) expected moves. This analysis is verified experimentally on 10,000 random instances each of the \((n^2-1)\)-puzzle for \(4 \leq n \leq 200\).

Audio Games (2005, 2007)

Audio images.

Timothy Roden, Ian Parberry, and David Ducrest, "Toward Mobile Entertainment: A Paradigm for Narrative-Based Audio Only Games", Science of Computer Programming, Volume 67, Issue 1, pp. 76-90, June 2007. A preliminary version of this paper appeared in Proceedings of the 2005 ACM SIGCHI International Conference on Advances in Computer Entertainment Technology, Valencia, Spain, pp. 274-277, June 15-17, 2005. [pdf]


The widespread use of sophisticated mobile computing devices has set the stage for a renaissance in audio only entertainment. Traditional visual games are already used widely in cellular phones and similar devices. A significant limitation is the small display size. In contrast, audio only games on suitable mobile hardware need not degrade due to the smaller form factor. This makes audio only games an attractive alternative to visual games. We describe a framework for authoring interactive narrative-based audio only games set in 3D virtual environments. Despite the novelty in audio only gaming, our approach builds on a foundation of several years of research into audio only applications for sight impaired users, augmented reality systems and human-computer interaction studies. In comparison to attempts to provide a realistic user interface, we argue a simple interface enhances both immersion and entertainment value, serendipitously making audio only games practical for mobile computing. Novel features of our system include real-time gameplay and multiplayer support. We also describe our software architecture, the current implementation of which uses low-cost existing PC-based hardware and software. In addition, we describe our first game, Dragon's Roar.

Author's Comments

I was asked to give an invited talk on this in 2010. You can see a video of this talk that includes some audio clips from our proof-of-concept games.

Portals and Portholes (2004, 2005)

PVS images

Timothy Roden and Ian Parberry, "Portholes and Planes: Faster Dynamic Evaluation of Potentially Visible Sets", ACM Computers in Entertainment, Vol. 3, No. 2, April/June 2005. A preliminary version of this paper appeared in the Proceedings of the International Workshop in Game Design and Technology, Liverpool, England, Nov. 15-16, 2004. [pdf]


We describe a simple and efficient dynamic occlusion culling algorithm for computing potentially visible sets (PVS) in densely occluded virtual environments. Our method is an optimization of a widely used technique in which a 3D environment is divided into cells and portals. Our algorithm computes the PVS in approximately half the time of previous portal methods at the expense of producing a slightly relaxed PVS. In addition, our algorithm enables fast culling of objects within cells using inexpensive object space methods by using a lookup table to compute the diminished object space view frustum. The algorithm takes advantage of temporal coherence, is easy to implement, and is particularly well suited for applications that need to compute a PVS for use in non-rendering tasks such as AI.

Subhunt (1997)


Ian Parberry and William R. Pensyl, "Subhunt: A Submarine Action Game", Unpublished Manuscript, 1997. [pdf]


Subhunt is a 2.5D, sprite based, real-time, first-person, single-player submarine action game produced by faculty and students at the University of North Texas. Players find themselves piloting a submarine with the task of locating and destroying enemy shipping while managing critical resources and trying not to get killed. Visual and audio cues create the illusion of action that allows the player to become completely immersed in the Subhunt virtual world.

Author's Comment

We couldn't find any place to publish this in 1997. After all, it reads more like a manual than an academic paper. Pity.

Created April 20, 2010. Written in HTML 4.01 and CSS 2.1 using vi. July 22, 2015.

Valid HTML 4.01 Strict Valid CSS!