Struttura dati per la modellazione basata su agenti Spaziali

Question

Quali sono alcune buone strutture dati per tenere traccia degli agenti in una simulazione spaziale bidimensionale?

Ho visto alcuni riferimenti ai quadrifori (che capisco) e ai kd-tree (che non capisco molto bene).

Sto cercando qualcosa attraverso cui un agente possa dire efficientemente: "Conosco la mia posizione, e vorrei sapere quali agenti sono vicini a me (entro un certo raggio di me)".

Gli esempi (lo pseudo-codice va bene) sarebbero molto apprezzati.

Sto lavorando in Java.

Answer 1

ho trovato qualcosa chiamato un Bucket PR Quadtree.

Answer 2

Bene, non sono sicuro di come sia implementato, ma lo MASON toolkit utilizza un algoritmo di discretizzazione che colloca gli agenti vicini l'uno all'altro nello stesso "bucket" di una tabella hash. Rende le ricerche molto veloci, poiché solo alcuni di questi bucket devono essere controllati per ogni query.

La cosa migliore per voi è probabilmente di dare un'occhiata al codice sorgente qui: http://code.google.com/p/mason/source/browse/trunk/mason/sim/field/continuous/Continuous2D.java?r=529