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
Sep 19, 2014

Sep 17, 2014

Sep 9, 2014

Sep 8, 2014

Sep 7, 2014


Sep 5, 2014

Aug 26, 2014

Aug 21, 2014


Aug 18, 2014

Aug 2, 2014

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