find_path: consider walkable instead of CONTENT_AIR
The path finding code works fairly well except that it considers
anythin not CONTENT_AIR to be "above the surface". This results in
paths that are unwalkable for entities since e.g. plants are not
walkable. The path would force them to jump on top of grass plants,
etc..
The obvious solution is not to use CONTENT_AIR as a criteria, but
instead distinguish between walkable and non-walkable nodes. This
results in paths that properly walk through grass nodes.
This was extensively tested by a flock of electric sheep.
Note that for underwater purposes this changes the behaviour from
"the surface is walkable" to "ignore water entirely" making the
path go across the water bottom, and pathing fail likely from the
water surface. This is intentional.
Before, the GridNodes were stored in vector<vector<vector<T>>>,
and initialized in advance. Putting three vectors inside each other
puts lots of unneccessary stress onto the allocator, costs more memory,
and has worse cache locality than a flat vector<T>.
For larger search distances, an the array getting initialized means
essentially O(distance^3) complexity in both time and memory,
which makes the current path search a joke. In order to really
profit from the dijkstra/A* algorithms, other data structures
need to be used for larger distances.
For shorter distances, a map based GridNode storage may be slow as
it requires lots of levels of indirection, which is bad for things like
cache locality, and an array based storage may be faster.
This commit does:
1. remove the vector<vector<vector<T>>> based GridNodes storage that
is allocated and initialized in advance and for the whole
possible area.
2. Add a vector<T> based GridNodes storage that is allocated and
initialized in advance for the whole possible area.
3. Add a map<P,T> based GridNodes storage whose elements are
allocated and initialized, when the path search code
demands it.
4. Add code to decide between approach 2 and 3,
based on the length of the path.
5. Remove the unused "surfaces" member of the PathGridnode class.
Setting this isn't as easy anymore for the
map based GridNodes storage.
est31 [Thu, 31 Mar 2016 23:52:17 +0000 (01:52 +0200)]
Pathfinder: Fix style
* Fix naming style for methods and classes:
Use camelCase for methods and PascalCase for classes as
code style demands it. And use sneak_case for methods that
are not member of a class.
* Replace "* " with " *" for Pointers
* Same for references
* Put function body opening braces on new line
* Other misc minor non functional style improvements
est31 [Thu, 31 Mar 2016 23:20:34 +0000 (01:20 +0200)]
Move pathfinder classes to cpp file
There is no need to put them into the header, they are solely used
inside the pathfinder.
Another advantage of this change is that only the pathfinder.cpp has
to be compiled if PATHFINDER_DEBUG gets defined or undefined, not
all files including the .h.
This commit moves the pathfinder classes to the cpp file without
modifications.
Also, the PATHFINDER_DEBUG macro gets moved to the cpp file and
the PATHFINDER_CALC_TIME macro gets moved to a plce where it
actually does work.
The old Ant build system has been deprecated for a while and new development is focused on Gradle.
I also removed a hardcoded string that lint caught and moved the patch files to a subdirectory.
I left the JNI files in the root directory.
Make logging use a fixed-length buffer to avoid race conditions.
Previously, race conditions occurred inside logging, that caused
segfaults because a thread was trying to use an old pointer that
was freed when the string was reallocated. Using a fixed-length buffer
avoids this, at the cost of cutting too long messages over seveal lines.
Biomes: Make dust fallback 'ignore' to fix y = 63 lighting
The shadow bug at y = 63 was caused by dark air being placed as dust,
when the biome dust was unspecified it was falling back to 'air'
In dustTopNodes only dust == 'ignore' will disable dust placement
Mgv7: Combine mountain terrain generation with base terrain generation
Previous mountain terrain generation was by necessity placing
stone in air, this was removing air from any overgenerated
structures such as tunnels, dungeons and large caves
Moving it into the base terrain generation loop ensures that
only 'ignore' is replaced
generateRidgeTerrain: only return if node_max.Y < water_level - 16
Previously, if water level was set a few nodes above a mapchunk
border the river channel was only partially excavated
falling: walk 4 additional diagonally down directions.
This seems very little cost and matches the old behavior more
closely. This will cause some more falling nodes to get added
to falling clusters. With the efficiency of the algorithm, this
really doesn't do much damage.
Mainmenu: Still support favorites if send_pre_v25_init is disabled
@SmallJoker has noted a bug that servers from the (local) main menu
favorites list can't be opened.
This commit fixes the bug by disabling any main menu based protocol
checks for servers from the favorite list.
Also, it fixes a second bug that happens when a server from the
public serverlist doesn't send its supported protocol versions,
most likely because its running a minetest older than commit [1].
Then we have shown an error msg that the server has enforced
one specific protocol version. This was most likely not the case.
Of course, we can't do anything better than do an assumption on
the protocol versions if they are not known. That assumption
should however be closest to the most often occuring case as
possible.
@kilbith spotted correctly that I had accidentally removed the
"soft" edging on the minimap overlay by converting it from RGBA
to Indexed, which killed the transparent pixels on the edging.
Auke Kok [Wed, 30 Mar 2016 14:50:10 +0000 (07:50 -0700)]
Convert nodeupdate to non-recursive
This took me a while to figure out. We no longer visit all 9 block
around and with the touched node, but instead visit adjacent plus
self. We then walk -non- recursively through all neigbors and if
they cause a nodeupdate, we just keep walking until it ends. On
the way back we prune the tail.
I've tested this with 8000+ sand nodes. Video result is here:
https://youtu.be/liKKgLefhFQ
Took ~ 10 seconds to process and return to normal.
Callbacks registered by register_on_player_hpchange are ordered so that non-modifiers are called after modifiers are called. Credit to @TeTpaAka who mentioned this previously-undocumented feature in #3799.
Minimap: "North" indicator arrow for circle minimap
Related: #3730
This adds a simple, and small "North" indicator to the circular
minimap. The indicator is in a classical triangle-like arrow with a
little bit of shading to accentuate the shape and give it a little
bit depth. The indicator is stuck exactly at the edge as far outwards
as possible, and is not too intrusive but still easy enough to spot.
Rui914 [Thu, 31 Mar 2016 08:26:39 +0000 (17:26 +0900)]
Mainmenu: Refactor tab UI code
- Use local variables for tabs in place of globals
- Merge together if statements where possible
- Replace manual table searching code with indexof where possible
David Knapp [Wed, 6 Apr 2016 06:53:00 +0000 (23:53 -0700)]
Fix ncurses lookup on Arch Linux
Arch Linux doesn't put it's ncursesw includes inside an ncursesw
directory. This script ends up setting USE_CURSES as true, but
doesn't pick up any of the headers.
Mapgen: Optimise cave noises and tunnel excavation
Instead of doing nothing at node_max.Y + 1 use 1-down
overgeneration for tunnel generation and noisemaps
Move some old unused code in mgv7 to end of file
It was caused by player not moving because fall was prevented, but their
velocity still increasing, causing fatal fall damage when world was
finally loaded. This commit fixes it by setting player velocity to zero
when the world around them is not loaded.
est31 [Mon, 28 Mar 2016 12:39:43 +0000 (14:39 +0200)]
mg_schematic: fix leak in lua API, and small cleanup
* Fix leak like behaviour if you load multiple schematics in a loop.
* Cleanup check in for, fixing theoretical out of bounds read if
Schematic::deserializeFromMts reduced the number of elements
in m_nodenames. A != check may need an overflow of the counter
before it hits, if origsize is larger than m_nodenames.size().
* Fix function name passed to errorstream: it was wrong. Also use
__FUNCTION__ instead of manually using the method name at other
places in the function.
kwolekr [Wed, 30 Mar 2016 03:59:39 +0000 (23:59 -0400)]
Mapgen: Don't spread light of nodes outside the desired area
This fixes #3935, a regression from 0338c2e.
An 'optimization' was performed where an index for the VoxelManip being
operated on was mistakenly used for bounds checking within the incorrect
VoxelArea, namely, the area wherein light should be spread.
tenplus1 [Sun, 27 Mar 2016 20:09:35 +0000 (21:09 +0100)]
stop falling.lua error
2016-03-27 15:47:01: ERROR[Main]: ServerError: Lua: Runtime error from mod '*builtin*' in callback luaentity_Step(): Node name is not set or is not a string!
2016-03-27 15:47:01: ERROR[Main]: stack traceback:
2016-03-27 15:47:01: ERROR[Main]: [C]: in function 'add_node'
2016-03-27 15:47:01: ERROR[Main]: /usr/share/minetest/builtin/game/falling.lua:96: in function </usr/share/minetest/builtin/game/falling.lua:43>