Commits

Mihael Peklar committed cc72f9c

Pathfinding code moved to new class.

Comments (0)

Files changed (6)

 CFLAGS=$(MY_CFLAGS)
 CXXFLAGS=$(MY_CXXFLAGS)
 LDFLAGS=-lSDL -lSDL_mixer -lSDL_image -lSDL_ttf -lGL -lGLU $(MY_LDFLAGS)
-OBJECTS=audiomgr.o    gamemode.o    gm_battle.o   texture.o  map.o tile.o tileset.o thecombat.o unit.o font.o button.o tiledesc.o order.o unitcontainer.o  texture_manager.o
+OBJECTS=audiomgr.o    gamemode.o    gm_battle.o   texture.o  map.o tile.o tileset.o thecombat.o unit.o font.o button.o tiledesc.o order.o unitcontainer.o  texture_manager.o pathfinder.o
 
 all: thecombat
 
 #include "tile.h"
 #include "unit.h"
 #include "font.h"
+#include"pathfinder.h"
 #include<utility>
 #include<queue>
 #include"order.h"
     fclose(f);
     blocked.resize(tiles.size(), 0);
     units=new UnitContainer(this);
+    pathfinder=new Pathfinder(this);
 }
 
 Map::~Map()
 	return this->units;
 }
 
+Pathfinder* Map::getPathfinder()
+{
+	return this->pathfinder;
+}
+
 void Map::paintSelf()
 {
     for(unsigned i = 0; i < this->tiles.size(); i++)
     }
 }
 
+double Map::tileSpeed(int x)
+{
+	if(x<0 || x>=this->getTileCount())
+		return -1.0;
+	return this->tileset->getSpeed(this->tiles[x]->getType());
+}
+
 bool Map::boundCheck(float x, float y)
 {
 	x+=TILE_WIDTH/2; y-=TILE_HEIGHT/2;
 
 /////////////////////////////////////////////////////////////
 //Pathfinding
-class Map::_pnode //used in pathfinding (Priority queue NODE)
-{
-	public:
-	double v;
-	int x, p;
-	_pnode() {}
-	_pnode(double V, int A, int B) : v(V), x(A), p(B) {}
-	friend bool operator < (const _pnode& a, const _pnode& b)
-	{
-		return a.v>b.v;
-	}
-};
-
-bool Map::siri(int x, int y)
-{
-	if(x<0 || x>=this->tilesPerRow || y<0 || y>=this->tilesPerColumn)
-		return false;
-	if(this->blocked[x+y*tilesPerRow])
-		return false;
-	return true;
-}
+//Transferred to pathfinder.cpp
+inline std::vector<int> Map::find_path(int st, int et) {return this->pathfinder->find_path(st, et);}
+std::deque<Order> Map::path_order(float px, float py, float ex, float ey) {return this->pathfinder->path_order(px, py, ex, ey);}
 
 using namespace std;
-
-#define pnode _pnode
-
-const double INFINITY=numeric_limits<double>::infinity();
-
-double Map::distance(int a, int b) //samo za ortogonalno susjedne tileove
-{
-	if(a>=tiles.size() && b>=tiles.size())
-		throw 5;
-	double d1=this->tileset->getSpeed(this->tiles[a]->getType());
-	double d2=this->tileset->getSpeed(this->tiles[b]->getType());
-	if(d1==-1.0 || d2==-1.0)
-		return INFINITY;
-	return (1/d1+1/d2)/2;
-		
-}
-
-std::vector<int> Map::find_path(int s, int e)
-{
-	std::vector<int> res;
-	std::vector< pair<int, int> > mem;
-	std::vector<bool> visited; visited.resize(tiles.size(), 0);
-	std::priority_queue< pnode > dot;
-	if(s<0 || e<0 || s>=this->tiles.size() || e>=this->tiles.size())
-		return res;
-//    res.push_back(s);
-	dot.push(pnode(0.0, s, -1));
-	int c=-1, p;
-	double d;
-	bool b=1;
-	blocked[s]=0;
-	while(!dot.empty())
-	{
-		if(dot.empty() || c>(int)tiles.size())
-			throw "ARGH!";
-		c=dot.top().x; d=dot.top().v; p=dot.top().p; dot.pop();
-		if(blocked[c] || visited[c])
-			continue;
-		visited[c]=true;
-		if(d==INFINITY)
-			continue;
-		int y=c/tilesPerRow;
-		int x=c-y*tilesPerRow;
-		mem.push_back(make_pair(c, p));
-		printf("DBQ: %d %d\n", x, y);
-		if(c==e)
-		{
-			b=0;
-			break;
-		}
-		if(siri(x-1, y))
-			dot.push(pnode(d+distance(c, c-1), c-1, mem.size()-1));
-		if(siri(x+1, y))
-			dot.push(pnode(d+distance(c, c+1), c+1, mem.size()-1));
-		if(siri(x, y-1))
-			dot.push(pnode(d+distance(c, c-tilesPerRow), c-tilesPerRow, mem.size()-1));
-		if(siri(x, y+1))
-			dot.push(pnode(d+distance(c, c+tilesPerRow), c+tilesPerRow, mem.size()-1));
-		//printf("STEP\n");
-	}
-	//blocked[s]=1;
-	//res.clear();
-	if(b)
-	{
-	    res.clear();
-		return res;
-    }
-	//Commented out for testing purposes
-	blocked[s]=0;
-	//blocked[e]=1;
-	for(int i=mem.size()-1; mem[i].second>=0; i=mem[i].second)
-		res.push_back(mem[i].first);
-	res.push_back(s);
-	return res;
-}
-
 vector<int> drawThis;
 
-std::deque<Order> Map::path_order(float px, float py, float ex, float ey)
-{
-	boundFix(ex, ey);
-	int s=this->findTile(px, py), e=this->findTile(ex, ey);
-	std::deque<Order> out;
-	std::vector<int> x=this->find_path(s, e);
-	std::reverse(x.begin(), x.end());
-	printf("DBS: %d\n", x.size());
-	drawThis=x;
-	float nx, ny;
-	Order o;
-	o.order=ORDER_MOVE;
-	o.details.move.srcx=px;
-	o.details.move.srcy=py;
-	if(s==e)
-		out.push_back(o);
-	for(std::vector<int>::iterator i=++x.begin(); i<x.end(); ++i)
-	{
-		nx=*i%this->tilesPerRow*TILE_WIDTH, ny=-*i/this->tilesPerRow*TILE_HEIGHT;
-		o.order=ORDER_MOVE;
-		//o.details.move=(struct OrderDetailsMove){ .srcx=px, .srcy=py, .dstx=nx, .dsty=ny, .progress=0.0}; //problem?
-		o.details.move.srcx=px;
-		o.details.move.srcy=py;
-		o.details.move.dstx=nx;
-		o.details.move.dsty=ny;
-		o.details.move.progress=0.0;
-		printf("DBO: %.2f %.2f %.2f %.2f\n", px, py, nx, ny);
-		out.push_back(o);
-		px=nx; py=ny;
-	}
-	if(!out.empty())
-	{
-		out.back().details.move.dstx=ex;
-		out.back().details.move.dsty=ey;
-	}
-//	o.details.move={nx, ny, ex, ey, 0.0}; //problem?
-	return out;
-}
-
 #include<GL/gl.h>
 extern Font* test;
 char temp[30];
 class Order;
 class Tile;
 class UnitContainer;
+class Pathfinder;
 
 class Map
 {
     Map(const std::string &filename);
     ~Map();
     void paintSelf();
-    double tileSpeed(int x, int y);
+    double tileSpeed(int);
+    double distance(int, int);
     int getTilesPerRow() {return this->tilesPerRow;}
     int getTilesPerColumn() {return this->tilesPerColumn;}
+    int getTileCount() {return this->tiles.size();}
     bool boundCheck(float x, float y);
     void boundFix(float& x, float& y, float offX=TILE_WIDTH/2, float offY=TILE_HEIGHT/2);
     std::vector<int> find_path(int st, int et);
     void drawPath(std::vector<int> path);
     void drawPath();
     UnitContainer* getUnits();
+    Pathfinder* getPathfinder();
 
     private:
+    Pathfinder* pathfinder;
     UnitContainer* units;
     Tileset* tileset;
-    double distance(int, int);
     bool siri(int x, int y);
     class _pnode;
     std::vector<Tile*> tiles;
+#include"pathfinder.h"
+#include"order.h"
+#include"map.h"
+#include<algorithm>
+#include<utility>
+#include<limits>
+#include<map>
+
+
+using namespace std;
+
+Pathfinder::Pathfinder(Map* map) : map(map), blocked(map->getTileCount()) {}
+
+/*inline double Pathfinder::asqrdistance(double x1, double y1, double x2, double y2)
+{
+	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
+}
+
+inline double Pathfinder::adistance(double x1, double y1, double x2, double y2)
+{
+	return sqrt(sqrdistance(x1, y1, x2, y2));
+}
+
+inline double Pathfinder::asqrdistanceFromTile(int t, double x2, double y2)
+{
+	double x1=
+	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
+}
+
+inline double Pathfinder::adistance(int t, double x2, double y2)
+{
+	return sqrt(sqrdistance(x1, y1, x2, y2));
+}
+*/
+
+class Pathfinder::_pnode //used in pathfinding (Priority queue NODE)
+{
+	public:
+	double v;
+	int x, p;
+	_pnode() {}
+	_pnode(double V, int A, int B) : v(V), x(A), p(B) {}
+	friend bool operator < (const _pnode& a, const _pnode& b)
+	{
+		return a.v>b.v;
+	}
+};
+
+const double INFINITY=numeric_limits<double>::infinity();
+#define pnode _pnode
+
+
+double Pathfinder::distance(int a, int b) //samo za ortogonalno susjedne tileove
+{
+	if(a>=map->getTileCount() && b>=map->getTileCount())
+		throw 5;
+	double d1=map->tileSpeed(a);
+	double d2=map->tileSpeed(b);
+	if(d1==-1.0 || d2==-1.0)
+		return INFINITY;
+	return (1/d1+1/d2)/2;
+		
+}
+
+bool Pathfinder::siri(int x, int y)
+{
+	if(x<0 || x>=this->map->getTilesPerRow() || y<0 || y>=this->map->getTilesPerColumn())
+		return false;
+	if(this->blocked[x+y*this->map->getTilesPerRow()])
+		return false;
+	return true;
+}
+
+std::vector<int> Pathfinder::find_path(int s, int e)
+{
+	const int numTiles=map->getTileCount();
+	std::vector<int> res;
+	std::vector< pair<int, int> > mem;
+	std::vector<bool> visited(numTiles, 0);
+	std::priority_queue< pnode > dot;
+	if(s<0 || e<0 || s>=numTiles || e>=numTiles)
+		return res;
+//    res.push_back(s);
+	dot.push(pnode(0.0, s, -1));
+	int c=-1, p;
+	double d;
+	bool b=1;
+	blocked[s]=0;
+	while(!dot.empty())
+	{
+		if(dot.empty() || c>numTiles)
+			throw "ARGH!";
+		c=dot.top().x; d=dot.top().v; p=dot.top().p; dot.pop();
+		if(blocked[c] || visited[c])
+			continue;
+		visited[c]=true;
+		if(d==INFINITY)
+			continue;
+		int y=c/this->map->getTilesPerRow();
+		int x=c-y*this->map->getTilesPerRow();
+		mem.push_back(make_pair(c, p));
+		//printf("DBQ: %d %d\n", x, y);
+		if(c==e)
+		{
+			b=0;
+			break;
+		}
+		if(siri(x-1, y))
+			dot.push(pnode(d+this->distance(c, c-1), c-1, mem.size()-1));
+		if(siri(x+1, y))
+			dot.push(pnode(d+this->distance(c, c+1), c+1, mem.size()-1));
+		if(siri(x, y-1))
+			dot.push(pnode(d+this->distance(c, c-map->getTilesPerRow()), c-map->getTilesPerRow(), mem.size()-1));
+		if(siri(x, y+1))
+			dot.push(pnode(d+this->distance(c, c+map->getTilesPerRow()), c+map->getTilesPerRow(), mem.size()-1));
+		//printf("STEP\n");
+	}
+	//blocked[s]=1;
+	//res.clear();
+	if(b)
+	{
+	    res.clear();
+		return res;
+    }
+	//Commented out for testing purposes
+	//blocked[s]=0;
+	//blocked[e]=1;
+	for(int i=mem.size()-1; mem[i].second>=0; i=mem[i].second)
+		res.push_back(mem[i].first);
+	res.push_back(s);
+	return res;
+}
+
+extern vector<int> drawThis;
+
+std::deque<Order> Pathfinder::path_order(float px, float py, float ex, float ey)
+{
+	map->boundFix(ex, ey);
+	int s=this->map->findTile(px, py), e=this->map->findTile(ex, ey);
+	std::deque<Order> out;
+	std::vector<int> x=this->find_path(s, e);
+	std::reverse(x.begin(), x.end());
+	//printf("DBS: %d\n", x.size());
+	drawThis=x;
+	float nx, ny;
+	Order o;
+	o.order=ORDER_MOVE;
+	o.details.move.srcx=px;
+	o.details.move.srcy=py;
+	if(s==e)
+		out.push_back(o);
+	for(std::vector<int>::iterator i=++x.begin(); i<x.end(); ++i)
+	{
+		nx=*i%this->map->getTilesPerRow()*TILE_WIDTH, ny=-*i/this->map->getTilesPerRow()*TILE_HEIGHT;
+		o.order=ORDER_MOVE;
+		//o.details.move=(struct OrderDetailsMove){ .srcx=px, .srcy=py, .dstx=nx, .dsty=ny, .progress=0.0}; //problem?
+		o.details.move.srcx=px;
+		o.details.move.srcy=py;
+		o.details.move.dstx=nx;
+		o.details.move.dsty=ny;
+		o.details.move.progress=0.0;
+		//printf("DBO: %.2f %.2f %.2f %.2f\n", px, py, nx, ny);
+		out.push_back(o);
+		px=nx; py=ny;
+	}
+	if(!out.empty())
+	{
+		out.back().details.move.dstx=ex;
+		out.back().details.move.dsty=ey;
+	}
+	for (std::deque<Order>::iterator i=out.begin(); i!=out.end(); ++i)
+		//printf("DBO: %d\n", i->order);
+//	o.details.move={nx, ny, ex, ey, 0.0}; //problem?
+	return out;
+}
+
+
+#ifndef PATHFINDER_H_INCLUDED
+#define PATHFINDER_H_INCLUDED
+
+#include<vector>
+#include<queue>
+
+class Map;
+class Order;
+
+class Pathfinder
+{
+	public:
+	Pathfinder(Map* map);
+    std::vector<int> find_path(int st, int et);
+    std::deque<Order> path_order(float px, float py, float ex, float ey);
+
+	private:
+    bool siri(int x, int y);
+    double distance(int, int);
+    class _pnode;
+    std::vector<bool> blocked;
+    Map* map;
+
+};
+
+#endif
Binary file added.