Procedural Generation of Isometric Racetracks Using Chain Code for Racing Games
Resumo
In this work, we propose a procedural generation method for railroad circuits based on the chain code algorithm.The process creates a list with directions in a two-dimensional space from a series of operations using the chain code and imagesof predefined real tracks. This list was used in the Unity engine to provide the positions, starting from a predefined starting point, which will insert the elements of the circuit during its creation. The race track format still goes through a preprocessing method to filter the ladder effect generated by the chain code andfine-tune details before being simulated in a game. This allow seach track to have a unique pattern and good gameplay. Testscarried out using our generation method in a 2D (two dimensions) isometric kart game showed that in all runs, the tracks had anaverage of 98.5% difference among them and maintained the gameplay standards.
Palavras-chave:
racetracks, racing games, chain code, procedural generation, 2D games
Referências
G. M. Costa and T. B. Borchartt, "Procedural terrain generator for platform games using Markov chain," in 17th Brazilian Symp. on Comp. G. and Digi. Ent., Foz do Iguaçu, PR, BR, Eds. Oct. 2018, pp. 671-674.
E. J. F. do Nascimento, D. V. Cavalcante, A. C. S. Abreu, D. P. P. Mesquita, and A. H. de S. Júnior, "Classificando Graus de Pterígio Utilizando Aprendizado de Máquina," in Journal of Health Informatics, Foz do Iguaçu, PR, BR, vol. 12, Dez. 2021, pp. 248-253.
E. S. Lima, B. Feijó, and A. L. Furtado, "Procedural Generation of Quests for Games Using Genetic Algorithms and Automated Planning," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 495-504.
Y. R. Serpa and M. A. F. Rodrigues, "Towards Machine-Learning Assisted Asset Generation for Games: A Study on Pixel Art Sprite Sheets," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 533-542.
P. Dam, F. Duarte, and A. Raposo, "Terrain Generation Based on Real World Locations for Military Training and Simulation," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 524-532.
Y. H. Pereira, R. Ueda, L. B. Galhardi, and J. D. Brancher, "Using Procedural Content Generation for Storytelling in a Serious Game Called Orange Care," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 543-548.
A. M. Connor, T. J. Greig, and J. Kruse, "Evaluating the Impact of Procedurally Generated Content on Game Immersion," The Computer Games Journal, vol. 6, pp. 1-17, Dec. 2017, doi:10.1007/s40869-017-0043-6.
A. V. C. Junior, "Uma ferramenta de auxílio ao designer na Geração Procedimental de Conteúdo para jogos de corrida," M.S. thesis, Univ. Fed. de Pernambuco, Recife, PE, BR, 2017. [Online]. Available: https://repositorio.ufpe.br/handle/123456789/29387
R. V. D. Ploeg, "Modeling Race Track Difficulty in Racing Games," MSc thesis, Dept. Inf. Comp. Sci., Univ. Utrecht, Utrecht, NLD, 2015. [Online]. Available: http://dspace.library.uu.nl/handle/1874/317764
E. Galin, A. Peytavie, N. Maréchal, and E. Guérin, "Procedural generation of roads," Comp. Graph. Forum, vol. 29, no. 2, pp. 429-438, Jun. 2010, doi: 10.1111/j.1467-8659.2009.01612.x.
Y. K. Liu and B. Žalik, "An efficient chain code with Huffman coding," Pattern Recognition, vol. 38, pp. 553-557, Apr. 2005, doi: 10.1016/j.patcog.2004.08.017.
E. Bribiesca, "A chain code for representing 3D curves," Pattern Recognition, vol. 33, pp. 755-765, May. 2000, doi: 10.1016/S0031-3203(99)00093-X.
P. Karczmarek, A. Kiersztyn, W. Pedrycz, and M. Dolecki, "An application of chain code-based local descriptor and its extension to face recognition," Pattern Recognition, vol. 65, pp. 26-34, Dec. 2016, doi: 10.1016/j.patcog.2016.12.008.
T. Poiker and D.H. Douglas, "Reflection Essay: Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature," Class. in Cart.: Reflec. on Influe. Art. from Cartographica, vol. 10, pp. 29-36, Mar. 2011, doi: 10.1002/9780470669488.ch3.
IGN Entertainment. "the history of racing games" ign.com. http://uk-microsites.ign.com/the-history-of-racing-games/ (accessed Jul. 1, 2021).
K. Graft. “Game Tech Deep Dive: Reworking the Unreal Engine for racing.” gamedeveloper.com. [link]. (accessed Jul. 1, 2021).
N. Shaker, J. Togelius, and M. Nelson, "Constructive generation methods for dungeons and levels" in Procedural Content Generation In Games, 1th Ed. Gewerbestr, CH: Springer Int. Pub., 2016, pp. 55–70.
J. Togelius, R. De Nardi, and S.M. Lucas, "Making racing fun through player modeling and track evolution," In G.N. Yannakakis and J. Hallam, Adaptive Approaches for Optimizing Player Satisfaction in Computer and Physical Games: Proceedings of the SAB’06 Workshop, Oct 2006, pp. 61-70. Available: http://yannakakis.net/wp-content/uploads/2012/02/Proceedings.pdf
R. Koster, "Different Fun For Different Folks," in Theory of Fun for Game Design, 2th ed. Sebastopol, CA, USA: O'Reilly Media, 2013, pp. 102-111.
E. A. D. Nintendo, "Super Mario Kart Instruction Booklet." nintendo.com. https://www.nintendo.co.jp/clvs/manuals/common/pdf/CLV-P-SAAFE.pdf (accessed May. 12 2021).
J. Togelius, R. De Nardi, and S. M. Lucas, "Towards automatic personalised content creation for racing games," 2007 IEEE Symposium on Computational Intelligence and Games, 2007, pp. 252-259, doi: 10.1109/CIG.2007.368106.
H. Freeman, "On the Encoding of Arbitrary Geometric Configurations," in IRE Transactions on Electronic Computers, vol. EC-10, no. 2, pp. 260-268, June 1961, doi: 10.1109/TEC.1961.5219197.
B. Žalik, D. Mongus, N. Lukač, and K. R. Žalik, "Efficient chain code compression with interpolative coding," in Information Sciences, vol. 439-440, pp. 39-49, May 2018, doi:10.1016/j.ins.2018.01.045.
M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup, "Procedural content generation for games: A survey," in ACM Transactions on Multimedia Computing, Communications, and Applications, vol. 9, pp. 1-22, Fev. 2013, doi: 10.1145/2422956.2422957.
K. Dhou and C. Cruzen, "An Innovative Chain Coding Technique for Compression Based on the Concept of Biological Reproduction: An Agent-Based Modeling Approach," in IEEE Internet of Things Journal, vol. 6, no. 6, pp. 9308-9315, Dec. 2019, doi: 10.1109/JIOT.2019.2912984.
A. N. Azmi, D. Nasien, and F. S. Omar, "Biometric signature verification system based on freeman chain code and k-nearest neighbor," in Multimedia Tools and Applications, vol. 76, pp. 1-15, Jul. 2017, doi: 10.1007/s11042-016-3831-2.
P. Karczmarek, A. Kiersztyn, W. Pedrycz, and M. Dolecki, "An application of chain code-based local descriptor and its extension to face recognition," in Pattern Recognition, vol. 65, pp. 26-34, Dec. 2016, doi: 10.1016/j.patcog.2016.12.008.
U. Ramer, "An iterative procedure for the polygonal approximation of plane curves," in Computer Graphics and Image Processing, vol. 1, pp. 244–256, Jul. 1972, doi:10.1016/s0146–664x(72)80017–0.
E. J. F. do Nascimento, D. V. Cavalcante, A. C. S. Abreu, D. P. P. Mesquita, and A. H. de S. Júnior, "Classificando Graus de Pterígio Utilizando Aprendizado de Máquina," in Journal of Health Informatics, Foz do Iguaçu, PR, BR, vol. 12, Dez. 2021, pp. 248-253.
E. S. Lima, B. Feijó, and A. L. Furtado, "Procedural Generation of Quests for Games Using Genetic Algorithms and Automated Planning," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 495-504.
Y. R. Serpa and M. A. F. Rodrigues, "Towards Machine-Learning Assisted Asset Generation for Games: A Study on Pixel Art Sprite Sheets," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 533-542.
P. Dam, F. Duarte, and A. Raposo, "Terrain Generation Based on Real World Locations for Military Training and Simulation," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 524-532.
Y. H. Pereira, R. Ueda, L. B. Galhardi, and J. D. Brancher, "Using Procedural Content Generation for Storytelling in a Serious Game Called Orange Care," in 18th Brazilian Symp. on Computer G. and Digi. Ent., Rio de Janeiro, RJ, BR, Eds. Oct. 2019, pp. 543-548.
A. M. Connor, T. J. Greig, and J. Kruse, "Evaluating the Impact of Procedurally Generated Content on Game Immersion," The Computer Games Journal, vol. 6, pp. 1-17, Dec. 2017, doi:10.1007/s40869-017-0043-6.
A. V. C. Junior, "Uma ferramenta de auxílio ao designer na Geração Procedimental de Conteúdo para jogos de corrida," M.S. thesis, Univ. Fed. de Pernambuco, Recife, PE, BR, 2017. [Online]. Available: https://repositorio.ufpe.br/handle/123456789/29387
R. V. D. Ploeg, "Modeling Race Track Difficulty in Racing Games," MSc thesis, Dept. Inf. Comp. Sci., Univ. Utrecht, Utrecht, NLD, 2015. [Online]. Available: http://dspace.library.uu.nl/handle/1874/317764
E. Galin, A. Peytavie, N. Maréchal, and E. Guérin, "Procedural generation of roads," Comp. Graph. Forum, vol. 29, no. 2, pp. 429-438, Jun. 2010, doi: 10.1111/j.1467-8659.2009.01612.x.
Y. K. Liu and B. Žalik, "An efficient chain code with Huffman coding," Pattern Recognition, vol. 38, pp. 553-557, Apr. 2005, doi: 10.1016/j.patcog.2004.08.017.
E. Bribiesca, "A chain code for representing 3D curves," Pattern Recognition, vol. 33, pp. 755-765, May. 2000, doi: 10.1016/S0031-3203(99)00093-X.
P. Karczmarek, A. Kiersztyn, W. Pedrycz, and M. Dolecki, "An application of chain code-based local descriptor and its extension to face recognition," Pattern Recognition, vol. 65, pp. 26-34, Dec. 2016, doi: 10.1016/j.patcog.2016.12.008.
T. Poiker and D.H. Douglas, "Reflection Essay: Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature," Class. in Cart.: Reflec. on Influe. Art. from Cartographica, vol. 10, pp. 29-36, Mar. 2011, doi: 10.1002/9780470669488.ch3.
IGN Entertainment. "the history of racing games" ign.com. http://uk-microsites.ign.com/the-history-of-racing-games/ (accessed Jul. 1, 2021).
K. Graft. “Game Tech Deep Dive: Reworking the Unreal Engine for racing.” gamedeveloper.com. [link]. (accessed Jul. 1, 2021).
N. Shaker, J. Togelius, and M. Nelson, "Constructive generation methods for dungeons and levels" in Procedural Content Generation In Games, 1th Ed. Gewerbestr, CH: Springer Int. Pub., 2016, pp. 55–70.
J. Togelius, R. De Nardi, and S.M. Lucas, "Making racing fun through player modeling and track evolution," In G.N. Yannakakis and J. Hallam, Adaptive Approaches for Optimizing Player Satisfaction in Computer and Physical Games: Proceedings of the SAB’06 Workshop, Oct 2006, pp. 61-70. Available: http://yannakakis.net/wp-content/uploads/2012/02/Proceedings.pdf
R. Koster, "Different Fun For Different Folks," in Theory of Fun for Game Design, 2th ed. Sebastopol, CA, USA: O'Reilly Media, 2013, pp. 102-111.
E. A. D. Nintendo, "Super Mario Kart Instruction Booklet." nintendo.com. https://www.nintendo.co.jp/clvs/manuals/common/pdf/CLV-P-SAAFE.pdf (accessed May. 12 2021).
J. Togelius, R. De Nardi, and S. M. Lucas, "Towards automatic personalised content creation for racing games," 2007 IEEE Symposium on Computational Intelligence and Games, 2007, pp. 252-259, doi: 10.1109/CIG.2007.368106.
H. Freeman, "On the Encoding of Arbitrary Geometric Configurations," in IRE Transactions on Electronic Computers, vol. EC-10, no. 2, pp. 260-268, June 1961, doi: 10.1109/TEC.1961.5219197.
B. Žalik, D. Mongus, N. Lukač, and K. R. Žalik, "Efficient chain code compression with interpolative coding," in Information Sciences, vol. 439-440, pp. 39-49, May 2018, doi:10.1016/j.ins.2018.01.045.
M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup, "Procedural content generation for games: A survey," in ACM Transactions on Multimedia Computing, Communications, and Applications, vol. 9, pp. 1-22, Fev. 2013, doi: 10.1145/2422956.2422957.
K. Dhou and C. Cruzen, "An Innovative Chain Coding Technique for Compression Based on the Concept of Biological Reproduction: An Agent-Based Modeling Approach," in IEEE Internet of Things Journal, vol. 6, no. 6, pp. 9308-9315, Dec. 2019, doi: 10.1109/JIOT.2019.2912984.
A. N. Azmi, D. Nasien, and F. S. Omar, "Biometric signature verification system based on freeman chain code and k-nearest neighbor," in Multimedia Tools and Applications, vol. 76, pp. 1-15, Jul. 2017, doi: 10.1007/s11042-016-3831-2.
P. Karczmarek, A. Kiersztyn, W. Pedrycz, and M. Dolecki, "An application of chain code-based local descriptor and its extension to face recognition," in Pattern Recognition, vol. 65, pp. 26-34, Dec. 2016, doi: 10.1016/j.patcog.2016.12.008.
U. Ramer, "An iterative procedure for the polygonal approximation of plane curves," in Computer Graphics and Image Processing, vol. 1, pp. 244–256, Jul. 1972, doi:10.1016/s0146–664x(72)80017–0.
Publicado
18/10/2021
Como Citar
NASCIMENTO, Erik Jhones F. do; CASTRO, Tassiana M.; ABREU, Ana Carolina S.; LIRA, Filipe A.; SOUZA, Amauri H..
Procedural Generation of Isometric Racetracks Using Chain Code for Racing Games. In: SIMPÓSIO BRASILEIRO DE JOGOS E ENTRETENIMENTO DIGITAL (SBGAMES), 20. , 2021, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 136-143.
