Kirjoittaja: Metabolix
Kirjoitettu: 06.08.2015 – 06.08.2015
Tagit: algoritmit, kirjaston käyttö, koodi näytille, vinkki
Tämän koodivinkin pääasiallinen tarkoitus on näyttää, kuinka Boost-kirjaston avulla voidaan kohtuullisen kivuttomasti liittää C++ ja Python yhteen. Esimerkkinä vinkissä toteutetaan A*-algoritmi ja kutsutaan sitä Pythonista.
A*-algoritmia käytetään reitinhakuun tai yleisemmin ratkaisun hakemiseen hakupuusta. Algoritmissa pidetään kirjaa saavutetun ratkaisun osan nykyisestä hinnasta ja arvioidusta loppuhinnasta. Haku jatkuu aina siitä kohdasta, josta loppuhinta arvioidaan pienimmäksi. Esimerkiksi ruudukossa olevassa labyrintissa nykyinen hinta on kuljettujen ruutujen määrä, ja loppuhinnan arvioon täytyy laskea, montako ruutua vähintään vielä on kuljettavana. Arvio ei saa koskaan olla todellista huonompi, koska silloin algoritmi ei välttämättä löydä parasta ratkaisua. Kuitenkin algoritmista tulee sitä tehokkaampi, mitä lähempänä arvio on todellisuutta. Jos loppuhinnan arvioksi asetetaan aina nolla (ts. nykyinen hinta), saadaan itse asiassa yksinkertaisempi Dijkstran algoritmi, joka käy läpi enemmän selvästi huonojakin vaihtoehtoja.
Tässä koodissa on A*-algoritmin toteutus. Funktion parametrit muutetaan Pythonin muuttujista tavallisiksi C++:n muuttujiksi, paluuarvo on Pythonin lista, ja koodin lopussa on muutama rivi, joilla funktio saadaan näkymään Pythonille.
Koodin kääntämiseen tarvitaan C++-kääntäjälle Boost- ja Python-kirjastot. Kääntäminen tapahtuu suunnilleen tällaisella komennolla:
g++ -o astarcpp.so -std=c++11 -Wall -pedantic -I/usr/include/python2.7/ -lboost_python -lpython2.7 -fPIC -shared astar.cpp
// astar.cpp
#include <set>
#include <map>
#include <boost/python.hpp>
namespace py = boost::python;
#if 0 // Vaihda ykköseksi, jos haluat nähdä, miten algoritmi etenee.
#include <iostream>
#define debug_output(a, b) \
((std::cout << a << b->x << ", " << b->y << ", cost " \
<< b->costNow << " / " << b->costTotal << "\n"), ((void)0))
#else
#define debug_output(a, b) ((void)0)
#endif
/// Tietue sijainnin säilyttämistä varten.
struct Position {
int x, y;
bool operator < (const Position& p) const {
return y < p.y || (y == p.y && x < p.x);
}
};
/// Tietue ruudun tietoja varten: sijainti, edellinen, hinta.
struct PathNode: Position {
PathNode* previous;
int costNow, costTotal;
bool started, done;
/// Kahden tilanteen vertailu: halvempi ensin.
struct CompareCostLess {
bool operator() (PathNode* const& a, PathNode* const& b) {
return a->costTotal < b->costTotal || (a->costTotal == b->costTotal && a < b);
}
};
};
/// A*-hakualgoritmi.
static py::object search(
py::list py_map_usable,
py::tuple py_a_pos,
py::tuple py_b_pos,
bool debug
) {
// Alku ja loppu C++-muotoon.
Position a_pos {py::extract<int>(py_a_pos[0]), py::extract<int>(py_a_pos[1])};
Position b_pos {py::extract<int>(py_b_pos[0]), py::extract<int>(py_b_pos[1])};
// Kartalta käytettävissä olevat pisteet C++-muotoon.
std::map<Position, PathNode> map;
const long len = py::len(py_map_usable);
for (long i = 0; i < len; ++i) {
Position p {py::extract<int>(py_map_usable[i][0]), py::extract<int>(py_map_usable[i][1])};
map[p].x = p.x;
map[p].y = p.y;
}
// Debuggaustilaa varten lista, johon kootaan kaikki vieraillut ruudut.
py::list debug_list;
// Tarkistetaan, että alkupiste ja loppupiste ovat olemassa.
auto a_iter = map.find(a_pos);
auto b_iter = map.find(b_pos);
if (a_iter == map.end() || b_iter == map.end()) {
return py::list();
}
PathNode* a_node = &a_iter->second;
PathNode* b_node = &b_iter->second;
// Merkitään alkupiste seuraavaksi käsiteltävien listaan.
// Tarkemmilla tiedoilla ei ole merkitystä, koska se on ainoa listalla.
std::set<PathNode*, PathNode::CompareCostLess> todo = {a_node};
// Kierretään silmukkaa niin kauan, kuin on tutkimattomia reittejä.
while (!todo.empty()) {
// Otetaan se reitin pää, josta voisi olla lyhin matka perille.
auto iter = todo.begin();
auto node = *iter;
todo.erase(iter);
debug_output("pop : ", node);
if (debug) {
debug_list.append(py::make_tuple(node->x, node->y));
}
// Merkitään tämän ruudun käsittely valmiiksi; ei voi olla lyhyempää reittiä tähän.
node->done = true;
// Jos ollaan jo perillä, palautetaan löydetty reitti.
if (node == b_node) {
if (debug) {
return debug_list;
}
py::list result;
for (; node; node = node->previous) {
result.append(py::make_tuple(node->x, node->y));
}
result.reverse();
return result;
}
// Muuten käydään läpi kaikki eri jatkosuunnat.
std::array<int, 2> directions[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& direction: directions) {
// Haetaan seuraava ruutu; jos ei löydy (tai on seinä), ohitetaan tämä suunta.
auto iter = map.find(Position {node->x + direction[0], node->y + direction[1]});
if (iter == map.end() || iter->second.done) {
continue;
}
PathNode* next = &iter->second;
// Uuden ruudun hinta (matka alusta) on yhden suurempi kuin edellisen.
int costNow = node->costNow + 1;
// Optimistinen arvio loppumatkasta lasketaan, kuin maaliin pääsisi suorinta reittiä.
int estimate = std::abs(b_node->x - next->x) + std::abs(b_node->y - next->y);
// Jos uutta ruutua ei ole vielä tutkittu
// tai jos nykyinen reitti siihen oli parempi kuin ennen,
if (!next->started || next->costNow > costNow) {
// poistetaan uusi ruutu todo-joukosta,
// päivitetään tiedot ja lisätään uudestaan todo-joukkoon.
todo.erase(next);
next->started = true;
next->previous = node;
next->costNow = costNow;
next->costTotal = costNow + estimate;
debug_output("push: ", next);
todo.insert(next);
}
}
}
// Jos silmukka loppuu, kelvollista reittiä ei ole.
if (debug) {
return debug_list;
}
return py::list();
}
// Pythonille funktiot debugilla ja ilman.
py::object search_debug(py::list map, py::tuple a, py::tuple b) {
return search(map, a, b, true);
}
py::object search_nodebug(py::list map, py::tuple a, py::tuple b) {
return search(map, a, b, false);
}
BOOST_PYTHON_MODULE(astarcpp) {
py::def("search", search_nodebug, py::args("map", "a", "b"));
py::def("search_debug", search_debug, py::args("map", "a", "b"));
}Moduuli toimii Pythonissa aivan normaalisti: tarvitaan import-rivi, minkä jälkeen funktioita voi kutsua tavalliseen tapaan.
#!/usr/bin/env python2 # -*- coding: utf-8 -*- from __future__ import print_function import astarcpp class GameMap: def __init__(self, data): self.data = data self.path = [] def solve(self): # Etsitään kartasta reitin alkupiste (A) ja loppupiste (B). # Jos pisteitä ei löydy, käytetään alueen nurkkia. self.a = self.b = a_first = b_last = None for y in range(len(self.data)): for x in range(len(self.data[y])): if self.data[y][x] == 'A': self.a = (x, y) elif self.data[y][x] == 'B': self.b = (x, y) elif self.data[y][x] != '#': b_last = (x, y) if a_first is None: a_first = (x, y) if self.a is None: self.a = a_first if self.b is None: self.b = b_last # Muutetaan kartta listaksi, jossa ovat vain avoimet ruudut. map_usable = [ (x, y, self.data[y][x]) for y in range(len(self.data)) for x in range(len(self.data[y])) if self.data[y][x] != "#" ] # Haetaan reitti. self.path = astarcpp.search(map_usable, self.a, self.b) def __str__(self): # Jos reittiä ei ole, palautetaan tekstinä kartta suoraan. if len(self.path) == 0: return '\n'.join(self.data) # Muuten käydään kartta läpi ja merkitään reitti. s = '' for y in range(len(self.data)): for x in range(len(self.data[y])): p = (x, y) if p == self.a: s += 'A' elif p == self.b: s += 'B' elif p in self.path: s += '.' else: s += self.data[y][x] s += '\n' return s[:-1] # Luodaan kartta, haetaan reitti, tulostetaan ratkaisu. a = GameMap([ "#####################", "#A# # # #", "# # # # # # # #", "# ### # # # # # #", "# # # # # # #", "# # ##### # # # # # #", "# # # # # # # #", "# # ####### # # # #", "# # # # # # # #", "# # ####### # # # # #", "# # # # # #", "# # ########### # # #", "# # # # #", "# ############### # #", "# #B#", "#####################", ]) a.solve() print(a)