//////////////////////////////////////////////////////////////////////////////////////
//
// Author: Seree Rakwong
// Date: 29-NOV-10
//
// Update: 2-DEC-10
// History: - Allocated memory for map if it has been assinged by assignment operator
//
#ifndef astar_h
#define astar_h
//
// memory map
//
class astar_point {
int row_;
int col_;
public:
astar_point();
astar_point(int row, int col);
int row() const { return row_; }
int& row() { return row_; }
int col() const { return col_; }
int& col() { return col_; }
};
class astar_node : public astar_point {
astar_point parent_;
int Gcost_;
int Hcost_;
int what_; // what is an object? path? wall? river? water? tree? or other obstacles?
public:
astar_node();
astar_node(const astar_point& parent, int row, int col);
public:
astar_point& parent() { return parent_; }
astar_point parent() const { return parent_; }
int& what() { return what_; }
int what() const { return what_; }
int Fcost() const { return (Gcost_ + Hcost_); }
int& Gcost() { return Gcost_; }
int& Hcost() { return Hcost_; }
int Gcost() const { return Gcost_; }
int Hcost() const { return Hcost_; }
public:
bool operator==(const astar_node& node);
bool operator==(const astar_point& point);
bool operator!=(const astar_node& node);
};
class astar_map {
int *map_ptr_;
int row_;
int col_;
public:
astar_map();
astar_map(const astar_map&);
virtual ~astar_map();
astar_map& operator=(const astar_map&);
public:
void destroy();
int create(int row, int col, int walkable = 0);
int get(int row, int col);
int set(int row, int col, int val);
int row() const { return row_; }
int col() const { return col_; }
};
//
// This is a helper class to load a map from file
//
#include <fstream>
#include <list>
class astar_map_loader : std::ifstream {
std::string filename_;
public:
astar_map_loader();
astar_map_loader(const char *filename);
virtual ~astar_map_loader();
int load(astar_map *amap, astar_node *begin, astar_node *end);
};
//
// This is an A* class
//
#include <vector>
class astar {
std::vector<astar_node> openlist_;
std::vector<astar_node> closedlist_;
astar_map *map_;
astar_node begin_node_; // this is a start point
astar_node end_node_; // this is a goal point
public:
astar();
virtual ~astar();
public:
int load_map(astar_map_loader& loader, astar_node *begin, astar_node *end);
int find_path(const astar_node& begin, const astar_node& end, std::list<astar_point> *path);
public:
astar_node& begin_node() { return begin_node_; }
astar_node& end_node() { return end_node_; }
astar_map* map() { return map_; }
void map(const astar_map& amap);
private:
void create_map();
void destroy_map();
astar_node lowest_Fcost_from_openlist();
void move_openlist_to_closedlist(astar_node& open_node);
void update_openlist(const astar_node& update_node);
bool is_on_openlist(const astar_node& node, astar_node *open_node);
bool is_on_closedlist(const astar_node& node);
bool is_cutting_across(const astar_node& node);
bool is_terrain(int row, int col);
astar_node& get_node(const astar_point& point);
protected:
virtual bool is_walkable(const astar_node& node);
virtual int get_Gcost(const astar_node& parent, int row, int col);
virtual int get_Hcost(const astar_node& node);
virtual std::vector<astar_node> get_adjacent_nodes(const astar_node& node, bool all_adjacent_nodes = true);
};
#endif // astar_h
//////////////////////////////////////////////////////////////////////////////////////
//
// astar.cpp
//
// Author: Seree Rakwong
// Date: 1-DEC-10
//
// Update: 2-DEC-10
// History: - Allocated memory for map if it has been assinged by assignment operator
// - Ignored the cutting across
//
#include "astar.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
//
// astar_point
//
astar_point::astar_point()
: row_(-1),
col_(-1) {
}
astar_point::astar_point(int row, int col)
: row_(row),
col_(col) {
}
//
// astar_node
//
astar_node::astar_node()
: parent_(),
Gcost_(1000000),
Hcost_(1000000),
what_(-1)
{
}
astar_node::astar_node(const astar_point& parent, int row, int col)
: astar_point(row, col),
parent_(parent),
Gcost_(1000000),
Hcost_(1000000),
what_(-1)
{
}
bool astar_node::operator==(const astar_point& point) {
return (row() == point.row() && col() == point.col());
}
bool astar_node::operator==(const astar_node& node) {
return (row() == node.row() && col() == node.col());
}
bool astar_node::operator!=(const astar_node& node) {
return (row() != node.row() || col() != node.col());
}
//
// astar_map
//
astar_map::astar_map()
: row_(0),
col_(0),
map_ptr_(0) {
}
astar_map::astar_map(const astar_map& amap)
: row_(0),
col_(0),
map_ptr_(0) {
if(amap.row() > 0 && amap.col() > 0) {
row_ = amap.row();
col_ = amap.col();
if(amap.map_ptr_) {
map_ptr_ = new int[row_*col_];
memcpy(map_ptr_, amap.map_ptr_, row_*col_*sizeof(int));
}
}
}
astar_map::~astar_map() {
destroy();
}
astar_map& astar_map::operator=(const astar_map& amap) {
if(this == &amap) return *this;
int row = amap.row();
int col = amap.col();
if(row <= 0 || col <= 0) return *this;
if(!amap.map_ptr_) return *this;
int *temp = new int[row*col];
if(!temp) return *this;
memcpy(temp, amap.map_ptr_, row*col*sizeof(int));
if(map_ptr_) delete[] map_ptr_;
map_ptr_ = temp;
row_ = row;
col_ = col;
return *this;
}
void astar_map::destroy() {
if(map_ptr_) {
delete[] map_ptr_;
map_ptr_ = 0;
}
row_ = 0;
col_ = 0;
}
int astar_map::create(int row, int col, int walkable) {
if(row <= 0 || col <= 0) return -1;
// cleanup the memory if necessary
destroy();
map_ptr_ = new int[row*col];
if(!map_ptr_) return -2;
memset(map_ptr_, walkable, row*col*sizeof(int));
// save the row and column
row_ = row;
col_ = col;
return 0;
}
//
// Return: It should be equal or greater than 0. If failed, returned value will be less than 0
//
int astar_map::get(int row, int col) {
if(!map_ptr_) return -1;
if(row < 0 || col < 0) return -2;
if(row >= row_ || col >= col_) return -3;
return map_ptr_[(col_*row)+col];
}
int astar_map::set(int row, int col, int val) {
if(!map_ptr_) return -1;
if(row < 0 || col < 0) return -2;
if(row >= row_ || col >= col_) return -3;
int old_val = map_ptr_[(col_*row)+col];
map_ptr_[(col_*row)+col] = val;
return old_val;
}
//
// astar_map_loader
//
astar_map_loader::astar_map_loader()
: ifstream() {
}
astar_map_loader::astar_map_loader(const char *filename)
: ifstream(filename) {
}
astar_map_loader::~astar_map_loader() {
close();
}
//
// simply read a file
// e.g.
//
//# no space between key and value
//# max_row=maximum a row
//# max_col=maximum a column
//# row_n=0 1 2 3 ... max_col-1 (only 1 character allowed and 1 space)
//max_row=6
//max_col=8
//start_row=2
//start_col=2
//end_row=2
//end_col=6
//row_0=0 0 0 0 0 0 0 0
//row_1=1 1 1 1 1 0 0 0
//row_2=0 0 0 0 1 0 0 0
//row_3=0 0 0 0 1 1 1 0
//row_4=0 0 0 0 1 0 1 0
//row_5=0 0 0 0 0 0 0 0
//
int astar_map_loader::load(astar_map *amap, astar_node *begin_node, astar_node *end_node) {
if(!is_open()) return -1;
string str;
char buffer[1024];
int max_row = 0, max_col = 0;
int start_row = -1, start_col = -1;
int end_row = -1, end_col = -1;
while(good()) {
getline(buffer, 1024);
str = buffer;
// skip if it is a comment or an empty line
if(buffer[0] == '#' || str.length() == 0) continue;
size_t pos = str.find_first_of('=');
string key = str.substr(0, pos);
string val = str.substr(pos+1, str.length());
if(key == "max_row") {
max_row = atoi(val.c_str());
if(max_row > 0 && max_col > 0) amap->create(max_row, max_col);
}
else if(key == "max_col") {
max_col = atoi(val.c_str());
if(max_row > 0 && max_col > 0) amap->create(max_row, max_col);
}
else if(key == "start_row") {
start_row = atoi(val.c_str());
if(start_row >= 0 && start_col >= 0) {
begin_node->row() = start_row;
begin_node->col() = start_col;
begin_node->Gcost() = 0;
begin_node->Hcost() = 0;
}
}
else if(key == "start_col") {
start_col = atoi(val.c_str());
if(start_row >= 0 && start_col >= 0) {
begin_node->row() = start_row;
begin_node->col() = start_col;
begin_node->Gcost() = 0;
begin_node->Hcost() = 0;
}
}
else if(key == "end_row") {
end_row = atoi(val.c_str());
if(end_row >= 0 && end_col >= 0) {
end_node->row() = end_row;
end_node->col() = end_col;
end_node->Gcost() = 0;
end_node->Hcost() = 0;
}
}
else if(key == "end_col") {
end_col = atoi(val.c_str());
if(end_row >= 0 && end_col >= 0) {
end_node->row() = end_row;
end_node->col() = end_col;
end_node->Gcost() = 0;
end_node->Hcost() = 0;
}
}
else {
if(max_row <= 0 || max_col <= 0) continue;
// find the row
int r;
for(r=0; r<max_row; r++) {
char row_buffer[16];
sprintf(row_buffer, "row_%d", r);
if(key == row_buffer) break;
}
// ok, set value into the map
int c;
for(c=0; c<max_col; c++) {
amap->set(r, c, val[c*2]-'0');
}
}
}
return 0;
}
//
// A*
//
astar::astar()
: map_(0) {
}
astar::~astar() {
destroy_map();
}
int astar::load_map(astar_map_loader& loader, astar_node *begin_node, astar_node *end_node) {
create_map();
return loader.load(map_, begin_node, end_node);
}
void astar::create_map() {
destroy_map();
map_ = new astar_map();
}
void astar::destroy_map() {
if(map_) delete map_;
map_ = 0;
}
void astar::map(const astar_map& amap) {
create_map();
*map_ = amap;
}
int astar::find_path(const astar_node& begin_node,
const astar_node& end_node,
list<astar_point> *path) {
// reset all openlist and closelist
openlist_.clear();
closedlist_.clear();
// save begin and end nodes
begin_node_ = begin_node; // Fcost = 0, Gcost = 0, Hcost = 0
end_node_ = end_node;
// 1) add the starting node to the open list
begin_node_.parent() = astar_point();
end_node_.parent() = astar_point();
openlist_.push_back(begin_node_);
int found_path = 0;
// 2) repeat the following
astar_node empty_node;
do {
// 2.1) look for the lowest F cost node on the open list that we refer to this as the current node
astar_node lowest_Fcost_node = lowest_Fcost_from_openlist();
#ifdef DEBUG
printf("lowest_Fcost_node, R[%d], C[%d], V[%d], F[%d], G[%d], H[%d]\n", lowest_Fcost_node.row(),
lowest_Fcost_node.col(), lowest_Fcost_node.what(),
lowest_Fcost_node.Fcost(), lowest_Fcost_node.Gcost(), lowest_Fcost_node.Hcost());
#endif
if(found_path || empty_node == lowest_Fcost_node)
break;
// 2.2) switch it to the closed list
move_openlist_to_closedlist(lowest_Fcost_node);
#ifdef DEBUG
printf("add closedlist: G[%d], H[%d], prow[%d], pcol[%d], row[%d], col[%d]\n",
lowest_Fcost_node.Gcost(), lowest_Fcost_node.Hcost(),
lowest_Fcost_node.parent().row(), lowest_Fcost_node.parent().col(),
lowest_Fcost_node.row(), lowest_Fcost_node.col());
#endif
// 2.3) for each of the 8 adjacent node to this
vector<astar_node> adj_nodes = get_adjacent_nodes(lowest_Fcost_node);
vector<astar_node>::iterator it = adj_nodes.begin();
for(; it != adj_nodes.end(); it++) {
// 2.3.1) if it is not walkable or if it is on the closed list, ignore it. otherwise do the following
astar_node cur_node(*it);
#ifdef DEBUG
printf("cur_node, R[%d], C[%d], V[%d], F[%d], G[%d], H[%d]", cur_node.row(),
cur_node.col(), cur_node.what(),
cur_node.Fcost(), cur_node.Gcost(), cur_node.Hcost());
#endif
if(!is_walkable(cur_node) ||
is_on_closedlist(cur_node)) {
continue;
}
if(is_cutting_across(cur_node)) {
// need to add Gcost value
#ifdef DEBUG
printf("before: G[%d], H[%d], prow[%d], pcol[%d], row[%d], col[%d]\n",
cur_node.Gcost(), cur_node.Hcost(),
cur_node.parent().row(), cur_node.parent().col(),
cur_node.row(), cur_node.col());
#endif
cur_node.Gcost() += 24;
#ifdef DEBUG
printf("after: G[%d], H[%d], prow[%d], pcol[%d], row[%d], col[%d]\n",
cur_node.Gcost(), cur_node.Hcost(),
cur_node.parent().row(), cur_node.parent().col(),
cur_node.row(), cur_node.col());
#endif
}
// 2.3.2) if it is not on the open list, add it to the open list. make the current node to the parent
// of this node. record the F, G, and H costs of the node
astar_node open_node;
if(!is_on_openlist(cur_node, &open_node)) {
#ifdef DEBUG
printf("add openlist: G[%d], H[%d], prow[%d], pcol[%d], row[%d], col[%d]\n",
cur_node.Gcost(), cur_node.Hcost(),
cur_node.parent().row(), cur_node.parent().col(),
cur_node.row(), cur_node.col());
#endif
openlist_.push_back(cur_node);
}
else {
// 2.3.3) if it is on the open list already, check to see if this path to that node is better,
// using G cost as the measure. a lower G cost means that this is a better path. if so,
// change the parent of the node to the current node, and recalculate the G and F scores
// of the node.
if(cur_node == open_node) {// && cur_node.Gcost() < open_node.Gcost()) {
#ifdef DEBUG
printf("cur: prow[%d], pcol[%d], row[%d], col[%d], G[%d] :: open prow[%d], pcol[%d], G[%d]\n",
cur_node.parent().row(), cur_node.parent().col(),
cur_node.row(), cur_node.col(), cur_node.Gcost(),
open_node.parent().row(), open_node.parent().col(), open_node.Gcost());
#endif
if(cur_node.Gcost() < open_node.Gcost()) {
open_node.parent() = astar_point(cur_node.parent().row(), cur_node.parent().col());
open_node.Gcost() = cur_node.Gcost();
open_node.Hcost() = get_Hcost(lowest_Fcost_node);
update_openlist(open_node);
}
}
}
// 2.3.4) add the target node to the closed list, in which case the path has been found, or
if(cur_node == end_node_) {
found_path = 1;
end_node_.parent() = astar_point(cur_node.row(), cur_node.col());
move_openlist_to_closedlist(cur_node);
break;
}
// 2.3.5) fail to find the target node, and open list is empty. in this case, there is no path
if(openlist_.empty()) {
found_path = -1;
break;
}
}
} while(1);
// 3) save the path. working backwards from the target node, go from each node to its parent node until
// reach the starting node.
if(found_path == 1) {
astar_node path_node = end_node_;
while(path_node != begin_node_) {
path->push_front(path_node.parent());
path_node = get_node(path_node.parent());
}
return 0; // succeeded
}
return 1; // failed
}
astar_node astar::lowest_Fcost_from_openlist() {
vector<astar_node>::iterator it = openlist_.begin();
astar_node lowest_node;
for(; it != openlist_.end(); it++) {
if(lowest_node.Fcost() > (*it).Fcost()) {
lowest_node = *it;
}
}
return lowest_node;
}
void astar::move_openlist_to_closedlist(astar_node& open_node) {
// remove from the openlist
vector<astar_node>::iterator it = openlist_.begin();
for(; it != openlist_.end(); it++) {
if((*it) == open_node) {
openlist_.erase(it);
break;
}
}
// add it into the closedlist
closedlist_.push_back(open_node);
}
vector<astar_node> astar::get_adjacent_nodes(const astar_node& parent, bool all_adjacent_nodes) {
vector<astar_node> nodes;
int row = parent.row();
int col = parent.col();
for(int r=row-1; r<=row+1; r++) {
for(int c=col-1; c<=col+1; c++) {
if(r == row && c == col) continue; // skip itself
if(all_adjacent_nodes) {
astar_node adj_node(astar_point(row, col), r, c);
adj_node.Gcost() = get_Gcost(parent, r, c);
adj_node.Hcost() = get_Hcost(adj_node);
adj_node.what() = map_->get(r, c);
nodes.push_back(adj_node);
}
else {
if(r == row || c == col) {
astar_node adj_node(astar_point(row, col), r, c);
adj_node.Gcost() = get_Gcost(parent, r, c);
adj_node.Hcost() = get_Hcost(adj_node);
adj_node.what() = map_->get(r, c);
nodes.push_back(adj_node);
}
}
}
}
return nodes;
}
int astar::get_Gcost(const astar_node& parent, int row, int col) {
if(row == parent.row() || col == parent.col())
return parent.Gcost() + 10;
return parent.Gcost() + 14;
}
int astar::get_Hcost(const astar_node& node) {
return 10*(abs(node.row()-end_node_.row()) + abs(node.col()-end_node_.col()));
}
bool astar::is_on_closedlist(const astar_node& node) {
vector<astar_node>::iterator it = closedlist_.begin();
for(; it != closedlist_.end(); it++) {
if((*it) == node) return true;
}
return false;
}
bool astar::is_on_openlist(const astar_node& node, astar_node *open_node) {
vector<astar_node>::iterator it = openlist_.begin();
for(; it != openlist_.end(); it++) {
if((*it) == node) {
*open_node = (*it);
return true;
}
}
return false;
}
bool astar::is_walkable(const astar_node& node) {
if(node.row() < 0 ||
node.col() < 0 ||
node.row() >= map_->row() ||
node.col() >= map_->col())
return false;
return (0 == map_->get(node.row(), node.col()));
}
bool astar::is_cutting_across(const astar_node& node) {
int row = node.row();
int col = node.col();
int prow = node.parent().row();
int pcol = node.parent().col();
if(row == prow || col == pcol) return false;
astar_node test_node(astar_point(), prow, col);
astar_node test_node2(astar_point(), row, pcol);
if(!is_walkable(test_node) || !is_walkable(test_node2)) return true;
return false;
}
bool astar::is_terrain(int row, int col) {
if(row < 0 || col < 0 ||
row >= map_->row() ||
col >= map_->col())
return false;
if(map_->get(row, col))
return true;
return false;
}
astar_node& astar::get_node(const astar_point& point) {
vector<astar_node>::iterator it = closedlist_.begin();
for(; it != closedlist_.end(); it++) {
if((*it) == point) {
return (*it);
}
}
return *closedlist_.end();
}
void astar::update_openlist(const astar_node& update_node) {
vector<astar_node>::iterator it = openlist_.begin();
for(; it != openlist_.end(); it++) {
if((*it) == update_node) {
(*it).parent() = update_node.parent();
(*it).Gcost() = update_node.Gcost();
(*it).Hcost() = update_node.Hcost();
break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////
//
//
// Author: Seree Rakwong
// Date: 1-DEC-10
//
#include <iostream>
#include "astar.h"
using namespace std;
const int MAX_ROW = 10;
const int MAX_COL = 10;
int map_1_1[MAX_ROW][MAX_COL] = {
{0, 1, 1, 0, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 0, 0, 1, 1, 0, 0}
};
int main(int argc, char **argv) {
astar_map sample_map;
int rc = sample_map.create(MAX_ROW, MAX_COL);
if(rc < 0) {
cerr << "create map failed\n";
return 1;
}
int r, c;
for(r=0; r<MAX_ROW; r++) {
for(c=0; c<MAX_COL; c++) {
rc = sample_map.set(r, c, map_1_1[r][c]);
}
}
astar _astar;
astar_node begin_node, end_node;
begin_node.row() = 0; begin_node.col() = 0; begin_node.Gcost() = 0; begin_node.Hcost() = 0;
end_node.row() = 9; end_node.col() = 9; end_node.Gcost() = 0; end_node.Hcost() = 0;
if(argc == 2) {
astar_map_loader loader(argv[1]);
_astar.load_map(loader, &begin_node, &end_node);
}
else {
_astar.map(sample_map);
}
astar_map *amap = _astar.map();
int max_row = amap->row();
int max_col = amap->col();
printf("Map loaded...\n");
printf(" ");
for(c=0; c<max_col; c++) {
printf("%-2d ", c);
}
printf("\n");
for(r=0; r<max_row; r++) {
printf("row_%02d: ", r);
for(c=0; c<max_col; c++) {
rc = amap->get(r, c);
printf("%-2d ", rc);
}
printf("\n");
}
printf("\nPath finding ...\n");
list<astar_point> path;
if(_astar.find_path(begin_node, end_node, &path)) {
cout << "path not found" << endl;
return 1;
}
list<astar_point>::iterator it = path.begin();
for(; it != path.end(); it++) {
r = (*it).row();
c = (*it).col();
printf("(%d, %d), ", r, c);
amap->set(r, c, 'X');
}
printf("\n");
printf("Map solving...\n");
printf(" ");
for(c=0; c<max_col; c++) {
printf("%-2d ", c);
}
printf("\n");
for(r=0; r<max_row; r++) {
printf("row_%02d: ", r);
for(c=0; c<max_col; c++) {
rc = amap->get(r, c);
if(rc == 'X') printf("%-2c ", (char)rc);
else printf("%-2d ", rc);
}
printf("\n");
}
return 0;
}
########################################################
# Author: Seree Rakwong
# Date: 1-DEC-10
# Filename: found_path.map
#
# no space between key and value
# max_row=maximum a row
# max_col=maximum a column
# row_n=0 1 2 3 ... max_col-1
# the row_n values must be 1 character
#
max_row=10
max_col=10
start_row=9
start_col=9
end_row=0
end_col=0
row_0=0 1 0 0 0 0 1 1 1 1
row_1=0 1 0 0 1 0 0 0 0 1
row_2=0 1 0 0 1 0 0 0 0 1
row_3=0 1 0 0 1 0 0 0 1 1
row_4=0 1 0 0 0 0 1 0 1 0
row_5=0 1 1 0 1 0 1 0 1 0
row_6=0 1 0 0 1 0 1 0 1 0
row_7=0 0 0 0 1 0 1 0 1 0
row_8=1 1 1 1 1 1 1 0 1 0
row_9=0 0 0 0 0 0 0 0 0 0
OUTPUT:
./astar found_path.map
Map loaded...
0 1 2 3 4 5 6 7 8 9
row_00: 0 1 0 0 0 0 1 1 1 1
row_01: 0 1 0 0 1 0 0 0 0 1
row_02: 0 1 0 0 1 0 0 0 0 1
row_03: 0 1 0 0 1 0 0 0 1 1
row_04: 0 1 0 0 0 0 1 0 1 0
row_05: 0 1 1 0 1 0 1 0 1 0
row_06: 0 1 0 0 1 0 1 0 1 0
row_07: 0 0 0 0 1 0 1 0 1 0
row_08: 1 1 1 1 1 1 1 0 1 0
row_09: 0 0 0 0 0 0 0 0 0 0
Path finding ...
(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (3, 4), (3, 5), (3, 6), (4, 7), (4, 8), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9),
Map solving...
0 1 2 3 4 5 6 7 8 9
row_00: X 1 1 0 0 0 1 1 0 0
row_01: X 1 1 0 0 0 0 0 0 0
row_02: X X X X 0 0 1 1 0 0
row_03: 0 1 1 0 X X X 0 0 0
row_04: 0 1 1 0 0 0 0 X X 0
row_05: 0 0 0 0 0 0 1 1 0 X
row_06: 0 0 0 0 0 0 1 1 0 X
row_07: 0 1 1 0 0 0 1 0 0 X
row_08: 0 0 0 0 0 0 1 0 0 X
row_09: 0 1 1 0 0 0 1 1 0 X
