AI on a 2d grid in python

I'm trying to figure out how to do a simple search/chase AI.
I know that I'm going to have to search around the mob entity to figure out if the player is close enough, I could probably get that done on my own, but what comes after is what gets me stuck. Once I have the (x,y) of the player, how do I get my mob entity to move a single cell (up, down, left, or right) until they reach the player entity?
Here's a bit of the code for reference.

Just the first part of the Board class.
Basically the portion where the grid is created once initiated. board = Board(10, 10)

class Board(object):
'''Board class to create empty grid of cells'''
def __init__(self, x_size, y_size, char='-'):
self.x_size = x_size
self.y_size = y_size
self.char = char
self.board = [[char for _ in range(x_size)] for _ in range(y_size)]


And the Entity class. player = Entity('Player', 5, 5, 10, 'o', 'alive')

class Entity(object):
'''Basic entity object
Has position and character'''
def __init__(self, name, x, y, hp, char, state):
self.name = name
self.x = x
self.y = y
self.hp = hp
self.char = char
self.state = state

def move(self, direction, board):
'''To update entity position'''
dx = self.x
dy = self.y
valid_moves = board.valid_moves(self)
if direction == 'left' and (self.x, self.y - 1) in valid_moves:
self.y = dy - 1
elif direction == 'right' and (self.x, self.y + 1) in valid_moves:
self.y = dy + 1
elif direction == 'up' and (self.x - 1, self.y) in valid_moves:
self.x = dx - 1
elif direction == 'down' and (self.x + 1, self.y) in valid_moves:
self.x = dx + 1
else:
if self.name == 'Player':
print 'You can\'t move there'
time.sleep(0.3)


The problem which you want to solve involves pathfinding. The simplest approach would be to build a graph of the grid and perform a Breadth First Search on that. Each cell is connected to its traversable (i.e. without obstacles) neighbors, so in the graph, each cell (vertex) will have 4 (or less if there are obstacles) connections (edges) to each of its neighbors. Pseudocode for BFS is as follows:

def bfs(grid, start, end):
frontier = Queue()
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.remove()
if current == end:
break
for n in current.neighbors:
if not came_from.has_key(n):
came_from[n] = current
return came_from


This returns a dictionary which shows how we arrived at a cell. To obtain a path from this dictionary, just traverse the dictionary till you find the start. Pseudocode:

def get_path(grid, start, end):
came_from = bfs(grid, start, end):
current = end
path = [end]
while not current == start:
current = came_from[current]
path.append(current)
return path.reverse()


The path returned by this function starts at "start", i.e. path[0] = start and ends at end, i.e. path[length-1] = end. This means that the next cell to move will always be path[1] provided that the path is recalculated every frame (it should, if the target is/can be moved every frame).

Why to do something so complex for something so trivial, you ask? This makes it all the more easier to compute paths and this method doesn't consume many CPU cycles. Plus, if you add obstacles this will still work, because the cells with obstacles will not be returned as neighbors, thus they won't be traversed at all.

Look at this link for interactive examples of how BFS works with pathfinding. I have taken the BFS function pseudocode from that link, but the explanation is based on my implementation for a turn-based game.

• Thank you. It's going to take a while for me to understand this. I'm not so good at converting pseudocode. Nov 9 '15 at 16:01
• @acollection_ The code I've given is pretty much Python, so shouldn't be a problem. Nov 9 '15 at 16:10
• I can't seem to get Queue() to work. It's saying that 'module' object is not callable. Nov 9 '15 at 16:42
• The Queue class is given on the implementation notes page. Nov 9 '15 at 17:41