2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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()
    frontier.add(start)
    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
                frontier.add(n)
    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.