A real-time collision detection algorithm for mobile billiards game

ABSTRACT

Collision detection is a key technique in game design. However, some algorithms employed in PC game are not suitable for mobile game because of the low performance and small screen size in mobile devices. Combining with the features of the mobile devices, this paper proposes a quick and feasible collision detection algorithm. This algorithm makes use of the multi-level collision detection and dynamic multi-resolution grid subdivision to reduce the computing time for collision detection, which improves the algorithm performance greatly. In the collision response phase, this paper adopts the time step binary search algorithm to ensure both the computing precision and system efficiency. The mobile billiards game designed for the Bird Company indicates that this algorithm has good performance and real-time interaction.

REFERENCES

• 1: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 2: Alejandro Garcia-Alonso , Nicolás Serrano , Juan Flaquer, Solving the Collision Detection Problem, IEEE Computer Graphics and Applications, v.14 n.3, p.36-43, May 1994 [doi>10.1109/38.279041]
• 3: S. K. L. F. Morgan, G. Expanding spheres: A collision detection algorithm for interest management in networked games,. ICEC 2004, 3166:435--440, 2004.
• 4: H. J. Z. M. Pan Zhigeng, Xu Weiwei and S. Jiaoying. Easybowling: a small bowling machine based on virtual simulation. Computers & Graphics, 1(27):231--238, 2003.
• 5: T. B. Pan Zhigeng and L. Powei. Pccavesmash: an immersive ping pong game. Accepted by IEEE VR2005 workshop, 2005.
• 6: Z. K. Pan Zhigeng, Zhang Mingmin. Multi-resolution modeling for virtual prototyping. IJIG, 1(2):329--343, 2001.
• 7: Z. M. L. Y. Pan Zhigeng, Ji Qingge. Simulation on pattern design and layout for group calisthenics and eurhythmics. Simulation & Gaming (accepted).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics

General Terms:
Algorithms

Keywords:
binary search, collision detection, mobile game, multi-resolution