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é
Serrano, Jairo E.C.
Castellanos Acuña, Leonardo
Martínez-Santos, Juan Carlos
- Tipo de recurso:
- 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é Serrano, Jairo E.C. Castellanos Acuña, Leonardo Martínez-Santos, Juan Carlos |
| dc.contributor.author.none.fl_str_mv |
Ortega Vargas, Álvaro José Serrano, Jairo E.C. Castellanos Acuña, Leonardo Martínez-Santos, Juan Carlos |
| 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.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.spa.spa.fl_str_mv |
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/bitstream/20.500.12585/10003/1/163.pdf https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/2/license.txt https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/3/163.pdf.txt https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/4/163.pdf.jpg |
| bitstream.checksum.fl_str_mv |
c5b84c86f117e755f38b6221168d36bf e20ad307a1c5f3f25af9304a7a7c86b6 89bb6f3b2b30873298b8f40a07af01b0 1e37e329cdc71eeef359eb405bbd73ef |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional UTB |
| repository.mail.fl_str_mv |
repositorioutb@utb.edu.co |
| _version_ |
1814021629979656192 |
| spelling |
Ortega Vargas, Álvaro Joséf700d5ce-e294-4b4d-a893-735584549326Serrano, Jairo E.C.fc39a2a7-1db9-4094-b54c-907bb4c863d0Castellanos Acuña, Leonardo1525fb10-689f-4996-84d8-7f97bfd9c131Martínez-Santos, Juan Carlos5c958644-c78d-401d-8ba9-bbd39fe773182021-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 Algorithminfo: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_c94fORIGINAL163.pdf163.pdfAbstractapplication/pdf82884https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/1/163.pdfc5b84c86f117e755f38b6221168d36bfMD51LICENSElicense.txtlicense.txttext/plain; charset=utf-83182https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/2/license.txte20ad307a1c5f3f25af9304a7a7c86b6MD52TEXT163.pdf.txt163.pdf.txtExtracted texttext/plain733https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/3/163.pdf.txt89bb6f3b2b30873298b8f40a07af01b0MD53THUMBNAIL163.pdf.jpg163.pdf.jpgGenerated Thumbnailimage/jpeg39041https://repositorio.utb.edu.co/bitstream/20.500.12585/10003/4/163.pdf.jpg1e37e329cdc71eeef359eb405bbd73efMD5420.500.12585/10003oai:repositorio.utb.edu.co:20.500.12585/100032023-05-26 16:27:20.216Repositorio Institucional UTBrepositorioutb@utb.edu.coQXV0b3Jpem8gKGF1dG9yaXphbW9zKSBhIGxhIEJpYmxpb3RlY2EgZGUgbGEgSW5zdGl0dWNpw7NuIHBhcmEgcXVlIGluY2x1eWEgdW5hIGNvcGlhLCBpbmRleGUgeSBkaXZ1bGd1ZSBlbiBlbCBSZXBvc2l0b3JpbyBJbnN0aXR1Y2lvbmFsLCBsYSBvYnJhIG1lbmNpb25hZGEgY29uIGVsIGZpbiBkZSBmYWNpbGl0YXIgbG9zIHByb2Nlc29zIGRlIHZpc2liaWxpZGFkIGUgaW1wYWN0byBkZSBsYSBtaXNtYSwgY29uZm9ybWUgYSBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBxdWUgbWUobm9zKSBjb3JyZXNwb25kZShuKSB5IHF1ZSBpbmNsdXllbjogbGEgcmVwcm9kdWNjacOzbiwgY29tdW5pY2FjacOzbiBww7pibGljYSwgZGlzdHJpYnVjacOzbiBhbCBww7pibGljbywgdHJhbnNmb3JtYWNpw7NuLCBkZSBjb25mb3JtaWRhZCBjb24gbGEgbm9ybWF0aXZpZGFkIHZpZ2VudGUgc29icmUgZGVyZWNob3MgZGUgYXV0b3IgeSBkZXJlY2hvcyBjb25leG9zIHJlZmVyaWRvcyBlbiBhcnQuIDIsIDEyLCAzMCAobW9kaWZpY2FkbyBwb3IgZWwgYXJ0IDUgZGUgbGEgbGV5IDE1MjAvMjAxMiksIHkgNzIgZGUgbGEgbGV5IDIzIGRlIGRlIDE5ODIsIExleSA0NCBkZSAxOTkzLCBhcnQuIDQgeSAxMSBEZWNpc2nDs24gQW5kaW5hIDM1MSBkZSAxOTkzIGFydC4gMTEsIERlY3JldG8gNDYwIGRlIDE5OTUsIENpcmN1bGFyIE5vIDA2LzIwMDIgZGUgbGEgRGlyZWNjacOzbiBOYWNpb25hbCBkZSBEZXJlY2hvcyBkZSBhdXRvciwgYXJ0LiAxNSBMZXkgMTUyMCBkZSAyMDEyLCBsYSBMZXkgMTkxNSBkZSAyMDE4IHkgZGVtw6FzIG5vcm1hcyBzb2JyZSBsYSBtYXRlcmlhLgoKQWwgcmVzcGVjdG8gY29tbyBBdXRvcihlcykgbWFuaWZlc3RhbW9zIGNvbm9jZXIgcXVlOgoKLSBMYSBhdXRvcml6YWNpw7NuIGVzIGRlIGNhcsOhY3RlciBubyBleGNsdXNpdmEgeSBsaW1pdGFkYSwgZXN0byBpbXBsaWNhIHF1ZSBsYSBsaWNlbmNpYSB0aWVuZSB1bmEgdmlnZW5jaWEsIHF1ZSBubyBlcyBwZXJwZXR1YSB5IHF1ZSBlbCBhdXRvciBwdWVkZSBwdWJsaWNhciBvIGRpZnVuZGlyIHN1IG9icmEgZW4gY3VhbHF1aWVyIG90cm8gbWVkaW8sIGFzw60gY29tbyBsbGV2YXIgYSBjYWJvIGN1YWxxdWllciB0aXBvIGRlIGFjY2nDs24gc29icmUgZWwgZG9jdW1lbnRvLgoKLSBMYSBhdXRvcml6YWNpw7NuIHRlbmRyw6EgdW5hIHZpZ2VuY2lhIGRlIGNpbmNvIGHDsW9zIGEgcGFydGlyIGRlbCBtb21lbnRvIGRlIGxhIGluY2x1c2nDs24gZGUgbGEgb2JyYSBlbiBlbCByZXBvc2l0b3JpbywgcHJvcnJvZ2FibGUgaW5kZWZpbmlkYW1lbnRlIHBvciBlbCB0aWVtcG8gZGUgZHVyYWNpw7NuIGRlIGxvcyBkZXJlY2hvcyBwYXRyaW1vbmlhbGVzIGRlbCBhdXRvciB5IHBvZHLDoSBkYXJzZSBwb3IgdGVybWluYWRhIHVuYSB2ZXogZWwgYXV0b3IgbG8gbWFuaWZpZXN0ZSBwb3IgZXNjcml0byBhIGxhIGluc3RpdHVjacOzbiwgY29uIGxhIHNhbHZlZGFkIGRlIHF1ZSBsYSBvYnJhIGVzIGRpZnVuZGlkYSBnbG9iYWxtZW50ZSB5IGNvc2VjaGFkYSBwb3IgZGlmZXJlbnRlcyBidXNjYWRvcmVzIHkvbyByZXBvc2l0b3Jpb3MgZW4gSW50ZXJuZXQgbG8gcXVlIG5vIGdhcmFudGl6YSBxdWUgbGEgb2JyYSBwdWVkYSBzZXIgcmV0aXJhZGEgZGUgbWFuZXJhIGlubWVkaWF0YSBkZSBvdHJvcyBzaXN0ZW1hcyBkZSBpbmZvcm1hY2nDs24gZW4gbG9zIHF1ZSBzZSBoYXlhIGluZGV4YWRvLCBkaWZlcmVudGVzIGFsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgSW5zdGl0dWNpw7NuLCBkZSBtYW5lcmEgcXVlIGVsIGF1dG9yKHJlcykgdGVuZHLDoW4gcXVlIHNvbGljaXRhciBsYSByZXRpcmFkYSBkZSBzdSBvYnJhIGRpcmVjdGFtZW50ZSBhIG90cm9zIHNpc3RlbWFzIGRlIGluZm9ybWFjacOzbiBkaXN0aW50b3MgYWwgZGUgbGEgSW5zdGl0dWNpw7NuIHNpIGRlc2VhIHF1ZSBzdSBvYnJhIHNlYSByZXRpcmFkYSBkZSBpbm1lZGlhdG8uCgotIExhIGF1dG9yaXphY2nDs24gZGUgcHVibGljYWNpw7NuIGNvbXByZW5kZSBlbCBmb3JtYXRvIG9yaWdpbmFsIGRlIGxhIG9icmEgeSB0b2RvcyBsb3MgZGVtw6FzIHF1ZSBzZSByZXF1aWVyYSBwYXJhIHN1IHB1YmxpY2FjacOzbiBlbiBlbCByZXBvc2l0b3Jpby4gSWd1YWxtZW50ZSwgbGEgYXV0b3JpemFjacOzbiBwZXJtaXRlIGEgbGEgaW5zdGl0dWNpw7NuIGVsIGNhbWJpbyBkZSBzb3BvcnRlIGRlIGxhIG9icmEgY29uIGZpbmVzIGRlIHByZXNlcnZhY2nDs24gKGltcHJlc28sIGVsZWN0csOzbmljbywgZGlnaXRhbCwgSW50ZXJuZXQsIGludHJhbmV0LCBvIGN1YWxxdWllciBvdHJvIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2NlcikuCgotIExhIGF1dG9yaXphY2nDs24gZXMgZ3JhdHVpdGEgeSBzZSByZW51bmNpYSBhIHJlY2liaXIgY3VhbHF1aWVyIHJlbXVuZXJhY2nDs24gcG9yIGxvcyB1c29zIGRlIGxhIG9icmEsIGRlIGFjdWVyZG8gY29uIGxhIGxpY2VuY2lhIGVzdGFibGVjaWRhIGVuIGVzdGEgYXV0b3JpemFjacOzbi4KCi0gQWwgZmlybWFyIGVzdGEgYXV0b3JpemFjacOzbiwgc2UgbWFuaWZpZXN0YSBxdWUgbGEgb2JyYSBlcyBvcmlnaW5hbCB5IG5vIGV4aXN0ZSBlbiBlbGxhIG5pbmd1bmEgdmlvbGFjacOzbiBhIGxvcyBkZXJlY2hvcyBkZSBhdXRvciBkZSB0ZXJjZXJvcy4gRW4gY2FzbyBkZSBxdWUgZWwgdHJhYmFqbyBoYXlhIHNpZG8gZmluYW5jaWFkbyBwb3IgdGVyY2Vyb3MgZWwgbyBsb3MgYXV0b3JlcyBhc3VtZW4gbGEgcmVzcG9uc2FiaWxpZGFkIGRlbCBjdW1wbGltaWVudG8gZGUgbG9zIGFjdWVyZG9zIGVzdGFibGVjaWRvcyBzb2JyZSBsb3MgZGVyZWNob3MgcGF0cmltb25pYWxlcyBkZSBsYSBvYnJhIGNvbiBkaWNobyB0ZXJjZXJvLgoKLSBGcmVudGUgYSBjdWFscXVpZXIgcmVjbGFtYWNpw7NuIHBvciB0ZXJjZXJvcywgZWwgbyBsb3MgYXV0b3JlcyBzZXLDoW4gcmVzcG9uc2FibGVzLCBlbiBuaW5nw7puIGNhc28gbGEgcmVzcG9uc2FiaWxpZGFkIHNlcsOhIGFzdW1pZGEgcG9yIGxhIGluc3RpdHVjacOzbi4KCi0gQ29uIGxhIGF1dG9yaXphY2nDs24sIGxhIGluc3RpdHVjacOzbiBwdWVkZSBkaWZ1bmRpciBsYSBvYnJhIGVuIMOtbmRpY2VzLCBidXNjYWRvcmVzIHkgb3Ryb3Mgc2lzdGVtYXMgZGUgaW5mb3JtYWNpw7NuIHF1ZSBmYXZvcmV6Y2FuIHN1IHZpc2liaWxpZGFkCgo= |