tags	author	title
project	PikaChin	AStarEngine

AStarEngine

This project is developped for the final project of NSD in NYCU.

Introduction

A* Search is a path finding algorithm which is usually used in the game development and some graph problem. The difference of A* Search and Dijkstra is that A* Search introduce the heuristic function. The heuristic function, which gives an intuitive of the current state/node to the goal/target.

The algorithm is as following:

At the start node, it can found the adjecent node, then calculate the f(node) value. The f(node) value is determined by g(node) and h(node). g(node) is same with the Dijkstra distance value. h(node) is the heuristic value determined by the user defined heuristic function, for example, Manhattan Distance.

Next, try to pop out the node with lowest f(node) value. Tag it as visited, and do the same process as the above.

Keep doing the process until reach the target node.

In this project, the logic of A* search is already written with c++. The user can experience A* search through implementing their own environment in c++/python.

The user should follow the environment interface to implement their own game. I will futher explain the interface of the environment in latter part.

How to Start

The project is written with C++ and Python. The system architecture will show in latter section. Here, you only need to know that the project is build with C++ and bind the C++ library into Python by using Pybind11.

Build

I suggest you to build the project with the Container:

podman run \
    -v=$PWD:/workspace \
    -w=/workspace \
    -it \
    --name="A_Star" \
    derrick4563/nsd:latest

# Then cd into the workspace directory
cd /workspace

# Build the project with setup.sh
./script/setup.sh -build

Hint: Use docker to run the container is ok, but I prefer podman. The reason for using podman rather than docker you can refer to this website.

The setup script will build the project generating test binary executable and pybind library. The pybind library name is astar_engine which will be placed into src/py_env directory automatically.

Because the pybind library is inside src/py_env, the Python environment file should be placed into this directory.

Try to import astar_engine in Python:

# cd /workspace/src/py_env
# python3
import astar_engine

If you want to implement your own environment in C++, you must have generate some new cpp file. Therefore, you will need to rebuild the project. At this moment, you can use the rebuild script:

./script/rebuild.sh

Run Example

There are two example environment I implement in the src directory. They are Randome Maze and Sliding Puzzle Game implemented in C++ and Python respectively.

Run Maze

You can run maze with AStarEngine by execute the compiled binary executable file main

# Usage: ./main [default|maze|your cpp env]
./build/main maze

It will show the random maze, which random generated by DFS, and also the founded path of this generated maze. The path is given by A* engine.

Run Sliding Puzzle Game

To run Sliding Puzzle Game, this game is implemented in Python, so you can run the Python file main.py

# Usage: python3 main.py [sliding_puzzle|your py env]
python3 src/main.py sliding_puzzle

Run this game will show the order to slide the board. The first board is about initial board status, which has been random slided. Because the path will be too long when the board size is large, I show the simple example of this game.

Implement Your Own Environment

When you want to try A* search on different environment, you should implement your own environment.

You can choose C++ or Python to implement your environment or game. Both need to follow the rule I mention below.

Be careful that if the environment/game is implemented in Python, the speed must be slower than C++. Therefore, if you want to have best A* search speed, you need to implement the environment/game with C++.

Implement in C++

To implement with C++, you need to create two class: State and Environment. Your own Environment and State must inherit base State and Environment class, just like the maze example I did.

// Inherit State class
class MazeState : public State {};
// Inherit Environment class
class Maze : public Environment {};

State: You should override two methods

• encode method
• decode method

virtual std::string encode() { return ""; }
virtual void decode(std::string) {}

encode will encode the state object and return a unique key which type is string.

decode will analyze the given key, and retrive the information from the key into the state obj.

Environment: Their are some method you can choosed to override

• state_transition: Will return the next state key from the given state and the action id.
• valid_actions: Will return a vector of valid actions depend on the given state.
• astar_heuristic: This is the environment user specified heuristic function.
• build_state: Will create a state object you have defined for your environment/game. The returned state object must be initialize with the given key.
• to_string (with two type of overloading): This function is just used to show the information of your environment or game. Take maze for example: show the maze wall on the terminal.

virtual std::string state_transition(std::shared_ptr<State>, int /* action index */);
virtual std::vector<int> valid_actions(std::shared_ptr<State>);
virtual float astar_heuristic(std::shared_ptr<State>) { return -1.0; }
virtual std::shared_ptr<State> build_state(std::string) { return nullptr; }
virtual std::string to_string() const { return ""; }
virtual std::string to_string(const Path&) const { return ""; }

You may override all of them to implement your own environment/game, or you can use append_edge to add the edge into the base environment. This means base Environment already maintain a graph, and the graph's edges are stored in a string-to-string unordered_map.

The method append_edge in the environment is used to apply a new edge into this grpah.

void append_edge(std::string, std::string);

These two parameter are key of a state. That is to say, build an edge of these two state.

If you want to just use append_edge to apply edge into graph, you must not override state_transition and valid_actions. Their default behavior is to retrive the information of the graph.

Implement in Python

Implement in Python is very similar with C++, and more easily.

The Environment in Python still need to create two type of class:

• State
• Environment

As you will guess, there are some methods you should define in your State and Environment class.

For State, you need to define:

• encode
• decode

These two method has same input and return definition with C++ State. A simple example is the SlidingPuzzleState:

def encode(self):
    key = str(self.board_size_) + '_'
    for i in range(self.board_size_ * self.board_size_):
        key += f'{self.board_[i // self.board_size_][i % self.board_size_]};'
    return key[:-1]

def decode(self, key):
    terms = key.split('_')
    if self.board_size_ == 0:
        self.board_size_ = int(terms[0])
        self.board_ = [[0 for i in range(self.board_size_)] for j in range(self.board_size_)]
    board = terms[1].split(';')
    for i in range(len(board)):
        self.board_[i // self.board_size_][i % self.board_size_] = int(board[i])
        if int(board[i]) == 0:
            self.empty_pos_[0] = i // self.board_size_
            self.empty_pos_[1] = i % self.board_size_

encode method return a key according to the state status. decode method retrive status information form a state key. The key is a string.

For Environment, you need to define:

• state_transition: The input is a state key and a action id, you should define how to act an action on a state in this method.
• valid_actions: This input is a state key, and you just need to return a tuple of valid actions id.
• astar_heuristic: The heuristic you can defined by your own. It can be anything what you want.

It's free to define the Environment, just follow the definition of these methods. The example game Sliding Puzzle show how to do a sample define for you. You can follow the style of Sliding Puzzle, or you can create one with your own idea.

Set your Environment to AStarEngine

After you finish define your environment, you must want to apply your environment/game into AStarEngine. In this section, I will tell you how to set your environment to AStarEngine.

C++

In C++, you can modify main.cpp and create a AStarEngine object. For example:

void run_your_game() {
    ...
}

Inside the runing function, you should first create your environment object.

std::shared_ptr<Environment> env = make_shared<YourEnv>(your, parameter);
// initialize your start key and target key of your env
// ...

You must be aware for the type of the shared_ptr. It should be the base class of environment: Environment.

After your environment is ready, you can set your environment to AStarEngine.

AStarEngine engine;
engine.set_environment(env);

Then you can run A* search.

Path path = engine.run();

The returned type is Path which defined in environment.h file. Path save the key on the path from start key to target key.

You can traverse the path by using following methods:

// get(i) will return the ith key.
std::string get(int index);
// size() will return the length of the path.
size_t size();

Python

In Python, the usage of AStarEngine is similar with C++.

def run_your_game():
    ...

Then create your environment object.

env = py_env.your_game.YourGameEnv(your parameter)
# Initialize your environment
# ...

Set your environment object to AStarEngine.

engine = py_env.astar_engine.AStarEngine()
engine.set_environment(env, py_env.your_game.YourGameState)

And last, run the AStarEngine.

path = engine.run()

The path returned by engine.run() is not the type of Path in C++. The Path object has been translate to be a Python list.

System Architecture

This section is for someone who want to understand more detail of this project.

Here are some important point of this project:

1. AStarEngine
2. Environment
3. State

To wrap the AStarEngine into Python, I use Pybind11. So there is a python_wrapper.cpp file.

The first thing I want to share is the inherit path.

Inherit Path

The inherit path is not complex but important. There is a base class of Environment and State. All the implemented environment or games must inherit those base class. (Take Maze for example)

The Environment method "build_state" should return a State pointer. Therefore, Maze (user defined environment) override build_state method, and would initiate MazeState object in this method.

And when we want to use AStarEngine, we must send a pointer of Environment to it.

All AStarEngine need is only the environment object. AStarEngine will not create State object by itself, it only get the state object from environment.

This is the basic structure of the Maze example. If you need to implement other environment/game in C++, just follow this structure to define the environment/game.

The above is only for C++. Python Environment (ex: Sliding Puzzle Game) is not that easy to provide the environment object to AStarEngine.

Wrape Python Environment

To make the environment defined with Python can be accessed by AStarEngine, I use CPython API to access the environment object. The class PythonEnv is defined for wrapping the Python Environment object. When it is need to call the method of the Python environment, it must get the result through PythonEnv.

The class PythonEnv object will hold a real environment Python object by a PyObject pointer.

As the result, when calling those important methods of the PythonEnv, they are all just calling PyObject_CallMethod(...).

That's how PythonEnv get the result from Python environment object, and the Python object must define specific method like state_transition, astar_heuristic, and valid_actions.

And the PythonState class is very similar to PythonEnv.

Set Environment to AStarEngine

Now that's talk about what it did when set the environment to AStarEngine.

For C++

It is very simple in C++ to set an environment object to AStarEngine. Just create a pointer of Environment and send this object through AStarEngine.set_environment.

For Python

In Python, because the Python environment cannot just send into AStarEngine, we must need the class PythonEnv to hold our Python environment object.

You can see the detail of python_wrapper.cpp. When wrapping the AStarEngine.set_environment to Python, I create a PythonEnv object when there is a Python environment Object send into this method.

py::class_<AStarEngine>(m, "AStarEngine")
    .def ("set_environment", [](AStarEngine& self, object& py_env, object& py_state_class) {
        std::shared_ptr<PythonEnv> py_env_wrapper = std::make_shared<PythonEnv>();
        py_env_wrapper->set_py_env(py_env.ptr());
        py_env_wrapper->set_state_class(py_state_class.ptr());
        self.set_environment(py_env_wrapper);
    })

The created PythonEnv object is actually what AStarEngine can see. That is to say, AStarEngine does not need to know that the environment object is whether in C++ or Python.

That's all the System Architecture of this project. Feel free to experience the AStarEngine.