{"id":1374,"date":"2018-12-13T00:00:00","date_gmt":"2018-12-13T03:00:00","guid":{"rendered":"http:\/\/ijandev-test.fi.uncoma.edu.ar\/Wordpress\/index.php\/2018\/12\/13\/biondelli-patricio-analisis-y-clasi-cacion-de-metodos-de-path-finding-en-videojuegos-diciembre-2018\/"},"modified":"2022-02-06T23:51:17","modified_gmt":"2022-02-07T02:51:17","slug":"1129-biondelli-patricio-analisis-y-clasi-cacion-de-metodos-de-path-finding-en-videojuegos-diciembre-2018","status":"publish","type":"post","link":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/nuevos-lic-lcc\/1129-biondelli-patricio-analisis-y-clasi-cacion-de-metodos-de-path-finding-en-videojuegos-diciembre-2018\/","title":{"rendered":"Biondelli, Patricio: An\u00e1lisis y clasi\fcaci\u00f3n de m\u00e9todos de path\ffinding en videojuegos. Diciembre 2018"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"1374\" class=\"elementor elementor-1374\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4887245f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4887245f\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-691899b2\" data-id=\"691899b2\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5b715cc1 elementor-widget elementor-widget-text-editor\" data-id=\"5b715cc1\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.6.7 - 03-07-2022 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#818a91;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#818a91;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><strong>T\u00edtulo<\/strong>:\u00a0 \u00abAn\u00e1lisis y clasi\fcaci\u00f3n de m\u00e9todos de path\ffinding en videojuegos\u00bb<\/p><p><strong>Tesista<\/strong>:\u00a0Patricio Biondelli<\/p><p><strong>Directora<\/strong>:\u00a0\u00a0Dra. Laura Cecchi<\/p><p><strong>Carrera<\/strong>: Licenciatura en Ciencias de la Computaci\u00f3n<\/p><p style=\"text-align: justify;\"><strong>D\u00eda y lugar<\/strong>: 13 de diciembre de 2018<br \/>\u00a0<\/p><p style=\"text-align: justify;\"><strong>Resumen<\/strong><\/p><p style=\"text-align: justify;\">En el contexto de la rob\u00f3tica, y en el de los veh\u00edculos aut\u00f3nomos y los videojuegos, el movimiento es un factor muy importante. Para que un personaje de videojuego\u00a0 o un\u00a0 robot pueda trasladarse desde un punto a otro, necesita de una serie de especificaciones precisas para poder tomar decisiones convenientes.\u00a0<\/p><p style=\"text-align: justify;\">Dada una regi\u00f3n que incluye varios obst\u00e1culos y un objeto con tama\u00f1o especificado, necesitamos encontrar un camino para el objeto desde el\u00a0 origen al destino.<\/p><p style=\"text-align: justify;\">La b\u00fasqueda de ruta, la cual se denomina pathfinding, es la forma en que un objeto encuentra un camino hacia su destino evitando obst\u00e1culos.\u00a0<\/p><p style=\"text-align: justify;\">En la actualidad, la evoluci\u00f3n de los videojuegos ha logrado resultados impactantes; son tan precisos y bien logrados que en la mayor\u00eda de los casos parecieran ser la vida real misma. Esto implica una complejidad adicional importante a la hora de dise\u00f1ar los algoritmos de pathfinding.<\/p><p style=\"text-align: justify;\">En esta tesis se han estudiado diversos m\u00e9todos de representaci\u00f3n del espacio de b\u00fasqueda, como aquellos basados en grillas y grafos, y tambi\u00e9n el basado en esferas.<\/p><p style=\"text-align: justify;\">Las representaciones\u00a0 descomponen el espacio en\u00a0 celdas t\u00edpicamente definidas por puntos, c\u00edrculos, pol\u00edgonos convexos\u00a0 o esferas y representan regiones\u00a0 del espacio que est\u00e1n libres de\u00a0 obst\u00e1culos. Para su an\u00e1lisis se consider\u00f3 la posibilidad de utilizar estas t\u00e9cnicas en ambientes\u00a0 f\u00edsicos o virtuales, su ajuste a entornos din\u00e1micos y el tiempo de acceso.\u00a0<\/p><p style=\"text-align: justify;\">Asimismo,\u00a0 se analizaron varios m\u00e9todos de pathfinding que fueron seleccionados tomando como preferencia aquellos que est\u00e1n a la vanguardia, pero que tambi\u00e9n cubren diferentes tipos de paradigmas y caracter\u00edsticas. De esta manera, hemos analizado m\u00e9todos de pathfinding que se adaptan a entornos online y otros que pueden trabajar en entornos parcialmente desconocidos o incluso totalmente desconocidos. Tambi\u00e9n, aquellos m\u00e9todos cuya motivaci\u00f3n inicial es la de mejorar la performance de A*, con interesantes propuestas de poda de caminos que pueden ser prescindibles, y otros casos en los cuales se permite a los personajes ir recolectando objetos, o lograr habilidades, para mejorar su desempe\u00f1o.\u00a0<\/p><p style=\"text-align: justify;\">Para cada m\u00e9todo se analizaron un conjunto de caracter\u00edsticas,\u00a0 que determinamos adecuadas al momento de la selecci\u00f3n de una\u00a0 t\u00e9cnica, a fin de determinar si\u00a0 es la que\u00a0 se ajusta al problema que\u00a0 deseamos resolver.<\/p><p style=\"text-align: justify;\">As\u00ed, fue posible categorizar los algoritmos de\u00a0 pathfinding basados en\u00a0 ambientes de b\u00fasqueda\u00a0 f\u00edsicos o\u00a0 virtuales, est\u00e1ticos o din\u00e1micos y si es posible su implementaci\u00f3n en tiempo\u00a0 real, entre otros.<\/p><p style=\"text-align: justify;\">Para evaluar la eficiencia de tales algoritmos, se tuvo en cuenta el\u00a0 tiempo de ejecuci\u00f3n, el\u00a0 gasto de memoria y propiedades\u00a0 como la optimalidad y completitud.<\/p><p style=\"text-align: justify;\">El relevamiento y an\u00e1lisis realizado en esta tesis se presenta como un punto de inicio para una revisi\u00f3n sistem\u00e1tica de este campo.\u00a0 Asimismo, provee\u00a0 a los\u00a0 investigadores con un marco del progreso parcial actual, que le permitir\u00e1 seleccionar\u00a0 de entre los algoritmos relevados el\u00a0 que se ajuste a su\u00a0 desarrollo.<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-523d598 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"523d598\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-79542c3\" data-id=\"79542c3\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d8e03fe elementor-widget elementor-widget-image\" data-id=\"d8e03fe\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.6.7 - 03-07-2022 *\/\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t<figure class=\"wp-caption\">\n\t\t\t\t\t\t\t\t\t\t<img width=\"782\" height=\"585\" src=\"https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg\" class=\"attachment-large size-large\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg 782w, https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli-300x224.jpg 300w, https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli-768x575.jpg 768w\" sizes=\"(max-width: 782px) 100vw, 782px\" \/>\t\t\t\t\t\t\t\t\t\t\t<figcaption class=\"widget-image-caption wp-caption-text\">Foto del d\u00eda de la defensa con su tutora y el tribunal integrado por los profesores Dra. Nadina Mart\u00ednez Carod y Mg. Gerardo Parra<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ed2a24e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ed2a24e\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a4e3735\" data-id=\"a4e3735\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-75abc87 elementor-align-center elementor-widget elementor-widget-button\" data-id=\"75abc87\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a href=\"https:\/\/www.fi.uncoma.edu.ar\/index.php\/nuevos-lic-lcc\/\" class=\"elementor-button-link elementor-button elementor-size-sm\" role=\"button\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">Ver otras tesis LCC FaI<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>T\u00edtulo:\u00a0 \u00abAn\u00e1lisis y clasi\fcaci\u00f3n de m\u00e9todos de path\ffinding en videojuegos\u00bb Tesista:\u00a0Patricio Biondelli Directora:\u00a0\u00a0Dra. Laura Cecchi Carrera: Licenciatura en Ciencias de la Computaci\u00f3n D\u00eda y lugar: 13 de diciembre de 2018\u00a0 Resumen En el contexto de la rob\u00f3tica, y en el de los veh\u00edculos aut\u00f3nomos y los videojuegos, el movimiento es un factor muy importante. Para &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/www.fi.uncoma.edu.ar\/index.php\/nuevos-lic-lcc\/1129-biondelli-patricio-analisis-y-clasi-cacion-de-metodos-de-path-finding-en-videojuegos-diciembre-2018\/\"> <span class=\"screen-reader-text\">Biondelli, Patricio: An\u00e1lisis y clasi\fcaci\u00f3n de m\u00e9todos de path\ffinding en videojuegos. Diciembre 2018<\/span> Leer m\u00e1s &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":8777,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-global-header-display":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":""},"categories":[14],"tags":[],"uagb_featured_image_src":{"full":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg",782,585,false],"thumbnail":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli-150x150.jpg",150,150,true],"medium":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli-300x224.jpg",300,224,true],"medium_large":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli-768x575.jpg",768,575,true],"large":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg",782,585,false],"1536x1536":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg",782,585,false],"2048x2048":["https:\/\/www.fi.uncoma.edu.ar\/wp-content\/uploads\/2018\/12\/tesis-biondelli.jpg",782,585,false]},"uagb_author_info":{"display_name":"ufai","author_link":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/author\/ufai\/"},"uagb_comment_info":0,"uagb_excerpt":"T\u00edtulo:\u00a0 \u00abAn\u00e1lisis y clasi\fcaci\u00f3n de m\u00e9todos de path\ffinding en videojuegos\u00bb Tesista:\u00a0Patricio Biondelli Directora:\u00a0\u00a0Dra. Laura Cecchi Carrera: Licenciatura en Ciencias de la Computaci\u00f3n D\u00eda y lugar: 13 de diciembre de 2018\u00a0 Resumen En el contexto de la rob\u00f3tica, y en el de los veh\u00edculos aut\u00f3nomos y los videojuegos, el movimiento es un factor muy importante. Para&hellip;","_links":{"self":[{"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/posts\/1374"}],"collection":[{"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/comments?post=1374"}],"version-history":[{"count":11,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/posts\/1374\/revisions"}],"predecessor-version":[{"id":8787,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/posts\/1374\/revisions\/8787"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/media\/8777"}],"wp:attachment":[{"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/media?parent=1374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/categories?post=1374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.fi.uncoma.edu.ar\/index.php\/wp-json\/wp\/v2\/tags?post=1374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}