Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm
Search and planning is a common Artificial Intelligence task on videogames development. This exercise covers the design of Non-player character (NPC) behavior, content generation, and narrative's construction. This work focus on NPC behavior, specifically on path planning. This paper presents a...
- Autores:
-
Ortega Vargas, Álvaro José
Castellanos Acuña, Leonardo
Martínez Santos, Juan Carlos
Serrano Castañeda, Jairo Enrique
- Tipo de recurso:
- Conferencia (Ponencia)
- Fecha de publicación:
- 2020
- Institución:
- Universidad Tecnológica de Bolívar
- Repositorio:
- Repositorio Institucional UTB
- Idioma:
- eng
- OAI Identifier:
- oai:repositorio.utb.edu.co:20.500.12585/10003
- Acceso en línea:
- https://hdl.handle.net/20.500.12585/10003
https://ieeexplore.ieee.org/document/9256835
- Palabra clave:
- NPC behavior
Game Development
Unity3D
Artificial Intelligence
Path Planning
LEMB
- Rights
- closedAccess
- License
- http://purl.org/coar/access_right/c_14cb
| id |
UTB2_e5905316d52dc3b89c2733a08960b267 |
|---|---|
| oai_identifier_str |
oai:repositorio.utb.edu.co:20.500.12585/10003 |
| network_acronym_str |
UTB2 |
| network_name_str |
Repositorio Institucional UTB |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| title |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| spellingShingle |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm NPC behavior Game Development Unity3D Artificial Intelligence Path Planning LEMB |
| title_short |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| title_full |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| title_fullStr |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| title_full_unstemmed |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| title_sort |
Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm |
| dc.creator.fl_str_mv |
Ortega Vargas, Álvaro José Castellanos Acuña, Leonardo Martínez Santos, Juan Carlos Serrano Castañeda, Jairo Enrique |
| dc.contributor.author.none.fl_str_mv |
Ortega Vargas, Álvaro José Castellanos Acuña, Leonardo Martínez Santos, Juan Carlos Serrano Castañeda, Jairo Enrique |
| dc.subject.keywords.spa.fl_str_mv |
NPC behavior Game Development Unity3D Artificial Intelligence Path Planning |
| topic |
NPC behavior Game Development Unity3D Artificial Intelligence Path Planning LEMB |
| dc.subject.armarc.none.fl_str_mv |
LEMB |
| description |
Search and planning is a common Artificial Intelligence task on videogames development. This exercise covers the design of Non-player character (NPC) behavior, content generation, and narrative's construction. This work focus on NPC behavior, specifically on path planning. This paper presents an implementation of an arcade videogame (Ms. Pacman type) with Unity, where the NPC's behavior (Ghosts) applies the Wavefront algorithm to find the shortest path to the Player Character (Mr. Pacman). This algorithm is an alternative to traditional algorithms the Djikstra algorithm and A-star used to solve this problem. |
| publishDate |
2020 |
| dc.date.issued.none.fl_str_mv |
2020-11-18 |
| dc.date.accessioned.none.fl_str_mv |
2021-02-15T16:21:48Z |
| dc.date.available.none.fl_str_mv |
2021-02-15T16:21:48Z |
| dc.date.submitted.none.fl_str_mv |
2021-02-12 |
| dc.type.spa.fl_str_mv |
Documento de Conferencia |
| dc.type.coarversion.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/lecture |
| dc.type.hasversion.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_8544 |
| format |
http://purl.org/coar/resource_type/c_8544 |
| status_str |
publishedVersion |
| dc.identifier.citation.spa.fl_str_mv |
Á. J. O. Vargas, J. E. C. Serrano, L. C. Acuña and J. C. Martinez-Santos, "Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm," 2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX), Barranquilla, Colombia, 2020, pp. 1-5, doi: 10.1109/GMAX49668.2020.9256835. |
| dc.identifier.uri.none.fl_str_mv |
https://hdl.handle.net/20.500.12585/10003 |
| dc.identifier.url.none.fl_str_mv |
https://ieeexplore.ieee.org/document/9256835 |
| dc.identifier.doi.none.fl_str_mv |
10.1109/GMAX49668.2020.9256835 |
| dc.identifier.instname.spa.fl_str_mv |
Universidad Tecnológica de Bolívar |
| dc.identifier.reponame.spa.fl_str_mv |
Repositorio Universidad Tecnológica de Bolívar |
| identifier_str_mv |
Á. J. O. Vargas, J. E. C. Serrano, L. C. Acuña and J. C. Martinez-Santos, "Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm," 2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX), Barranquilla, Colombia, 2020, pp. 1-5, doi: 10.1109/GMAX49668.2020.9256835. 10.1109/GMAX49668.2020.9256835 Universidad Tecnológica de Bolívar Repositorio Universidad Tecnológica de Bolívar |
| url |
https://hdl.handle.net/20.500.12585/10003 https://ieeexplore.ieee.org/document/9256835 |
| dc.language.iso.spa.fl_str_mv |
eng |
| language |
eng |
| dc.rights.coar.fl_str_mv |
http://purl.org/coar/access_right/c_14cb |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/closedAccess |
| eu_rights_str_mv |
closedAccess |
| rights_invalid_str_mv |
http://purl.org/coar/access_right/c_14cb |
| dc.format.extent.none.fl_str_mv |
5 páginas |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.place.spa.fl_str_mv |
Cartagena de Indias |
| dc.source.spa.fl_str_mv |
2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX) |
| institution |
Universidad Tecnológica de Bolívar |
| bitstream.url.fl_str_mv |
https://repositorio.utb.edu.co/bitstreams/3aa330dc-91be-44e7-91dd-16162fc274e4/download https://repositorio.utb.edu.co/bitstreams/71c72bc1-0271-4956-9f36-1f36b6d1dfbf/download https://repositorio.utb.edu.co/bitstreams/1ee95620-a64b-470f-8a9a-a06feb2d66d2/download https://repositorio.utb.edu.co/bitstreams/b616db1e-a61b-4152-80f7-0126557c9757/download |
| bitstream.checksum.fl_str_mv |
c5b84c86f117e755f38b6221168d36bf e20ad307a1c5f3f25af9304a7a7c86b6 89bb6f3b2b30873298b8f40a07af01b0 1e37e329cdc71eeef359eb405bbd73ef |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Digital Universidad Tecnológica de Bolívar |
| repository.mail.fl_str_mv |
bdigital@metabiblioteca.com |
| _version_ |
1858228400351608832 |
| spelling |
Ortega Vargas, Álvaro Joséf700d5ce-e294-4b4d-a893-735584549326Castellanos Acuña, Leonardo1525fb10-689f-4996-84d8-7f97bfd9c131Martínez Santos, Juan Carlosvirtual::2115-1Serrano Castañeda, Jairo Enriquevirtual::2723-12021-02-15T16:21:48Z2021-02-15T16:21:48Z2020-11-182021-02-12Á. J. O. Vargas, J. E. C. Serrano, L. C. Acuña and J. C. Martinez-Santos, "Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront Algorithm," 2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX), Barranquilla, Colombia, 2020, pp. 1-5, doi: 10.1109/GMAX49668.2020.9256835.https://hdl.handle.net/20.500.12585/10003https://ieeexplore.ieee.org/document/925683510.1109/GMAX49668.2020.9256835Universidad Tecnológica de BolívarRepositorio Universidad Tecnológica de BolívarSearch and planning is a common Artificial Intelligence task on videogames development. This exercise covers the design of Non-player character (NPC) behavior, content generation, and narrative's construction. This work focus on NPC behavior, specifically on path planning. This paper presents an implementation of an arcade videogame (Ms. Pacman type) with Unity, where the NPC's behavior (Ghosts) applies the Wavefront algorithm to find the shortest path to the Player Character (Mr. Pacman). This algorithm is an alternative to traditional algorithms the Djikstra algorithm and A-star used to solve this problem.5 páginasapplication/pdfeng2020 IEEE Games, Multimedia, Animation and Multiple Realities Conference (GMAX)Path Planning for Non-Playable Characters in Arcade Video Games using the Wavefront AlgorithmDocumento de Conferenciainfo:eu-repo/semantics/lectureinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_8544http://purl.org/coar/version/c_970fb48d4fbd8a85NPC behaviorGame DevelopmentUnity3DArtificial IntelligencePath PlanningLEMBinfo:eu-repo/semantics/closedAccesshttp://purl.org/coar/access_right/c_14cbCartagena de IndiasInvestigadoresGN Yannakakis y J. Togelius, "Un panorama de la inteligencia artificial y computacional en los juegos", IEEE Transactions on Computational Intelligence and AI in Games , vol. 7, no. 4, págs. 317-335, 2014.Y. Zhen, Z. Wanpeng y L. Hongfu, "Técnicas de inteligencia artificial en juegos de estrategia en tiempo real", Actas de la 2a Conferencia Internacional de Ciencias de la Computación e Inteligencia Artificial de 2018, págs. 11-21, 2018.PE Hart, NJ Nilsson y B. Raphael, "Una base formal para la determinación heurística de rutas de costo mínimo", transacciones IEEE sobre ciencia de sistemas y cibernética , vol. 4, no. 2, págs. 100-107, 1968.X. Cui y H. Shi, "Una búsqueda de caminos basada en * en los juegos de computadora modernos", Revista Internacional de Ciencias de la Computación y Seguridad de Redes , vol. 11, no. 1, págs. 125-130, 2011PI Cowling, M. Buro, M. Bida, A. Botea, B. Bouzy, MV Butz, et al., "Search in real-time video games", Artificial and Computational Intelligence in Games , 2013.V. Bulitko, Y. Björnsson, NR Sturtevant y R. Lawrence, "Búsqueda heurística en tiempo real para encontrar rutas en videojuegos", Inteligencia artificial para juegos de computadora , págs. 1-30, 2011.IM Zidane y K. Ibrahim, "Wavefront y algoritmos estrella para la planificación de trayectorias de robots móviles", Conferencia internacional sobre sistemas inteligentes avanzados e informática , págs. 69-80, 2017.A. Mittal, A. Jain, A. Kumar y R. Tiwari, "Persecución-evasión: El perseguidor múltiple persigue al evasor múltiple usando el frente de onda y el método húngaro", Actas de la Conferencia Internacional sobre Sistemas de Computación y Comunicación , págs. 473- 488, 2018.C. Tang, R. Sun, S. Yu, L. Chen y J. Zheng, "Exploración autónoma de robots móviles de interior basada en el algoritmo de frente de onda", Conferencia internacional sobre robótica inteligente y aplicaciones , págs. 338-348, 2019H. Carbajal Montesinos, "Constructión de un componente de software para la búsqueda del camino más corto y el control de movimiento en un videojuego de estrategia en tiempo real", Pontificia Universidad Católica del Perú , abril de 2017.D. Rico Zambrana, Análisis de algoritmos de inteligencia artificial para videojuegos, marzo de 2017.Compl50-07: Algoritmo de planificación de frente de onda de robótica inteligente, 2009.http://purl.org/coar/resource_type/c_c94fPublication35de2f55-a620-47ac-97f2-9961adeac601virtual::2115-1db6967a8-73d5-4623-92c5-5e62d5ad495cvirtual::2723-135de2f55-a620-47ac-97f2-9961adeac601virtual::2115-1db6967a8-73d5-4623-92c5-5e62d5ad495cvirtual::2723-1ORIGINAL163.pdf163.pdfAbstractapplication/pdf82884https://repositorio.utb.edu.co/bitstreams/3aa330dc-91be-44e7-91dd-16162fc274e4/downloadc5b84c86f117e755f38b6221168d36bfMD51trueAnonymousREADLICENSElicense.txtlicense.txttext/plain; charset=utf-83182https://repositorio.utb.edu.co/bitstreams/71c72bc1-0271-4956-9f36-1f36b6d1dfbf/downloade20ad307a1c5f3f25af9304a7a7c86b6MD52falseAnonymousREADTEXT163.pdf.txt163.pdf.txtExtracted texttext/plain733https://repositorio.utb.edu.co/bitstreams/1ee95620-a64b-470f-8a9a-a06feb2d66d2/download89bb6f3b2b30873298b8f40a07af01b0MD53falseAnonymousREADTHUMBNAIL163.pdf.jpg163.pdf.jpgGenerated Thumbnailimage/jpeg39041https://repositorio.utb.edu.co/bitstreams/b616db1e-a61b-4152-80f7-0126557c9757/download1e37e329cdc71eeef359eb405bbd73efMD54falseAnonymousREAD20.500.12585/10003oai:repositorio.utb.edu.co:20.500.12585/100032025-05-23 14:31:55.204open.accesshttps://repositorio.utb.edu.coRepositorio Digital Universidad Tecnológica de Bolívarbdigital@metabiblioteca.comQXV0b3Jpem8gKGF1dG9yaXphbW9zKSBhIGxhIEJpYmxpb3RlY2EgZGUgbGEgSW5zdGl0dWNpw7NuIHBhcmEgcXVlIGluY2x1eWEgdW5hIGNvcGlhLCBpbmRleGUgeSBkaXZ1bGd1ZSBlbiBlbCBSZXBvc2l0b3JpbyBJbnN0aXR1Y2lvbmFsLCBsYSBvYnJhIG1lbmNpb25hZGEgY29uIGVsIGZpbiBkZSBmYWNpbGl0YXIgbG9zIHByb2Nlc29zIGRlIHZpc2liaWxpZGFkIGUgaW1wYWN0byBkZSBsYSBtaXNtYSwgY29uZm9ybWUgYSBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBxdWUgbWUobm9zKSBjb3JyZXNwb25kZShuKSB5IHF1ZSBpbmNsdXllbjogbGEgcmVwcm9kdWNjacOzbiwgY29tdW5pY2FjacOzbiBww7pibGljYSwgZGlzdHJpYnVjacOzbiBhbCBww7pibGljbywgdHJhbnNmb3JtYWNpw7NuLCBkZSBjb25mb3JtaWRhZCBjb24gbGEgbm9ybWF0aXZpZGFkIHZpZ2VudGUgc29icmUgZGVyZWNob3MgZGUgYXV0b3IgeSBkZXJlY2hvcyBjb25leG9zIHJlZmVyaWRvcyBlbiBhcnQuIDIsIDEyLCAzMCAobW9kaWZpY2FkbyBwb3IgZWwgYXJ0IDUgZGUgbGEgbGV5IDE1MjAvMjAxMiksIHkgNzIgZGUgbGEgbGV5IDIzIGRlIGRlIDE5ODIsIExleSA0NCBkZSAxOTkzLCBhcnQuIDQgeSAxMSBEZWNpc2nDs24gQW5kaW5hIDM1MSBkZSAxOTkzIGFydC4gMTEsIERlY3JldG8gNDYwIGRlIDE5OTUsIENpcmN1bGFyIE5vIDA2LzIwMDIgZGUgbGEgRGlyZWNjacOzbiBOYWNpb25hbCBkZSBEZXJlY2hvcyBkZSBhdXRvciwgYXJ0LiAxNSBMZXkgMTUyMCBkZSAyMDEyLCBsYSBMZXkgMTkxNSBkZSAyMDE4IHkgZGVtw6FzIG5vcm1hcyBzb2JyZSBsYSBtYXRlcmlhLgoKQWwgcmVzcGVjdG8gY29tbyBBdXRvcihlcykgbWFuaWZlc3RhbW9zIGNvbm9jZXIgcXVlOgoKLSBMYSBhdXRvcml6YWNpw7NuIGVzIGRlIGNhcsOhY3RlciBubyBleGNsdXNpdmEgeSBsaW1pdGFkYSwgZXN0byBpbXBsaWNhIHF1ZSBsYSBsaWNlbmNpYSB0aWVuZSB1bmEgdmlnZW5jaWEsIHF1ZSBubyBlcyBwZXJwZXR1YSB5IHF1ZSBlbCBhdXRvciBwdWVkZSBwdWJsaWNhciBvIGRpZnVuZGlyIHN1IG9icmEgZW4gY3VhbHF1aWVyIG90cm8gbWVkaW8sIGFzw60gY29tbyBsbGV2YXIgYSBjYWJvIGN1YWxxdWllciB0aXBvIGRlIGFjY2nDs24gc29icmUgZWwgZG9jdW1lbnRvLgoKLSBMYSBhdXRvcml6YWNpw7NuIHRlbmRyw6EgdW5hIHZpZ2VuY2lhIGRlIGNpbmNvIGHDsW9zIGEgcGFydGlyIGRlbCBtb21lbnRvIGRlIGxhIGluY2x1c2nDs24gZGUgbGEgb2JyYSBlbiBlbCByZXBvc2l0b3JpbywgcHJvcnJvZ2FibGUgaW5kZWZpbmlkYW1lbnRlIHBvciBlbCB0aWVtcG8gZGUgZHVyYWNpw7NuIGRlIGxvcyBkZXJlY2hvcyBwYXRyaW1vbmlhbGVzIGRlbCBhdXRvciB5IHBvZHLDoSBkYXJzZSBwb3IgdGVybWluYWRhIHVuYSB2ZXogZWwgYXV0b3IgbG8gbWFuaWZpZXN0ZSBwb3IgZXNjcml0byBhIGxhIGluc3RpdHVjacOzbiwgY29uIGxhIHNhbHZlZGFkIGRlIHF1ZSBsYSBvYnJhIGVzIGRpZnVuZGlkYSBnbG9iYWxtZW50ZSB5IGNvc2VjaGFkYSBwb3IgZGlmZXJlbnRlcyBidXNjYWRvcmVzIHkvbyByZXBvc2l0b3Jpb3MgZW4gSW50ZXJuZXQgbG8gcXVlIG5vIGdhcmFudGl6YSBxdWUgbGEgb2JyYSBwdWVkYSBzZXIgcmV0aXJhZGEgZGUgbWFuZXJhIGlubWVkaWF0YSBkZSBvdHJvcyBzaXN0ZW1hcyBkZSBpbmZvcm1hY2nDs24gZW4gbG9zIHF1ZSBzZSBoYXlhIGluZGV4YWRvLCBkaWZlcmVudGVzIGFsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgSW5zdGl0dWNpw7NuLCBkZSBtYW5lcmEgcXVlIGVsIGF1dG9yKHJlcykgdGVuZHLDoW4gcXVlIHNvbGljaXRhciBsYSByZXRpcmFkYSBkZSBzdSBvYnJhIGRpcmVjdGFtZW50ZSBhIG90cm9zIHNpc3RlbWFzIGRlIGluZm9ybWFjacOzbiBkaXN0aW50b3MgYWwgZGUgbGEgSW5zdGl0dWNpw7NuIHNpIGRlc2VhIHF1ZSBzdSBvYnJhIHNlYSByZXRpcmFkYSBkZSBpbm1lZGlhdG8uCgotIExhIGF1dG9yaXphY2nDs24gZGUgcHVibGljYWNpw7NuIGNvbXByZW5kZSBlbCBmb3JtYXRvIG9yaWdpbmFsIGRlIGxhIG9icmEgeSB0b2RvcyBsb3MgZGVtw6FzIHF1ZSBzZSByZXF1aWVyYSBwYXJhIHN1IHB1YmxpY2FjacOzbiBlbiBlbCByZXBvc2l0b3Jpby4gSWd1YWxtZW50ZSwgbGEgYXV0b3JpemFjacOzbiBwZXJtaXRlIGEgbGEgaW5zdGl0dWNpw7NuIGVsIGNhbWJpbyBkZSBzb3BvcnRlIGRlIGxhIG9icmEgY29uIGZpbmVzIGRlIHByZXNlcnZhY2nDs24gKGltcHJlc28sIGVsZWN0csOzbmljbywgZGlnaXRhbCwgSW50ZXJuZXQsIGludHJhbmV0LCBvIGN1YWxxdWllciBvdHJvIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2NlcikuCgotIExhIGF1dG9yaXphY2nDs24gZXMgZ3JhdHVpdGEgeSBzZSByZW51bmNpYSBhIHJlY2liaXIgY3VhbHF1aWVyIHJlbXVuZXJhY2nDs24gcG9yIGxvcyB1c29zIGRlIGxhIG9icmEsIGRlIGFjdWVyZG8gY29uIGxhIGxpY2VuY2lhIGVzdGFibGVjaWRhIGVuIGVzdGEgYXV0b3JpemFjacOzbi4KCi0gQWwgZmlybWFyIGVzdGEgYXV0b3JpemFjacOzbiwgc2UgbWFuaWZpZXN0YSBxdWUgbGEgb2JyYSBlcyBvcmlnaW5hbCB5IG5vIGV4aXN0ZSBlbiBlbGxhIG5pbmd1bmEgdmlvbGFjacOzbiBhIGxvcyBkZXJlY2hvcyBkZSBhdXRvciBkZSB0ZXJjZXJvcy4gRW4gY2FzbyBkZSBxdWUgZWwgdHJhYmFqbyBoYXlhIHNpZG8gZmluYW5jaWFkbyBwb3IgdGVyY2Vyb3MgZWwgbyBsb3MgYXV0b3JlcyBhc3VtZW4gbGEgcmVzcG9uc2FiaWxpZGFkIGRlbCBjdW1wbGltaWVudG8gZGUgbG9zIGFjdWVyZG9zIGVzdGFibGVjaWRvcyBzb2JyZSBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBkZSBsYSBvYnJhIGNvbiBkaWNobyB0ZXJjZXJvLgoKLSBGcmVudGUgYSBjdWFscXVpZXIgcmVjbGFtYWNpw7NuIHBvciB0ZXJjZXJvcywgZWwgbyBsb3MgYXV0b3JlcyBzZXLDoW4gcmVzcG9uc2FibGVzLCBlbiBuaW5nw7puIGNhc28gbGEgcmVzcG9uc2FiaWxpZGFkIHNlcsOhIGFzdW1pZGEgcG9yIGxhIGluc3RpdHVjacOzbi4KCi0gQ29uIGxhIGF1dG9yaXphY2nDs24sIGxhIGluc3RpdHVjacOzbiBwdWVkZSBkaWZ1bmRpciBsYSBvYnJhIGVuIMOtbmRpY2VzLCBidXNjYWRvcmVzIHkgb3Ryb3Mgc2lzdGVtYXMgZGUgaW5mb3JtYWNpw7NuIHF1ZSBmYXZvcmV6Y2FuIHN1IHZpc2liaWxpZGFkCgo= |