Buenas,

pretendo hacer un 'juego naval' y situar los barcos como puntos en un mapa 2D por coordenadas X,Y.

Asta ahí bien, el problema es que pretendo hacer una estructura de datos que me ordene los barcos por proximidad (para saber
que barcos tiene más a tiro cada uno). Obviamente los barcos se van moviendo y modificando sus posiciones en el mapa.

Si fueran 20 barcos no habría problema, pero se trata de hacer un trabajo de optimización, vamos a suponer que hay un millón
de barcos.

Con este escenario se dan dos problemas:

1- Calcular la proximidad por X,Y. Si fueran números sueltos sería muy fácil, pero por coordenadas? Que función matematica me
   devolvería a que distancia se encuentra una coordenada de otra? El modulo entre dos puntos? En verdad esto es lo de menos
   eso es fácil de buscar, solo lo añado para entrar de lleno en materia y contar con que hay un tiempo de calculo extra.

2- Estructura de datos y metodos de busqueda.

   Había pensado en una busqueda dicotómica, una busqueda rápida (aunque no se yo si con un millón de entradas...).
   Pero para ello necesito una tabla con un millon de posiciones y para modificar la tabla para ordenarla necesito
   desplazar toda la tabla... mucho tiempo.

   Por otra banda para no desplazar los nodos de datos al ordenarlos, había pensado en una lista encadenada,
   pero ahí no puedo hacer busquedas, tengo que ir recorriendo toda la lista asta encontrar donde le toca ir...

Si suponemos que cada 30 segundos la mitad de los barcos se han movido... como lo hago para en
trenta segundos actualizar los datos??

Supongo que es mejor que lo implemente todo en una estructura de datos en memoria y no usar bases de datos, ya que se tardaría
tiempo en llamar funciones de la base de datos, a parte lo que tarde la base de datos en procesarlo, más que las bases de
datos lo pasan por disco, más tiempo aun...

Mejor C para que sea más rapido todo?


Como lo veis? Alguna solución, aportación o consejo?

 

Dependerá de la función distancia que quieras utilizar.

Si he entendido bien, necesitas actualizar las posiciones de los barcos cada 30 segundos y una vez están actualizados, necesitas una función que sea algo como proximos(B, k) que retorne los barcos que estén a distancia menor de k del barco B.

La solución que te plantean sirve para la primera parte perfectamente, pero para la segunda en general no funcionará. Con un set supongo que te refieres a lo que internamente suele ser o bien un árbol AVL o bien un Red-Black Tree.

Esto plantea un problema y es que según la distancia que utilice no puedes contestar la segunda función rápido. Por ejemplo, consideremos la distancia euclidiana estándar. No podemos usar ninguna ordenación de manera que los contiguos a un elemento sean los más próximos a él (según esa distancia) y esto implicaría que habría que mirar todos los barcos para poder contestar, es decir, demasiado lento. Si tomamos como distancia que sólo considere la primera coordenada, entonces funcionaría pero no es que sea una distancia muy normal (y de hecho, no es una distancia en el sentido matemático).

Lo que se me ocurre que te puede ir mejor a simple vista es un Burkhard-Keller Tree (BK-Tree). Cada vez que cambies las posiciones tendrás que construir un nuevo árbol (para un millón de barcos le debería dar tiempo de hacerlo en uno o dos segundos así a ojo, por lo que vas sobrado con 30) y gracias a eso podrás contestar rápido las preguntas de proximidad. Además, sirve para cualquier distancia, siempre que sea una distancia en el sentido matemático:

• d(a, b) >= 0 y d(a, b) = 0 <=> a = b
• d(a, b) = d(b, a)
• d(a, b) <= d(a, c) + d(c, b), para cualquier c