From a1c2de7f75e8eb39906bb11e357ad75e61c80cf5 Mon Sep 17 00:00:00 2001 From: Cloudwalk Date: Wed, 10 Jun 2020 11:56:38 -0400 Subject: [PATCH] Implement EXT_NODEGRAPH --- makefile.inc | 1 + nodegraph.c | 1238 ++++++++++++++++++++++++++++++++++++++++++++++++++ nodegraph.h | 50 ++ svvm_cmds.c | 424 ++++++++++++++++- 4 files changed, 1688 insertions(+), 25 deletions(-) create mode 100644 nodegraph.c create mode 100644 nodegraph.h diff --git a/makefile.inc b/makefile.inc index 6d9826fb..2abd83d3 100644 --- a/makefile.inc +++ b/makefile.inc @@ -130,6 +130,7 @@ OBJ_COMMON= \ model_shared.o \ model_sprite.o \ netconn.o \ + nodegraph.o \ palette.o \ polygon.o \ portals.o \ diff --git a/nodegraph.c b/nodegraph.c new file mode 100644 index 00000000..ee8372aa --- /dev/null +++ b/nodegraph.c @@ -0,0 +1,1238 @@ +#include "quakedef.h" +#include "nodegraph.h" + +// ============================================================================ +#define NODEGRAPH_NODES_COUNT_LIMIT 4096 +#define NODEGRAPH_QUERY_ENTRIES_LIMIT NODEGRAPH_NODES_COUNT_LIMIT +#define NODEGRAPH_QUERIES_COUNT_LIMIT 128 + +// ============================================================================ +#define NODEGRAPH_NODES_DATA_LENGTH (NODEGRAPH_NODES_COUNT_LIMIT * 3) +#define NODEGRAPH_LINKS_DATA_LENGTH (NODEGRAPH_NODES_COUNT_LIMIT * NODEGRAPH_NODES_COUNT_LIMIT / 8) + +// ============================================================================ +#define GRAPH_MATRIX_ELEMENT_INDEX(i, j) GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, NODEGRAPH_NODES_COUNT_LIMIT) +#define GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, size) (i * size + j) + +// ============================================================================ +typedef struct nodegraph_s +{ + vec_t nodes[NODEGRAPH_NODES_DATA_LENGTH]; + char links[NODEGRAPH_LINKS_DATA_LENGTH]; + int nodes_count; +} +nodegraph_t; + +typedef struct nodegraph_query_s +{ + short entries[NODEGRAPH_QUERY_ENTRIES_LIMIT]; + short graphid; + short entries_count; +} +nodegraph_query_t; + +typedef struct nodegraph_floyd_warshall_matrix_s +{ + short indexes[NODEGRAPH_NODES_COUNT_LIMIT * NODEGRAPH_NODES_COUNT_LIMIT]; +} +nodegraph_floyd_warshall_matrix_t; + +// ============================================================================ +typedef struct nodegraph_query_sort_data_s +{ + short queryid; + vec3_t point; +} +nodegraph_query_sort_data_t; + +// ============================================================================ +static nodegraph_t g_nodegraph_set[NODEGRAPH_GRAPHSET_SIZE_LIMIT]; +static nodegraph_query_t g_nodegraph_queries[NODEGRAPH_QUERIES_COUNT_LIMIT]; +static nodegraph_floyd_warshall_matrix_t g_nodegraph_floyd_warshall_matrices[NODEGRAPH_GRAPHSET_SIZE_LIMIT]; + +// ============================================================================ +static nodegraph_query_sort_data_t g_nodegraph_query_sort_data; + +// ============================================================================ +static int nodegraph_query_sort_function(const void *left, const void *right) +{ + const short queryid = g_nodegraph_query_sort_data.queryid; + + const short leftid = *(const short *)left; + const short rightid = *(const short *)right; + + vec3_t pointleft; + vec3_t pointright; + + float distanceleft; + float distanceright; + + nodegraph_query_t *query; + nodegraph_t *nodegraph; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + Con_DPrintf("%s, queryid is out of bounds: %d\n", __FUNCTION__, queryid); + return 0; + } + + query = &g_nodegraph_queries[queryid]; + nodegraph = &g_nodegraph_set[query->graphid]; + + if (leftid < 0 || leftid >= nodegraph->nodes_count) + { + Con_DPrintf("%s, leftid is out of bounds: %d\n", __FUNCTION__, leftid); + return 0; + } + + if (rightid < 0 || rightid >= nodegraph->nodes_count) + { + Con_DPrintf("%s, rightid is out of bounds: %d\n", __FUNCTION__, rightid); + return 0; + } + + nodegraph_graph_get_node(query->graphid, leftid, pointleft); + nodegraph_graph_get_node(query->graphid, rightid, pointright); + + distanceleft = VectorDistance(pointleft, g_nodegraph_query_sort_data.point); + distanceright = VectorDistance(pointright, g_nodegraph_query_sort_data.point); + + return distanceleft - distanceright; +} + +// ============================================================================ +static qboolean nodegraph_graph_queries_clear(short graphid) +{ + short i; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + nodegraph_query_t *query = &g_nodegraph_queries[i]; + + if (query->graphid == graphid) + { + nodegraph_query_release(i); + } + } + + return true; +} + +// ============================================================================ +static qboolean nodegraph_graph_rebuild_floyd_warshall_matrices(void) +{ + short graphid, i, j, k; + + float *floyd_matrix_measures = (float *)Mem_Alloc(tempmempool, NODEGRAPH_NODES_COUNT_LIMIT * NODEGRAPH_NODES_COUNT_LIMIT * sizeof(float)); + + if (!floyd_matrix_measures) + { + return false; + } + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + nodegraph_floyd_warshall_matrix_t *floyd_matrix = &g_nodegraph_floyd_warshall_matrices[graphid]; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = 16777216.0f; + floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = -1; + + if (nodegraph_graph_does_link_exist(graphid, i, j)) + { + vec3_t nodefrom; + vec3_t nodeto; + + float distance; + + nodegraph_graph_get_node(graphid, i, nodefrom); + nodegraph_graph_get_node(graphid, j, nodeto); + + distance = VectorDistance(nodefrom, nodeto); + + floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = distance; + floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = j; + } + } + } + + for (i = 0; i < nodegraph->nodes_count; i++) + { + floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, i)] = 0.0f; + floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, i)] = i; + } + + for (k = 0; k < nodegraph->nodes_count; k++) + { + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + float distance = floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, k)] + floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(k, j)]; + + if (floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] > distance) + { + floyd_matrix_measures[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = distance; + floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, k)]; + } + } + } + } + } + + Mem_Free(floyd_matrix_measures); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graphset_clear(void) +{ + short i; + + for (i = 0; i < NODEGRAPH_GRAPHSET_SIZE_LIMIT; i++) + { + nodegraph_graph_clear(i); + } + + return true; +} + +// ============================================================================ +qboolean nodegraph_graphset_load(void) +{ + char vabuf[1024]; + char *graphset_data; + + qboolean nodegraph_graphset_has_been_loaded; + + nodegraph_graphset_has_been_loaded = (graphset_data = (char *)FS_LoadFile(va(vabuf, sizeof(vabuf), "%s.qng", sv.worldnamenoextension), tempmempool, true, NULL)) != NULL; + + if (nodegraph_graphset_has_been_loaded) + { + short graphid; + short graphset_nodes_count[NODEGRAPH_GRAPHSET_SIZE_LIMIT]; + + size_t offset, length; + + Con_Printf("Loaded %s.qng\n", sv.worldnamenoextension); + + nodegraph_graphset_clear(); + + offset = 0; + + length = sizeof(short) * NODEGRAPH_GRAPHSET_SIZE_LIMIT; + memcpy((void *)graphset_nodes_count, (const void *)(graphset_data + offset), length); + + offset += length; + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + nodegraph->nodes_count = graphset_nodes_count[graphid]; + + if (nodegraph->nodes_count > 0) + { + short i, j; + char *nodegraph_links_sub_matrix; + + length = sizeof(float) * 3 * nodegraph->nodes_count; + memcpy((void *)nodegraph->nodes, (const void *)(graphset_data + offset), length); + + offset += length; + + nodegraph_links_sub_matrix = graphset_data + offset; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + int entryindex = GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, nodegraph->nodes_count); + qboolean does_link_exist = ((nodegraph_links_sub_matrix[entryindex / 8] & (1 << (entryindex % 8))) != 0); + + if (does_link_exist) + { + nodegraph_graph_add_link(graphid, i, j); + } + } + } + + length = (nodegraph->nodes_count * nodegraph->nodes_count - 1) / 8 + 1; + offset += length; + } + } + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + nodegraph_floyd_warshall_matrix_t *floyd_matrix = &g_nodegraph_floyd_warshall_matrices[graphid]; + + short i, j; + short *floyd_sub_matrix_indexes = (short *)(graphset_data + offset); + + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, j)] = floyd_sub_matrix_indexes[GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, nodegraph->nodes_count)]; + } + } + + offset += sizeof(short) * nodegraph->nodes_count * nodegraph->nodes_count; + } + + Mem_Free(graphset_data); + + return true; + } + + return false; +} + +// ============================================================================ +qboolean nodegraph_graphset_save(void) +{ + char vabuf[1024]; + + char *graphset_data; + size_t graphset_data_size; + + qboolean nodegraph_graphset_has_been_saved; + + short graphid; + short graphset_nodes_count[NODEGRAPH_GRAPHSET_SIZE_LIMIT]; + + size_t offset, length; + + nodegraph_graph_rebuild_floyd_warshall_matrices(); + + graphset_data_size = sizeof(short) * NODEGRAPH_GRAPHSET_SIZE_LIMIT + sizeof(g_nodegraph_set) + sizeof(g_nodegraph_floyd_warshall_matrices); + graphset_data = (char *)Mem_Alloc(tempmempool, graphset_data_size); + + if (!graphset_data) + { + return false; + } + + memset((void *)graphset_data, 0, graphset_data_size); + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + graphset_nodes_count[graphid] = nodegraph->nodes_count; + } + + offset = 0; + + length = sizeof(short) * NODEGRAPH_GRAPHSET_SIZE_LIMIT; + memcpy((void *)(graphset_data + offset), (const void *)graphset_nodes_count, length); + + offset += length; + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + + if (nodegraph->nodes_count > 0) + { + short i, j; + char *nodegraph_links_sub_matrix; + + length = sizeof(float) * 3 * nodegraph->nodes_count; + memcpy((void *)(graphset_data + offset), (const void *)nodegraph->nodes, length); + + offset += length; + + nodegraph_links_sub_matrix = graphset_data + offset; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + if (nodegraph_graph_does_link_exist(graphid, i, j)) + { + int entryindex = GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, nodegraph->nodes_count); + nodegraph_links_sub_matrix[entryindex / 8] |= 1 << (entryindex % 8); + } + } + } + + length = (nodegraph->nodes_count * nodegraph->nodes_count - 1) / 8 + 1; + offset += length; + } + } + + for (graphid = 0; graphid < NODEGRAPH_GRAPHSET_SIZE_LIMIT; graphid++) + { + nodegraph_t *nodegraph = &g_nodegraph_set[graphid]; + nodegraph_floyd_warshall_matrix_t *floyd_matrix = &g_nodegraph_floyd_warshall_matrices[graphid]; + + short i, j; + short *floyd_sub_matrix_indexes = (short *)(graphset_data + offset); + + for (i = 0; i < nodegraph->nodes_count; i++) + { + for (j = 0; j < nodegraph->nodes_count; j++) + { + floyd_sub_matrix_indexes[GRAPH_MATRIX_ELEMENT_INDEX_SIZED(i, j, nodegraph->nodes_count)] = floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(i, j)]; + } + } + + offset += sizeof(short) * nodegraph->nodes_count * nodegraph->nodes_count; + } + + graphset_data_size = offset; + + nodegraph_graphset_has_been_saved = FS_WriteFile(va(vabuf, sizeof(vabuf), "%s.qng", sv.worldnamenoextension), (const void *)graphset_data, (fs_offset_t)graphset_data_size); + + Mem_Free(graphset_data); + + if (nodegraph_graphset_has_been_saved) + { + Con_Printf("Saved %s.qng\n", sv.worldnamenoextension); + } + + return nodegraph_graphset_has_been_saved; +} + +// ============================================================================ +qboolean nodegraph_graph_clear(short graphid) +{ + nodegraph_t *nodegraph; + nodegraph_floyd_warshall_matrix_t *floyd_matrix; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + memset((void *)nodegraph, 0, sizeof(nodegraph_t)); + + nodegraph_graph_queries_clear(graphid); + + floyd_matrix = &g_nodegraph_floyd_warshall_matrices[graphid]; + memset((void *)floyd_matrix, 0, sizeof(nodegraph_floyd_warshall_matrix_t)); + + return true; +} + +// ============================================================================ +short nodegraph_graph_nodes_count(short graphid) +{ + nodegraph_t *nodegraph; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + return nodegraph->nodes_count; +} + +// ============================================================================ +qboolean nodegraph_graph_add_node(short graphid, const vec3_t node) +{ + nodegraph_t *nodegraph; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodegraph->nodes_count >= NODEGRAPH_NODES_COUNT_LIMIT) + { + Con_DPrintf("%s, the number of nodes exceeds the limit: %d\n", __FUNCTION__, NODEGRAPH_NODES_COUNT_LIMIT); + return false; + } + + VectorCopy(node, &nodegraph->nodes[nodegraph->nodes_count * 3]); + nodegraph->nodes_count++; + + nodegraph_graph_queries_clear(graphid); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_remove_node(short graphid, short nodeid) +{ + nodegraph_t *nodegraph; + + short i, j; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeid < 0 || nodeid >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeid is out of bounds: %d\n", __FUNCTION__, nodeid); + return false; + } + + for (i = nodeid; i < nodegraph->nodes_count - 1; i++) + { + VectorCopy(&nodegraph->nodes[(i + 1) * 3], &nodegraph->nodes[i * 3]); + + for (j = 0; j < nodegraph->nodes_count; j++) + { + nodegraph_graph_does_link_exist(graphid, i + 1, j) ? nodegraph_graph_add_link(graphid, i, j) : nodegraph_graph_remove_link(graphid, i, j); + nodegraph_graph_does_link_exist(graphid, j, i + 1) ? nodegraph_graph_add_link(graphid, j, i) : nodegraph_graph_remove_link(graphid, j, i); + } + } + + VectorSet(&nodegraph->nodes[(nodegraph->nodes_count - 1) * 3], 0.0f, 0.0f, 0.0f); + nodegraph->nodes_count--; + + nodegraph_graph_queries_clear(graphid); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_is_node_valid(short graphid, short nodeid) +{ + nodegraph_t *nodegraph; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeid < 0 || nodeid >= nodegraph->nodes_count) + { + return false; + } + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_get_node(short graphid, short nodeid, vec3_t outnode) +{ + nodegraph_t *nodegraph; + + VectorSet(outnode, NAN, NAN, NAN); + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeid < 0 || nodeid >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeid is out of bounds: %d\n", __FUNCTION__, nodeid); + return false; + } + + VectorCopy(&nodegraph->nodes[nodeid * 3], outnode); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_add_link(short graphid, short nodeidfrom, short nodeidto) +{ + nodegraph_t *nodegraph; + + int entryindex; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeidfrom < 0 || nodeidfrom >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidfrom is out of bounds: %d\n", __FUNCTION__, nodeidfrom); + return false; + } + + if (nodeidto < 0 || nodeidto >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidto is out of bounds: %d\n", __FUNCTION__, nodeidto); + return false; + } + + entryindex = GRAPH_MATRIX_ELEMENT_INDEX(nodeidfrom, nodeidto); + nodegraph->links[entryindex / 8] |= 1 << (entryindex % 8); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_remove_link(short graphid, short nodeidfrom, short nodeidto) +{ + nodegraph_t *nodegraph; + + int entryindex; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeidfrom < 0 || nodeidfrom >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidfrom is out of bounds: %d\n", __FUNCTION__, nodeidfrom); + return false; + } + + if (nodeidto < 0 || nodeidto >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidto is out of bounds: %d\n", __FUNCTION__, nodeidto); + return false; + } + + entryindex = GRAPH_MATRIX_ELEMENT_INDEX(nodeidfrom, nodeidto); + nodegraph->links[entryindex / 8] &= ~(1 << (entryindex % 8)); + + return true; +} + +// ============================================================================ +qboolean nodegraph_graph_does_link_exist(short graphid, short nodeidfrom, short nodeidto) +{ + nodegraph_t *nodegraph; + + int entryindex; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return false; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeidfrom < 0 || nodeidfrom >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidfrom is out of bounds: %d\n", __FUNCTION__, nodeidfrom); + return false; + } + + if (nodeidto < 0 || nodeidto >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidto is out of bounds: %d\n", __FUNCTION__, nodeidto); + return false; + } + + entryindex = GRAPH_MATRIX_ELEMENT_INDEX(nodeidfrom, nodeidto); + + return ((nodegraph->links[entryindex / 8] & (1 << (entryindex % 8))) != 0); +} + +// ============================================================================ +short nodegraph_graph_find_nearest_nodeid(short graphid, const vec3_t position) +{ + nodegraph_t *nodegraph; + + short i, nodeid; + float distance, shortestdistance; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + nodeid = -1; + shortestdistance = 16777216.0f; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + distance = VectorDistance(&nodegraph->nodes[i * 3], position); + + if (shortestdistance > distance) + { + nodeid = i; + shortestdistance = distance; + } + } + + return nodeid; +} + +// ============================================================================ +short nodegraph_graph_query_path(short graphid, short nodeidfrom, short nodeidto) +{ + nodegraph_t *nodegraph; + nodegraph_floyd_warshall_matrix_t *floyd_matrix; + + short i, queryid; + nodegraph_query_t *query; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + floyd_matrix = &g_nodegraph_floyd_warshall_matrices[graphid]; + + if (nodeidfrom < 0 || nodeidfrom >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidfrom is out of bounds: %d\n", __FUNCTION__, nodeidfrom); + return -1; + } + + if (nodeidto < 0 || nodeidto >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeidto is out of bounds: %d\n", __FUNCTION__, nodeidto); + return -1; + } + + queryid = -1; + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + if (!nodegraph_query_is_valid(i)) + { + queryid = i; + break; + } + } + + if (queryid != -1) + { + query = &g_nodegraph_queries[queryid]; + + query->graphid = graphid; + + if (floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(nodeidfrom, nodeidto)] != -1) + { + query->entries[query->entries_count] = nodeidfrom; + query->entries_count++; + + while (nodeidfrom != nodeidto) + { + nodeidfrom = floyd_matrix->indexes[GRAPH_MATRIX_ELEMENT_INDEX(nodeidfrom, nodeidto)]; + + query->entries[query->entries_count] = nodeidfrom; + query->entries_count++; + + if (query->entries_count >= NODEGRAPH_QUERY_ENTRIES_LIMIT) + { + break; + } + } + } + + if (query->entries_count == 0) + { + nodegraph_query_release(queryid); + queryid = -1; + } + } + + return queryid; +} + +// ============================================================================ +short nodegraph_graph_query_nodes_linked(short graphid, short nodeid) +{ + nodegraph_t *nodegraph; + + short i, queryid; + nodegraph_query_t *query; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + if (nodeid < 0 || nodeid >= nodegraph->nodes_count) + { + Con_DPrintf("%s, nodeid is out of bounds: %d\n", __FUNCTION__, nodeid); + return -1; + } + + queryid = -1; + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + if (!nodegraph_query_is_valid(i)) + { + queryid = i; + break; + } + } + + if (queryid != -1) + { + query = &g_nodegraph_queries[queryid]; + + query->graphid = graphid; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + if (nodegraph_graph_does_link_exist(graphid, nodeid, i)) + { + query->entries[query->entries_count] = i; + query->entries_count++; + } + + if (query->entries_count >= NODEGRAPH_QUERY_ENTRIES_LIMIT) + { + break; + } + } + + if (query->entries_count == 0) + { + nodegraph_query_release(queryid); + queryid = -1; + } + else + { + g_nodegraph_query_sort_data.queryid = queryid; + nodegraph_graph_get_node(graphid, nodeid, g_nodegraph_query_sort_data.point); + + qsort(query->entries, query->entries_count, sizeof(short), nodegraph_query_sort_function); + } + + } + + return queryid; +} + +// ============================================================================ +short nodegraph_graph_query_nodes_in_radius(short graphid, const vec3_t position, float radius) +{ + nodegraph_t *nodegraph; + + vec3_t node; + short i, queryid; + nodegraph_query_t *query; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + queryid = -1; + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + if (!nodegraph_query_is_valid(i)) + { + queryid = i; + break; + } + } + + if (queryid != -1) + { + query = &g_nodegraph_queries[queryid]; + + query->graphid = graphid; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + nodegraph_graph_get_node(graphid, i, node); + + if (VectorDistance(position, node) <= radius) + { + query->entries[query->entries_count] = i; + query->entries_count++; + } + + if (query->entries_count >= NODEGRAPH_QUERY_ENTRIES_LIMIT) + { + break; + } + } + + if (query->entries_count == 0) + { + nodegraph_query_release(queryid); + queryid = -1; + } + else + { + g_nodegraph_query_sort_data.queryid = queryid; + VectorCopy(position, g_nodegraph_query_sort_data.point); + + qsort(query->entries, query->entries_count, sizeof(short), nodegraph_query_sort_function); + } + } + + return queryid; +} + +// ============================================================================ +qboolean nodegraph_query_release(short queryid) +{ + nodegraph_query_t *query; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + Con_DPrintf("%s, queryid is out of bounds: %d\n", __FUNCTION__, queryid); + return false; + } + + query = &g_nodegraph_queries[queryid]; + memset((void *)query, 0, sizeof(nodegraph_query_t)); + + return true; +} + +// ============================================================================ +short nodegraph_query_entries_count(short queryid) +{ + nodegraph_query_t *query; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + Con_DPrintf("%s, queryid is out of bounds: %d\n", __FUNCTION__, queryid); + return -1; + } + + query = &g_nodegraph_queries[queryid]; + + return query->entries_count; +} + +// ============================================================================ +qboolean nodegraph_query_is_valid(short queryid) +{ + nodegraph_query_t *query; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + return false; + } + + query = &g_nodegraph_queries[queryid]; + + return query->entries_count > 0; +} + +// ============================================================================ +short nodegraph_query_get_graphid(short queryid) +{ + nodegraph_query_t *query; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + Con_DPrintf("%s, queryid is out of bounds: %d\n", __FUNCTION__, queryid); + return -1; + } + + query = &g_nodegraph_queries[queryid]; + + return query->graphid; +} + +// ============================================================================ +short nodegraph_query_get_nodeid(short queryid, short entryid) +{ + nodegraph_query_t *query; + + if (queryid < 0 || queryid >= NODEGRAPH_QUERIES_COUNT_LIMIT) + { + Con_DPrintf("%s, queryid is out of bounds: %d\n", __FUNCTION__, queryid); + return -1; + } + + query = &g_nodegraph_queries[queryid]; + + if (entryid < 0 || entryid >= query->entries_count) + { + Con_DPrintf("%s, entryid is out of bounds: %d\n", __FUNCTION__, entryid); + return -1; + } + + if (query->graphid < 0 || query->graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, query->graphid); + return -1; + } + + return query->entries[entryid]; +} + +// ============================================================================ +qboolean nodegraph_moveprobe_fly(const vec3_t nodefrom, const vec3_t nodeto, const vec3_t mins, const vec3_t maxs, short type) +{ + int contents = SUPERCONTENTS_SOLID | SUPERCONTENTS_MONSTERCLIP | SUPERCONTENTS_BOTCLIP; + + vec3_t from, to; + trace_t trace; + + qboolean connected; + + if (type == NODEGRAPH_MOVEPROBE_TYPE_FLY_AIR || type == NODEGRAPH_MOVEPROBE_TYPE_FLY_WATER) + { + contents |= SUPERCONTENTS_LIQUIDSMASK; + } + + VectorCopy(nodefrom, from); + from[2] -= mins[2]; + + VectorCopy(nodeto, to); + to[2] -= mins[2]; + + trace = SV_TraceBox(from, mins, maxs, to, MOVE_NOMONSTERS, NULL, contents, 0, 0, 0.0f); + + connected = trace.fraction == 1.0; + + if (type == NODEGRAPH_MOVEPROBE_TYPE_FLY_AIR) + { + connected = connected && (SV_PointSuperContents(from) & (SUPERCONTENTS_LIQUIDSMASK)) == 0; + connected = connected && (SV_PointSuperContents(to) & (SUPERCONTENTS_LIQUIDSMASK)) == 0; + } + + if (type == NODEGRAPH_MOVEPROBE_TYPE_FLY_WATER) + { + connected = connected && (SV_PointSuperContents(from) & (SUPERCONTENTS_LIQUIDSMASK)) != 0; + connected = connected && (SV_PointSuperContents(to) & (SUPERCONTENTS_LIQUIDSMASK)) != 0; + } + + return connected; +} + +// ============================================================================ +qboolean nodegraph_moveprobe_walk(const vec3_t nodefrom, const vec3_t nodeto, const vec3_t mins, const vec3_t maxs, float stepheight, float dropheight) +{ + int contents = SUPERCONTENTS_SOLID | SUPERCONTENTS_MONSTERCLIP | SUPERCONTENTS_BOTCLIP; + + float distance, walked; + float tracestep = max(1.0f, min(maxs[0] - mins[0], maxs[1] - mins[1]) / 2.0f); + + vec3_t from, to, direction, destination; + + qboolean connected = false; + + VectorSubtract(nodeto, nodefrom, direction); + distance = VectorLength(direction); + + if (distance <= 0.015625f) + { + return true; + } + + direction[2] = 0.0f; + VectorNormalize(direction); + + VectorCopy(nodefrom, from); + from[2] -= mins[2]; + + VectorCopy(nodeto, destination); + destination[2] -= mins[2]; + + walked = 0.0f; + + while (walked <= distance) + { + trace_t trace; + + VectorMA(from, tracestep, direction, from); + from[2] += stepheight; + + VectorCopy(from, to); + to[2] -= stepheight + dropheight + 0.5f; + + trace = SV_TraceBox(from, mins, maxs, to, MOVE_NOMONSTERS, NULL, contents, 0, 0, 0.0f); + + if (trace.startsolid || trace.fraction == 1.0) + { + break; + } + + if (VectorDistance(trace.endpos, destination) <= tracestep) + { + connected = true; + break; + } + + VectorCopy(trace.endpos, from); + + walked += tracestep; + } + + return connected; +} + +// ============================================================================ +short nodegraph_graph_query_nodes_in_radius_fly_reachable(short graphid, const vec3_t position, float radius, const vec3_t mins, const vec3_t maxs, short type) +{ + nodegraph_t *nodegraph; + + vec3_t node; + short i, queryid; + nodegraph_query_t *query; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + queryid = -1; + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + if (!nodegraph_query_is_valid(i)) + { + queryid = i; + break; + } + } + + if (queryid != -1) + { + query = &g_nodegraph_queries[queryid]; + + query->graphid = graphid; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + nodegraph_graph_get_node(graphid, i, node); + + if (VectorDistance(position, node) <= radius) + { + if (nodegraph_moveprobe_fly(position, node, mins, maxs, type)) + { + query->entries[query->entries_count] = i; + query->entries_count++; + } + } + + if (query->entries_count >= NODEGRAPH_QUERY_ENTRIES_LIMIT) + { + break; + } + } + + if (query->entries_count == 0) + { + nodegraph_query_release(queryid); + queryid = -1; + } + else + { + g_nodegraph_query_sort_data.queryid = queryid; + VectorCopy(position, g_nodegraph_query_sort_data.point); + + qsort(query->entries, query->entries_count, sizeof(short), nodegraph_query_sort_function); + } + } + + return queryid; +} + +// ============================================================================ +short nodegraph_graph_query_nodes_in_radius_walk_reachable(short graphid, const vec3_t position, float radius, const vec3_t mins, const vec3_t maxs, float stepheight, float dropheight) +{ + nodegraph_t *nodegraph; + + vec3_t node; + short i, queryid; + nodegraph_query_t *query; + + if (graphid < 0 || graphid >= NODEGRAPH_GRAPHSET_SIZE_LIMIT) + { + Con_DPrintf("%s, graphid is out of bounds: %d\n", __FUNCTION__, graphid); + return -1; + } + + nodegraph = &g_nodegraph_set[graphid]; + + queryid = -1; + + for (i = 0; i < NODEGRAPH_QUERIES_COUNT_LIMIT; i++) + { + if (!nodegraph_query_is_valid(i)) + { + queryid = i; + break; + } + } + + if (queryid != -1) + { + query = &g_nodegraph_queries[queryid]; + + query->graphid = graphid; + + for (i = 0; i < nodegraph->nodes_count; i++) + { + nodegraph_graph_get_node(graphid, i, node); + + if (VectorDistance(position, node) <= radius) + { + if (nodegraph_moveprobe_walk(position, node, mins, maxs, stepheight, dropheight)) + { + query->entries[query->entries_count] = i; + query->entries_count++; + } + } + + if (query->entries_count >= NODEGRAPH_QUERY_ENTRIES_LIMIT) + { + break; + } + } + + if (query->entries_count == 0) + { + nodegraph_query_release(queryid); + queryid = -1; + } + else + { + g_nodegraph_query_sort_data.queryid = queryid; + VectorCopy(position, g_nodegraph_query_sort_data.point); + + qsort(query->entries, query->entries_count, sizeof(short), nodegraph_query_sort_function); + } + } + + return queryid; +} diff --git a/nodegraph.h b/nodegraph.h new file mode 100644 index 00000000..818634a4 --- /dev/null +++ b/nodegraph.h @@ -0,0 +1,50 @@ +#ifndef NODEGRAPH_H +#define NODEGRAPH_H + +// ============================================================================ +#define NODEGRAPH_GRAPHSET_SIZE_LIMIT 8 + +// ============================================================================ +#define NODEGRAPH_MOVEPROBE_TYPE_FLY_WHATEVER 0 +#define NODEGRAPH_MOVEPROBE_TYPE_FLY_AIR 1 +#define NODEGRAPH_MOVEPROBE_TYPE_FLY_WATER 2 + +// ============================================================================ +qboolean nodegraph_graphset_clear(void); + +qboolean nodegraph_graphset_load(void); +qboolean nodegraph_graphset_save(void); + +qboolean nodegraph_graph_clear(short graphid); + +short nodegraph_graph_nodes_count(short graphid); + +qboolean nodegraph_graph_add_node(short graphid, const vec3_t node); +qboolean nodegraph_graph_remove_node(short graphid, short nodeid); +qboolean nodegraph_graph_is_node_valid(short graphid, short nodeid); + +qboolean nodegraph_graph_get_node(short graphid, short nodeid, vec3_t outnode); + +qboolean nodegraph_graph_add_link(short graphid, short nodeidfrom, short nodeidto); +qboolean nodegraph_graph_remove_link(short graphid, short nodeidfrom, short nodeidto); +qboolean nodegraph_graph_does_link_exist(short graphid, short nodeidfrom, short nodeidto); + +short nodegraph_graph_find_nearest_nodeid(short graphid, const vec3_t position); + +short nodegraph_graph_query_path(short graphid, short nodeidfrom, short nodeidto); +short nodegraph_graph_query_nodes_linked(short graphid, short nodeid); +short nodegraph_graph_query_nodes_in_radius(short graphid, const vec3_t position, float radius); + +qboolean nodegraph_query_release(short queryid); +short nodegraph_query_entries_count(short queryid); +qboolean nodegraph_query_is_valid(short queryid); +short nodegraph_query_get_graphid(short queryid); +short nodegraph_query_get_nodeid(short queryid, short entryid); + +qboolean nodegraph_moveprobe_fly(const vec3_t nodefrom, const vec3_t nodeto, const vec3_t mins, const vec3_t maxs, short type); +qboolean nodegraph_moveprobe_walk(const vec3_t nodefrom, const vec3_t nodeto, const vec3_t mins, const vec3_t maxs, float stepheight, float dropheight); + +short nodegraph_graph_query_nodes_in_radius_fly_reachable(short graphid, const vec3_t position, float radius, const vec3_t mins, const vec3_t maxs, short type); +short nodegraph_graph_query_nodes_in_radius_walk_reachable(short graphid, const vec3_t position, float radius, const vec3_t mins, const vec3_t maxs, float stepheight, float dropheight); + +#endif // NODEGRAPH_H diff --git a/svvm_cmds.c b/svvm_cmds.c index 2ae68c1a..011bfcdf 100644 --- a/svvm_cmds.c +++ b/svvm_cmds.c @@ -2,6 +2,7 @@ #include "prvm_cmds.h" #include "jpeg.h" +#include "nodegraph.h" //============================================================================ // Server @@ -228,6 +229,7 @@ const char *vm_sv_extensions = "TW_SV_STEPCONTROL " "ZQ_PAUSE " "EXT_WRATH " +"EXT_NODEGRAPH " "DP_RM_CLIPGROUP " //"EXT_CSQC " // not ready yet ; @@ -3258,7 +3260,379 @@ static void VM_SV_frameduration(prvm_prog_t *prog) PRVM_G_FLOAT(OFS_RETURN) = model->animscenes[framenum].framecount / model->animscenes[framenum].framerate; } +// #700 float() nodegraph_graphset_clear (EXT_NODEGRAPH) +static void VM_nodegraph_graphset_clear(prvm_prog_t *prog) +{ + VM_SAFEPARMCOUNT(0, VM_nodegraph_graphset_clear); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graphset_clear(); +} + +// #701 float() nodegraph_graphset_load (EXT_NODEGRAPH) +static void VM_nodegraph_graphset_load(prvm_prog_t *prog) +{ + VM_SAFEPARMCOUNT(0, VM_nodegraph_graphset_load); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graphset_load(); +} + +// #702 float() nodegraph_graphset_save (EXT_NODEGRAPH) +static void VM_nodegraph_graphset_save(prvm_prog_t *prog) +{ + VM_SAFEPARMCOUNT(0, VM_nodegraph_graphset_save); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graphset_save(); +} + +// #703 float(float graphid) nodegraph_graph_clear (EXT_NODEGRAPH) +static void VM_nodegraph_graph_clear(prvm_prog_t *prog) +{ + short graphid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_graph_clear); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_clear(graphid); +} + +// #704 float(float graphid) nodegraph_graph_nodes_count (EXT_NODEGRAPH) +static void VM_nodegraph_graph_nodes_count(prvm_prog_t *prog) +{ + short graphid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_graph_nodes_count); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_nodes_count(graphid); +} + +// #705 float(float graphid, vector node) nodegraph_graph_add_node (EXT_NODEGRAPH) +static void VM_nodegraph_graph_add_node(prvm_prog_t *prog) +{ + short graphid; + vec3_t node; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_add_node); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), node); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_add_node(graphid, node); +} + +// #706 float(float graphid, float nodeid) nodegraph_graph_remove_node (EXT_NODEGRAPH) +static void VM_nodegraph_graph_remove_node(prvm_prog_t *prog) +{ + short graphid; + short nodeid; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_remove_node); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeid = (short)PRVM_G_FLOAT(OFS_PARM1); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_remove_node(graphid, nodeid); +} + +// #707 float(float graphid, float nodeid) nodegraph_graph_is_node_valid (EXT_NODEGRAPH) +static void VM_nodegraph_graph_is_node_valid(prvm_prog_t *prog) +{ + short graphid; + short nodeid; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_is_node_valid); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeid = (short)PRVM_G_FLOAT(OFS_PARM1); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_is_node_valid(graphid, nodeid); +} + +// #708 vector(float graphid, float nodeid) nodegraph_graph_get_node (EXT_NODEGRAPH) +static void VM_nodegraph_graph_get_node(prvm_prog_t *prog) +{ + short graphid; + short nodeid; + vec3_t outnode; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_get_node); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeid = (short)PRVM_G_FLOAT(OFS_PARM1); + + nodegraph_graph_get_node(graphid, nodeid, outnode); + + VectorCopy(outnode, PRVM_G_VECTOR(OFS_RETURN)); +} + +// #709 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_add_link (EXT_NODEGRAPH) +static void VM_nodegraph_graph_add_link(prvm_prog_t *prog) +{ + short graphid; + short nodeidfrom; + short nodeidto; + + VM_SAFEPARMCOUNT(3, VM_nodegraph_graph_add_link); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeidfrom = (short)PRVM_G_FLOAT(OFS_PARM1); + nodeidto = (short)PRVM_G_FLOAT(OFS_PARM2); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_add_link(graphid, nodeidfrom, nodeidto); +} + +// #710 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_remove_link (EXT_NODEGRAPH) +static void VM_nodegraph_graph_remove_link(prvm_prog_t *prog) +{ + short graphid; + short nodeidfrom; + short nodeidto; + + VM_SAFEPARMCOUNT(3, VM_nodegraph_graph_remove_link); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeidfrom = (short)PRVM_G_FLOAT(OFS_PARM1); + nodeidto = (short)PRVM_G_FLOAT(OFS_PARM2); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_remove_link(graphid, nodeidfrom, nodeidto); +} +// #711 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_does_link_exist (EXT_NODEGRAPH) +static void VM_nodegraph_graph_does_link_exist(prvm_prog_t *prog) +{ + short graphid; + short nodeidfrom; + short nodeidto; + + VM_SAFEPARMCOUNT(3, VM_nodegraph_graph_does_link_exist); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeidfrom = (short)PRVM_G_FLOAT(OFS_PARM1); + nodeidto = (short)PRVM_G_FLOAT(OFS_PARM2); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_does_link_exist(graphid, nodeidfrom, nodeidto); +} + +// #712 float(float graphid, vector position) nodegraph_graph_find_nearest_nodeid (EXT_NODEGRAPH) +static void VM_nodegraph_graph_find_nearest_nodeid(prvm_prog_t *prog) +{ + short graphid; + vec3_t position; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_find_nearest_nodeid); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), position); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_find_nearest_nodeid(graphid, position); +} + +// #713 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_query_path (EXT_NODEGRAPH) +static void VM_nodegraph_graph_query_path(prvm_prog_t *prog) +{ + short graphid; + short nodeidfrom; + short nodeidto; + + VM_SAFEPARMCOUNT(3, VM_nodegraph_graph_query_path); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeidfrom = (short)PRVM_G_FLOAT(OFS_PARM1); + nodeidto = (short)PRVM_G_FLOAT(OFS_PARM2); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_query_path(graphid, nodeidfrom, nodeidto); +} + +// #714 float(float graphid, float nodeid) nodegraph_graph_query_nodes_linked (EXT_NODEGRAPH) +static void VM_nodegraph_graph_query_nodes_linked(prvm_prog_t *prog) +{ + short graphid; + short nodeid; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_graph_query_nodes_linked); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + nodeid = (short)PRVM_G_FLOAT(OFS_PARM1); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_query_nodes_linked(graphid, nodeid); +} + +// #715 float(float graphid, vector position, float radius) nodegraph_graph_query_nodes_in_radius (EXT_NODEGRAPH) +static void VM_nodegraph_graph_query_nodes_in_radius(prvm_prog_t *prog) +{ + short graphid; + vec3_t position; + float radius; + + VM_SAFEPARMCOUNT(3, VM_nodegraph_graph_query_nodes_in_radius); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), position); + radius = PRVM_G_FLOAT(OFS_PARM2); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_query_nodes_in_radius(graphid, position, radius); +} + +// #716 float(float queryid) nodegraph_query_release (EXT_NODEGRAPH) +static void VM_nodegraph_query_release(prvm_prog_t *prog) +{ + short queryid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_query_release); + + queryid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_query_release(queryid); +} + +// #717 float(float queryid) nodegraph_query_entries_count (EXT_NODEGRAPH) +static void VM_nodegraph_query_entries_count(prvm_prog_t *prog) +{ + short queryid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_query_entries_count); + + queryid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_query_entries_count(queryid); +} + +// #718 float(float queryid) nodegraph_query_is_valid (EXT_NODEGRAPH) +static void VM_nodegraph_query_is_valid(prvm_prog_t *prog) +{ + short queryid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_query_is_valid); + + queryid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_query_is_valid(queryid); +} + +// #719 float(float queryid) nodegraph_query_get_graphid (EXT_NODEGRAPH) +static void VM_nodegraph_query_get_graphid(prvm_prog_t *prog) +{ + short queryid; + + VM_SAFEPARMCOUNT(1, VM_nodegraph_query_get_graphid); + + queryid = (short)PRVM_G_FLOAT(OFS_PARM0); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_query_get_graphid(queryid); +} + +// #720 float(float queryid, float entryid) nodegraph_query_get_nodeid (EXT_NODEGRAPH) +static void VM_nodegraph_query_get_nodeid(prvm_prog_t *prog) +{ + short queryid; + short entryid; + + VM_SAFEPARMCOUNT(2, VM_nodegraph_query_get_nodeid); + + queryid = (short)PRVM_G_FLOAT(OFS_PARM0); + entryid = (short)PRVM_G_FLOAT(OFS_PARM1); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_query_get_nodeid(queryid, entryid); +} + +// #721 float(vector nodefrom, vector nodeto, vector mins, vector maxs, float type) nodegraph_moveprobe_fly (EXT_NODEGRAPH) +static void VM_nodegraph_moveprobe_fly(prvm_prog_t *prog) +{ + vec3_t nodefrom; + vec3_t nodeto; + vec3_t mins; + vec3_t maxs; + short type; + + VM_SAFEPARMCOUNT(5, VM_nodegraph_moveprobe_fly); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM0), nodefrom); + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), nodeto); + VectorCopy(PRVM_G_VECTOR(OFS_PARM2), mins); + VectorCopy(PRVM_G_VECTOR(OFS_PARM3), maxs); + + type = (short)PRVM_G_FLOAT(OFS_PARM4); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_moveprobe_fly(nodefrom, nodeto, mins, maxs, type); +} + +// #722 (vector nodefrom, vector nodeto, vector mins, vector maxs, float stepheight, float dropheight) nodegraph_moveprobe_walk (EXT_NODEGRAPH) +static void VM_nodegraph_moveprobe_walk(prvm_prog_t *prog) +{ + vec3_t nodefrom; + vec3_t nodeto; + vec3_t mins; + vec3_t maxs; + float stepheight; + float dropheight; + + VM_SAFEPARMCOUNT(6, VM_nodegraph_moveprobe_walk); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM0), nodefrom); + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), nodeto); + VectorCopy(PRVM_G_VECTOR(OFS_PARM2), mins); + VectorCopy(PRVM_G_VECTOR(OFS_PARM3), maxs); + + stepheight = PRVM_G_FLOAT(OFS_PARM4); + dropheight = PRVM_G_FLOAT(OFS_PARM5); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_moveprobe_walk(nodefrom, nodeto, mins, maxs, stepheight, dropheight); +} +// #723 float(float graphid, vector position, float radius, vector mins, vector maxs, float type) nodegraph_graph_query_nodes_in_radius_fly_reachable (EXT_NODEGRAPH) +static void VM_nodegraph_graph_query_nodes_in_radius_fly_reachable(prvm_prog_t *prog) +{ + short graphid; + vec3_t position; + float radius; + vec3_t mins; + vec3_t maxs; + short type; + + VM_SAFEPARMCOUNT(6, VM_nodegraph_graph_query_nodes_in_radius_fly_reachable); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), position); + + radius = PRVM_G_FLOAT(OFS_PARM2); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM3), mins); + VectorCopy(PRVM_G_VECTOR(OFS_PARM4), maxs); + + type = (short)PRVM_G_FLOAT(OFS_PARM5); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_query_nodes_in_radius_fly_reachable(graphid, position, radius, mins, maxs, type); +} + +// #724 float(float graphid, vector position, float radius, vector mins, vector maxs, float stepheight, float dropheight) nodegraph_graph_query_nodes_in_radius_walk_reachable (EXT_NODEGRAPH) +static void VM_nodegraph_graph_query_nodes_in_radius_walk_reachable(prvm_prog_t *prog) +{ + short graphid; + vec3_t position; + float radius; + vec3_t mins; + vec3_t maxs; + float stepheight; + float dropheight; + + VM_SAFEPARMCOUNT(7, VM_nodegraph_graph_query_nodes_in_radius_walk_reachable); + + graphid = (short)PRVM_G_FLOAT(OFS_PARM0); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM1), position); + + radius = PRVM_G_FLOAT(OFS_PARM2); + + VectorCopy(PRVM_G_VECTOR(OFS_PARM3), mins); + VectorCopy(PRVM_G_VECTOR(OFS_PARM4), maxs); + + stepheight = PRVM_G_FLOAT(OFS_PARM5); + dropheight = PRVM_G_FLOAT(OFS_PARM6); + + PRVM_G_FLOAT(OFS_RETURN) = (float)nodegraph_graph_query_nodes_in_radius_walk_reachable(graphid, position, radius, mins, maxs, stepheight, dropheight); +} prvm_builtin_t vm_sv_builtins[] = { NULL, // #0 NULL function (not callable) (QUAKE) VM_makevectors, // #1 void(vector ang) makevectors (QUAKE) @@ -3965,31 +4339,31 @@ NULL, // #696 NULL, // #697 NULL, // #698 NULL, // #699 -NULL, // #700 -NULL, // #701 -NULL, // #702 -NULL, // #703 -NULL, // #704 -NULL, // #705 -NULL, // #706 -NULL, // #707 -NULL, // #708 -NULL, // #709 -NULL, // #710 -NULL, // #711 -NULL, // #712 -NULL, // #713 -NULL, // #714 -NULL, // #715 -NULL, // #716 -NULL, // #717 -NULL, // #718 -NULL, // #719 -NULL, // #720 -NULL, // #721 -NULL, // #722 -NULL, // #723 -NULL, // #724 +VM_nodegraph_graphset_clear, // #700 float() nodegraph_graphset_clear (EXT_NODEGRAPH) +VM_nodegraph_graphset_load, // #701 float() nodegraph_graphset_load (EXT_NODEGRAPH) +VM_nodegraph_graphset_save, // #702 float() nodegraph_graphset_save (EXT_NODEGRAPH) +VM_nodegraph_graph_clear, // #703 float(float graphid) nodegraph_graph_clear (EXT_NODEGRAPH) +VM_nodegraph_graph_nodes_count, // #704 float(float graphid) nodegraph_graph_nodes_count (EXT_NODEGRAPH) +VM_nodegraph_graph_add_node, // #705 float(float graphid, vector node) nodegraph_graph_add_node (EXT_NODEGRAPH) +VM_nodegraph_graph_remove_node, // #706 float(float graphid, float nodeid) nodegraph_graph_remove_node (EXT_NODEGRAPH) +VM_nodegraph_graph_is_node_valid, // #707 float(float graphid, float nodeid) nodegraph_graph_is_node_valid (EXT_NODEGRAPH) +VM_nodegraph_graph_get_node, // #708 vector(float graphid, float nodeid) nodegraph_graph_get_node (EXT_NODEGRAPH) +VM_nodegraph_graph_add_link, // #709 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_add_link (EXT_NODEGRAPH) +VM_nodegraph_graph_remove_link, // #710 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_remove_link (EXT_NODEGRAPH) +VM_nodegraph_graph_does_link_exist, // #711 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_does_link_exist (EXT_NODEGRAPH) +VM_nodegraph_graph_find_nearest_nodeid, // #712 float(float graphid, vector position) nodegraph_graph_find_nearest_nodeid (EXT_NODEGRAPH) +VM_nodegraph_graph_query_path, // #713 float(float graphid, float nodeidfrom, float nodeidto) nodegraph_graph_query_path (EXT_NODEGRAPH) +VM_nodegraph_graph_query_nodes_linked, // #714 float(float graphid, float nodeid) nodegraph_graph_query_nodes_linked (EXT_NODEGRAPH) +VM_nodegraph_graph_query_nodes_in_radius, // #715 float(float graphid, vector position, float radius) nodegraph_graph_query_nodes_in_radius (EXT_NODEGRAPH) +VM_nodegraph_query_release, // #716 float(float queryid) nodegraph_query_release (EXT_NODEGRAPH) +VM_nodegraph_query_entries_count, // #717 float(float queryid) nodegraph_query_entries_count (EXT_NODEGRAPH) +VM_nodegraph_query_is_valid, // #718 float(float queryid) nodegraph_query_is_valid (EXT_NODEGRAPH) +VM_nodegraph_query_get_graphid, // #719 float(float queryid) nodegraph_query_get_graphid (EXT_NODEGRAPH) +VM_nodegraph_query_get_nodeid, // #720 float(float queryid, float entryid) nodegraph_query_get_nodeid (EXT_NODEGRAPH) +VM_nodegraph_moveprobe_fly, // #721 float(vector nodefrom, vector nodeto, vector mins, vector maxs, float type) nodegraph_moveprobe_fly (EXT_NODEGRAPH) +VM_nodegraph_moveprobe_walk, // #722 (vector nodefrom, vector nodeto, vector mins, vector maxs, float stepheight, float dropheight) nodegraph_moveprobe_walk (EXT_NODEGRAPH) +VM_nodegraph_graph_query_nodes_in_radius_fly_reachable, // #723 float(float graphid, vector position, float radius, vector mins, vector maxs, float type) nodegraph_graph_query_nodes_in_radius_fly_reachable (EXT_NODEGRAPH) +VM_nodegraph_graph_query_nodes_in_radius_walk_reachable, // #724 float(float graphid, vector position, float radius, vector mins, vector maxs, float stepheight, float dropheight) nodegraph_graph_query_nodes_in_radius_walk_reachable (EXT_NODEGRAPH) NULL, // #725 NULL, // #726 NULL, // #727 -- 2.39.2