1

/* $Id$ */

     2

     3

#include "../yapf_base.hpp"

     4

     5

struct CYapfMap1

     6

{

     7

	enum {xMax = 32, yMax = 68};

     8

	static int MapZ(int x, int y)

     9

	{

    10

		static const char *z1[yMax] = {

    11

			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",

    12

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    13

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    14

			"A000000000001000000000000000000000000000000000000000000000000000000A",

    15

			"A000000000001000000000000000000000000000000000000000000000000000000A",

    16

			"A000033333333333000000000000000000000000000000000000000000000000000A",

    17

			"A000030000000000000000000000000000000000000000000000000000000000000A",

    18

			"A000030000000000000000000000000000000000000000000000000000000000000A",

    19

			"A000030000000000000000000000000000000000000000000000000000000000000A",

    20

			"A000030000000000000000000000000000000000000000000000000000000000000A",

    21

			"A000030000000000000000000000000000000000000000000000000000000000000A",

    22

			"A210030000000000000000000000000000000000000000000000000000000000000A",

    23

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    24

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    25

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    26

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    27

			"A011333323333333233333333333333333333333333333333333333333333000000A",

    28

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    29

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    30

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    31

			"A210030000000000000000000000000000000000000000000000000000003000000A",

    32

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    33

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    34

			"A000230000000000000000000000000000000000000000000000000000003000000A",

    35

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    36

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    37

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    38

			"A000000000000000000000000000003333333333333333333333333333333000000A",

    39

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    40

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    41

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    42

			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",

    43

		};

    44

    45

		static const char *z2[yMax] = {

    46

			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",

    47

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    48

			"A003333333333333333333333333333333333333333333333333300000000000000A",

    49

			"A003000000001000000000000000000000000000000000000000300000000000000A",

    50

			"A003000000001000000000000000000000000000000000000000300000000000000A",

    51

			"A003333333333333333333333333333333333333300000000000300000000000000A",

    52

			"A000030000000000000000000000000000000000300000000000300000000000000A",

    53

			"A000030000000000000000000000000000000000333333333333300000000000000A",

    54

			"A000030000000000000000000000000000000000300000000000000000000000000A",

    55

			"A000030000000000000000000000000000000000300000000000000000000000000A",

    56

			"A000030000000000000000000000000000000000300000000000000000000000000A",

    57

			"A210030000000000000000000000000000000000300000000000000000000000000A",

    58

			"A000000000000000000000000000000000000000333300000000000000000000000A",

    59

			"A000000000000000000000000000000000000000000300000000000000000000000A",

    60

			"A000000000000000000000000000000000000000000300000000000000000000000A",

    61

			"A000000000000000000000000000000000000000000300000000000000000000000A",

    62

			"A012333323333333233333333333333333333333333333333333333333333000000A",

    63

			"A000030000000000000000000000000000000000000000000000000000003000000A",

    64

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    65

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    66

			"A210030000000000000000000000000000000000000000000000000330003000000A",

    67

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    68

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    69

			"A000230000000000000000000000000000000000000000000000000300003000000A",

    70

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    71

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    72

			"A000030000000000000000000000000000000000000000000000000300003000000A",

    73

			"A000000000000000000000000000003333333333333333333333333333333000000A",

    74

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    75

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    76

			"A000000000000000000000000000000000000000000000000000000000000000000A",

    77

			"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",

    78

		};

    79

    80

		static const char **z = z1;

    81

    82

		if (x >= 0 && x < xMax && y >= 0 && y < yMax) {

    83

			int ret = z[x][y];

    84

			return ret;

    85

		}

    86

		return z[0][0];

    87

	}

    88

};

    89

    90

struct CNodeKey1 {

    91

	int            m_x;

    92

	int            m_y;

    93

	Trackdir       m_td;

    94

	DiagDirection  m_exitdir;

    95

    96

	CNodeKey1() : m_x(0), m_y(0), m_td(INVALID_TRACKDIR) {}

    97

    98

	int CalcHash() const {return m_x | (m_y << 5) | (m_td << 10);}

    99

	bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_td == other.m_td);}

   100

};

   101

   102

struct CNodeKey2 : public CNodeKey1

   103

{

   104

	int CalcHash() const {return m_x | (m_y << 5) | (m_exitdir << 10);}

   105

	bool operator == (const CNodeKey1& other) const {return (m_x == other.m_x) && (m_y == other.m_y) && (m_exitdir == other.m_exitdir);}

   106

};

   107

   108

template <class Tkey_>

   109

struct CTestYapfNodeT {

   110

	typedef Tkey_ Key;

   111

	typedef CTestYapfNodeT<Tkey_> Node;

   112

   113

	Tkey_           m_key;

   114

	CTestYapfNodeT *m_parent;

   115

	int             m_cost;

   116

	int             m_estimate;

   117

	CTestYapfNodeT *m_next;

   118

   119

	CTestYapfNodeT(CTestYapfNodeT* parent = NULL) : m_parent(parent), m_cost(0), m_estimate(0), m_next(NULL) {}

   120

   121

	const Tkey_& GetKey() const {return m_key;}

   122

	int GetCost() {return m_cost;}

   123

	int GetCostEstimate() {return m_estimate;}

   124

	bool operator < (const CTestYapfNodeT& other) const {return m_estimate < other.m_estimate;}

   125

	CTestYapfNodeT* GetHashNext() {return m_next;}

   126

	void SetHashNext(CTestYapfNodeT* next) {m_next = next;}

   127

};

   128

   129

typedef CTestYapfNodeT<CNodeKey1> CYapfNode1;

   130

typedef CTestYapfNodeT<CNodeKey2> CYapfNode2;

   131

   132

template <class Types>

   133

struct CYapfTestBaseT

   134

{

   135

	typedef typename Types::Tpf Tpf;

   136

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

   137

	typedef typename Node::Key Key;    ///< key to hash tables

   138

	typedef typename Types::Map Map;

   139

   140

	int m_x1, m_y1;

   141

	int m_x2, m_y2;

   142

	Trackdir m_td1;

   143

   144

	CYapfTestBaseT()

   145

		: m_x1(0), m_y1(0), m_x2(0), m_y2(0), m_td1(INVALID_TRACKDIR)

   146

	{

   147

	}

   148

   149

	void Set(int x1, int y1, int x2, int y2, Trackdir td1)

   150

	{

   151

		m_x1 = x1;

   152

		m_y1 = y1;

   153

		m_x2 = x2;

   154

		m_y2 = y2;

   155

		m_td1 = td1;

   156

	}

   157

   158

	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

   159

	FORCEINLINE char TransportTypeChar() const {return 'T';}

   160

   161

	FORCEINLINE void PfFollowNode(Node& org)

   162

	{

   163

		int x_org = org.m_key.m_x;

   164

		int y_org = org.m_key.m_y;

   165

		int z_org = Map::MapZ(x_org, y_org);

   166

		DiagDirection exitdir = TrackdirToExitdir(org.m_key.m_td);

   167

   168

		TileIndexDiffC diff = TileIndexDiffCByDir(exitdir);

   169

		int x_new = x_org + diff.x;

   170

		int y_new = y_org + diff.y;

   171

		int z_new = Map::MapZ(x_new, y_new);

   172

   173

		int z_diff = z_new - z_org;

   174

		if (abs(z_diff) > 1) return;

   175

   176

		TrackdirBits trackdirs = DiagdirReachesTrackdirs(exitdir);

   177

		TrackdirBits trackdirs90 = TrackdirCrossesTrackdirs(org.m_key.m_td);

   178

		trackdirs &= (TrackdirBits)~(int)trackdirs90;

   179

   180

		while (trackdirs != TRACKDIR_BIT_NONE) {

   181

			Trackdir td_new = (Trackdir)FindFirstBit2x64(trackdirs);

   182

			trackdirs = (TrackdirBits)KillFirstBit2x64(trackdirs);

   183

   184

			Node& n = Yapf().CreateNewNode();

   185

			n.m_key.m_x  =  x_new;

   186

			n.m_key.m_y  =  y_new;

   187

			n.m_key.m_td = td_new;

   188

			n.m_key.m_exitdir = TrackdirToExitdir(n.m_key.m_td);

   189

			n.m_parent   = &org;

   190

			Yapf().AddNewNode(n);

   191

		}

   192

	}

   193

   194

	FORCEINLINE void PfSetStartupNodes()

   195

	{

   196

		Node& n1 = Yapf().CreateNewNode();

   197

		n1.m_key.m_x = m_x1;

   198

		n1.m_key.m_y = m_y1;

   199

		n1.m_key.m_td = m_td1;

   200

		n1.m_key.m_exitdir = TrackdirToExitdir(n1.m_key.m_td);

   201

		Yapf().AddStartupNode(n1);

   202

	}

   203

   204

	FORCEINLINE bool PfCalcCost(Node& n)

   205

	{

   206

		// base tile cost depending on distance

   207

		int c = IsDiagonalTrackdir(n.m_key.m_td) ? 10 : 7;

   208

		// additional penalty for curve

   209

		if (n.m_parent != NULL && n.m_key.m_td != n.m_parent->m_key.m_td) c += 3;

   210

		// z-difference cost

   211

		int z_new = Map::MapZ(n.m_key.m_x, n.m_key.m_y);

   212

		int z_old = Map::MapZ(n.m_parent->m_key.m_x, n.m_parent->m_key.m_y);

   213

		if (z_new > z_old) n.m_cost += (z_new - z_old) * 10;

   214

		// apply it

   215

		n.m_cost = n.m_parent->m_cost + c;

   216

		return true;

   217

	}

   218

   219

	FORCEINLINE bool PfCalcEstimate(Node& n)

   220

	{

   221

		int dx = abs(n.m_key.m_x - m_x2);

   222

		int dy = abs(n.m_key.m_y - m_y2);

   223

		int dd = min(dx, dy);

   224

		int dxy = abs(dx - dy);

   225

		int d = 14 * dd + 10 * dxy;

   226

		n.m_estimate = n.m_cost + d /*+ d / 4*/;

   227

		return true;

   228

	}

   229

   230

	FORCEINLINE bool PfDetectDestination(Node& n)

   231

	{

   232

		bool bDest = (n.m_key.m_x == m_x2) && (n.m_key.m_y == m_y2);

   233

		return bDest;

   234

	}

   235

   236

	static int stTestAstar(bool silent)

   237

	{

   238

		Tpf pf;

   239

		pf.Set(3, 3, 20, 56, TRACKDIR_X_NE);

   240

		int ret = pf.TestAstar(silent);

   241

		return ret;

   242

	}

   243

   244

	int TestAstar(bool silent)

   245

	{

   246

		CPerformanceTimer pc;

   247

   248

		pc.Start();

   249

		bool bRet = Yapf().FindPath(NULL);

   250

		pc.Stop();

   251

   252

		if (!bRet) return 1;

   253

   254

		typedef CFixedSizeArrayT<int, 1024> Row;

   255

		typedef CFixedSizeArrayT<Row, 1024> Box;

   256

   257

		Box box;

   258

		{

   259

			for (int x = 0; x < Map::xMax; x++) {

   260

				Row& row = box.Add();

   261

				for (int y = 0; y < Map::yMax; y++) {

   262

					row.Add() = Map::MapZ(x, y);

   263

				}

   264

			}

   265

		}

   266

		int nPathTiles = 0;

   267

		{

   268

			for (Node* pNode = &Yapf().GetBestNode(); pNode != NULL; pNode = pNode->m_parent) {

   269

				box[pNode->m_key.m_x][pNode->m_key.m_y] = '.';

   270

				nPathTiles++;

   271

			}

   272

		}

   273

		{

   274

			printf("\n\n");

   275

			for (int x = 0; x < Map::xMax; x++) {

   276

				for (int y = 0; y < Map::yMax; y++) {

   277

					printf("%c", box[x][y]);

   278

				}

   279

				printf("\n");

   280

			}

   281

		}

   282

   283

		{

   284

			printf("\n");

   285

			printf("Path Tiles:    %6d\n", nPathTiles);

   286

//			printf("Closed nodes:  %6d\n", pf.m_nodes.ClosedCount());

   287

//			printf("Open nodes:    %6d\n", pf.m_nodes.OpenCount());

   288

//			printf("A-star rounds: %6d\n", pf.m_num_steps);

   289

		}

   290

		int total_time = pc.Get(1000000);

   291

		if (total_time != 0)

   292

			printf("Total time:    %6d us\n", pc.Get(1000000));

   293

   294

		printf("\n");

   295

   296

		{

   297

			int nCnt = Yapf().m_nodes.TotalCount();

   298

			for (int i = 0; i < nCnt; i++) {

   299

				Node& n = Yapf().m_nodes.ItemAt(i);

   300

				int& z = box[n.m_key.m_x][n.m_key.m_y];

   301

				z = (z < 'a') ? 'a' : (z + 1);

   302

			}

   303

		}

   304

		{

   305

			for (int x = 0; x < Map::xMax; x++) {

   306

				for (int y = 0; y < Map::yMax; y++) {

   307

					printf("%c", box[x][y]);

   308

				}

   309

				printf("\n");

   310

			}

   311

		}

   312

   313

		return 0;

   314

	}

   315

};

   316

   317

struct CDummy1 {};

   318

struct CDummy2 {};

   319

struct CDummy3 {};

   320

   321

template <class Tpf_, class Tnode_list, class Tmap>

   322

struct CYapf_TypesT

   323

{

   324

	typedef CYapf_TypesT<Tpf_, Tnode_list, Tmap> Types;

   325

   326

	typedef Tpf_                              Tpf;

   327

	typedef Tnode_list                        NodeList;

   328

	typedef Tmap                              Map;

   329

	typedef CYapfBaseT<Types>                 PfBase;

   330

	typedef CYapfTestBaseT<Types>             PfFollow;

   331

	typedef CDummy1                           PfOrigin;

   332

	typedef CDummy2                           PfDestination;

   333

	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;

   334

	typedef CDummy3                           PfCost;

   335

};

   336

   337

typedef CNodeList_HashTableT<CYapfNode1, 12, 16> CNodeList1;

   338

typedef CNodeList_HashTableT<CYapfNode2, 12, 16> CNodeList2;

   339

   340

struct CTestYapf1

   341

	: public CYapfT<CYapf_TypesT<CTestYapf1, CNodeList1, CYapfMap1> >

   342

{

   343

};

   344

   345

struct CTestYapf2

   346

	: public CYapfT<CYapf_TypesT<CTestYapf2, CNodeList2, CYapfMap1> >

   347

{

   348

};

   349

   350