/* * $RCSfile$ $Revision$ $State$ */ /**************************************************************************** * File: librtmp_local.h * * * * Copyright 1993 by Loral Advanced Distributed Simulation, Inc. * * * * Loral Advanced Distributed Simulation, Inc. * * 10 Moulton Street * * Cambridge, MA 02238 * * 617-873-1850 * * * * This software was developed by Loral under U. S. Government contracts* * and may be reproduced by or for the U. S. Government pursuant to * * the copyright license under the clause at DFARS 252.227-7013 * * (OCT 1988). * * * * Contents: Private header file for libroutemap * * Created: Tue Nov 9 1993 * * Author: jesmith * * Remarks: * * * ****************************************************************************/ #include "libroutemap.h" #include "planner.h" #define SAME(x,y) ((abs((x)-(y)) < 0.0001)) /* Definition for quadtree constructed during corridor finding */ #define ROUTEMAP_NUM_QUADS (1+4+16+64+256) #define ROUTEMAP_QUAD_DEPTH 5 /* The maximum number of connections to other corridors per corridor. * This must be at least 4 to fully connect the graph. We make it somewhat * larger to preplan shortcuts. */ #define ROUTEMAP_MAX_CONNECT 12 typedef struct routemap_pseg { float64 x, y; float64 dx, dy; } ROUTEMAP_PSEG; typedef struct routemap_corridor { /* Information about the corridor */ ROUTEMAP_PSEG seg; float64 length; float32 begin_index; float32 end_index; /* Temporary information used for pruning during search */ float64 cost; int32 disallowed; /* Obstacles attached to the corridor */ struct routemap_obstacle *begin_obst; struct routemap_obstacle *end_obst; /* Connections to other corridors */ int32 n_connect; struct routemap_corridor *connect[ROUTEMAP_MAX_CONNECT]; /* Clump into which this corridor falls */ struct routemap_clump *clump; struct routemap_corridor *prev; struct routemap_corridor *next; } ROUTEMAP_CORRIDOR; typedef struct routemap_plan_step { /* A step in the plan has *EITHER* a corridor or a location */ float64 x, y, width; ROUTEMAP_CORRIDOR *corridor; uint8 is_free; uint8 failed; struct routemap_plan_step *next; } ROUTEMAP_PLAN_STEP; typedef struct routemap_obstacle { /* Obstacle type */ uint16 type_mask; /* Flag indicating a linear (non-polygonal) obstacle */ unsigned linear : 1; /* Flags indicating whether the first/last vertices of a linear * obstacle might be open (not connected to any other obstacles). */ unsigned start_open : 1; unsigned end_open : 1; /* Flag indicating that this obstacle isn't really there, but * instead was created to get a corridor. */ unsigned not_real : 1; /* Gross-level information about the obstacle */ int32 center_x, center_y; int16 width, height; /* Vertices of the obstacle (polygons have one repeated) */ int32 n_verts; struct routemap_obstacle_vertex { /* The vertex and the vector to the next vertex */ ROUTEMAP_PSEG seg; float64 len_sq; } *verts; /* Corridors attached to this obstacle */ int32 n_corridors; ROUTEMAP_CORRIDOR **corridors; /* Linear obstacles with blocked ends have references to other * obstacles which can be more easily avoided. */ struct routemap_bypass { /* There are two bypasses per side for each obstacle */ struct routemap_obstacle *positive_start; struct routemap_obstacle *positive_end; struct routemap_obstacle *negative_start; struct routemap_obstacle *negative_end; /* Flags indicating that bypasses is connected to obstacle * start/start or end/end. */ unsigned positive_start_flip : 1; unsigned positive_end_flip : 1; unsigned negative_start_flip : 1; unsigned negative_end_flip : 1; } *bypass; /* Clump into which this obstacle falls */ struct routemap_clump *clump; /* Next obstacle in the quad */ struct routemap_obstacle *next_quad; /* Next obstacle in the master list */ struct routemap_obstacle *next; } ROUTEMAP_OBSTACLE; typedef struct routemap_clump { int32 n_obstacles; ROUTEMAP_OBSTACLE **obstacles; int32 n_corridors; ROUTEMAP_CORRIDOR **corridors; struct routemap_clump *next; } ROUTEMAP_CLUMP; typedef struct routemap_vert_list { struct routemap_vert_list *next; point *p; /* USED TO NOT BE A POINTER */ } ROUTEMAP_VERT_LIST; typedef struct routemap_bucket_list { struct routemap_bucket_list *next; point *p; } ROUTEMAP_BUCKET_LIST; typedef struct routemap_hash_table { int32 poly_mod; int32 bot_y,bot_x; int32 num_buckets; int32 x_div,y_div; ROUTEMAP_BUCKET_LIST **bucket; } ROUTEMAP_HASH_TABLE; typedef struct routemap_poly_list { struct routemap_poly_list *next; int32 poly_num; int32 poly_width; /* which width generated this polygon */ } ROUTEMAP_POLY_LIST; typedef struct routemap_square { ROUTEMAP_VERT_LIST *local_points; ROUTEMAP_POLY_LIST *local_polys; } ROUTEMAP_SQUARE; struct routemap_boundary { int32 n_verts; struct routemap_obstacle_vertex *verts; }; struct routemap_data { /* Terrain database */ CTDB *ctdb; /* Maximum difference between an actual vertex and our approximation */ float64 max_error; /* Maximum length of a corridor */ float64 max_corridor; /* Maximum rate of expansion & contraction */ float64 max_grow; float64 max_shrink; /* Minimum distance over which a unit may change its width */ float64 min_expansion_dist; /* Max distance to tree canopy entrance/exit, add a point if necessary */ float64 add_point_distance; /* add a point to tree canopy entrance/exit only if the width at the * entrace/exit is too small */ float64 add_point_width_ratio; /***** stuff I added - Oded *************/ /* weighting of path if it's a narrow one */ float32 distance_weighting; /* the minimum width required for a tank, and the desired width for a formation of tanks */ float32 small_width, large_width; int32 num_x_squares, num_y_squares; /* dimensions of local partioning */ ROUTEMAP_SQUARE **squares; float32 x_min,x_max,y_min,y_max; /* size of area to partition */ float32 size_square_x, size_square_y; /* size of individual square */ int32 num_glue_points; /* number of additional points on the grid */ int32 num_widths; /* number of different widths to expand obstacles by */ float32 *extra_width; /* an array of size num_widths which contains the expansion sizes */ float32 *weight_for_width; /* an array of size num_widths which says how much to weigh an edge between points of width i. Normally, weight_for_width[0]=1.0, and the rest are progressively smaller since it's better to be on an edge of higher width */ /****************************************/ /* Soil type information */ struct { int32 num_soils; int32 *soils; } lakes, boulders; /* Planning constraints. */ ROUTEMAP_BOUNDARY_PTR left_bound; ROUTEMAP_BOUNDARY_PTR right_bound; int32 num_clists; ROUTEMAP_CORRIDOR_LIST **clists; /* Information about the quad nodes */ struct routemap_quad_info { int32 cx, cy; int32 parent; int32 children[4]; int32 num_descendants; ROUTEMAP_OBSTACLE *obstacles; } quad_info[ROUTEMAP_NUM_QUADS]; ROUTEMAP_OBSTACLE *obstacles; ROUTEMAP_CORRIDOR *corridors; ROUTEMAP_CLUMP *clumps; }; extern int32 routemap_negative_side(); extern int32 routemap_outside_boundaries(); extern int32 routemap_wrong_side(); extern ROUTEMAP_PLAN_STEP *routemap_new_step(); extern void routemap_free_step(); extern void routemap_free_steps(); extern void routemap_check_leaks(); extern ROUTEMAP_PLAN_STEP *routemap_link_corridors(); extern float64 routemap_corr_index(); extern float64 routemap_seg_seg_dist_sq(); extern int32 routemap_select_quad(); extern void my_preplan(); /* VERY PRIVATE VARIABLES AND FUNCTIONS! DO NOT USE OUTSIDE! */ extern void routemap_add_adj_list(); extern void routemap_add_edges_locally(); extern void routemap_add_to_global_graph(); extern void routemap_add_to_local_squares(); extern void routemap_associate_polys_with_cells(); extern void routemap_build_heap(); extern void routemap_build_local_visib_graphs(); extern void routemap_calculate_bounding_box(); extern void routemap_create_map_and_initial_visib_graph(); extern int32 * routemap_dijkstra(); extern float32 routemap_distance(); extern float32 routemap_distance_squared(); extern float32 routemap_dot_product(); extern void routemap_dump_graph(); extern void routemap_dump_head(); extern int32 routemap_equal_sign(); extern void routemap_get_intersections_with_grid(); extern void routemap_hash_init(); extern void routemap_hash_insert(); extern point * routemap_hash_find(); extern void routemap_heap_decrease_key(); extern heap_element routemap_heap_extract_min(); extern void routemap_heapify(); extern void routemap_insert_point_to_local_list(); extern void routemap_insert_point_to_ordered_list(); extern int32 routemap_is_line_tangent_to_poly(); extern int32 routemap_line_hits_poly(); extern int32 routemap_line_hits_local_poly(); extern int32 routemap_line_intersection(); extern int32 routemap_my_between(); extern void routemap_my_strcpy(); extern int32 routemap_my_total_between(); extern int32 routemap_point_in_any_poly(); extern int32 routemap_point_in_bounding_box(); extern int32 routemap_point_in_rect(); extern int32 routemap_point_in_poly(); extern int32 routemap_rectangle_overlap(); extern void routemap_remove_edge(); extern int32 routemap_repeated_vertex(); extern int32 routemap_return_index_of_vertex(); extern int32 routemap_same_point(); extern void routemap_smooth_plan(); extern void routemap_sort_polygon(); extern int32 routemap_tangent_line(); extern int32 routemap_total_within_segment(); extern void routemap_update_graph_locally(); extern float32 routemap_weighted_distance(); extern int32 routemap_within_segment(); extern int32 routemap_which_vertex(); extern void my_preplan(); extern map * routemap_my_no_go_map; extern graph * routemap_my_visib_graph; extern int32 avg_search_time, avg_update_time; extern int32 avg_search_time_sqd, avg_update_time_sqd;