Ya que no he visto mucha información del tema en el foro, les dejo una implementación que he hecho en C++. Mi intención es que se compartamos formas de hacerlo más eficiente, encontrar errores, publicar implementaciones en otros lenguajes...
La implementación que he hecho no tiene interfaz gráfica. La entrada consiste en 4 naturales (f, c, fi, fj) y un mapa. Donde f y c son las filas y las columnas. fi y fj son las coordenadas del final con 0 <= fi < f y 0 <= fj < c. El mapa consiste en '.' terreno libre, 'X' pared y 'I' inicio.
Ejemplo de entrada (en GNU/Linux se puede copiar a un archivo y hacer ./ejecutable <entrada.txt):
- Código: Seleccionar todo
8 16 0 15
X.X......X......
....X..X....XX..
X..X.XX.XXXX..XX
X.X...X......X.I
..X.X.X.XX.X....
....X...X....X..
.XXXXXXX...XX...
.........X.....X
La salida consiste en el mapa inicial con 'O's marcando el camino. También saca por el canal de error los nodos tratados.
Salida:
- Código: Seleccionar todo
X.XOOOOOOX.OOOOO
..OOX..XOOO.XX..
XO.X.XX.XXXX..XX
XOX...X......X.I
.OX.X.X.XX.XOOO.
O...X...X.OOOX..
OXXXXXXXOO.XX...
OOOOOOOOOX.....X
Implementación en C++:
- Código: Seleccionar todo
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
struct Node {
char c;
int g, h, pi, pj;
bool usado;
};
struct NInfo {
int f, i, j;
};
typedef vector<Node> Vn;
typedef vector<Vn> Mn;
#define INF 100000;
bool operator<(const NInfo& ni1, const NInfo& ni2) {
if (ni1.f != ni2.f) return ni1.f > ni2.f;
if (ni1.i != ni2.i) return ni1.i > ni2.i;
return ni1.j > ni2.j;
}
int H(int i, int j, int fi, int fj) {
return abs(i-fi)+abs(j-fj);
}
void escriu(const Mn& m) {
for (int i = 0; i < m.size(); ++i) {
for (int j = 0; j < m[i].size(); ++j) {
cout << m[i][j].c;
}
cout << endl;
}
}
void anyade_nodo(Mn& mn, priority_queue<NInfo>& c, int i, int j, int di, int dj,int fi, int fj, bool diagonal = false) {
int m = mn.size();
int n = mn[0].size();
int incr = 10;
if (diagonal) incr = 14;
if (i+di >= 0 and j+dj >= 0 and i+di < m and j+dj < n and
not mn[i+di][j+dj].usado and mn[i+di][j+dj].g > mn[i][j].g+incr and
mn[i+di][j+dj].c != 'X') {
if (diagonal and mn[i+di][j].c == 'X' or mn[i][j+dj].c == 'X') return;
mn[i+di][j+dj].g = mn[i][j].g+incr;
mn[i+di][j+dj].h = H(i+di, j+dj, fi, fj)*10;
mn[i+di][j+dj].pi = i;
mn[i+di][j+dj].pj = j;
NInfo ni2;
ni2.i = i+di;
ni2.j = j+dj;
ni2.f = mn[i+di][j+dj].g+mn[i+di][j+dj].h;
c.push(ni2);
}
}
int main() {
int m, n;
cin >> m >> n;
int fi, fj;
cin >> fi >> fj;
Mn mn(m, Vn(n));
priority_queue<NInfo> cabierta;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mn[i][j].g = INF;
mn[i][j].usado = false;
cin >> mn[i][j].c;
if (mn[i][j].c == 'I') {
mn[i][j].g = 0;
NInfo ni;
ni.i = i;
ni.j = j;
ni.f = H(i, j, fi, fj);
cabierta.push(ni);
}
}
}
bool final = false;
while (!final and !cabierta.empty()) {
NInfo ni = cabierta.top();
cabierta.pop();
int i = ni.i;
int j = ni.j;
if (i == fi and j == fj) final = true;
if (not mn[i][j].usado and not final) {
cerr << "i:" << i << "j:" << j << endl;
mn[i][j].usado = true;
anyade_nodo(mn, cabierta, i, j, -1, 0, fi, fj);
anyade_nodo(mn, cabierta, i, j, +1, 0, fi, fj);
anyade_nodo(mn, cabierta, i, j, 0, -1, fi, fj);
anyade_nodo(mn, cabierta, i, j, 0, +1, fi, fj);
anyade_nodo(mn, cabierta, i, j, -1, -1, fi, fj, true);
anyade_nodo(mn, cabierta, i, j, +1, +1, fi, fj, true);
anyade_nodo(mn, cabierta, i, j, -1, +1, fi, fj, true);
anyade_nodo(mn, cabierta, i, j, +1, -1, fi, fj, true);
}
}
char c = mn[fi][fj].c;
while (c != 'I') {
mn[fi][fj].c = 'O';
int iaux = mn[fi][fj].pi;
int jaux = mn[fi][fj].pj;
fi = iaux;
fj = jaux;
c = mn[fi][fj].c;
}
escriu(mn);
}
Como documentación he utilizado:
-http://en.wikipedia.org/wiki/A*
-http://www.policyalmanac.org/games/articulo1.htm (aunque no conseguí descargarme la implementación)
Saludos.
