Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

The pathfinding in my game uses this function to generate a graph:

def make_graph(self, size, impassable):
    nodes = [[astar_gridnode(x, y) for y in range(size)] for x in range(size)]
    graph = {}
    for x, y in product(range(size), range(size)):
        node = nodes[x][y]
        graph[node] = []
        for i, j in product([-1, 0, 1], [-1, 0, 1]):
            # Check that we are inside the grid area.
            if not (0 <= x + i < size): continue
            if not (0 <= y + j < size): continue
            # Check if the target area is impassable.
            if (x + i, y + j) in impassable: continue
            # All looks good. Add target space as reachable from current (x, y) space.
            graph[nodes[x][y]].append(nodes[x+i][y+j])
    return graph, nodes

It works great, but I've come to the point where the terrain needs to be modified sometimes to add or subtract impassable nodes, such as when buildings are created/destroyed, or the space occupied by units. It would be easy enough to append impassable and run make_graph again, but that's not possible because the map is huge (divided into 12x12 size squares) and creating the graph for the whole map takes a couple seconds.

So how can I modify just small parts of the graph?

Edit: I found the solution and wanted to post it as an answer for clarity, but nothing happens when I click the button, so I'll post it here instead.

for space in add_to_impassable:
    self.addimpassable(space)

def addimpassable(self, space):
    x, y = space[0], space[1]
    node = self.nodes[x][y]
    for i, j in product([-1, 0, 1], [-1, 0, 1]):
        try:
            self.graph[self.nodes[x][y]].remove(self.nodes[x+i][y+j])
            self.graph[self.nodes[x+i][y+j]].remove(self.nodes[x][y])
        except:
            pass # node is already removed, so trying to add it again by 
            # planting a structure side by side with this one would cause a crash.
share|improve this question
1  
You may want to look into using a weighted graph structure, with that you could boost the weight on the edge connecting the blocked nodes to something ridiculously high. Standard shortest path algorithms working on weighted graphs will take that high weight as undesirable, you could modify that to block passage if you needed. –  Patrick Hughes Apr 28 '13 at 22:49
    
That might work for blocked areas in an open field, but would still allow units to walk through buildings or other units if a part of the map is walled off by something other than the original impassable nodes. –  user11177 Apr 28 '13 at 22:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.