summaryrefslogtreecommitdiff
path: root/src/gui/guiEngine.cpp
blob: b40707d0165a3bf8d5fcb109d760f2ad5a4733da (plain)
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
/*
Minetest
Copyright (C) 2013 sapier

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "guiEngine.h"

#include <IGUIStaticText.h>
#include <ICameraSceneNode.h>
#include "client/renderingengine.h"
#include "scripting_mainmenu.h"
#include "util/numeric.h"
#include "config.h"
#include "version.h"
#include "porting.h"
#include "filesys.h"
#include "settings.h"
#include "guiMainMenu.h"
#include "sound.h"
#include "client/sound_openal.h"
#include "client/clouds.h"
#include "httpfetch.h"
#include "log.h"
#include "client/fontengine.h"
#include "client/guiscalingfilter.h"
#include "irrlicht_changes/static_text.h"

#if ENABLE_GLES
#include "client/tile.h"
#endif


/******************************************************************************/
void TextDestGuiEngine::gotText(const StringMap &fields)
{
	m_engine->getScriptIface()->handleMainMenuButtons(fields);
}

/******************************************************************************/
void TextDestGuiEngine::gotText(const std::wstring &text)
{
	m_engine->getScriptIface()->handleMainMenuEvent(wide_to_utf8(text));
}

/******************************************************************************/
MenuTextureSource::~MenuTextureSource()
{
	for (const std::string &texture_to_delete : m_to_delete) {
		const char *tname = texture_to_delete.c_str();
		video::ITexture *texture = m_driver->getTexture(tname);
		m_driver->removeTexture(texture);
	}
}

/******************************************************************************/
video::ITexture *MenuTextureSource::getTexture(const std::string &name, u32 *id)
{
	if (id)
		*id = 0;

	if (name.empty())
		return NULL;

	m_to_delete.insert(name);

#if ENABLE_GLES
	video::ITexture *retval = m_driver->findTexture(name.c_str());
	if (retval)
		return retval;

	video::IImage *image = m_driver->createImageFromFile(name.c_str());
	if (!image)
		return NULL;

	image = Align2Npot2(image, m_driver);
	retval = m_driver->addTexture(name.c_str(), image);
	image->drop();
	return retval;
#else
	return m_driver->getTexture(name.c_str());
#endif
}

/******************************************************************************/
/** MenuMusicFetcher                                                          */
/******************************************************************************/
void MenuMusicFetcher::fetchSounds(const std::string &name,
			std::set<std::string> &dst_paths,
			std::set<std::string> &dst_datas)
{
	if(m_fetched.count(name))
		return;
	m_fetched.insert(name);
	std::string base;
	base = porting::path_share + DIR_DELIM + "sounds";
	dst_paths.insert(base + DIR_DELIM + name + ".ogg");
	int i;
	for(i=0; i<10; i++)
		dst_paths.insert(base + DIR_DELIM + name + "."+itos(i)+".ogg");
	base = porting::path_user + DIR_DELIM + "sounds";
	dst_paths.insert(base + DIR_DELIM + name + ".ogg");
	for(i=0; i<10; i++)
		dst_paths.insert(base + DIR_DELIM + name + "."+itos(i)+".ogg");
}

/******************************************************************************/
/** GUIEngine                                                                 */
/******************************************************************************/
GUIEngine::GUIEngine(JoystickController *joystick,
		gui::IGUIElement *parent,
		IMenuManager *menumgr,
		MainMenuData *data,
		bool &kill) :
	m_parent(parent),
	m_menumanager(menumgr),
	m_smgr(RenderingEngine::get_scene_manager()),
	m_data(data),
	m_kill(kill)
{
	//initialize texture pointers
	for (image_definition &texture : m_textures) {
		texture.texture = NULL;
	}
	// is deleted by guiformspec!
	m_buttonhandler = new TextDestGuiEngine(this);

	//create texture source
	m_texture_source = new MenuTextureSource(RenderingEngine::get_video_driver());

	//create soundmanager
	MenuMusicFetcher soundfetcher;
#if USE_SOUND
	if (g_settings->getBool("enable_sound") && g_sound_manager_singleton.get())
		m_sound_manager = createOpenALSoundManager(g_sound_manager_singleton.get(), &soundfetcher);
#endif
	if (!m_sound_manager)
		m_sound_manager = &dummySoundManager;

	//create topleft header
	m_toplefttext = L"";

	core::rect<s32> rect(0, 0, g_fontengine->getTextWidth(m_toplefttext.c_str()),
		g_fontengine->getTextHeight());
	rect += v2s32(4, 0);

	m_irr_toplefttext = gui::StaticText::add(RenderingEngine::get_gui_env(),
			m_toplefttext, rect, false, true, 0, -1);

	//create formspecsource
	m_formspecgui = new FormspecFormSource("");

	/* Create menu */
	m_menu = new GUIFormSpecMenu(joystick,
			m_parent,
			-1,
			m_menumanager,
			NULL /* &client */,
			m_texture_source,
			m_formspecgui,
			m_buttonhandler,
			"",
			false);

	m_menu->allowClose(false);
	m_menu->lockSize(true,v2u32(800,600));

	// Initialize scripting

	infostream << "GUIEngine: Initializing Lua" << std::endl;

	m_script = new MainMenuScripting(this);

	try {
		m_script->setMainMenuData(&m_data->script_data);
		m_data->script_data.errormessage = "";

		if (!loadMainMenuScript()) {
			errorstream << "No future without main menu!" << std::endl;
			abort();
		}

		run();
	} catch (LuaError &e) {
		errorstream << "Main menu error: " << e.what() << std::endl;
		m_data->script_data.errormessage = e.what();
	}

	m_menu->quitMenu();
	m_menu->drop();
	m_menu = NULL;
}

/******************************************************************************/
bool GUIEngine::loadMainMenuScript()
{
	// Set main menu path (for core.get_mainmenu_path())
	m_scriptdir = g_settings->get("main_menu_path");
	if (m_scriptdir.empty()) {
		m_scriptdir = porting::path_share + DIR_DELIM + "builtin" + DIR_DELIM + "mainmenu";
	}

	// Load builtin (which will load the main menu script)
	std::string script = porting::path_share + DIR_DELIM "builtin" + DIR_DELIM "init.lua";
	try {
		m_script->loadScript(script);
		// Menu script loaded
		return true;
	} catch (const ModError &e) {
		errorstream << "GUIEngine: execution of menu script failed: "
			<< e.what() << std::endl;
	}

	return false;
}

/******************************************************************************/
void GUIEngine::run()
{
	// Always create clouds because they may or may not be
	// needed based on the game selected
	video::IVideoDriver *driver = RenderingEngine::get_video_driver();

	cloudInit();

	unsigned int text_height = g_fontengine->getTextHeight();

	irr::core::dimension2d<u32> previous_screen_size(g_settings->getU16("screen_w"),
		g_settings->getU16("screen_h"));

	static const video::SColor sky_color(255, 140, 186, 250);

	// Reset fog color
	{
		video::SColor fog_color;
		video::E_FOG_TYPE fog_type = video::EFT_FOG_LINEAR;
		f32 fog_start = 0;
		f32 fog_end = 0;
		f32 fog_density = 0;
		bool fog_pixelfog = false;
		bool fog_rangefog = false;
		driver->getFog(fog_color, fog_type, fog_start, fog_end, fog_density,
				fog_pixelfog, fog_rangefog);

		driver->setFog(sky_color, fog_type, fog_start, fog_end, fog_density,
				fog_pixelfog, fog_rangefog);
	}

	while (RenderingEngine::run() && (!m_startgame) && (!m_kill)) {

		const irr::core::dimension2d<u32> &current_screen_size =
			RenderingEngine::get_video_driver()->getScreenSize();
		// Verify if window size has changed and save it if it's the case
		// Ensure evaluating settings->getBool after verifying screensize
		// First condition is cheaper
		if (previous_screen_size != current_screen_size &&
				current_screen_size != irr::core::dimension2d<u32>(0,0) &&
				g_settings->getBool("autosave_screensize")) {
			g_settings->setU16("screen_w", current_screen_size.Width);
			g_settings->setU16("screen_h", current_screen_size.Height);
			previous_screen_size = current_screen_size;
		}

		//check if we need to update the "upper left corner"-text
		if (text_height != g_fontengine->getTextHeight()) {
			updateTopLeftTextSize();
			text_height = g_fontengine->getTextHeight();
		}

		driver->beginScene(true, true, sky_color);

		if (m_clouds_enabled)
		{
			cloudPreProcess();
			drawOverlay(driver);
		}
		else
			drawBackground(driver);

		drawHeader(driver);
		drawFooter(driver);

		RenderingEngine::get_gui_env()->drawAll();

		driver->endScene();

		if (m_clouds_enabled)
			cloudPostProcess();
		else
			sleep_ms(25);

		m_script->step();

#ifdef __ANDROID__
		m_menu->getAndroidUIInput();
#endif
	}
}

/******************************************************************************/
GUIEngine::~GUIEngine()
{
	if (m_sound_manager != &dummySoundManager){
		delete m_sound_manager;
		m_sound_manager = NULL;
	}

	infostream<<"GUIEngine: Deinitializing scripting"<<std::endl;
	delete m_script;

	m_irr_toplefttext->setText(L"");

	//clean up texture pointers
	for (image_definition &texture : m_textures) {
		if (texture.texture)
			RenderingEngine::get_video_driver()->removeTexture(texture.texture);
	}

	delete m_texture_source;

	if (m_cloud.clouds)
		m_cloud.clouds->drop();
}

/******************************************************************************/
void GUIEngine::cloudInit()
{
	m_cloud.clouds = new Clouds(m_smgr, -1, rand());
	m_cloud.clouds->setHeight(100.0f);
	m_cloud.clouds->update(v3f(0, 0, 0), video::SColor(255,240,240,255));

	m_cloud.camera = m_smgr->addCameraSceneNode(0,
				v3f(0,0,0), v3f(0, 60, 100));
	m_cloud.camera->setFarValue(10000);

	m_cloud.lasttime = RenderingEngine::get_timer_time();
}

/******************************************************************************/
void GUIEngine::cloudPreProcess()
{
	u32 time = RenderingEngine::get_timer_time();

	if(time > m_cloud.lasttime)
		m_cloud.dtime = (time - m_cloud.lasttime) / 1000.0;
	else
		m_cloud.dtime = 0;

	m_cloud.lasttime = time;

	m_cloud.clouds->step(m_cloud.dtime*3);
	m_cloud.clouds->render();
	m_smgr->drawAll();
}

/******************************************************************************/
void GUIEngine::cloudPostProcess()
{
	float fps_max = g_settings->getFloat("pause_fps_max");
	// Time of frame without fps limit
	u32 busytime_u32;

	// not using getRealTime is necessary for wine
	u32 time = RenderingEngine::get_timer_time();
	if(time > m_cloud.lasttime)
		busytime_u32 = time - m_cloud.lasttime;
	else
		busytime_u32 = 0;

	// FPS limiter
	u32 frametime_min = 1000./fps_max;

	if (busytime_u32 < frametime_min) {
		u32 sleeptime = frametime_min - busytime_u32;
		RenderingEngine::get_raw_device()->sleep(sleeptime);
	}
}

/******************************************************************************/
void GUIEngine::setFormspecPrepend(const std::string &fs)
{
	if (m_menu) {
		m_menu->setFormspecPrepend(fs);
	}
}


/******************************************************************************/
void GUIEngine::drawBackground(video::IVideoDriver *driver)
{
	v2u32 screensize = driver->getScreenSize();

	video::ITexture* texture = m_textures[TEX_LAYER_BACKGROUND].texture;

	/* If no texture, draw background of solid color */
	if(!texture){
		video::SColor color(255,80,58,37);
		core::rect<s32> rect(0, 0, screensize.X, screensize.Y);
		driver->draw2DRectangle(color, rect, NULL);
		return;
	}

	v2u32 sourcesize = texture->getOriginalSize();

	if (m_textures[TEX_LAYER_BACKGROUND].tile)
	{
		v2u32 tilesize(
				MYMAX(sourcesize.X,m_textures[TEX_LAYER_BACKGROUND].minsize),
				MYMAX(sourcesize.Y,m_textures[TEX_LAYER_BACKGROUND].minsize));
		for (unsigned int x = 0; x < screensize.X; x += tilesize.X )
		{
			for (unsigned int y = 0; y < screensize.Y; y += tilesize.Y )
			{
				draw2DImageFilterScaled(driver, texture,
					core::rect<s32>(x, y, x+tilesize.X, y+tilesize.Y),
					core::rect<s32>(0, 0, sourcesize.X, sourcesize.Y),
					NULL, NULL, true);
			}
		}
		return;
	}

	/* Draw background texture */
	draw2DImageFilterScaled(driver, texture,
		core::rect<s32>(0, 0, screensize.X, screensize.Y),
		core::rect<s32>(0, 0, sourcesize.X, sourcesize.Y),
		NULL, NULL, true);
}

/******************************************************************************/
void GUIEngine::drawOverlay(video::IVideoDriver *driver)
{
	v2u32 screensize = driver->getScreenSize();

	video::ITexture* texture = m_textures[TEX_LAYER_OVERLAY].texture;

	/* If no texture, draw nothing */
	if(!texture)
		return;

	/* Draw background texture */
	v2u32 sourcesize = texture->getOriginalSize();
	draw2DImageFilterScaled(driver, texture,
		core::rect<s32>(0, 0, screensize.X, screensize.Y),
		core::rect<s32>(0, 0, sourcesize.X, sourcesize.Y),
		NULL, NULL, true);
}

/******************************************************************************/
void GUIEngine::drawHeader(video::IVideoDriver *driver)
{
	core::dimension2d<u32> screensize = driver->getScreenSize();

	video::ITexture* texture = m_textures[TEX_LAYER_HEADER].texture;

	/* If no texture, draw nothing */
	if(!texture)
		return;

	f32 mult = (((f32)screensize.Width / 2.0)) /
			((f32)texture->getOriginalSize().Width);

	v2s32 splashsize(((f32)texture->getOriginalSize().Width) * mult,
			((f32)texture->getOriginalSize().Height) * mult);

	// Don't draw the header if there isn't enough room
	s32 free_space = (((s32)screensize.Height)-320)/2;

	if (free_space > splashsize.Y) {
		core::rect<s32> splashrect(0, 0, splashsize.X, splashsize.Y);
		splashrect += v2s32((screensize.Width/2)-(splashsize.X/2),
				((free_space/2)-splashsize.Y/2)+10);

	video::SColor bgcolor(255,50,50,50);

	draw2DImageFilterScaled(driver, texture, splashrect,
		core::rect<s32>(core::position2d<s32>(0,0),
		core::dimension2di(texture->getOriginalSize())),
		NULL, NULL, true);
	}
}

/******************************************************************************/
void GUIEngine::drawFooter(video::IVideoDriver *driver)
{
	core::dimension2d<u32> screensize = driver->getScreenSize();

	video::ITexture* texture = m_textures[TEX_LAYER_FOOTER].texture;

	/* If no texture, draw nothing */
	if(!texture)
		return;

	f32 mult = (((f32)screensize.Width)) /
			((f32)texture->getOriginalSize().Width);

	v2s32 footersize(((f32)texture->getOriginalSize().Width) * mult,
			((f32)texture->getOriginalSize().Height) * mult);

	// Don't draw the footer if there isn't enough room
	s32 free_space = (((s32)screensize.Height)-320)/2;

	if (free_space > footersize.Y) {
		core::rect<s32> rect(0,0,footersize.X,footersize.Y);
		rect += v2s32(screensize.Width/2,screensize.Height-footersize.Y);
		rect -= v2s32(footersize.X/2, 0);

		draw2DImageFilterScaled(driver, texture, rect,
			core::rect<s32>(core::position2d<s32>(0,0),
			core::dimension2di(texture->getOriginalSize())),
			NULL, NULL, true);
	}
}

/******************************************************************************/
bool GUIEngine::setTexture(texture_layer layer, const std::string &texturepath,
		bool tile_image, unsigned int minsize)
{
	video::IVideoDriver *driver = RenderingEngine::get_video_driver();

	if (m_textures[layer].texture) {
		driver->removeTexture(m_textures[layer].texture);
		m_textures[layer].texture = NULL;
	}

	if (texturepath.empty() || !fs::PathExists(texturepath)) {
		return false;
	}

	m_textures[layer].texture = driver->getTexture(texturepath.c_str());
	m_textures[layer].tile    = tile_image;
	m_textures[layer].minsize = minsize;

	if (!m_textures[layer].texture) {
		return false;
	}

	return true;
}

/******************************************************************************/
bool GUIEngine::downloadFile(const std::string &url, const std::string &target)
{
#if USE_CURL
	std::ofstream target_file(target.c_str(), std::ios::out | std::ios::binary);
	if (!target_file.good()) {
		return false;
	}

	HTTPFetchRequest fetch_request;
	HTTPFetchResult fetch_result;
	fetch_request.url = url;
	fetch_request.caller = HTTPFETCH_SYNC;
	fetch_request.timeout = g_settings->getS32("curl_file_download_timeout");
	httpfetch_sync(fetch_request, fetch_result);

	if (!fetch_result.succeeded) {
		target_file.close();
		fs::DeleteSingleFileOrEmptyDirectory(target);
		return false;
	}
	target_file << fetch_result.data;

	return true;
#else
	return false;
#endif
}

/******************************************************************************/
void GUIEngine::setTopleftText(const std::string &text)
{
	m_toplefttext = translate_string(utf8_to_wide(text));

	updateTopLeftTextSize();
}

/******************************************************************************/
void GUIEngine::updateTopLeftTextSize()
{
	core::rect<s32> rect(0, 0, g_fontengine->getTextWidth(m_toplefttext.c_str()),
		g_fontengine->getTextHeight());
	rect += v2s32(4, 0);

	m_irr_toplefttext->remove();
	m_irr_toplefttext = gui::StaticText::add(RenderingEngine::get_gui_env(),
			m_toplefttext, rect, false, true, 0, -1);
}

/******************************************************************************/
s32 GUIEngine::playSound(const SimpleSoundSpec &spec, bool looped)
{
	s32 handle = m_sound_manager->playSound(spec, looped);
	return handle;
}

/******************************************************************************/
void GUIEngine::stopSound(s32 handle)
{
	m_sound_manager->stopSound(handle);
}

/******************************************************************************/
unsigned int GUIEngine::queueAsync(const std::string &serialized_func,
		const std::string &serialized_params)
{
	return m_script->queueAsync(serialized_func, serialized_params);
}
td::endl); } return; } //don't add anything if it isn't an air node if (ndef->get(current).walkable || !ndef->get(below).walkable) { DEBUG_OUT("Pathfinder: " << PP(realpos) << " not on surface" << std::endl); if (ndef->get(current).walkable) { elem.type = 's'; DEBUG_OUT(PP(ipos) << ": " << 's' << std::endl); } else { elem.type = '-'; DEBUG_OUT(PP(ipos) << ": " << '-' << std::endl); } return; } elem.valid = true; elem.pos = realpos; elem.type = 'g'; DEBUG_OUT(PP(ipos) << ": " << 'a' << std::endl); if (m_pathf->m_prefetch) { elem.directions[DIR_XP] = m_pathf->calcCost(realpos, v3s16( 1, 0, 0)); elem.directions[DIR_XM] = m_pathf->calcCost(realpos, v3s16(-1, 0, 0)); elem.directions[DIR_ZP] = m_pathf->calcCost(realpos, v3s16( 0, 0, 1)); elem.directions[DIR_ZM] = m_pathf->calcCost(realpos, v3s16( 0, 0,-1)); } } ArrayGridNodeContainer::ArrayGridNodeContainer(Pathfinder *pathf, v3s16 dimensions) : m_x_stride(dimensions.Y * dimensions.Z), m_y_stride(dimensions.Z) { m_pathf = pathf; m_nodes_array.resize(dimensions.X * dimensions.Y * dimensions.Z); INFO_TARGET << "Pathfinder ArrayGridNodeContainer constructor." << std::endl; for (int x = 0; x < dimensions.X; x++) { for (int y = 0; y < dimensions.Y; y++) { for (int z= 0; z < dimensions.Z; z++) { v3s16 ipos(x, y, z); initNode(ipos, &access(ipos)); } } } } PathGridnode &ArrayGridNodeContainer::access(v3s16 p) { return m_nodes_array[p.X * m_x_stride + p.Y * m_y_stride + p.Z]; } MapGridNodeContainer::MapGridNodeContainer(Pathfinder *pathf) { m_pathf = pathf; } PathGridnode &MapGridNodeContainer::access(v3s16 p) { std::map<v3s16, PathGridnode>::iterator it = m_nodes.find(p); if (it != m_nodes.end()) { return it->second; } PathGridnode &n = m_nodes[p]; initNode(p, &n); return n; } /******************************************************************************/ std::vector<v3s16> Pathfinder::getPath(v3s16 source, v3s16 destination, unsigned int searchdistance, unsigned int max_jump, unsigned int max_drop, PathAlgorithm algo) { #ifdef PATHFINDER_CALC_TIME timespec ts; clock_gettime(CLOCK_REALTIME, &ts); #endif std::vector<v3s16> retval; //initialization m_searchdistance = searchdistance; m_maxjump = max_jump; m_maxdrop = max_drop; m_start = source; m_destination = destination; m_min_target_distance = -1; m_prefetch = true; if (algo == PA_PLAIN_NP) { m_prefetch = false; } //calculate boundaries within we're allowed to search int min_x = MYMIN(source.X, destination.X); int max_x = MYMAX(source.X, destination.X); int min_y = MYMIN(source.Y, destination.Y); int max_y = MYMAX(source.Y, destination.Y); int min_z = MYMIN(source.Z, destination.Z); int max_z = MYMAX(source.Z, destination.Z); m_limits.MinEdge.X = min_x - searchdistance; m_limits.MinEdge.Y = min_y - searchdistance; m_limits.MinEdge.Z = min_z - searchdistance; m_limits.MaxEdge.X = max_x + searchdistance; m_limits.MaxEdge.Y = max_y + searchdistance; m_limits.MaxEdge.Z = max_z + searchdistance; v3s16 diff = m_limits.MaxEdge - m_limits.MinEdge; m_max_index_x = diff.X; m_max_index_y = diff.Y; m_max_index_z = diff.Z; delete m_nodes_container; if (diff.getLength() > 5) { m_nodes_container = new MapGridNodeContainer(this); } else { m_nodes_container = new ArrayGridNodeContainer(this, diff); } #ifdef PATHFINDER_DEBUG printType(); printCost(); printYdir(); #endif //fail if source or destination is walkable MapNode node_at_pos = m_map->getNode(destination); if (m_ndef->get(node_at_pos).walkable) { VERBOSE_TARGET << "Destination is walkable. " << "Pos: " << PP(destination) << std::endl; return retval; } node_at_pos = m_map->getNode(source); if (m_ndef->get(node_at_pos).walkable) { VERBOSE_TARGET << "Source is walkable. " << "Pos: " << PP(source) << std::endl; return retval; } //If source pos is hovering above air, drop //to the first walkable node (up to m_maxdrop). //All algorithms expect the source pos to be *directly* above //a walkable node. v3s16 true_source = v3s16(source); source = walkDownwards(source, m_maxdrop); //If destination pos is hovering above air, go downwards //to the first walkable node (up to m_maxjump). //This means a hovering destination pos could be reached //by a final upwards jump. v3s16 true_destination = v3s16(destination); destination = walkDownwards(destination, m_maxjump); //validate and mark start and end pos v3s16 StartIndex = getIndexPos(source); v3s16 EndIndex = getIndexPos(destination); PathGridnode &startpos = getIndexElement(StartIndex); PathGridnode &endpos = getIndexElement(EndIndex); if (!startpos.valid) { VERBOSE_TARGET << "Invalid startpos " << "Index: " << PP(StartIndex) << "Realpos: " << PP(getRealPos(StartIndex)) << std::endl; return retval; } if (!endpos.valid) { VERBOSE_TARGET << "Invalid stoppos " << "Index: " << PP(EndIndex) << "Realpos: " << PP(getRealPos(EndIndex)) << std::endl; return retval; } endpos.target = true; startpos.source = true; startpos.totalcost = 0; bool update_cost_retval = false; //calculate node costs switch (algo) { case PA_DIJKSTRA: update_cost_retval = updateAllCosts(StartIndex, v3s16(0, 0, 0), 0, 0); break; case PA_PLAIN_NP: case PA_PLAIN: update_cost_retval = updateCostHeuristic(StartIndex, EndIndex); break; default: ERROR_TARGET << "Missing PathAlgorithm" << std::endl; break; } if (update_cost_retval) { #ifdef PATHFINDER_DEBUG std::cout << "Path to target found!" << std::endl; printPathLen(); #endif //find path std::vector<v3s16> index_path; buildPath(index_path, EndIndex); //Now we have a path of index positions, //and it's in reverse. //The "true" start or end position might be missing //since those have been given special treatment. #ifdef PATHFINDER_DEBUG std::cout << "Index path:" << std::endl; printPath(index_path); #endif //from here we'll make the final changes to the path std::vector<v3s16> full_path; //calculate required size int full_path_size = index_path.size(); if (source != true_source) { full_path_size++; } if (destination != true_destination) { full_path_size++; } full_path.reserve(full_path_size); //manually add true_source to start of path, if needed if (source != true_source) { full_path.push_back(true_source); } //convert all index positions to "normal" positions and insert //them into full_path in reverse std::vector<v3s16>::reverse_iterator rit = index_path.rbegin(); for (; rit != index_path.rend(); ++rit) { full_path.push_back(getIndexElement(*rit).pos); } //manually add true_destination to end of path, if needed if (destination != true_destination) { full_path.push_back(true_destination); } //Done! We now have a complete path of normal positions. #ifdef PATHFINDER_DEBUG std::cout << "Full path:" << std::endl; printPath(full_path); #endif #ifdef PATHFINDER_CALC_TIME timespec ts2; clock_gettime(CLOCK_REALTIME, &ts2); int ms = (ts2.tv_nsec - ts.tv_nsec)/(1000*1000); int us = ((ts2.tv_nsec - ts.tv_nsec) - (ms*1000*1000))/1000; int ns = ((ts2.tv_nsec - ts.tv_nsec) - ( (ms*1000*1000) + (us*1000))); std::cout << "Calculating path took: " << (ts2.tv_sec - ts.tv_sec) << "s " << ms << "ms " << us << "us " << ns << "ns " << std::endl; #endif return full_path; } else { #ifdef PATHFINDER_DEBUG printPathLen(); #endif INFO_TARGET << "No path found" << std::endl; } //return return retval; } Pathfinder::~Pathfinder() { delete m_nodes_container; } /******************************************************************************/ v3s16 Pathfinder::getRealPos(v3s16 ipos) { return m_limits.MinEdge + ipos; } /******************************************************************************/ PathCost Pathfinder::calcCost(v3s16 pos, v3s16 dir) { PathCost retval; retval.updated = true; v3s16 pos2 = pos + dir; //check limits if (!m_limits.isPointInside(pos2)) { DEBUG_OUT("Pathfinder: " << PP(pos2) << " no cost -> out of limits" << std::endl); return retval; } MapNode node_at_pos2 = m_map->getNode(pos2); //did we get information about node? if (node_at_pos2.param0 == CONTENT_IGNORE ) { VERBOSE_TARGET << "Pathfinder: (1) area at pos: " << PP(pos2) << " not loaded"; return retval; } if (!m_ndef->get(node_at_pos2).walkable) { MapNode node_below_pos2 = m_map->getNode(pos2 + v3s16(0, -1, 0)); //did we get information about node? if (node_below_pos2.param0 == CONTENT_IGNORE ) { VERBOSE_TARGET << "Pathfinder: (2) area at pos: " << PP((pos2 + v3s16(0, -1, 0))) << " not loaded"; return retval; } //test if the same-height neighbor is suitable if (m_ndef->get(node_below_pos2).walkable) { //SUCCESS! retval.valid = true; retval.value = 1; retval.y_change = 0; DEBUG_OUT("Pathfinder: "<< PP(pos) << " cost same height found" << std::endl); } else { //test if we can fall a couple of nodes (m_maxdrop) v3s16 testpos = pos2 + v3s16(0, -1, 0); MapNode node_at_pos = m_map->getNode(testpos); while ((node_at_pos.param0 != CONTENT_IGNORE) && (!m_ndef->get(node_at_pos).walkable) && (testpos.Y > m_limits.MinEdge.Y)) { testpos += v3s16(0, -1, 0); node_at_pos = m_map->getNode(testpos); } //did we find surface? if ((testpos.Y >= m_limits.MinEdge.Y) && (node_at_pos.param0 != CONTENT_IGNORE) && (m_ndef->get(node_at_pos).walkable)) { if ((pos2.Y - testpos.Y - 1) <= m_maxdrop) { //SUCCESS! retval.valid = true; retval.value = 2; //difference of y-pos +1 (target node is ABOVE solid node) retval.y_change = ((testpos.Y - pos2.Y) +1); DEBUG_OUT("Pathfinder cost below height found" << std::endl); } else { INFO_TARGET << "Pathfinder:" " distance to surface below too big: " << (testpos.Y - pos2.Y) << " max: " << m_maxdrop << std::endl; } } else { DEBUG_OUT("Pathfinder: no surface below found" << std::endl); } } } else { //test if we can jump upwards (m_maxjump) v3s16 targetpos = pos2; // position for jump target v3s16 jumppos = pos; // position for checking if jumping space is free MapNode node_target = m_map->getNode(targetpos); MapNode node_jump = m_map->getNode(jumppos); bool headbanger = false; // true if anything blocks jumppath while ((node_target.param0 != CONTENT_IGNORE) && (m_ndef->get(node_target).walkable) && (targetpos.Y < m_limits.MaxEdge.Y)) { //if the jump would hit any solid node, discard if ((node_jump.param0 == CONTENT_IGNORE) || (m_ndef->get(node_jump).walkable)) { headbanger = true; break; } targetpos += v3s16(0, 1, 0); jumppos += v3s16(0, 1, 0); node_target = m_map->getNode(targetpos); node_jump = m_map->getNode(jumppos); } //check headbanger one last time if ((node_jump.param0 == CONTENT_IGNORE) || (m_ndef->get(node_jump).walkable)) { headbanger = true; } //did we find surface without banging our head? if ((!headbanger) && (targetpos.Y <= m_limits.MaxEdge.Y) && (!m_ndef->get(node_target).walkable)) { if (targetpos.Y - pos2.Y <= m_maxjump) { //SUCCESS! retval.valid = true; retval.value = 2; retval.y_change = (targetpos.Y - pos2.Y); DEBUG_OUT("Pathfinder cost above found" << std::endl); } else { DEBUG_OUT("Pathfinder: distance to surface above too big: " << (targetpos.Y - pos2.Y) << " max: " << m_maxjump << std::endl); } } else { DEBUG_OUT("Pathfinder: no surface above found" << std::endl); } } return retval; } /******************************************************************************/ v3s16 Pathfinder::getIndexPos(v3s16 pos) { return pos - m_limits.MinEdge; } /******************************************************************************/ PathGridnode &Pathfinder::getIndexElement(v3s16 ipos) { return m_nodes_container->access(ipos); } /******************************************************************************/ inline PathGridnode &Pathfinder::getIdxElem(s16 x, s16 y, s16 z) { return m_nodes_container->access(v3s16(x,y,z)); } /******************************************************************************/ bool Pathfinder::isValidIndex(v3s16 index) { if ( (index.X < m_max_index_x) && (index.Y < m_max_index_y) && (index.Z < m_max_index_z) && (index.X >= 0) && (index.Y >= 0) && (index.Z >= 0)) return true; return false; } /******************************************************************************/ v3s16 Pathfinder::invert(v3s16 pos) { v3s16 retval = pos; retval.X *=-1; retval.Y *=-1; retval.Z *=-1; return retval; } /******************************************************************************/ bool Pathfinder::updateAllCosts(v3s16 ipos, v3s16 srcdir, int current_cost, int level) { PathGridnode &g_pos = getIndexElement(ipos); g_pos.totalcost = current_cost; g_pos.sourcedir = srcdir; level ++; //check if target has been found if (g_pos.target) { m_min_target_distance = current_cost; DEBUG_OUT(LVL " Pathfinder: target found!" << std::endl); return true; } bool retval = false; // the 4 cardinal directions const static v3s16 directions[4] = { v3s16(1,0, 0), v3s16(-1,0, 0), v3s16(0,0, 1), v3s16(0,0,-1) }; for (v3s16 direction : directions) { if (direction != srcdir) { PathCost cost = g_pos.getCost(direction); if (cost.valid) { direction.Y = cost.y_change; v3s16 ipos2 = ipos + direction; if (!isValidIndex(ipos2)) { DEBUG_OUT(LVL " Pathfinder: " << PP(ipos2) << " out of range, max=" << PP(m_limits.MaxEdge) << std::endl); continue; } PathGridnode &g_pos2 = getIndexElement(ipos2); if (!g_pos2.valid) { VERBOSE_TARGET << LVL "Pathfinder: no data for new position: " << PP(ipos2) << std::endl; continue; } assert(cost.value > 0); int new_cost = current_cost + cost.value; // check if there already is a smaller path if ((m_min_target_distance > 0) && (m_min_target_distance < new_cost)) { return false; } if ((g_pos2.totalcost < 0) || (g_pos2.totalcost > new_cost)) { DEBUG_OUT(LVL "Pathfinder: updating path at: "<< PP(ipos2) << " from: " << g_pos2.totalcost << " to "<< new_cost << std::endl); if (updateAllCosts(ipos2, invert(direction), new_cost, level)) { retval = true; } } else { DEBUG_OUT(LVL "Pathfinder:" " already found shorter path to: " << PP(ipos2) << std::endl); } } else { DEBUG_OUT(LVL "Pathfinder:" " not moving to invalid direction: " << PP(directions[i]) << std::endl); } } } return retval; } /******************************************************************************/ int Pathfinder::getXZManhattanDist(v3s16 pos) { int min_x = MYMIN(pos.X, m_destination.X); int max_x = MYMAX(pos.X, m_destination.X); int min_z = MYMIN(pos.Z, m_destination.Z); int max_z = MYMAX(pos.Z, m_destination.Z); return (max_x - min_x) + (max_z - min_z); } /******************************************************************************/ bool Pathfinder::updateCostHeuristic(v3s16 isource, v3s16 idestination) { // A* search algorithm. // The open list contains the pathfinder nodes that still need to be // checked. The priority queue sorts the pathfinder nodes by // estimated cost, with lowest cost on the top. std::priority_queue<v3s16, std::vector<v3s16>, PathfinderCompareHeuristic> openList(PathfinderCompareHeuristic(this)); v3s16 source = getRealPos(isource); v3s16 destination = getRealPos(idestination); // initial position openList.push(source); // the 4 cardinal directions const static v3s16 directions[4] = { v3s16(1,0, 0), v3s16(-1,0, 0), v3s16(0,0, 1), v3s16(0,0,-1) }; v3s16 current_pos; PathGridnode& s_pos = getIndexElement(isource); s_pos.source = true; s_pos.totalcost = 0; // estimated cost from start to finish int cur_manhattan = getXZManhattanDist(destination); s_pos.estimated_cost = cur_manhattan; while (!openList.empty()) { // Pick node with lowest total cost estimate. // The "cheapest" node is always on top. current_pos = openList.top(); openList.pop(); v3s16 ipos = getIndexPos(current_pos); // check if node is inside searchdistance and valid if (!isValidIndex(ipos)) { DEBUG_OUT(LVL " Pathfinder: " << PP(current_pos) << " out of search distance, max=" << PP(m_limits.MaxEdge) << std::endl); continue; } PathGridnode& g_pos = getIndexElement(ipos); g_pos.is_closed = true; g_pos.is_open = false; if (!g_pos.valid) { continue; } if (current_pos == destination) { // destination found, terminate g_pos.target = true; return true; } // for this node, check the 4 cardinal directions for (v3s16 direction_flat : directions) { int current_totalcost = g_pos.totalcost; // get cost from current node to currently checked direction PathCost cost = g_pos.getCost(direction_flat); if (!cost.updated) { cost = calcCost(current_pos, direction_flat); g_pos.setCost(direction_flat, cost); } // update Y component of direction if neighbor requires jump or fall v3s16 direction_3d = v3s16(direction_flat); direction_3d.Y = cost.y_change; // get position of true neighbor v3s16 neighbor = current_pos + direction_3d; v3s16 ineighbor = getIndexPos(neighbor); PathGridnode &n_pos = getIndexElement(ineighbor); if (cost.valid && !n_pos.is_closed && !n_pos.is_open) { // heuristic function; estimate cost from neighbor to destination cur_manhattan = getXZManhattanDist(neighbor); // add neighbor to open list n_pos.sourcedir = invert(direction_3d); n_pos.totalcost = current_totalcost + cost.value; n_pos.estimated_cost = current_totalcost + cost.value + cur_manhattan; n_pos.is_open = true; openList.push(neighbor); } } } // no path found; all possible nodes within searchdistance have been exhausted return false; } /******************************************************************************/ bool Pathfinder::buildPath(std::vector<v3s16> &path, v3s16 ipos) { // The cost calculation should have set a source direction for all relevant nodes. // To build the path, we go backwards from the destination until we reach the start. for(u32 waypoints = 1; waypoints++; ) { if (waypoints > PATHFINDER_MAX_WAYPOINTS) { ERROR_TARGET << "Pathfinder: buildPath: path is too long (too many waypoints), aborting" << std::endl; return false; } // Insert node into path PathGridnode &g_pos = getIndexElement(ipos); if (!g_pos.valid) { ERROR_TARGET << "Pathfinder: buildPath: invalid next pos detected, aborting" << std::endl; return false; } g_pos.is_element = true; path.push_back(ipos); if (g_pos.source) // start node found, terminate return true; // go to the node from which the pathfinder came ipos += g_pos.sourcedir; } ERROR_TARGET << "Pathfinder: buildPath: no source node found" << std::endl; return false; } /******************************************************************************/ v3s16 Pathfinder::walkDownwards(v3s16 pos, unsigned int max_down) { if (max_down == 0) return pos; v3s16 testpos = v3s16(pos); MapNode node_at_pos = m_map->getNode(testpos); unsigned int down = 0; while ((node_at_pos.param0 != CONTENT_IGNORE) && (!m_ndef->get(node_at_pos).walkable) && (testpos.Y > m_limits.MinEdge.Y) && (down <= max_down)) { testpos += v3s16(0, -1, 0); down++; node_at_pos = m_map->getNode(testpos); } //did we find surface? if ((testpos.Y >= m_limits.MinEdge.Y) && (node_at_pos.param0 != CONTENT_IGNORE) && (m_ndef->get(node_at_pos).walkable)) { if (down == 0) { pos = testpos; } else if ((down - 1) <= max_down) { //difference of y-pos +1 (target node is ABOVE solid node) testpos += v3s16(0, 1, 0); pos = testpos; } else { VERBOSE_TARGET << "Pos too far above ground: " << "Index: " << PP(getIndexPos(pos)) << "Realpos: " << PP(getRealPos(getIndexPos(pos))) << std::endl; } } else { DEBUG_OUT("Pathfinder: no surface found below pos" << std::endl); } return pos; } #ifdef PATHFINDER_DEBUG /******************************************************************************/ void Pathfinder::printCost() { printCost(DIR_XP); printCost(DIR_XM); printCost(DIR_ZP); printCost(DIR_ZM); } /******************************************************************************/ void Pathfinder::printYdir() { printYdir(DIR_XP); printYdir(DIR_XM); printYdir(DIR_ZP); printYdir(DIR_ZM); } /******************************************************************************/ void Pathfinder::printCost(PathDirections dir) { std::cout << "Cost in direction: " << dirToName(dir) << std::endl; std::cout << std::setfill('-') << std::setw(80) << "-" << std::endl; std::cout << std::setfill(' '); for (int y = 0; y < m_max_index_y; y++) { std::cout << "Level: " << y << std::endl; std::cout << std::setw(4) << " " << " "; for (int x = 0; x < m_max_index_x; x++) { std::cout << std::setw(4) << x; } std::cout << std::endl; for (int z = 0; z < m_max_index_z; z++) { std::cout << std::setw(4) << z <<": "; for (int x = 0; x < m_max_index_x; x++) { if (getIdxElem(x, y, z).directions[dir].valid) std::cout << std::setw(4) << getIdxElem(x, y, z).directions[dir].value; else std::cout << std::setw(4) << "-"; } std::cout << std::endl; } std::cout << std::endl; } } /******************************************************************************/ void Pathfinder::printYdir(PathDirections dir) { std::cout << "Height difference in direction: " << dirToName(dir) << std::endl; std::cout << std::setfill('-') << std::setw(80) << "-" << std::endl; std::cout << std::setfill(' '); for (int y = 0; y < m_max_index_y; y++) { std::cout << "Level: " << y << std::endl; std::cout << std::setw(4) << " " << " "; for (int x = 0; x < m_max_index_x; x++) { std::cout << std::setw(4) << x; } std::cout << std::endl; for (int z = 0; z < m_max_index_z; z++) { std::cout << std::setw(4) << z <<": "; for (int x = 0; x < m_max_index_x; x++) { if (getIdxElem(x, y, z).directions[dir].valid) std::cout << std::setw(4) << getIdxElem(x, y, z).directions[dir].y_change; else std::cout << std::setw(4) << "-"; } std::cout << std::endl; } std::cout << std::endl; } } /******************************************************************************/ void Pathfinder::printType() { std::cout << "Type of node:" << std::endl; std::cout << std::setfill('-') << std::setw(80) << "-" << std::endl; std::cout << std::setfill(' '); for (int y = 0; y < m_max_index_y; y++) { std::cout << "Level: " << y << std::endl; std::cout << std::setw(3) << " " << " "; for (int x = 0; x < m_max_index_x; x++) { std::cout << std::setw(3) << x; } std::cout << std::endl; for (int z = 0; z < m_max_index_z; z++) { std::cout << std::setw(3) << z <<": "; for (int x = 0; x < m_max_index_x; x++) { char toshow = getIdxElem(x, y, z).type; std::cout << std::setw(3) << toshow; } std::cout << std::endl; } std::cout << std::endl; } std::cout << std::endl; } /******************************************************************************/ void Pathfinder::printPathLen() { std::cout << "Pathlen:" << std::endl; std::cout << std::setfill('-') << std::setw(80) << "-" << std::endl; std::cout << std::setfill(' '); for (int y = 0; y < m_max_index_y; y++) { std::cout << "Level: " << y << std::endl; std::cout << std::setw(3) << " " << " "; for (int x = 0; x < m_max_index_x; x++) { std::cout << std::setw(3) << x; } std::cout << std::endl; for (int z = 0; z < m_max_index_z; z++) { std::cout << std::setw(3) << z <<": "; for (int x = 0; x < m_max_index_x; x++) { std::cout << std::setw(3) << getIdxElem(x, y, z).totalcost; } std::cout << std::endl; } std::cout << std::endl; } std::cout << std::endl; } /******************************************************************************/ std::string Pathfinder::dirToName(PathDirections dir) { switch (dir) { case DIR_XP: return "XP"; break; case DIR_XM: return "XM"; break; case DIR_ZP: return "ZP"; break; case DIR_ZM: return "ZM"; break; default: return "UKN"; } } /******************************************************************************/ void Pathfinder::printPath(std::vector<v3s16> path) { unsigned int current = 0; for (std::vector<v3s16>::iterator i = path.begin(); i != path.end(); ++i) { std::cout << std::setw(3) << current << ":" << PP((*i)) << std::endl; current++; } } #endif