PENGI AI

Overview

A university project that involved creating an AI controller that could avoid, and kill bees by pushing blocks. Implemented using A* and finite state machines.

Specification

The goal was to create a controller that was capable of winning five consecutive rounds in an arena populated with five bees, in which each round is won by killing three bees by pushing blocks into them. A round is lost if the PENGI character controlled by the controller comes into contact with a bee.

A number of restrictions where imposed onto the controller:

  • Bees could only be killed by pushing a block in one of four directions: up, down, left, right.
  • Movement was restricted to four directions: up, down, left, right
  • The controller could only move one block at a time

Design

Based on the goal, and the restrictions imposed for the controller, it was apparent that controller must implement the following behaviours:​

  1. Getting into an opportune position in order to push a block into a bee
  2. Once in position the controller must be able to push the block into the bee
  3. The controller must be able to flee from the bees to avoid dying

In order to achieve the desired behaviours above some additional requirements are needed, specifically the controller needed to be able to navigate through the environment, and that also meant sensing the bees in the environment, at all times.

Finite State Machine

A finite state machine was chosen to implement decision making  due to the small number of required behaviours. A finite state machine consists of a set of states, and transitions between those states that are dependent on a set of conditions. The behaviours defined above are regarded as strategic, or high level states and comprise of searching, attacking, and fleeing.

A set of mechanical states, or low level states are also created which define the mechanical behaviour of the controller as described by the requirements. Setting a low level state will control the movement and the pushing of a block.

The condition used to transition between these states is entirely based on the distance between the PENGI character and the bees within the level. Within each state checks are continuously made that take into account distance, current state,  and obstacles between both the controller and a bee.

Input
State
State Change
Output
Attack Position Chosen
Search
Seek
Move
Bee in Range of Attack Block
Seek
Attack
Move Cube
Bee in Unsafe Range and no Obstacles In-between Controller and Bee
Search | Attack | Flee
Flee
Move
No Attack Position Chosen
Flee | Attack
Search
Calculate Path
State Transition Table

A* Pathfinding

Many algorithms exist which are useful for searching an environment, the A* algorithm was chosen for the implementation because it is efficient and produces the shortest path between two points. The A* algorithm usually requires a simplified environment, which makes it suitable choice for the project as the environment was comprised of tiles, whereby each tile is used in the algorithm to construct a path.

​A* algorithms rely on a heuristic, and the Manhattan Distance was chosen for this particular implementation. By associating a movement cost for navigating between tiles, and then summating the number of tiles required to move in both the x and y directions, a cost can be produced to represent the suitability of the tile, with respect to its closeness to the destination tile.

The algorithm only considers tiles that are described as free when constructing the path, ignoring any tiles that contain blocks or bees.

GitHub-Mark-120px-plus

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s