A* Search
In this tutorial we will learn how to give objects in the environment a small amount of intelligence by allowing them to use the A-Star Search algorithm to do pathfinding.
We build a simple environment where the agent must find a goal state while being chased by a gross spider. We build two versions of this environment where the spider
has different movement characteristics.
In the first environment the spider
can only move up, down left and right. In the second environment the spider
can only rotate left and right and move forwards.
Defining Spider Movement
Firstly we need to define how the spider
moves. In the example where we just want the spider
to be able to move UP, DOWN, LEFT and RIGHT, we can just define a default chase
action:
- Name: chase
InputMapping:
Internal: true
This action will have the default action mapping of UP, DOWN, LEFT and RIGHT. Also note that this action has Internal: true
so that this action cannot be performed by any controlling agents.
Alternatively for the environment where we want our spider
to rotate left and right, and only move in the direction that it is travelling you can do the following:
- Name: chase
InputMapping:
Inputs:
1:
Description: Rotate left
OrientationVector: [ -1, 0 ]
2:
Description: Move forwards
OrientationVector: [ 0, -1 ]
VectorToDest: [ 0, -1 ]
3:
Description: Rotate right
OrientationVector: [ 1, 0 ]
Relative: true
Internal: true
See also
You can find much more information about action spaces here
Using the Search
option
The goal of out environment is to make the spider
object find a path from its current location to a particular destination using the mocements we defined in chase
.
In GDY this is super simple to do and is the same for both of the cases above. You just need to tell the Griddly engine which actions it can use and which objects are impassable.
We can do that by using the Search
option in an exec
command.
- exec:
Action: chase
Delay: 10
Search:
ImpassableObjects: [ wall ]
TargetObjectName: catcher
In the Griddly engine, this uses the A* search algorithm to find the best actionId
(in this case which direction) to get the spider
closer to the catcher
object.
In this case the catcher
object is the name of the avatar we control. We also tell the A* algorithm that you cannot move through wall
objects.
Now all we need to do is make sure the exec
command is called when the spider
moves. We can do that by adding to the Behaviours
of the chase
action:
- Name: chase
...
Behaviours:
- Src:
Object: spider
Commands:
- mov: _dest
- exec:
Action: chase
Delay: 10
Search:
ImpassableObjects: [ wall ]
TargetObjectName: catcher
Dst:
Object: _empty
# We only need this Behaviour if we are using the rotating version of the chase action
- Src:
Object: spider
Commands:
- rot: _dir
- exec:
Action: chase
Delay: 0
Search:
ImpassableObjects: [ wall ]
TargetObjectName: catcher
Dst:
Object: spider
What we are doing here is telling telling the Griddly engine to execute another search operation every time the spider
moves, (or rotates).
We also only execute the chase
action after a small delay of 10 if the spider actually moves to a new location. If the spider just rotates on the spot, we immediately execute another chase
action so it moves as well as rotates.