Звезда с ++, что не так - PullRequest
Новая
       4

Звезда с ++, что не так

0 голосов
/ 06 февраля 2012

Вот, я понятия не имею, почему это не работает. Иногда нормально, иногда вылетает, а иногда возвращает неправильный путь ...

// apath.h 

#ifndef APATH_H
#define APATH_H
#include <vector>
#include <cmath>
#include <memory>
#include <allegro.h>

using namespace std;

double len(int x1, int y1, int x2, int y2);

class GameMap;

class point
{
public:
      int x,y;
      double f,g;
      point *parent;
      point(int _x=0, int _y=0, point *par=NULL) {x=_x; y=_y; parent=par; f=0; g=0;};
      void countF(int sx, int sy, int tx, int ty)
      {
      g=len(x,y,tx,ty);
      f=g+len(sx,sy,x,y);
      };
};

struct point2d
{
      int x,y;
};

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const point2d directions[]=
{
      {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},
};


class path
{
public:
      vector<point2d> way;
      int step;
      bool findPath(int x, int y, int fx, int fy, GameMap& map, BITMAP* out);
private:
      vector<point> open;
      vector<point> closed;
};


#endif

и apath.cpp:

// apath.cpp 

#include "apath.h"
#include <vector>
#include <cmath>



double len(int x1, int y1, int x2, int y2) 
{
       return (sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
       //return max(abs(x1-x2), abs(y1-y2));

      /*int mx=max(x1,x2)-min(x1,x2);
      int my=max(y1,y2)-min(y1,y2);
      return (min(mx,my)*14+max(mx,my)-min(mx,my)*10);*/
};

bool findPoint(vector<point> arr, point pt, point &ret)
{
     for (int i=0; i<arr.size(); i++) if (arr[i].x==pt.x && arr[i].y==pt.y) { ret=arr[i]; return true;}
     return '\0';
};

// GameMap содержит карту ... 

bool path::findPath(int x, int y, int fx, int fy, GameMap& map, BITMAP* out)
{
     while(!open.empty()) open.pop_back();
     while(!closed.empty()) closed.pop_back();
     while(!way.empty()) way.pop_back();

     point start(x,y);
     start.countF(x,y,fx,fy);
     open.push_back(start);

     point finish(fx,fy);

     double min=999999999;
     int index;
     point tmp;
     point *tmp2;
     point comparer;


     while (!findPoint(closed,finish,comparer))
     {
           min=999999999;
           for (int i=0; i<open.size(); i++)
           {
               if(open[i].f<min)
                   {
                       min=open[i].f;
                       index=i;
                   }
           }

           tmp=open[index];
           closed.push_back(open[index]);
           open.erase(open.begin()+index);

           for (int i=0; i<8; i++)
               {
                    tmp2=new point(tmp.x+directions[i].x,tmp.y+directions[i].y);
                    if (map.getCollisionXY(tmp2->x,tmp2->y)==1 // map.getCollision returns 1 when you cant pass through the tile and 0 otherwise...
                    || findPoint(closed,*tmp2,comparer)) continue;
                    if (!findPoint(open,*tmp2,comparer)) 
                    { 
                        point newP(tmp.x+directions[i].x,tmp.y+directions[i].y,&closed[closed.size()-1]);
                        newP.countF(x,y,fx,fy);
                        open.push_back(newP);
                    }
                    else
                    {
                        if (comparer.g>tmp.g)
                        {
                             comparer.parent=&closed[closed.size()-1];
                             comparer.countF(x,y,fx,fy);
                        }
                    }
                    delete tmp2;
               }
/*     for (int i=0; i<open.size(); i++)
        if (open[i].parent!=0)circlefill(out,open[i].x*16+4,open[i].y*16+4,3,0xff0000);
           if (open.empty()) return false;
     for (int i=0; i<closed.size(); i++)
        if (closed[i].parent!=0)circlefill(out,closed[i].x*16+12,closed[i].y*16+12,3,0xffff00);*/ //debug draw

     }
     point2d pt;
     pt.x=finish.x;
     pt.y=finish.y;
     way.push_back(pt);
     point wayer;
     wayer=closed[closed.size()-1];
     while(wayer.parent!=0) //CRASH from here
     {
         wayer=*wayer.parent;
         pt.x=wayer.x;
         pt.y=wayer.y;
         way.push_back(pt);
//         circlefill(out,pt.x*16+12,pt.y*16+12,3,0xffffff); //debug draw
     }    //CRASH to here, i dont exacly know where it is, but when trying to recreate path.
     return true;
};

Некоторые объяснения: GameMap это класс с картой и его getCollisionXY возвращает 1, которое вы не можете пройти через плитку, и 0 в противном случае.

Спасибо за любую помощь.

1 Ответ

1 голос
/ 06 февраля 2012

Один основной источник, который я вижу, который может вызвать нарушение доступа, состоит в том, что ваши точки содержат родителей в качестве указателей, и они являются членами вектора.Если вектор перераспределен, эти указатели могут стать недействительными.

Кроме того, трудно сразу увидеть причину сбоя.

Вы действительно должны запустить свой код через отладчик.Я только что указал на одну вещь, которую сразу вижу.

...