All Possible Moves On a Grid

Hello, I’m creating a virtual tabletop for playing Dungeons and Dragons with some friends and I need a little help. I am wondering what the best way to find all possible paths a player or npc can take on a square grid is. It will take into account the distance a player can move and any obstacles. In D&D each grid space is 5 feet, and diagonals are counted 5 feet for the first square, then alternating 10 and 5 feet. I hope that’s pretty clear, thanks for any help!

Graph theory.

http://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif

Or any other like A* (A star).

@VegatableJuiceF: Ok, I was thinking a pathfinding algorithm was the way to go, but wasn’t sure.
@MichelleSea: Thanks, I was planning on using that system for level building.

Yeah, Dijkstra’s algorithm is probably enough.

I’ve heard it’s more than necessary for games compared to A*, but you might want to look into it and do some research.

I recently added A* pathfinding to my bghelper module. There’s an example blend file present as well. It’s on my Google Code page, and you’ll need an SVN tool (like just plain SVN or TortoiseSVN) to check out the module and example.

If you want to take a look at pathfinding I’d suggest starting here:
http://www.policyalmanac.org/games/aStarTutorial.htm

But first you’ll need to know a little bit about python and about graphs and arrays.

Here’s a little script that can help explain the basics:


### an array looks like this:

level_array_1 = [[1,0,0],
               [0,0,0],
               [0,0,0]]

### ones are walls, zeros are floor
### rows are x, columns are y 

###############################

### here is a similar array, generated in a different way
### this is a much more comfortable way to generate a large array
### just change x and y size to get bigger arrays

x_size = 3
y_size = 3

level_array_2 = [[0 for y in range(y_size)] for x in range(x_size)]

### you could include more data in a single tile by changing the "0" part in to a list.
### for example:

level_array_3 = [[[0,1,False,None] for y in range(y_size)] for x in range(x_size)]

### will give a lot of potential info in each tile.

### we can set an array tile value like this:

level_array_2[0][0] = 1

### where [0][0] means [x][y]

### If you're using an array of lists you'll have to specify which index of the list you want to call

level_array_3[0][0][2] = True

### we can get an array tile in a similar way

x = 0
y = 0

top_left = level_array_1[x][y]

print ("top left tile: ", top_left)

### you'll see that the console prints "1"
### arrays start in the top left and read down and to the right
### We can get multiple array tiles by using a search list or array

search_array = [[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1]]

### lets add some tiles to a neighbors list

neighbors = []

x = 1
y = 1

for tile in search_array:
    check_x = x + tile[0]
    check_y = y + tile[1]

    check_tile = level_array_1[check_x][check_y]
    if check_tile != 1:
        neighbors.append([check_x,check_y])

print ("neighbor list 1: ", neighbors)

### but be careful! if you try to call a tile outside the array you'll get an error:
### uncomment the following to see what I mean:

##
##x = 2
##y = 1
##
##for tile in search_array:
##    check_x = x + tile[0]
##    check_y = y + tile[1]
##
##    check_tile = level_array_1[check_x][check_y]


### We can also iterate through all the tiles in an array and check each in turn.
### this will give us our graph which we can take away to use with A* or other kinds of path-finding

new_array = [[1,0,0],
            [0,1,0],
            [0,0,1]]

### first we need an empty graph

graph = {}

### Next we iterate though the tiles by x and y values

for x in range(x_size):
    for y in range(y_size):
        ### we don't want to check the neighbors of tiles which are walls
        if new_array[x][y] != 1:
            neighbors = []
            
            for tile in search_array:
                check_x = x + tile[0]
                check_y = y + tile[1]

                ### here's a small check to make sure the tile being checked is inside the array 
                if check_x >= 0 and check_x < x_size and check_y >= 0 and check_y < y_size:
                    
                    check_tile = new_array[check_x][check_y]
                    if check_tile != 1:
                        neighbors.append([check_x,check_y])

            if neighbors != []:
                ### if there are any neighbors we want to add them to the graph dictionary
                ### we use a key that can be reconstructed using key.split("$") to get a list of the original x and y values
                key = str(x) + "$" + str(y)
                
                graph[key] = neighbors
print ("graph: ", graph)

### if I want to check a particular tile and it's neighbors I can do it like this:

x = 2
y = 1

string = str(x) + "$" + str(y)

tile_neighbors = graph[key]

print ("tile neighbors: ", tile_neighbors)

### run the script to see the output
### thanks for reading and have fun with arrays graphs! They are essential for tile based games,
### and useful for many more things such as inventories or puzzles.
    


It seems like Dijkstra’s algorithm will work better for me since, from what i have read, it seems like the advantage of A* is that it doesn’t visit every node, but I need to visit every node anyway.
@SolarLune: Thanks, if I decide that A* will work better I’ll definitely look into using your module.
@Smoking_mirror: Thanks for all the info. I already have a pretty good grasp of python and arrays, but graphs are totally new to me.