Quadtree search.

Basically this is a more efficient method of getting the grid coordinates from the mouse coordinates. For example, this could be used in a RPG or RTS type game. The code is probably general enough to be used for pygame and others as well.

The first function, rfind, takes any empty list, the size of the playing field (probably in pixels, i mean, thats the point of it), the location of the mouse cursor (if you’re not looking straight down you’re probably going to have to do some adjustments) and then a 0.

The map size for this should always be a power of 2. eg 2^x. This isn’t really a problem though, as you can simply block the player from moving into the ones you don’t want, so you’ll still be able to have fancy shaped maps.

There is a problem at the moment however. For some reason, it’s not returning properly. I can print the value correctly 1 instruction before returning it, but returning it screws up.

Anyway, here’s the file.

#recursive find.py
import sys
width = 1000
height = 1000

x = 48
y = 48

def rFind(l, width, height, posx, posy, count):
    halfx = width/2.0
    halfy = height/2.0
    if posx >= halfx:
        posx -= halfx
        if posy >= halfy:
            quadrant = 4
            posy -= halfy
        else:
            quadrant = 1
    else:
        if posy >= halfy:
            posy -= halfy
            quadrant = 3
        else:
            quadrant = 2
    l.append(quadrant)
    if count < 10:
        rFind(l, halfx, halfy, posx, posy, count + 1)
    else:
        print l
        return l


def processData(l, width, height, x, y, i, locx, locy):
    """Takes the stuff from rFind and gives you the actual grid location
    """
    #not sure if i need width and height
    if i + 1 < len(l):
        print "finding grid square"
        number = l[i]
        #weird part starts here
        if number == 1:
            locx += x/2
        if number == 2:
            pass
        if number == 3:
            locy += y/2
        if number == 4:
            locx += x/2
            locy += y/2
        
        processData(l, width, height, x/2, y/2, i+1, locx, locy)
    else:
        return (locx, locy)

    
    
   
    
if __name__ == "__main__":
    width = 1000
    height = 1000
    ls = rFind([], width, height, 0, 300, 0)
    endPos = processData(ls, width, height, 48, 48, 0, 0, 0)
    print endPos

What, nobody wants to tackle recursion problems? :stuck_out_tongue:

I have the feeling no-one understands what it is you’re doing. :U

I think that there may be people that understand what this is (It’s some sort of quicksearch for areas, right?), but implementing it without a working example wouldn’t be easy for anyone.

Basically it Lets you figure out what grid cell something is in, given they’re global coordinates. At least, the first part half-does it. The second functoin (processData) doesn’t work just yet.

The first function (rFind) works perfectly, it just fails when it goes to return the value. If you use globals or the gamelogic dictionary you can do that fine. It’s just that for my particular use i can’t use either of them, as it’s meant to be a file that you import.

If you didn’t have this script, the other obvious way to do it would be to get the coordinates of every cell and check if the object is in it. Quite obviously, if you’ve got a grid of just 2^6, thats a huge amount to search.

I’ts funny to think that people might not understand my stuff because it’s too complicated. :stuck_out_tongue:

Ouch :stuck_out_tongue: I struggle with making my character act properly, and you just pull this out your ass :ba:

No but seriously, awesome work dude. :smiley: You get an elvis for that <:RocknRoll:<

The condition for the return is never satisfied in your top level call.

If you didn’t have this script, the other obvious way to do it would be to get the coordinates of every cell and check if the object is in it. Quite obviously, if you’ve got a grid of just 2^6, thats a huge amount to search.
If you have the origin of the grid system, and the dimensions of each cell, then there is no need to search for anything:


class Grid: 
    """ grid_origin, cell_dimension, and obj_pos must all be Mathutils Vectors """ 
    def __init__(self, grid_origin, cell_dimension): 
         
        self.grid_origin = grid_origin 
        self.cell_dimension = cell_dimension 
         
    def getCellPosition(self, obj_pos): 
         
        delta_vec = obj_pos - self.grid_origin 
         
        for i in range(3): 
            if delta_vec[i] != 0: 
                delta_vec[i] /= self.cell_dimension[i] 
                delta_vec[i] = round(delta_vec[i]) 
                delta_vec[i] *= self.cell_dimension[i] 
             
        return delta_vec

Working example is attached:

Attachments

grid_test.blend (151 KB)

Most of what i program is computer automated versions of actions we do normally. I mean, what human wouldn’t do it somewhat this way?

I wouldn’t even be able to do anything in the GE though, i do too low level a lot of the time. As well as maths for the sake of it.

Um, that relies quite a bit on blender functions doesn’t it? The difference is, i think, that my system, when it works, goes between square grid systems. Yours just does the one? Sort of.

What you’re doing is getting the coords of the object
Then you’re dividing the coords from ^ by the grid size to get it into grid units.
Then rounding it to the nearest grid unit thing,
then multiplying it by the grid size to get it back into blender grid units.

What happens if you’ve got a vast difference in size. Eg, when the objects unit is in a 1000x1000 sized grid and you’re trying to get it into the coordinates of a 64x64 sized grid. (By xy sized grid, i mean there are xy number of cells in the grid, and x and y are just the number of cells on the edges).

, does that mean i have to return

l

in the first cycle? I can’t see how to implement this.

I’m not using any blender functions, as you can plainly see. The Mathutils Vector type is utilized for convenience only; this can be done with pure python lists:


class Grid: 
 
    def __init__(self, grid_origin, cell_dimension): 
         
        self.grid_origin = grid_origin 
        self.cell_dimension = cell_dimension 
         
    def getCellPosition(self, obj_pos): 

        delta_vec = [0]*3
         
        for i in range(3):
            delta_vec[i] = obj_pos[i] - self.grid_origin[i] 
            if delta_vec[i] != 0: 
                delta_vec[i] /= self.cell_dimension[i] 
                delta_vec[i] = round(delta_vec[i]) 
                delta_vec[i] *= self.cell_dimension[i] 
             
        return delta_vec

The difference is, i think, that my system, when it works, goes between square grid systems. Yours just does the one? Sort of.
My system is three-dimensional, and infinite, but it still requires a reference system (it also supports non-cube cell dimensions, if you’re interested in that).

The ability to transform a point from one coordinate space, to another, is fairly trivial, and not something that would require a “grid”, or convoluted recursive functions.

What happens if you’ve got a vast difference in size. Eg, when the objects unit is in a 1000x1000 sized grid and you’re trying to get it into the coordinates of a 64x64 sized grid. (By xy sized grid, i mean there are xy number of cells in the grid, and x and y are just the number of cells on the edges).
A grid, by it’s very nature, has to encapsulate patches of uniform “base space”; if you just have two coordinate systems, and you want to transform an arbitrary point from one to the other:


x_1000sq = 0
y_1000sq = 300
trans_1000to64 = 1000.0/64.0
x_64sq = x_1000/trans_1000to64
y_64sq = y_1000/trans_1000to64

in the first cycle? I can’t see how to implement this.
This should work:


if count &lt; 10:
    rFind(l, halfx, halfy, posx, posy, count + 1)

return l

Yeah, now i’m struggling to find out why i overcomplicated this so much. Might still be able to use it for something else later though.

Hi Fake,

your approach makes sense if you have non-uniform cells. But it would require a different calculation of splitting them into subtrees.
With uniform cells Socials solution is much faster. O(1) < O(log n).