Analytics Vidhya
Published in

Analytics Vidhya

Agents! how do they work?

How do enemies find us

I’ve been away for a few weeks doing tons of research for new materials that I can bring for this blog and thinking how best to organize them. Also, I’ve been designing a study and project plan to share my AI, Data Science and developer journey with the community and I believe. After much deliberating , I decided to split the blog into three main categories :

  1. Development: we’re going to deal here with the specifics of creating new software projects , these articles will be code intensive and will verse on topics such as software projects, algorithms, design patterns and development tools and frameworks.
  2. Data Science Theory and Trends: These articles will be focused more on the theoretical aspects of Data Science, Machine Learning and AI with brief discussions about implementation and possibly the latest tools used in the practice of this discipline. These articles will not be as code intensive as the Development articles, but may include some code examples or maybe dense in math.
  3. Opinion pieces: Light articles giving my take on specific Data Science or development topics, this will be short and to the point , not very detailed and likely will not contain any heavy math explanations or code snippets. These articles are intended to showcase my thinking about a very specific topic.

This will be the direction of my publications from now on , of course research and development takes a good deal of time so don’t expect a development article every other day, however , with the Opinion Pieces I pretend to be able to publish more regularly , while de R+D takes place in the background.

One of the most interesting applications for Artificial Intelligence is strategy games: how do enemies know where to go and where to hit? , this article illustrates one of the most basic principles of pathfinding , through the creation of a simple Python text videogame.

The Game — Cross the Street and Avoid Danger!

The premise of the game is exceedingly simple. Our player has to cross the board map while an enemy is in pursue. Every time the player makes a move , the enemy closes in its position until the player manages to cross the whole board , in which case he will win, or the enemy catches him , in which case the player will lose.

This game is then comprised by three objects: Board, Player and Enemy

Before we go into the details of how these three objects interact with each other , we need to briefly discuss how computer agents are conceived

Elementals of Agent Design

In general , an Agent is anything that can perceive its environment through Sensors and act upon the environment through Actuators. In the case of computer agents , the agent may detect things like keystrokes , specific data values , files or network data packages.

The agent decides how to act through its actuators with a decision function called agent function, that takes as input whatever information is perceived through its sensors. The agent then is able to act upon its environment.

Basic Agent structure

In our game, the Board serves as environment and the Player and Enemy objects are the main agents. Of these, only Enemy is an autonomous agent, in that reacts without any prompt , other than the Player’s movement, and its sole purpose is to chase the Player around the board. Following our agent definition , Enemy has the following structure:

  1. Sensor: Enemy can see the Player position in the board, recognizes at all times where the Player is.
  2. Function: Through the A* pathfinding algorithm , Enemy decides how to move to chase the player
  3. Actuator: Enemy updates its position in the board moving ever closer towards the player

Player is an agent as well, however not an autonomous one , since player depends on the commands by a human in order to be able to function. The player also can see the enemy position , and the human behind it decides how to move in order to evade the enemy and move towards the goal.

Now that that’s clear, let’s dive into the code

Program Design

Classes:

Board

Board is the most sophisticated class within the program , its functionality is actually split in two separate data structures:

  1. To display the board , a nested list (10x10) that displays the player an enemy as string elements (“P”,“E”)
def __init__(self, player=None, enemy=None):
self.main_board =[["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"],
["_", "_", "_", "_", "_", "_", "_", "_", "_","_"]]

2. A graph data structure in the background, that stores the board as a collection of interconnected node objects. The graph stores the positions of each node and also the neighbor positions to each node in the graph, this information is the base for A* implementation

"""
Node Class stores node information for each node in the board
"""


class Node():
def __init__(self, coordinates):
self.coordinates = coordinates
self.neighbors = []
"""
Create neighbors creates and stores the neigbhor information for all the elements in the board
"""
def create_neighbors(self, board_nodes):
directions = [(1, 0), [0, 1], [-1, 0], [0, -1]]
for direction in directions:
neighbor_coordinates = (self.coordinates[0]+direction[0], self.coordinates[1]+direction[1])
for j in board_nodes:
if j.coordinates == neighbor_coordinates:
self.neighbors.append(j)

Board keeps references to both the Player and Enemy objects as well as a list with all the nodes created for each board position. Note that the node stores te coordinates of the node within the board, so we just need a single reference to obtain and update the position of an agent within the environment

self.nodes = []
self.player = player
self.enemy = enemy

Finally , board positions the initial Player and Enemy (Player always starts for a fixed position, Enemy from a random one), creates all the nodes in the board and their neighbor connectivity and displays the game state

def place_player(self):
player_row_index = 9
player_column_index = 5
for i in self.nodes:
if i.coordinates == (player_row_index, player_column_index):
player_node = i
player = Agent.Player(player_row_index, player_column_index, player_node)
player.node = player_node
self.player = player
self.main_board[player.row][player.column] = player.tag

def place_enemy(self):
enemy_row_index = random.randint(0, 9)
enemy_column_index = random.randint(0, 9)
for i in self.nodes:
if i.coordinates == (enemy_row_index, enemy_column_index):
enemy_node = i
enemy = Agent.Enemy(enemy_row_index, enemy_column_index, enemy_node)
self.main_board[enemy.row][enemy.column] = enemy.tag
self.enemy = enemy

def create_nodes(self):
board_height = len(self.main_board)
board_width = len(self.main_board[0])
for x in range(board_width):
for y in range(board_height):
node = Node((x, y))
self.nodes.append(node)

def create_node_neighbors(self):
for node in self.nodes:
node.create_neighbors(self.nodes)

def display_board(self):
for i in self.main_board:
print(i)

Agent

The agent class is rather simple , it only needs a tag , to designate it as Player (“P”) or Enemy (“E”). It also needs a reference to the graph’s node, and that’s it!

class Agent():
def __init__(self, row_index=None, column_index=None, tag="", node=None):
self.position = [row_index, column_index]
self.node = node
self.tag = tag

The Game Loop

The basic operations of the game are summarized with this loop

Game Loop

Of these, the method that results of most interest is the Move Enemy method. This is where the A* algorithm and the graph implementation come into play.

I don’t want to get into a full explanation of how A* is implemented, a magnificent explanation can be found here :

My implementation is almost identical to the basic form of A* given by Red Blob Games , a summarized explanation on how the algorithm works is:

  1. From the enemy starting position , the entirety of the graph is traversed , recording the position of every node relative to that of the enemy, in such a way that all the nodes in the graph have a recorded path to the enemy’s position
  2. Knowing the player’s position, a path is constructed from the node where the player is known to be , connecting it to the enemy position. A list of nodes is generated forming the path that connects the two positions.
  3. The enemy then moves to one of the nodes in the constructed path , updating his position to be closer to the player.

The whole process is a relatively short program, notice the implementation of a Queue , to enqueue and dequeue the neighbor nodes as we traverse the graphs

def move_enemy(board):
player_node = board.player.node
enemy_node = board.enemy.node
"""
Enemy agent scans the board
"""
frontier = Queue.Queue()
frontier.enqueue(enemy_node)
came_from={}
came_from[enemy_node] = None
while not frontier.is_empty():
current = frontier.dequeue()
for nxt in current.neighbors:
if nxt not in came_from:
frontier.enqueue(nxt)
came_from[nxt] = current
"""
Enemy Agent builds the path towards the player
"""
current = player_node
path = []
while current != enemy_node:
path.append(current)
current = came_from[current]
path.append(enemy_node)
path.reverse()
for i in path:
print(i.coordinates)
"""
Updates the enemy position in the board based on the constructed path towards the player
"""
board.main_board[board.enemy.node.coordinates[0]][board.enemy.node.coordinates[1]] = "_"
board.enemy.node = path[2]
board.main_board[board.enemy.node.coordinates[0]][board.enemy.node.coordinates[1]] = "E"
board.display_board()
return board

Final Thoughts

We’ve seen a simple agent implementation that allows a computer program to give some illusion of intelligence. From this core logic , I wish to develop a much more interesting game of simulation , for which I’m currently working on the main features and structure.

Path finding algorithms rely greatly on graphs , and graphs have many other applications besides games (they feature prominently in deep learning algorithms) , so the study of these structures and how to work with them is also of value for any machine learning practitioner.

You may find the full code of this implementation here

Special thanks to Red Blob Games , this website is a must to understand many game algorithms and their implementation , I’ve had a lot of fun delving into its material

Finally , if you want to delve deeper in modern artificial intelligence techniques, may recommendation is:

Russell S. and Norvig P. “Artificial Intelligence, A Modern Approach” Third Edition, Prentice Hall Upper Saddle River , New Jersey 2010

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jose

Jose

46 Followers

Engineer , Data and AI enthusiast . Amateur programmer