2 #include <dragonstd/array.h>
3 #include <dragonstd/list.h>
4 #include <dragonstd/tree.h>
10 #include "common/facedir.h"
11 #include "server/server_node.h"
12 #include "server/server_terrain.h"
13 #include "server/tree_physics.h"
14 #include "server/voxel_depth_search.h"
26 } CheckTreeSearchNodeMeta;
28 static inline bool is_tree_with_root(TerrainNode *node)
32 return ((TreeData *) node->data)->has_root;
39 static int cmp_chunk(const TerrainChunk *chunk, const v3s32 *pos)
41 return v3s32_cmp(&chunk->pos, pos);
44 static void unlock_chunk(TerrainChunk *chunk)
46 pthread_rwlock_unlock(&chunk->lock);
49 static void init_search_node(DepthSearchNode *search_node, CheckTreeArg *arg)
51 // first, get chunk position and offset
52 v3s32 chunkp = terrain_chunkp(search_node->pos);
54 // check for chunk in cache
55 TerrainChunk *chunk = tree_get(&arg->chunks, &chunkp, &cmp_chunk, NULL);
57 // if not found in cache, get it from server_terrain and lock it
59 chunk = terrain_get_chunk(server_terrain, chunkp, CHUNK_MODE_PASSIVE);
61 // check if chunk is unloaded
63 // if chunk is unloaded, don't remove the tree, it might have a connection to ground
64 search_node->type = DEPTH_SEARCH_TARGET;
70 // try to obtain the chunk lock
71 int lock_err = pthread_rwlock_wrlock(&chunk->lock);
73 // a deadlock might occur because of the order the chunks are locked
74 if (lock_err == EDEADLK) {
75 // notify caller deadlock has occured
78 // finish search directly
79 search_node->type = DEPTH_SEARCH_TARGET;
85 // assert that no different error has occured while trying to obtain the lock
86 assert(lock_err == 0);
88 // insert chunk into cache
89 tree_add(&arg->chunks, &chunk->pos, chunk, &cmp_chunk, NULL);
93 v3s32 offset = terrain_offset(search_node->pos);
95 // type coersion for easier access
96 TerrainChunkMeta *meta = chunk->extra;
98 // pointer to node and generation stage
99 TerrainNode *node = &chunk->data[offset.x][offset.y][offset.z];
100 u32 *tgs = &meta->tgsb.raw.nodes[offset.x][offset.y][offset.z];
102 // type coersion for easier access
103 TreeData *data = node->data;
105 // have we found terrain?
106 if (*tgs == STAGE_TERRAIN && node->type != NODE_AIR) {
107 // if we've reached the target, set search node type accordingly
108 search_node->type = DEPTH_SEARCH_TARGET;
109 } else if (is_tree_with_root(node) && v3s32_equals(arg->root, data->root)) {
110 // if node is part of our tree, continue search
111 search_node->type = DEPTH_SEARCH_PATH;
113 // allocate meta storage
114 CheckTreeSearchNodeMeta *search_meta = search_node->extra = malloc(sizeof *search_meta);
116 // store chunk, node and stage pointer for later
117 search_meta->chunk = chunk;
118 search_meta->node = node;
119 search_meta->tgs = tgs;
121 // otherwise, this is a roadblock
122 search_node->type = DEPTH_SEARCH_BLOCK;
126 static void free_search_node(DepthSearchNode *node)
134 static void destroy_search_node(DepthSearchNode *node, List *changed_chunks)
136 if (node->type == DEPTH_SEARCH_PATH && !(*node->success)) {
137 // this is a tree/leaves node without connection to ground
139 CheckTreeSearchNodeMeta *meta = node->extra;
141 // overwrite node and generation stage
142 *meta->node = server_node_create(NODE_AIR);
143 *meta->tgs = STAGE_PLAYER;
145 // flag chunk as changed
146 list_add(changed_chunks, meta->chunk, meta->chunk, &cmp_ref, NULL);
149 free_search_node(node);
153 Check whether all positions (that are part of the same tree) still are connected to the ground.
154 Destroy any tree parts without ground connection.
156 The advantage of grouping them together is that they can use the same search cache.
158 static bool check_tree(v3s32 root, Array *positions, Array *chunks)
161 // inform depth search callbacks about root of tree (to only match nodes that belong to it)
163 // output parameter to prevent deadlocks
164 arg.deadlock = false;
165 // cache chunks, to accelerate lookup and prevent locking them twice
166 tree_ini(&arg.chunks);
168 // add the chunks the starting points are in to the chunk cache
169 for (size_t i = 0; i < chunks->siz; i++) {
170 TerrainChunk *chunk = ((TerrainChunk **) chunks->ptr)[i];
171 tree_add(&arg.chunks, &chunk->pos, chunk, &cmp_chunk, NULL);
174 // nodes that have been visited
175 // serves as search cache and contains all tree nodes, to remove them if no ground found
179 // success means ground has been found
181 // true if ground has been found for all positions
182 bool success_all = true;
183 // individual buffer for each start position (required by depth search algo)
184 bool success_buf[positions->siz];
186 // iterate over start positions
187 for (size_t i = 0; i < positions->siz; i++) {
188 success_buf[i] = false;
190 // call depth search algorithm to collect positions and find ground
191 if (!voxel_depth_search(((v3s32 *) positions->ptr)[i], (void *) &init_search_node, &arg,
192 &success_buf[i], &visit))
195 // immediately stop if there was a deadlock
200 if (success_all || arg.deadlock) {
201 // ground has been found for all parts (or a deadlock was detected)
203 // if ground has been found for all, there is no need to pass more complex callback
204 tree_clr(&visit, &free_search_node, NULL, NULL, 0);
206 // unlock grabbed chunks
207 tree_clr(&arg.chunks, &unlock_chunk, NULL, NULL, 0);
209 // return false if there was a deadlock - caller will reinitiate search
210 return !arg.deadlock;
213 // keep track of changed chunks
215 list_ini(&changed_chunks);
217 // some or all positions have no connection to ground, pass callback to destroy nodes without
218 tree_clr(&visit, &destroy_search_node, &changed_chunks, NULL, 0);
220 // now, unlock all the chunks (before sending some of them)
221 tree_clr(&arg.chunks, &unlock_chunk, NULL, NULL, 0);
223 // send changed chunks
224 server_terrain_lock_and_send_chunks(&changed_chunks);
231 To be called after a node has been removed.
232 For all neigbors that are part of a tree, check whether the tree now still has connection to
233 the ground, destroy tree (partly) otherwise.
235 - select neighbor nodes that are leaves or wood
236 - in every iteration, select only the nodes that belong to the same tree (have the same root)
237 - in every iteration, keep the chunks the selected nodes belong to locked
238 - skip nodes that don't match the currently selected root, process them in a later iteration
240 void tree_physics_check(v3s32 center)
242 // remember directions that have been processed
243 bool dirs[6] = {false};
249 // the first node that has a root will initialize these variables
250 bool selected_root = false;
253 // remember selected positions and their associated locked chunks
254 Array positions, chunks;
255 array_ini(&positions, sizeof(v3s32), 5);
256 array_ini(&chunks, sizeof(TerrainChunk *), 5);
258 // remember indices of positions selected in this iteration
259 bool selected[6] = {false};
261 for (int i = 0; i < 6; i++) {
262 // we already processed this direction
266 // this may change back to false if we skip
269 // facedir contains offsets to neighbor nodes
270 v3s32 pos = v3s32_add(center, facedir[i]);
274 TerrainChunk *chunk = terrain_get_chunk_nodep(server_terrain, pos, &offset, CHUNK_MODE_PASSIVE);
278 // check if chunk is already locked
279 bool locked_before = array_idx(&chunks, &chunk) != -1;
281 // lock if not locked
282 // fixme: a deadlock can happen here lol
284 assert(pthread_rwlock_wrlock(&chunk->lock) == 0);
286 // now that chunk is locked, actually get node
287 TerrainNode *node = &chunk->data[offset.x][offset.y][offset.z];
289 // check whether we're dealing with a tree node that has a root
290 if (is_tree_with_root(node)) {
291 // type coersion for easier access
292 TreeData *data = node->data;
294 // select root and initialize variables
295 if (!selected_root) {
296 selected_root = true;
300 // check whether root matches
301 if (v3s32_equals(root, data->root)) {
303 array_apd(&positions, &pos);
305 // remember chunk - unless it's already on the list
307 array_apd(&chunks, &chunk);
309 // remember index was selected
312 // don't run rest of loop body to not unlock chunk
315 // if it doesn't match selected root, mark as skipped
321 // only unlock if it wasn't locked before
323 pthread_rwlock_unlock(&chunk->lock);
328 if (!check_tree(root, &positions, &chunks)) {
329 // a return value of false means a deadlock occured (should be very rare)
330 printf("[verbose] tree_physics detected deadlock (this not an issue, but should not happen frequently)\n");
332 // sleep for 50ms to hopefully resolve the conflict
333 nanosleep(&(struct timespec) {0, 50e6}, NULL);
335 // invalidate faces that were selected in this iteration
336 for (int i = 0; i < 6; i++)
342 array_clr(&positions);
346 // repeat until all directions have been processed