!HelP! Have Problems with algorithm A* (A star) in processing

Programming Questions

cuqtaa

!HelP! Have Problems with algorithm A* (A star) in processing

in Programming Questions • 6 months ago

I have probremas as sometimes the algorithm A star, gives me the route from the endpoint to the starting point, and in other cases does not give me the route or a route straight will attach some pictures so they can see.

Picture 1.

Tables are dark yellow route boxes, white boxes in the list boxes are closed and the blue boxes are in the open list.

in the picture above it seems that everything is fine, but the problem arises in the following situations.

in the following picture fine too.

Error in Astar in the follow pictures...

in the following pictures you can see that the algorithm is not scoring well I end path, errors have proven time and otherwise, but I can not always make the algorithm fits well for any route with obstacles or not.

I need to solve this problem the algorithm is about my thesis University of Francisco de Paula Santander Colombia, Cucuta, this is an application that will direct to a mobile robot to verify if the path is clear of obstacles, in my university do not handle processing I'm starting with, so I need help from the communities, will attach the code of algritmo be grateful to all those who can help me.

void Planeacion()
{int f=0;
int g=0;
int h=0;
int indice = 0;
//Expande NodoInicial en 8posiciones
while(finalizado == false){
if(abierta.size() == 0)
{println("NO HAY CAMINO HACIA LA META");
rutafin();
finalizado = true;}
int menor = ((ClassNodo)abierta.get(0)).fRead();
mejornodo = 0;
for(int t = abierta.size()-1;t != 0;t--){
if(menor > ((ClassNodo)abierta.get(t)).fRead())
{
menor=((ClassNodo)abierta.get(t)).fRead();
mejornodo = t;}}
nodoactual = ((ClassNodo)abierta.get(mejornodo));
nodoactual.indiceWrite(indice);
print("NCApunta:");print(nodoactual.pxRead());println(nodoactual.pyRead());
abierta.remove(mejornodo);
cerrada.add(nodoactual);
indice++;
if(nodoactual.hpos.xRead() == (destino.xRead()) && nodoactual.hpos.yRead() == (destino.yRead()))
{println("Solucion Encontrada");
nodofin.pxWrite(nodoactual.hpos.xRead());
nodofin.pyWrite(nodoactual.hpos.yRead());
rutafin();
draw();
finalizado = true;}
else{
for(int i = nodoactual.hpos.xRead()-1;i < nodoactual.hpos.xRead()+2; i++)
{
for(int j= nodoactual.hpos.yRead()-1;j<nodoactual.hpos.yRead()+2; j++)
{ countfor++;
if(i>=0 && i<=49 && j>=0 && j<=49){
if(i == nodoactual.hpos.xRead() && j == nodoactual.hpos.yRead() )
{ }
else{count++;
findcerrada = false;
findabierta = false;
findobstaculo = false;
posad = new ClassCoordenada(i,j);
nodoadyacente = new ClassNodo(posad,0,0,0,0,0,0);
if(posad.xRead() == nodoactual.hpos.xRead() || posad.yRead()== nodoactual.hpos.yRead() )
{g =10;
}
else{g = 14;}
nodoadyacente.pxWrite(nodoactual.hpos.xRead());
nodoadyacente.pyWrite(nodoactual.hpos.yRead());
nodoadyacente.gWrite(g + nodoactual.gRead());
nodoadyacente.hWrite(heuristic(nodoadyacente, nodofin));
nodoadyacente.fWrite(nodoadyacente.gRead() + nodoadyacente.hRead());
findcerrada = false;
for(int c = cerrada.size()-1; c >=0; c--)
{ findcerrada = false;
if(posad.xRead() == ((ClassNodo)cerrada.get(c)).hpos.xRead()
&& posad.yRead() == ((ClassNodo)cerrada.get(c)).hpos.yRead()
){
findcerrada = true;
break;
}}
findobstaculo = false;
if(findcerrada == false){
for(int l = obstaculo.size()-1; l >=0; l--)
{
if( i == (((ClassNodo)obstaculo.get(l)).hpos.xRead())
&& j == (((ClassNodo)obstaculo.get(l)).hpos.yRead())
){println("obstaculo");findobstaculo = true;break;}} }
if(findabierta == false && findobstaculo == false){
for(int c = abierta.size()-1;c>=0;c--){
if(posad.xRead() == ((ClassNodo)abierta.get(c)).hpos.xRead()
&& posad.yRead() == ((ClassNodo)abierta.get(c)).hpos.yRead()
)
{ findabierta=true;
if(((ClassNodo)abierta.get(c)).gRead()<nodoadyacente.gRead())
{
((ClassNodo)abierta.get(c)).pxWrite(nodoactual.pxRead());
((ClassNodo)abierta.get(c)).pyWrite(nodoactual.pyRead());
for(int n = cerrada.size()-1;n>=0;n--)
{if(nodoactual.pxRead() == ((ClassNodo)cerrada.get(h)).hpos.xRead() && nodoactual.pyRead() == ((ClassNodo)cerrada.get(h)).hpos.yRead())
{
if(((ClassNodo)abierta.get(c)).hpos.xRead() == ((ClassNodo)cerrada.get(h)).hpos.xRead() || ((ClassNodo)abierta.get(c)).hpos.yRead()== ((ClassNodo)cerrada.get(h)).hpos.yRead() )
{g =10;
((ClassNodo)abierta.get(c)).gWrite(g + ((ClassNodo)cerrada.get(h)).gRead());
((ClassNodo)abierta.get(c)).hWrite(nodoadyacente.hRead());
((ClassNodo)abierta.get(c)).fWrite(((ClassNodo)abierta.get(c)).gRead() + ((ClassNodo)abierta.get(c)).hRead());
break;}}
}
break;
}}}}
if(findabierta == false && findcerrada == false && findobstaculo == false){
abierta.add(nodoadyacente);
fill(0,255,223);
rect((posad.xRead()*8)+30,(posad.yRead()*8)+100,8,8);
}
ver = false;
print("f: ");print(nodoadyacente.fRead());print(" h: ");print(nodoadyacente.hRead());print(" g: "); print(nodoadyacente.gRead());print(" posx: "); print(nodoadyacente.hpos.xRead()); print(" posy: "); println(nodoadyacente.hpos.yRead());
print("Apunta Adyacente: ");print(nodoadyacente.pxRead());print(",");println(nodoadyacente.pyRead());
}
}
}
}
}
}// }While
}// }Void Planeacion
int heuristic(ClassNodo inicio, ClassNodo destino){
int manhattan;
manhattan =10*( abs(inicio.hpos.xRead() - destino.hpos.xRead())+ abs(inicio.hpos.yRead() - destino.hpos.yRead()));
return manhattan;}
void rutafin(){
int rutax,rutay;
int finx,finy;
for(int i = cerrada.size()-1; i>=0; i--){
finx = ((ClassNodo)cerrada.get(i)).hpos.xRead();
finy = ((ClassNodo)cerrada.get(i)).hpos.yRead();
grid[finx][finy].display();
}
botinicio.botonpress(4);
construirRuta();
draw();
}
void construirRuta(){
int finx,finy;
finx = nodofin.hpos.xRead();
finy = nodofin.hpos.yRead();
temp = new ClassCoordenada(finx,finy);
finx = nodoactual.pxRead();
print("finx" + finx);
finy = nodoactual.pyRead();
println(" " + "finy" + finy);
while(finx != nodoinicio.pxRead() && finy != nodoinicio.pyRead())
{println("entro while");
for(int i=cerrada.size()-1;i>=0;i--)
{if(finx ==((ClassNodo)cerrada.get(i)).hpos.xRead() && finy == ((ClassNodo)cerrada.get(i)).hpos.yRead())
{grid[finx][finy].ruta(finx,finy);
println("finx" + finx + " cerradax " + ((ClassNodo)cerrada.get(i)).hpos.xRead());
println("finy" + finy + " cerraday " + ((ClassNodo)cerrada.get(i)).hpos.yRead());
temp.xWrite(finx);
temp.yWrite(finy);
ruta.add(temp);
println("Dibujando" + " "+ cerrada.size() + "sizeRuta" + " " + ruta.size() );
finx = ((ClassNodo)cerrada.get(i)).pxRead();
finy = ((ClassNodo)cerrada.get(i)).pyRead();
break;
}
}
}
}

Replies(2)

GoToLoop

Re: !HelP! Have Problems with algorithm A* (A star) in processing

6 months ago

A pity we don't have access to all of those variable declarations! So we can't run your code as it is!

And a nice tip: when declaring your Collection variable types such as an ArrayList, use angle brackets too:

List<ClassNode> nodoAdyacente;

This way, you specify which type of object are stored there.

And you can get rid of all those casts -> (ClassNodo)!

cuqtaa

Re: !HelP! Have Problems with algorithm A* (A star) in processing

6 months ago

please look all codes

https://drive.google.com/folderview?id=0B8BNHGnvViQPZUZrc21DcGVEZWM&usp=sharing

jejejeje i begin with processing, and very little programming basics jejejeje take this into account! : p There you leave the link to the folder with the main codes is AestrellaFULL. (Google Traductor)

Top Reply