La SPHERE pierde mucho tiempo chocando con escombreras

[angel-manuel]

El titulo lo dice todo.

Para arreglarlo se me ha ocurrido lo siguiente:

1. Se obtienen todas las posiciones de las escombreras
2. Se triangula con algo así https://en.wikipedia.org/wiki/Delaunay_triangulation aunque en 3D
3. Cada triangulo es una zona y se toma como un nodo conectado con los triángulos adyacentes. A lo que es lo mismo, se juntan los centros(en principio el circuncentro pero solo si cae dentro del triángulo) de los triángulos y se hace un grafo. El grafo quedaría algo así:
4. Se utiliza un algoritmo de pathfinding para recorrer grafos con bastante heurística para que no se eternice como A*

El resultado seria una función a la que le pasas unas coordenadas, consulta en que triángulo cae y te da una ruta entre escombreras.

También seria genial una función que de antemano te estima el coste de ir de A a B y otro más que se encargara de recolectar cierta escombrera sin chocar con las otras.

EDIT: Al parecer los algoritmos para triangular dependen mucha de si se esta en 2D o en 3D o nD, incluso hay algoritmos exclusivos para casos 2D. No se si deberíamos implementar primero los más sencillos independientemente de eso. Otra cosa es que los peores algoritmos son 0(n^2) pero n=10, bastante poco, y todo esto de la triangulación solo necesita ser hecho una vez.

[angel-manuel]

La primera solución que he propuesto me parece bastante engorrosa. Trabajare en algo más sencillo en la rama iss5_v2

[angel-manuel]

El problema se ha agravado considerablemente, ahora si te chocas con un debris te multiplican la velocidad por -1

[angel-manuel]

Añadida la rama movement(contiene distanceToDebris.cpp) a master. Funciona en la mitad de los escenarios.