pygame is
Python
Simple DirectMedia Layer
 
 
pygame.org is
Site Swing
Wiki

SpatialHashMap

      
Search:  
 
 
#This is a spatial hash. 
#A simple way of putting it is: "we store these points in a grid, 
# and you can retrieve an entire grid cell with its points."
 
 
import random
import time
import math
 
 
def from_points(cell_size, points):
    """
    Build a HashMap from a list of points.
    """
    hashmap = HashMap(cell_size)
    #setdefault = hashmap.grid.setdefault
    #key = hashmap.key
    for point in points:
        #setdefault(key(point),[]).append(point)
        dict_setdefault(hashmap.grid, hashmap.key(point),[]).append(point)
    return hashmap
 
 
 
# this is because dict.setdefault does not work.
def dict_setdefault(D, k, d):
    #D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D
    r = D.get(k,d)
    if k not in D:
        D[k] = d
    return r
 
 
 
class HashMap(object):
    """
    Hashmap is a a spatial index which can be used for a broad-phase
    collision detection strategy.
    """
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.grid = {}
 
 
    def key(self, point):
        cell_size = self.cell_size
        return (
            int((math.floor(point[0]/cell_size))*cell_size),
            int((math.floor(point[1]/cell_size))*cell_size),
            int((math.floor(point[2]/cell_size))*cell_size)
        )
 
    def insert(self, point):
        """
        Insert point into the hashmap.
        """
        #self.grid.setdefault(self.key(point), []).append(point)
        dict_setdefault( self.grid, self.key(point), []).append(point)
   
    def query(self, point):
        """
        Return all objects in the cell specified by point.
        """
        #return self.grid.setdefault(self.key(point), [])
        return dict_setdefault( self.grid, self.key(point), [])
 
 
 
 
if __name__ == '__main__':
 
 
    #NUM_POINTS = 100000
    #NUM_POINTS = 6000
    NUM_POINTS = 1000000
    #new_point = lambda: (
    #    #random.uniform(-100,100),random.uniform(-100,100),random.uniform(-100,100)
    #    (random.random() * 200) - 100, (random.random() * 200) - 100, (random.random() * 200) - 100
    #)
 
    #points = [new_point() for i in xrange(NUM_POINTS)]
    points = []
    for i in range(NUM_POINTS):
        points.append( ((random.random() * 200) - 100,
                        (random.random() * 200) - 100,
                        (random.random() * 200) - 100 ) )
 
 
    T = time.time()
    hashmap = from_points(10, points)
    print 1.0 / (time.time() - T), '%d point builds per second.' % NUM_POINTS
 
    T = time.time()
 
    # if this is using ints, then the thing fails to compile with shedskin.
    #hashmap.query((0,0,0))
    hashmap.query((0.0,0.0,0.0))
    print 1.0 / (time.time() - T), '%d point queries per second.' % NUM_POINTS
 
    #hashmap.insert([22,33,33])
    hashmap.insert((22.0,33.0,33.0))
spotlight

 
our projects
pygame.org welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
 
recent releases
Oct 20, 2014

Oct 16, 2014

Oct 9, 2014

Oct 8, 2014

Oct 7, 2014

Oct 4, 2014

Oct 1, 2014

Sep 19, 2014

Sep 17, 2014

Sep 9, 2014

Sep 8, 2014

Sep 7, 2014

... more!
 
for pygame related questions, comments, and suggestions, please see help (lists, irc)