upcgames/The-Last-Training


zap Can you be the fastest man in the world?

License: MIT

Language: JavaScript


The Last Training

⚡️ Can you be the fastest man in the world?


Windows Mac Linux
Version web Version web Version web
[Aún no Disponible] - -

Enunciado

Trabajo Final del curso de Complejidad Algorítmica, consiste en la elaboración de un juego que, en una primera etapa haga uso de algoritmos de búsqueda y en una segunda etapa algoritmos de optimización basados en algoritmos codiciosos y (o) programación dinámica.

Introducción

Problema

En una desesperación por querer vencer a Savitar, Barry Allen mejor conocido como "The Flash" convoca a una reunión de velocitas a la que asisten Wally West "Kid Flash" y Jessie Wells "Jessie Quick". Dadas las circunstancias llegan a la conclusión de que deben hacer un entrenamiento de sus capacidades (velocidad y toma de decisión) en un escenario lleno de misiones con distintas dificultades.

Objetivo

Para evaluar quien es el mejor tienen que empezar en un punto, haber cumplido todas las misiones planteadas en el mapa y luego terminar en otro. Gracias a esto se pueden evidenciar algoritmos de busqueda y optimización para la toma de decisiones y encontrar el camino más corto hacia la meta.

Marco Conceptual

Algoritmo de Prim

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

Algoritmo de Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Tipos de Datos Abstractos

Cola de Prioridades

Una cola de prioridades es un tipo de dato abstracto similar a una cola en la que los elementos tienen adicionalmente, una prioridad asignada. En una cola de prioridades un elemento con mayor prioridad será desencolado antes que un elemento de menor prioridad. Si dos elementos tienen la misma prioridad, se desencolarán siguiendo el orden de cola.

Grafos

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos. Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas). Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Espacio de Búsqueda

Cuando se resuelve un problema, se busca la mejor solución entre un conjunto de posibles soluciones. Al conjunto de todas las posibles soluciones a un problema concreto se llama espacio de búsqueda. Cada punto en el espacio de búsqueda representa una posible solución. Cada posible solución se le puede asociar un fitness o un valor que indicará cómo de buena es la solución para el problema. Un algoritmo genético (AG) devolverá la mejor solución de entre todas las posibles que tenga en un momento dado.

SOBRE UPC LAB Y UPC GAMES

En UPC LAB Somos un grupo de de gente apasionada por la tecnología, que nos gusta desarrollar aplicaciones de todo tipo. También ayudamos y hacemos aplicaciones, si quieres más información escribe a: upclabperu@gmail.com.

En UPC GAMES seguimos esta mentalidad, nos gusta hacer juegos; Visual Studio, Python, Unity, Unreal, Realidad Virtual, no importa la plataforma.

Estamos buscando activamente gente que crea en esta filosofía, para que pueda compartir sus juegos, pero mucho más que eso: Comentar, corregir, sugerir, agregar funcionalidades y hacer juegos en grupo.

Project Statistics

Sourcerank 3
Repository Size 28 MB
Stars 0
Forks 1
Watchers 3
Open issues 0
Dependencies 41
Contributors 3
Tags 0
Created
Last updated
Last pushed

Top Contributors See all

Hugo Andrés Yupanqui Gómez Franco Rivera Xetier

Something wrong with this page? Make a suggestion

Login to resync this repository