1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

/*
 *  AnnotatedMapAbstraction.cpp
 
	Creates a graph abstraction of a map and annotates that graph with clearance values and terrain types.

	Clerance is defined as the amount of space (measured in tiles) around any given location on a map. We take as a measure of clearance the minimum of 
	three rays drawn from any given map tile to the edge of the area in the S, E, and SE directions.
	We add  +1 (the minimum clearance any node on the map is guaranteed to have) to arrive at the final value.      
	 _ _ _ _ _ 
	|x|_|_|_|_|
	|_|_|_|_|_|
	|_|_|_|y|_|
	|_|_|_|_|z|
	
	Eg. the clearance values for the three tiles above are: x=4, y=2, z=1.
	
	Each node has 1 clearance value annotation for each combination of individual terrain types.
	Eg. If the basic terrain types are Ground and Trees then 2^n - 1 combinations of terrain exist and hence 2^n - n annotations are needed.

 *  hog
 *
 *  Created by Daniel Harabor on 5/12/07.
 *  Copyright 2007 __MyCompanyName__. All rights reserved.
 *
 */

#include "AnnotatedMapAbstraction.h"
#include "AnnotatedAStar.h"
#include "AHAConstants.h"
#ifdef OS_MAC
	#include "GLUT/glut.h"
	#include <OpenGL/gl.h>
#else
	#include <GL/glut.h>
	#include <GL/gl.h>
#endif


using namespace std;

AbstractAnnotatedMapAbstraction::AbstractAnnotatedMapAbstraction(Map* m, AbstractAnnotatedAStar* alg) : mapAbstraction(m)
{
	abstractions.push_back(getMapGraph(m));	
	this->searchalg = alg;
	addMissingEdges();
}

AnnotatedMapAbstraction::AnnotatedMapAbstraction(Map* m, AbstractAnnotatedAStar* searchalg) : AbstractAnnotatedMapAbstraction(m, searchalg) 
{
	annotateMap();
	
	drawCV=false; // disable drawing of clearance values
}

/* annotateMap
	Annotates the mapAbstraction with terrain and clearance value annotations 
*/
void AnnotatedMapAbstraction::annotateMap() 
{

	// clearance values is a recursive process; the bottom-right corner of the grid is the recursive base for all other calculations.
	for(int x=getMap()->getMapWidth()-1;x>=0; x--)
	{
		for(int y=getMap()->getMapHeight()-1;y>=0; y--)
		{
			node* n = getNodeFromMap(x,y);
			annotateNode(n);
			n->setLabelL(kParent, -1);
		}
	}
}

void AnnotatedMapAbstraction::annotateNode(node* n)
{
	if(n) // some tiles may not have corresponding nodes (HOG does not create node objects for tiles with type ('@'))
	{	
		int x = n->getLabelL(kFirstData);
		int y = n->getLabelL(kFirstData+1);
		n->setTerrainType(getMap()->getTerrainType(x,y)); //NB: duplicates map data but much easier to access; separate tiles/nodes sucks
		int nterr = n->getTerrainType();
		if(nterr != 0) // only want to consider nodes with valid terrain types
		{	
			node *adj1, *adj2, *adj3; // adjacent neighbours
			adj1 = getNodeFromMap(x+1, y+1);
			adj2 = getNodeFromMap(x+1,y);
			adj3 = getNodeFromMap(x,y+1);
			
			if(adj1 && adj2 && adj3)
			{	
				/* one annotation per capability */
				for(int i=0; i<NUMCAPABILITIES; i++) // NB: hard-coded assumption about # of valid terrains
				{
					/* only want to calculate annotations for capabilities that include the node's terrain type */
					if((capabilities[i]&n->getTerrainType())==n->getTerrainType())
					{
						int min = adj1->getClearance(capabilities[i]);
						min = adj2->getClearance(capabilities[i])<min?adj2->getClearance(capabilities[i]):min;
						min = adj3->getClearance(capabilities[i])<min?adj3->getClearance(capabilities[i]):min;
						n->setClearance(capabilities[i], min+1); // NB: +1 for minimum tile clearance
					}
					else
						n->setClearance(capabilities[i], 0);

				}
			}
			else // tile is on a border or perimeter boundary. clearance = 1
			{
				for(int i=0; i<NUMCAPABILITIES; i++) 
				{
					if((capabilities[i]&n->getTerrainType())==n->getTerrainType())
						n->setClearance(capabilities[i], 1);
					else
						n->setClearance(capabilities[i], 0);
				}

			}
		}
	}
}

/* addMissingEdges
        Overcomes the limitations present in HOG's mapAbstraction class: neighbouring nodes of different terrain types do not have an edge between 
        them; presumably because the intention is that such nodes should not be traversable. The only problem is that this decision shouldn't be made
        by the mapAbstraction class but the agent traversing the map. 
        
        So, this method adds the missing edges between neighboring nodes and leaves it up to the agent to figure out what nodes are traversable vs not 
        according to its unique characteristics/abilities        
*/
void AbstractAnnotatedMapAbstraction::addMissingEdges()
{
	int mheight = this->getMap()->getMapHeight();
	int mwidth = this->getMap()->getMapWidth();
	graph *g = this->getAbstractGraph(0);
	
	for(int x=0; x<mwidth; x++)
		for(int y=0;y<mheight;y++)
		{
			node *n = this->getNodeFromMap(x,y);
			if(n)
			{	
				int nid = n->getNum();
				node *neighbours[4];
				neighbours[0] = getNodeFromMap(x-1,y);
				neighbours[1] = getNodeFromMap(x,y-1);
				neighbours[2] = getNodeFromMap(x-1,y-1);
				neighbours[3] = getNodeFromMap(x+1, y-1);
				
				if(neighbours[0] && !(g->findEdge(nid,neighbours[0]->getNum())))
				{
					edge *e = new edge(nid, neighbours[0]->getNum(), 1.0);
					g->addEdge(e);
				}
				if(neighbours[1] && !(g->findEdge(nid,neighbours[1]->getNum())))
				{
					edge *e = new edge(nid, neighbours[1]->getNum(), 1.0);
					g->addEdge(e);
				}
				if(neighbours[2] && !(g->findEdge(nid,neighbours[2]->getNum())))
				{
					edge *e = new edge(nid, neighbours[2]->getNum(), ROOT_TWO);
					g->addEdge(e);
				}

				if(neighbours[3] && !(g->findEdge(nid,neighbours[3]->getNum())))
				{
					edge *e = new edge(nid, neighbours[3]->getNum(), ROOT_TWO);
					g->addEdge(e);
				}
			}
		}
		
	//cout << "numedges: "<<g->getNumEdges();
}

/*	Determines if a valid solution exists between two locations given some size and terrain constraints 
	NB: Unlike other HOG mapAbstractions, pathable is really difficult to do here; there's no actual abstraction going on; 
	only a 1:1 node/tile representation which we annotate with clearance values for navigation.
	Consequently, the only way to determine pathability is to run the search and see if it's OK -- so, not very useful for quickly
	evaluating sets of locations!
	
	Class is a building-block for AnnotatedClusterAbstraction (which handles the above much better)
*/
bool AnnotatedMapAbstraction::pathable(node* from, node* to, int capability, int agentsize)
{	
	AbstractAnnotatedAStar* aastar = dynamic_cast<AbstractAnnotatedAStar*>(getSearchAlgorithm());
	assert(aastar != 0);
	
	aastar->setClearance(agentsize);
	aastar->setCapability(capability);
	path *p = getSearchAlgorithm()->getPath(this, from, to);
	
	if(p) 
	{
		delete p;
		return true;
	}
	
	return false;	
}

bool AnnotatedMapAbstraction::pathable(node* from, node* to)
{
	return pathable(from, to, (kGround|kTrees), 1); // default values if none specified
}

void AnnotatedMapAbstraction::openGLDraw()
{
	drawClearanceInfo();
	mapAbstraction::openGLDraw();
}

void AnnotatedMapAbstraction::drawClearanceInfo()
{
        char clearance[2];
        node* n;
        recVec rv;
        double r;

        glColor3f (0.51F, 1.0F, 0.0F);
        for(int i=0;i<this->getMap()->getMapWidth(); i++)
                for(int j=0; j<this->getMap()->getMapHeight();j++)
                {
				
                        n = this->getNodeFromMap(i,j,kNone);
						if(n)
						{
							sprintf(clearance, "%x", n->getClearance((kGround|kTrees)));
							this->getMap()->getOpenGLCoord(i,j,rv.x,rv.y,rv.z,r);
							glRasterPos3f((float)rv.x-0.02, (float)rv.y+0.01, rv.z-0.011);
							glutBitmapCharacter (GLUT_BITMAP_HELVETICA_12, clearance[0]);
							glutBitmapCharacter (GLUT_BITMAP_HELVETICA_12, clearance[1]);
						}
                }
}