Brainstorm: Grids

Hey there, this post is going to be a brainstorm point in which I just type out my thoughts as they come to me about how to implement a simple grid into my pygame program.

Alright, so first off, I need a grid because I imagine it will help out in the long run for things like movement, object creation and saving/loading mechanisms. As the game’s set up for now, movement is based on pixels, so they path-finding is quite a bit slow, with 250k (500hx500w) nodes at the moment and that’s really exceptionally high and python’s not built for speed… So anyways I need to split up the screen for that reason first.

So what is a grid then? A grid, as far as I understand it, is a way to divide the game’s surface into smaller, more manageable sections. With these sections I could possibly isolate and create new arrays specific for each section which would each contain the items I’d have laying in it. You can draw images per grid section and use that to draw your game world. There’s always more.

So in order to implement the grid into my game, I need to figure out a way to code them in. So, they’re squares that need to be adjacent to each other. They should each be in an instance of some generic Grid class that will contain basic details, like vision, allow movement or not, contain items, elevation, that sort of thing.

If I were to create it I think I should create them in a “for” loop, so something like for w in screen_width, and for h in screen_height, create Grid instance. I guess that’s good for now, what if I want to create a game world that is bigger than one single screen? I’d need to create a new variable like world_width instead and use that to create a grid.

How would I store them? I used the roguebasin tutorial for python+libtcod a while back, they appended each tile to a list within a list so if you wanted a tile at co-ords: 10,10 you’d look up gridList[10][10], accessing the width list, and then inside it, the heightlist.

That reminds me though, say I do want to create an object at co-ords 100,200; how would I figure out what grid section I’m clicking in? Would each click’s co-ords need to search through the entire list of all grids, or would I append the co-ords that each grid contains as an attribute to a grid. If I do that then, what will I do when I start scrolling the screen? Wouldn’t I need to change then all the pixels inside each Grid.coords’s list? I guess I’ll have to worry about that later.

So what I’m going to do now is to create a new small script that creates that dummy grid instance for every 5 pixels which will bring down the work the path-finding has to do five times, to 50k pixels it could have to look through. I’m not sure if that’s the best way to do it for now, but it’s never written in stone.

Until next time.

UPDATE

I’ve tried doing a few things:

        for w in xrange(0, 500 +1):
            for h in xrange(0, 500 +1):
                if h % 5 == 0:
                    #every 5 pixels wide:
                    if w % 5 == 0:
                    #if newGridStart:
                        g = Grid()
                        g.coords.append((w, h))

                        #print 'created grid at ', w, h

                    else:
                        print w, h
                elif w % 5 == 4 and h % 5 == 4:
                    self.listOfGrids.append(g)
                    print 'appended', w, h

and tried to clean it up to make it look like this:

        for w in xrange(0, 500 +1):
            for h in xrange(0, 500 +1):

                if w % 5 == 0 and h % 5 == 0:
                    g =  Grid()
                    print 'new grid started at', w, h
                elif w % 5 == 4 and h % 5 == 4:
                    self.listOfGrids.append(g)
                    print 'appended grid at', w, h

                else:
                    g.coords.append((w, h))
                    print 'appended coords at', w, h

but that added way too many coords to each grid section or too little depending on which I ran.

So I thought about it some more and I’m going to go over the pixels twice. Once to get all the topleft corners of each grid, then I’m going to fill the grids up with coords based on the topleft corner co-ord. I’ll update this later, when I write out that code.

UPDATE 2

Alright, awesome, I’m pretty happy, I managed to work it out, using pretty much what I had described above. If you try to run the code yourself, you might want to comment out that print statement that shows all the co-ords in a given grid section
    def createGrid(self):
        self.listOfGrids = []

        #go through all the pixels in a game screen
        for w in xrange(0, 500 +1):
            for h in xrange(0, 500 +1):
                #if the co-ords are both muliples of 5:
                if w % 5 == 0 and h % 5 == 0:
                    g =  Grid()
                    g.origin = w, h
                    self.listOfGrids.append(g)
                    #print 'new grid started at', w, h

        print 'done gridding, now adding all the points to each grid'

        #for each grid in list, go through at add all the pixels it covers
        for grid in self.listOfGrids:
            origin =  grid.origin #origin is the top left pixel of the grid
            for w in xrange(0, 5):
                for h in xrange(0, 5):
                    x, y =  map(sum,zip(origin,(w, h)))
                    #what this is is:
                    #zipped= zip(origin, (w,h) )
                    #map(sum, zipped)
                    new_coord =  (x, y)
                    grid.coords.append(new_coord)
                    #print 'added {0} to {1} grid'.format(new_coord, origin)
            print grid.coords, 'length :', len(grid.coords)
        print 'done adding all co-ords'

Update 3

Thanks to a commenter, Matt, I have further optimized the grid code to the following which is about five(!) times less code:

    def createGrid(self):
        self.listOfGrids = []
        
        #go through all the pixels in a game screen
        for w in xrange(0, 500 +1, 5):
            for h in xrange(0, 500 +1, 5):
                g =  Grid()
                g.origin = w, h
                self.listOfGrids.append(g)
                                       
        print 'done gridding, now adding all the points to each grid'
        
        #for each grid in list, go through at add all the pixels it covers
        for grid in self.listOfGrids:
            origin =  grid.origin  #origin is the top left pixel of the grid
            for w in xrange(0, 5):
                for h in xrange(0, 5):
                     grid.coords.append((origin[0] + w, origin[1] + h))
                    
                  
        print 'done adding all co-ords'