Estructura de datos para el modelado basado en agentes espaciales

Question

¿Cuáles son algunas buenas estructuras de datos para realizar un seguimiento de los agentes en una simulación espacial bidimensional?

He visto algunas referencias a quadtrees (que entiendo) y kd-trees (que no entiendo muy bien).

Estoy buscando algo a través del cual un agente pueda decir eficientemente: "Conozco mi ubicación y me gustaría saber qué agentes están cerca de mí (dentro de un cierto radio de mí mismo)".

Ejemplos (el pseudocódigo está bien) sería muy apreciado.

Estoy trabajando en Java.

Answer 1

he encontrado algo que se llama un Bucket PR Quadtree.

Answer 2

Bueno, no estoy seguro de cómo se implementa exactamente, pero el MASON toolkit usa un algoritmo de discretización que ubica a los agentes que están cerca el uno del otro en el mismo "cubo" de una tabla hash. Hace búsquedas muy rápidas, ya que solo se deben verificar algunos de estos segmentos para cada consulta.

Lo mejor para usted es, probablemente, para echar un vistazo al código fuente aquí: http://code.google.com/p/mason/source/browse/trunk/mason/sim/field/continuous/Continuous2D.java?r=529