Christopher Jefferson
Wendy Moncur
ABSTRACT
Constraint Programming offers a powerful means of solving a wide variety of combinatorial problems. We have used this powerful paradigm to create a successful computer game called Combination. Combination is an application for the iPhone and iPod touch. It has been on sale internationally through the iTunes store since December, 2008 and received a number of positive reviews.
In this paper we explain how all the levels of Combination were generated, checked for correctness and rated for difficulty completely automatically through the use of constraints. We go on to evaluate this method of creation with the use of a human evaluation. This showed that fun, immersing computer games can be created with constraint programming.
- C. Bessiere and R. Debruyne. Theoretical analysis of singleton arc consistency and its extensions. Artif. Intell., 172: 29--41, January 2008. Google Scholar
Digital Library
- M. Federoff. Heuristics and usability guidelines for the creation and evaluation of fun in video games. Unpublished Master of Science, Indiana University, 2002.Google Scholar
- I. P. Gent, S. Linton, and B. M. Smith. Symmetry breaking in the alien tiles puzzle. Report APES-22-2000, 2000.Google Scholar
- R. Haralik and G. Elliott. Increasing tree efficiency for constraint satisfaction problems. Artificial Intelligence, 14: 263--313, 1980.Google ScholarCross Ref
- C. Jennett, A. L. Cox, P. Cairns, S. Dhoparee, A. Epps, and T. Tijis. Measuring and defining the experience of immersion in games. International Journal of Human-Computer Studies, 66: 641--661, 2008. Google ScholarDigital Library
- J. Lauriere. A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10: 29--127, 1978.Google ScholarCross Ref
- R. L. Mandryk and K. M. Inkpen. Physiological indicators for the evaluation of co-located collaborative play. Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 102--111, 2004. Google ScholarDigital Library
- J.-C. Régin. Generalized arc consistency for global cardinality constraint. In AAAI/IAAI, Vol. 1, pages 209--215, 1996. Google ScholarDigital Library
- I. Shlyakhter. Generating effective symmetry-breaking predicates for search problems. Discrete Appl. Math., 155(12): 1539--1548, 2007. Google ScholarDigital Library
- H. Simonis. Sudoku as a constraint problem. Proceedings of the Modelling Workshop at CP, 2005.Google Scholar
- H. Simonis. Kakuro as a constraint problem. Proceedings of the Modref Workshop at CP, 2008.Google Scholar
- H. Simonis. Shikaku as a constraint problem. CSCLP 2009, 2009.Google Scholar
- B. M. Smith, K. E. Petrie, and I. P. Gent. Models and symmetry breaking for peaceable armies of queens. Proceedings of CPAIOR, Springer LNCS 3011: 271--286, 2004.Google Scholar
Index Terms
- Combination: automated generation of puzzles with constraints
Comments