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?
Mostrar Mensajes
