Obtener ruta más corta

[amchacon]

Me encuentro en un problema un poco elemental. A ver si alguien me puede dar alguna pista de como resolverlo.

Tenemos una cuadrícula tal que:



Ahí tenemos dos cuadrados pintados:



Partiendo del cuadrado rojo, tenemos que obtener una ruta para llegar al cuadrado azul (moviendose verticalmente/horizontalmente). Para complicar más la cosa ponemos algunos obstaculos aleatorios:



La ruta más corta sería:

(7,2)
(7,9)
(10,9)


¿Cómo podríamos implementar esto en C++?

[aguml]

yo no te puedo ayudar en eso pero alguna vez he preguntado por algo parecido y me comentaron que buscara info sobre como se crean juegos y sobre los algoritmos de colisiones asi que supongo que es lo que necesitas.

[xiruko]

La ruta más corta sería:
(7,2)
(7,9)
(10,9)

De hecho hay varias que son las más cortas. La que indicas es de 14 cuadrados, igual que por ejemplo, (2, 7) - (9, 7) - (9, 10) o (8, 2) - (8, 3) - (9, 3) - (9, 10), donde el primer número sería la fila y el segundo la columna.

Como primera aproximación, podrías intentar que el cuadrado rojo vaya alternativamente hacia la coordenada x e y del cuadrado azul. Es decir, primero intente ir hasta la coordenada x, si llega a la fila o columna donde está el azul o choca con algo que entonces intente ir hasta la y, si vuelve a chocar que vaya a la x, etc. y así hasta que llegue. En el ejemplo que pones, este algoritmo daría alguna de las soluciones que te he comentado arriba.

Igualmente es demasiado simple así que no le pidas mucho... Si por ejemplo llegaras a chocar y el cuadrado rojo estuviera rodeado por obstáculos, ahí te quedarías... O si chocas con algo mientras estás en la fila o columna donde está el cuadrado azul, te quedarías ahí también...

Pero bueno, igual te da alguna idea para poder empezar.

Saludos!

[ecfisa]

Hola amchacon.

Lo que buscas se resuelve mediante teoría de grafos, en este enlace tenes una explicación genérica: grafos.


Saludos.   

[OmarHack]

Puedes trazar todas las rutas posibles, y seleccionar las más cortas para usar en el programa.

[lapras]

El algoritmo de dijkstra te podria servir. O algo adaptado.

[amchacon]

De hecho hay varias que son las más cortas. La que indicas es de 14 cuadrados, igual que por ejemplo, (2, 7) - (9, 7) - (9, 10) o (8, 2) - (8, 3) - (9, 3) - (9, 10), donde el primer número sería la fila y el segundo la columna.

Como primera aproximación, podrías intentar que el cuadrado rojo vaya alternativamente hacia la coordenada x e y del cuadrado azul. Es decir, primero intente ir hasta la coordenada x, si llega a la fila o columna donde está el azul o choca con algo que entonces intente ir hasta la y, si vuelve a chocar que vaya a la x, etc. y así hasta que llegue. En el ejemplo que pones, este algoritmo daría alguna de las soluciones que te he comentado arriba.

Igualmente es demasiado simple así que no le pidas mucho... Si por ejemplo llegaras a chocar y el cuadrado rojo estuviera rodeado por obstáculos, ahí te quedarías... O si chocas con algo mientras estás en la fila o columna donde está el cuadrado azul, te quedarías ahí también...

Pero bueno, igual te da alguna idea para poder empezar.

Saludos!

No me sirve, los obstaculos pueden estar dispuestos de cualquier forma... Prefiero un método genérico 

Hola amchacon.

Lo que buscas se resuelve mediante teoría de grafos, en este enlace tenes una explicación genérica: grafos.


Saludos.   

El algoritmo de busqueda en anchura es interesante   

El algoritmo de dijkstra te podria servir. O algo adaptado.

Pero aquí las distancias son iguales... No sé si vale la pena *_*

[lapras]

Vale la pena por que el algoritmo de dijkstra es muy eficiente.
Te he hecho un programita en c++ que calcula el camino más corto entre dos celdas de un array.
Tienes obstaculos que se representan con un 1.

La función "getShortestPath" es la que lo hace todo y en el main lo que se hace es probar un ejemplo.

Código (cpp) [Seleccionar] Expandir

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Cell{
int x;
int y;
public:
int getx(){return x;}
int gety(){return y;}
void setx(int x){this->x=x;}
void sety(int y){this->y=y;}

bool operator==(Cell o){return x==o.x && y==o.y;}
Cell operator=(Cell o){x=o.x; y=o.y; return *this;}

Cell(int x,int y):x(x),y(y){}
Cell():x(0),y(0){}
};
vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height);



int main(){
int ejemplo[]={
0,1,0,1,0,0,0,0, //0: void
0,1,0,1,0,0,0,0, //1: obstacle
0,1,0,1,0,0,0,0,
0,1,0,1,0,0,0,0,
0,1,0,1,0,0,0,0,
0,1,0,1,0,0,0,0,
0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,0};

vector<Cell> camino= getShortestPath(Cell(0,0),Cell(7,0),ejemplo,8,8);
for(int i=0;i<camino.size();i++){
cout<<"("<<camino[i].getx()<<", "<<camino[i].gety()<<")"<<endl;
}

}

vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height){

if(ori==dest) return vector<Cell>();
unsigned int *sizes=new unsigned int[width*height];
Cell *prev=new Cell[width*height];
for(int i=0;i<width*height;i++){sizes[i]=-1; prev[i]=Cell(-1,-1);}

sizes[ori.getx()+ori.gety()*width]=0;
prev[ori.getx()+ori.gety()*width]=ori;


queue<Cell> porVisitar;
porVisitar.push(ori);

while(!porVisitar.empty()){
Cell cur=porVisitar.front();
porVisitar.pop();
cout<<porVisitar.size()<<endl;
for(int i=-1;i<2;i++)
for(int j=-1;j<2;j++)
if( (cur.getx()+j)>=0 && (cur.getx()+j)<width && (cur.gety()+i)>=0 && (cur.gety()+i)<height && //is not out of bounds
array[(cur.getx()+j)+(cur.gety()+i)*width]==0 && //is not an obstable
sizes[cur.getx()+cur.gety()*width]+1 < sizes[(cur.getx()+j)+(cur.gety()+i)*width] //there is not a better path
){
sizes[(cur.getx()+j)+(cur.gety()+i)*width]=sizes[cur.getx()+cur.gety()*width]+1;
prev[(cur.getx()+j)+(cur.gety()+i)*width]=Cell(cur.getx(),cur.gety());
porVisitar.push(Cell(cur.getx()+j,cur.gety()+i));
}

}

if(prev[dest.getx()+dest.gety()*width]==Cell(-1,-1)) return vector<Cell>();

Cell pp=dest;
vector<Cell> res(sizes[dest.getx()+dest.gety()*width]+1);
for(int i=res.size()-1; !(pp==ori); i--){
res[i]=pp;
pp=prev[pp.getx()+pp.gety()*width];
}

return res;

}


Lo que se hace es considerar que:
1) Toda celda del array es un nodo.
2) Todas las celdas estan conectadas a sus vecinas.
3) Todas las aristas son bidireccionales.
4) Todas las aristas miden lo mismo: 1.

Y con esto lo que se hace es implementar dijkstra en un caso particular más sencillo.

Te pongo un pastebin para que puedas copiar y pegar:
http://pastebin.com/unRpQgK5

[amchacon]

Muyy interesante 

Es todo lo que necesitaba gracias