“The Connect-The-Dots family of puzzles: design and automatic generation” by Löffler, Kaiser, Kapel, Klappe, Kreveld, et al. …
Conference:
Type:
Title:
- The Connect-The-Dots family of puzzles: design and automatic generation
Session/Category Title: Games & Design
Presenter(s)/Author(s):
Moderator(s):
Abstract:
In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings.Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging “game play”, making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle –one satisfying the mentioned criteria– is computationally hard, and present several heuristic algorithms.Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.
References:
1. Amenta, N., Bern, M. W., and Eppstein, D. 1998. The crust and the beta-skeleton: Combinatorial curve reconstruction. Graphical Models and Image Processing 60, 2, 125–135. Google ScholarDigital Library
2. Aspvall, B., Plass, M. F., and Tarjan, R. E. 1979. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8, 3, 121–123.Google ScholarCross Ref
3. Brodal, G. S., and Jacob, R. 2002. Dynamic planar convex hull. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, IEEE, 617–626. Google ScholarDigital Library
4. Browne, C. 2011. Evolutionary Game Design. SpringerBriefs in Computer Science. Springer.Google Scholar
5. Burch, M., Vehlow, C., Konevtsova, N., and Weiskopf, D. 2011. Evaluating partially drawn links for directed graph edges. In Graph Drawing – 19th International Symposium, GD 2011, Springer, vol. 7034 of Lecture Notes in Computer Science, 226–237. Google ScholarDigital Library
6. Chan, W. S., and Chin, F. 1996. Approximation of polygonal curves with minimum number of line segments or minimum error. Int. J. Comput. Geometry Appl. 6, 1, 59–77.Google ScholarCross Ref
7. Christensen, J., Marks, J., and Shieber, S. 1995. An empirical study of algorithms for point-feature label placement. ACM Trans. Graphics 14, 3, 203–232. Google ScholarDigital Library
8. Colton, S. 2002. Automated puzzle generation. In Proceedings of the AISB’02 Symposium on AI and Creativity in the Arts and Science.Google Scholar
9. de Berg, M., van Kreveld, M., and Schirra, S. 1998. Topologically correct subdivision simplification using the bandwidth criterion. Cartography and Geographic Information Systems 25, 243–257.Google ScholarCross Ref
10. Dey, T. K., Mehlhorn, K., and Ramos, E. A. 2000. Curve reconstruction: Connecting dots with good reason. Comput. Geom. 15, 4, 229–244. Google ScholarDigital Library
11. Douglas, D. H., and Peucker, T. K. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization 10, 2, 112–122.Google ScholarCross Ref
12. Estkowski, R., and Mitchell, J. S. B. 2001. Simplifying a polygonal subdivision while keeping it simple. In Proc. 17th Annu. ACM Symposium on Computational Geometry, 40–49. Google ScholarDigital Library
13. Guibas, L. J., Hershberger, J., Mitchell, J. S. B., and Snoeyink, J. 1993. Approximating polygons and subdivisions with minimum link paths. Int. J. Comput. Geometry Appl. 3, 4, 383–415.Google ScholarCross Ref
14. Harborth, H. 1994. Match sticks in the plane. In The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, R. K. Guy and R. E. Woodrow, Eds. Mathematical Association of America, Washington DC, 281288.Google Scholar
15. Hendrikx, M., Meijer, S., Velden, J. V. D., and Iosup, A. 2013. Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications 9, 1, 1–24. Google ScholarDigital Library
16. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. A., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In SIGGRAPH, ACM, J. J. Thomas, Ed., 71–78. Google ScholarDigital Library
17. Imai, H., and Iri, M. 1988. Polygonal approximations of a curve formulations and algorithms. In Computational Morphology, Elsevier Science, 71–86.Google Scholar
18. Jin, J.-H., Shin, H. J., and Choi, J.-J. 2013. SPOID: a system to produce spot-the-difference puzzle images with difficulty. The Visual Computer 29, 6–8, 481–489. Google ScholarDigital Library
19. O’Rourke, J., Booth, H., and Washington, R. 1987. Connect-the-dots: A new heuristic. Computer Vision, Graphics, and Image Processing 39, 258–266. Google ScholarDigital Library
20. Ortíz-Garćia, E. G., Salcedo-Sanz, S., Leiva-Murillo, J. M., Pérez-Bellido, Á. M., and Portilla-Figueras, J. A. 2007. Automated generation and visualization of picture-logic puzzles. Computers & Graphics 31, 5, 750–760. Google ScholarDigital Library
21. Paterson, M., and Yao, F. F. 1992. On nearest-neighbor graphs. In ICALP, Springer, W. Kuich, Ed., vol. 623 of Lecture Notes in Computer Science, 416–426. Google ScholarDigital Library
22. Xu, J., and Kaplan, C. S. 2007. Image-guided maze construction. ACM Trans. Graph. 26, 3, 29. Google ScholarDigital Library
23. Yoon, J.-C., Lee, I.-K., and Kang, H. 2008. A hidden-picture puzzles generator. Comput. Graph. Forum 27, 7, 1869–1877.Google ScholarCross Ref
