Buenas, quiero hacer una búsqueda de la forma más eficiente posible. La situación es la siguiente:
-En un plano 2D tengo unos puntos clave y tengo que encontrar el punto clave más próximo a mi posición. Esos puntos clave están en un list aunque podría guardarlos en otra estructura. Mi código actual es este:
Gracias!
Olvidé decir que tanto mi posición como los puntos clave están en movimiento.
No es un problema de leetcode pero casi, es para programar una IA que juegue a un pseudo quidditch. Los puntos clave son las pelotas con las que se puede marcar gol (5 o 7) y mi posición es la posición de mis jugadores (dos).
El caso es que me he quedado atascado y mi IA ya no mejora nunca así que se me ha ocurrido que podría ser porque la búsqueda de la pelota más cercana es muy lenta.
#4 ¿Y si es un juego por qué no mantienes en memoria la distancia de las dos pelotas esas con respecto a los jugadores?
#6 Ya ya, estoy en ello. Es que no había oído hablar de quadtree en mi vida.
#7 Porque están en movimiento y las pelotas más cercanas van variando.
Os pongo un partido de ejemplo contra un bot básico (luego te enfrentas a la ia de otros jugadores)
https://www.codingame.com/replay/452162430
#8 te permite de algún modo calcular la distancia de los puntos clave al centro de la pista y a ambas porterías, o el código que pones es todo lo que hay?
#9 puedo calcular la distancia sí. de cada elemento (mis magos, magos rivales, bludgers y pelotas) tengo su posicion (x,y) y su velocidad (vx, vy) entre otros datos.
El centro del campo es (8000, 3750) y el centro de las porterías sería (0, 3750) y (16000, 3750)
#10 entiendo que el código se ejecuta por ciclo del gameloop para ambos equipos, no creo que afecte la velocidad del algoritmo (y de afectar sería como dice #11, la cantidad de puntos es muy baja, lo descartaría también)
Lo veo más bien tema de diversificación de tareas.
Por ejemplo...
En la búsqueda daría preferencia a los puntos clave de menor velocidad.
Distribuiría estrategia, que uno de los players ataque siempre al punto clave más cercano y que el otro player de preferencia a los puntos clave que estén en tu medio campo (en caso de estar vacío tu medio campo que siga la lógica del primer player).
Pues eso pensaba yo al principio pero luego he visto que haciendo algunos cambios menores de optimización de código mejoraban los resultados.
Por ejemplo hice una función que determinase el estado del campo (si las bolas estaban cerca de mi portería o si ya tenía suficientes cerca de la suya para ganar) y en funcion del resultado de esa función que los jugadores fuesen a por unas bolas u otras. Perdí como 80 puestos en la clasificación y sigo sin saber por qué la verdad.
El último cambio que hice fue tener en cuenta la velocidad de las pelotas a la hora de decir a mi jugador a donde dirigirse. Para que así fuera al punto donde va a estar la pelota en lugar del punto en el que estaba. Tampoco ha supuesto una mejora en los resultados.
Así que estoy un poco perdido porque no funcionan este tipo de mejoras génericas y no entiendo bien por qué.
Ten en cuenta lo que te cueste mantener la estructura, que la vas a actualizar en cada loop.
Tienes max X/ max Y? es decir el mapa tiene limites no demasiado grandes?
edit: acabo de ver el video xd
Nunca he hecho multi agente pero probaría q learning. Si sabes como representar bien los estados te puedes copiar las policies de los mejores jugadores. este juego no lo habia visto nunca
¿Y si guardas/actualizas en cada movimiento de las pelotas o los jugadores las distancias entre ellos? Así la lista a iterar cuando necesitas saber que pelota es la más cercana sería igual al número de pelotas.
Lo que has explicado en #13 para que el jugador vaya a donde la pelota va a estar, en vez de a donde está, puedes hacerlo también para "predecir" que pelota va a estar más cerca.
Me he registrado y he estado jugando al juego de Thor, y me he pasado 1h porque hacia las distancias manhattan mal, restaba en lugar de hacer el mínimo de dos vectores xd no estoy en posision de ayudar a nadie. esta guapa la pagina. hay un monton de lenguajes.
#18 Soy un fracaso.
BTW antes me he equivocado, queria decir *aproximate q learning que no recuerdo si se daba por hecho. En esta web no he probado cuanto te limitan el tiempo... empieza por markov que creo que era mas simple de implementar. Y no trabajes con quadtrees lol, simplificar las posiciones con cuadrantes seguramente funcione como heuristica.
A cuanta profundidad estas mirando y que usas?
Otra cosa que se me ocurre es relajar las cálculos sobre el espacio de búsqueda dependiendo de la distancia de tus agentes. Si metes los cuadrantes puedes aproximar las cosas distantes y trabajar con toda la precisión con las cosas cercanas.
