… | |
… | |
121 | }; |
121 | }; |
122 | |
122 | |
123 | #define RP_TRAFFIC_DISTORTION 1 |
123 | #define RP_TRAFFIC_DISTORTION 1 |
124 | #define RP_TURN_RESTRICTION 2 |
124 | #define RP_TURN_RESTRICTION 2 |
125 | #define RP_TURN_RESTRICTION_RESOLVED 4 |
125 | #define RP_TURN_RESTRICTION_RESOLVED 4 |
|
|
126 | #define RP_TRAFFIC_LIGHT 8 |
|
|
127 | #define RP_TRAFFIC_LIGHT_RESOLVED 16 |
126 | |
128 | |
127 | /** |
129 | /** |
128 | * @brief A segment in the route graph or path |
130 | * @brief A segment in the route graph or path |
129 | * |
131 | * |
130 | * This is a segment in the route graph or path. A segment represents a driveable way. |
132 | * This is a segment in the route graph or path. A segment represents a driveable way. |
… | |
… | |
253 | struct vehicleprofile *vehicleprofile; /**< The vehicle profile */ |
255 | struct vehicleprofile *vehicleprofile; /**< The vehicle profile */ |
254 | struct callback *idle_cb; /**< Idle callback to process the graph */ |
256 | struct callback *idle_cb; /**< Idle callback to process the graph */ |
255 | struct callback *done_cb; /**< Callback when graph is done */ |
257 | struct callback *done_cb; /**< Callback when graph is done */ |
256 | struct event_idle *idle_ev; /**< The pointer to the idle event */ |
258 | struct event_idle *idle_ev; /**< The pointer to the idle event */ |
257 | struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */ |
259 | struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */ |
|
|
260 | // *ORIG* #define HASH_SIZE 8192 |
|
|
261 | // #define HASH_SIZE 65536 |
258 | #define HASH_SIZE 8192 |
262 | #define HASH_SIZE 16384 |
259 | struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */ |
263 | struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */ |
260 | }; |
264 | }; |
261 | |
265 | |
262 | #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1)) |
266 | #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1)) |
263 | |
267 | |
… | |
… | |
281 | GList *list; |
285 | GList *list; |
282 | } u; |
286 | } u; |
283 | }; |
287 | }; |
284 | |
288 | |
285 | static struct route_info * route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *c); |
289 | static struct route_info * route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *c); |
|
|
290 | static struct route_info * route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted); |
286 | static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c); |
291 | static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c); |
287 | static void route_graph_update(struct route *this, struct callback *cb, int async); |
292 | static void route_graph_update(struct route *this, struct callback *cb, int async); |
288 | static void route_graph_build_done(struct route_graph *rg, int cancel); |
293 | static void route_graph_build_done(struct route_graph *rg, int cancel); |
289 | static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile); |
294 | static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile); |
290 | static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile); |
295 | static void route_process_street_graph(struct route_graph *this, struct item *item, struct vehicleprofile *profile); |
… | |
… | |
703 | if (!this->path2) |
708 | if (!this->path2) |
704 | { |
709 | { |
705 | return 0; |
710 | return 0; |
706 | } |
711 | } |
707 | |
712 | |
|
|
713 | // this fixed a crash for large offroad start segments |
|
|
714 | if (!this->pos->street) |
|
|
715 | { |
|
|
716 | return 0; |
|
|
717 | } |
|
|
718 | |
708 | if (!item_is_equal(this->pos->street->item, dst->street->item)) |
719 | if (!item_is_equal(this->pos->street->item, dst->street->item)) |
709 | { |
720 | { |
710 | return 0; |
721 | return 0; |
711 | } |
722 | } |
712 | |
723 | |
713 | if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg)) |
724 | if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg)) |
714 | { // We would have to drive against the one-way road |
725 | { // We would have to drive against the one-way road |
715 | return 0; |
726 | return 0; |
716 | } |
727 | } |
|
|
728 | |
717 | if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos)) |
729 | if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos)) |
718 | { |
730 | { |
719 | return 0; |
731 | return 0; |
720 | } |
732 | } |
|
|
733 | |
721 | pro = route_projection(this); |
734 | pro = route_projection(this); |
722 | if (pro == projection_none) |
735 | if (pro == projection_none) |
|
|
736 | { |
723 | return 0; |
737 | return 0; |
|
|
738 | } |
724 | |
739 | |
725 | if (transform_distance(pro, &this->pos->c, &dst->lp) > this->destination_distance) |
740 | if (transform_distance(pro, &this->pos->c, &dst->lp) > this->destination_distance) |
726 | { |
741 | { |
727 | return 0; |
742 | return 0; |
728 | } |
743 | } |
729 | |
744 | |
730 | if (g_list_next(this->destinations)) |
745 | if (g_list_next(this->destinations)) |
|
|
746 | { |
731 | return 1; |
747 | return 1; |
|
|
748 | } |
732 | else |
749 | else |
|
|
750 | { |
733 | return 2; |
751 | return 2; |
|
|
752 | } |
734 | } |
753 | } |
735 | |
754 | |
736 | static struct route_info * |
755 | static struct route_info * |
737 | route_previous_destination(struct route *this) |
756 | route_previous_destination(struct route *this) |
738 | { |
757 | { |
… | |
… | |
747 | return l->data; |
766 | return l->data; |
748 | } |
767 | } |
749 | |
768 | |
750 | static void route_path_update_done(struct route *this, int new_graph) |
769 | static void route_path_update_done(struct route *this, int new_graph) |
751 | { |
770 | { |
752 | // dbg(0, "enter\n"); |
771 | //dbg(0, "enter\n"); |
753 | |
772 | |
754 | struct route_path *oldpath = this->path2; |
773 | struct route_path *oldpath = this->path2; |
755 | struct attr route_status; |
774 | struct attr route_status; |
756 | struct route_info *prev_dst; |
775 | struct route_info *prev_dst; |
757 | route_status.type = attr_route_status; |
776 | route_status.type = attr_route_status; |
|
|
777 | |
758 | if (this->path2 && (this->path2->in_use > 1)) |
778 | if (this->path2 && (this->path2->in_use > 1)) |
759 | { |
779 | { |
760 | this->path2->update_required = 1 + new_graph; |
780 | this->path2->update_required = 1 + new_graph; |
|
|
781 | //dbg(0,"return 001\n"); |
761 | return; |
782 | return; |
762 | } |
783 | } |
|
|
784 | |
763 | route_status.u.num = route_status_building_path; |
785 | route_status.u.num = route_status_building_path; |
764 | route_set_attr(this, &route_status); |
786 | route_set_attr(this, &route_status); |
765 | prev_dst = route_previous_destination(this); |
787 | prev_dst = route_previous_destination(this); |
|
|
788 | |
766 | if (this->link_path) |
789 | if (this->link_path) |
767 | { |
790 | { |
768 | this->path2 = route_path_new(this->graph, NULL, prev_dst, this->current_dst, this->vehicleprofile); |
791 | this->path2 = route_path_new(this->graph, NULL, prev_dst, this->current_dst, this->vehicleprofile); |
769 | if (this->path2) |
792 | if (this->path2) |
770 | this->path2->next = oldpath; |
793 | this->path2->next = oldpath; |
… | |
… | |
776 | { |
799 | { |
777 | this->path2->next = oldpath->next; |
800 | this->path2->next = oldpath->next; |
778 | route_path_destroy(oldpath, 0); |
801 | route_path_destroy(oldpath, 0); |
779 | } |
802 | } |
780 | } |
803 | } |
|
|
804 | |
781 | if (this->path2) |
805 | if (this->path2) |
782 | { |
806 | { |
783 | struct route_path_segment *seg = this->path2->path; |
807 | struct route_path_segment *seg = this->path2->path; |
784 | int path_time = 0, path_len = 0; |
808 | int path_time = 0, path_len = 0; |
785 | while (seg) |
809 | while (seg) |
… | |
… | |
806 | { |
830 | { |
807 | this->link_path = 1; |
831 | this->link_path = 1; |
808 | this->current_dst = prev_dst; |
832 | this->current_dst = prev_dst; |
809 | route_graph_reset(this->graph); |
833 | route_graph_reset(this->graph); |
810 | route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb); |
834 | route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, this->route_graph_flood_done_cb); |
|
|
835 | //dbg(0,"return 002\n"); |
811 | return; |
836 | return; |
812 | } |
837 | } |
813 | |
838 | |
814 | if (!new_graph && this->path2->updated) |
839 | if (!new_graph && this->path2->updated) |
815 | { |
840 | { |
… | |
… | |
820 | route_status.u.num = route_status_path_done_new; |
845 | route_status.u.num = route_status_path_done_new; |
821 | } |
846 | } |
822 | } |
847 | } |
823 | else |
848 | else |
824 | { |
849 | { |
825 | route_status.u.num = route_status_not_found; |
|
|
826 | // dbg(0, "try harder\n"); |
850 | // dbg(0, "try harder\n"); |
827 | // Try to rebuild the graph with smaller roads |
851 | // Try to rebuild the graph with smaller roads |
828 | if (this->try_harder == 0) |
852 | if (this->try_harder == 0) |
829 | { |
853 | { |
830 | this->try_harder = 1; |
854 | this->try_harder = 1; |
831 | route_graph_destroy(this->graph); |
855 | route_graph_destroy(this->graph); |
832 | this->graph = NULL; |
856 | this->graph = NULL; |
833 | route_path_update(this, 1, 1); |
857 | route_path_update(this, 1, 1); |
834 | } |
858 | } |
|
|
859 | else |
|
|
860 | { |
|
|
861 | route_status.u.num = route_status_not_found; |
|
|
862 | } |
835 | } |
863 | } |
836 | |
864 | |
837 | this->link_path = 0; |
865 | this->link_path = 0; |
838 | route_set_attr(this, &route_status); |
866 | route_set_attr(this, &route_status); |
|
|
867 | |
|
|
868 | //dbg(0,"leave\n"); |
839 | } |
869 | } |
840 | |
870 | |
841 | /** |
871 | /** |
842 | * @brief Updates the route graph and the route path if something changed with the route |
872 | * @brief Updates the route graph and the route path if something changed with the route |
843 | * |
873 | * |
… | |
… | |
849 | * |
879 | * |
850 | * @param this The route to update |
880 | * @param this The route to update |
851 | */ |
881 | */ |
852 | void route_path_update(struct route *this, int cancel, int async) |
882 | void route_path_update(struct route *this, int cancel, int async) |
853 | { |
883 | { |
854 | // dbg(0, "enter\n"); |
884 | //dbg(0, "enter\n"); |
855 | |
885 | |
856 | //dbg(1, "enter %d\n", cancel); |
886 | //dbg(1, "enter %d\n", cancel); |
857 | if (!this->pos || !this->destinations) |
887 | if (!this->pos || !this->destinations) |
858 | { |
888 | { |
859 | //dbg(1, "destroy\n"); |
889 | //dbg(0, "destroy\n"); |
860 | route_path_destroy(this->path2, 1); |
890 | route_path_destroy(this->path2, 1); |
861 | this->path2 = NULL; |
891 | this->path2 = NULL; |
862 | return; |
892 | return; |
863 | } |
893 | } |
|
|
894 | |
864 | if (cancel) |
895 | if (cancel) |
865 | { |
896 | { |
866 | route_graph_destroy(this->graph); |
897 | route_graph_destroy(this->graph); |
867 | this->graph = NULL; |
898 | this->graph = NULL; |
868 | } |
899 | } |
|
|
900 | |
869 | /* the graph is destroyed when setting the destination */ |
901 | /* the graph is destroyed when setting the destination */ |
870 | if (this->graph) |
902 | if (this->graph) |
871 | { |
903 | { |
872 | if (this->graph->busy) |
904 | if (this->graph->busy) |
873 | { |
905 | { |
874 | //dbg(1, "busy building graph\n"); |
906 | //dbg(0, "busy building graph\n"); |
875 | return; |
907 | return; |
876 | } |
908 | } |
877 | // we can try to update |
909 | // we can try to update |
878 | //dbg(1, "try update\n"); |
910 | //dbg(0, "try update\n"); |
879 | route_path_update_done(this, 0); |
911 | route_path_update_done(this, 0); |
880 | } |
912 | } |
881 | else |
913 | else |
882 | { |
914 | { |
883 | route_path_destroy(this->path2, 1); |
915 | route_path_destroy(this->path2, 1); |
884 | this->path2 = NULL; |
916 | this->path2 = NULL; |
885 | } |
917 | } |
|
|
918 | |
886 | if (!this->graph || !this->path2) |
919 | if (!this->graph || !this->path2) |
887 | { |
920 | { |
888 | //dbg(1, "rebuild graph\n"); |
921 | //dbg(0, "rebuild graph\n"); |
889 | if (!this->route_graph_flood_done_cb) |
922 | if (!this->route_graph_flood_done_cb) |
890 | { |
923 | { |
891 | this->route_graph_flood_done_cb = callback_new_2(callback_cast(route_path_update_done), this, (long) 1); |
924 | this->route_graph_flood_done_cb = callback_new_2(callback_cast(route_path_update_done), this, (long) 1); |
892 | callback_add_names(this->route_graph_flood_done_cb, "route_path_update", "route_path_update_done"); |
925 | callback_add_names(this->route_graph_flood_done_cb, "route_path_update", "route_path_update_done"); |
893 | } |
926 | } |
894 | //dbg(1, "route_graph_update\n"); |
927 | //dbg(0, "route_graph_update\n"); |
895 | route_graph_update(this, this->route_graph_flood_done_cb, async); |
928 | route_graph_update(this, this->route_graph_flood_done_cb, async); |
896 | } |
929 | } |
|
|
930 | |
|
|
931 | //dbg(0,"leave\n"); |
897 | } |
932 | } |
898 | |
933 | |
899 | /** |
934 | /** |
900 | * @brief This will calculate all the distances stored in a route_info |
935 | * @brief This will calculate all the distances stored in a route_info |
901 | * |
936 | * |
… | |
… | |
923 | } |
958 | } |
924 | else |
959 | else |
925 | { |
960 | { |
926 | ri->percent = 50; |
961 | ri->percent = 50; |
927 | } |
962 | } |
|
|
963 | |
|
|
964 | //dbg(0,"len extra=%d\n", ri->lenextra); |
928 | } |
965 | } |
929 | |
966 | |
930 | /** |
967 | /** |
931 | * @brief This sets the current position of the route passed |
968 | * @brief This sets the current position of the route passed |
932 | * |
969 | * |
… | |
… | |
936 | * @param this The route to set the position of |
973 | * @param this The route to set the position of |
937 | * @param pos Coordinates to set as position |
974 | * @param pos Coordinates to set as position |
938 | */ |
975 | */ |
939 | void route_set_position(struct route *this, struct pcoord *pos) |
976 | void route_set_position(struct route *this, struct pcoord *pos) |
940 | { |
977 | { |
941 | // dbg(0, "enter\n"); |
978 | //dbg(0, "enter\n"); |
942 | |
979 | |
943 | if (this->pos) |
980 | if (this->pos) |
|
|
981 | { |
944 | route_info_free(this->pos); |
982 | route_info_free(this->pos); |
|
|
983 | } |
945 | |
984 | |
946 | this->pos = NULL; |
985 | this->pos = NULL; |
947 | this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos); |
986 | this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos); |
948 | |
987 | |
|
|
988 | //dbg(0,"this->pos=%p\n", this->pos); |
|
|
989 | |
|
|
990 | // try harder |
|
|
991 | if (this->pos == NULL) |
|
|
992 | { |
|
|
993 | this->pos = route_find_nearest_street_harder(this->vehicleprofile, this->ms, pos, 5000); |
|
|
994 | //dbg(0,"this->pos=%p\n", this->pos); |
|
|
995 | } |
|
|
996 | |
949 | // If there is no nearest street, bail out. |
997 | // If there is no nearest street, bail out. |
950 | if (!this->pos) |
998 | if (!this->pos) |
|
|
999 | { |
|
|
1000 | //dbg(0,"this->pos=%p\n", this->pos); |
|
|
1001 | //dbg(0,"return 001\n"); |
951 | return; |
1002 | return; |
|
|
1003 | } |
|
|
1004 | |
|
|
1005 | //dbg(0, "1: x y: %i %i\n", pos->x, pos->y); |
|
|
1006 | //dbg(0, "2: x y: %i %i\n", this->pos->c.x, this->pos->c.y); |
|
|
1007 | //dbg(0, "3: x y: %i %i\n", this->pos->lp.x, this->pos->lp.y); |
|
|
1008 | |
952 | |
1009 | |
953 | this->pos->street_direction = 0; |
1010 | this->pos->street_direction = 0; |
954 | //dbg(1, "this->pos=%p\n", this->pos); |
1011 | //dbg(1, "this->pos=%p\n", this->pos); |
955 | route_info_distances(this->pos, pos->pro); |
1012 | route_info_distances(this->pos, pos->pro); |
|
|
1013 | |
|
|
1014 | //dbg(0,"sp 002\n"); |
|
|
1015 | |
956 | route_path_update(this, 0, 1); |
1016 | route_path_update(this, 0, 1); |
|
|
1017 | |
|
|
1018 | //dbg(0,"leave\n"); |
957 | } |
1019 | } |
958 | |
1020 | |
959 | /** |
1021 | /** |
960 | * @brief Sets a route's current position based on coordinates from tracking |
1022 | * @brief Sets a route's current position based on coordinates from tracking |
961 | * |
1023 | * |
962 | * @param this The route to set the current position of |
1024 | * @param this The route to set the current position of |
963 | * @param tracking The tracking to get the coordinates from |
1025 | * @param tracking The tracking to get the coordinates from |
964 | */ |
1026 | */ |
965 | void route_set_position_from_tracking(struct route *this, struct tracking *tracking, enum projection pro) |
1027 | void route_set_position_from_tracking(struct route *this, struct tracking *tracking, enum projection pro) |
966 | { |
1028 | { |
967 | //// dbg(0, "enter\n"); |
1029 | //dbg(0, "enter\n"); |
968 | |
1030 | |
969 | struct coord *c; |
1031 | struct coord *c; |
970 | struct route_info *ret; |
1032 | struct route_info *ret; |
971 | struct street_data *sd; |
1033 | struct street_data *sd; |
972 | |
1034 | |
… | |
… | |
1078 | { |
1140 | { |
1079 | d = dy * sy; |
1141 | d = dy * sy; |
1080 | } |
1142 | } |
1081 | |
1143 | |
1082 | m = d * rel / 100 + abs; |
1144 | m = d * rel / 100 + abs; |
|
|
1145 | |
|
|
1146 | //dbg(0,"m=%d d=%d rel=%d abs=%d\n",m,d,rel,abs); |
|
|
1147 | |
1083 | sel->u.c_rect.lu.x -= m; |
1148 | sel->u.c_rect.lu.x -= m; |
1084 | sel->u.c_rect.rl.x += m; |
1149 | sel->u.c_rect.rl.x += m; |
1085 | sel->u.c_rect.lu.y += m; |
1150 | sel->u.c_rect.lu.y += m; |
1086 | sel->u.c_rect.rl.y -= m; |
1151 | sel->u.c_rect.rl.y -= m; |
1087 | sel->next = NULL; |
1152 | sel->next = NULL; |
… | |
… | |
1106 | struct map_selection *ret, *sel; |
1171 | struct map_selection *ret, *sel; |
1107 | int i; |
1172 | int i; |
1108 | struct coord_rect r; |
1173 | struct coord_rect r; |
1109 | |
1174 | |
1110 | if (!count) |
1175 | if (!count) |
|
|
1176 | { |
1111 | return NULL; |
1177 | return NULL; |
|
|
1178 | } |
|
|
1179 | |
1112 | r.lu = c[0]; |
1180 | r.lu = c[0]; |
1113 | r.rl = c[0]; |
1181 | r.rl = c[0]; |
1114 | for (i = 1; i < count; i++) |
1182 | for (i = 1; i < count; i++) |
1115 | { |
1183 | { |
|
|
1184 | // extend the rectangle to include all waypoints -> make 1 big rectangle |
1116 | coord_rect_extend(&r, &c[i]); |
1185 | coord_rect_extend(&r, &c[i]); |
1117 | } |
1186 | } |
|
|
1187 | |
|
|
1188 | // the route selection rectangle will be extened further, to find all routes (by 25%) |
|
|
1189 | #ifdef HAVE_API_ANDROID |
|
|
1190 | if (global_show_route_rectangles) |
|
|
1191 | { |
|
|
1192 | send_route_rect_to_java(r.lu.x, r.lu.y, r.rl.x, r.rl.y, -99); |
|
|
1193 | } |
|
|
1194 | #endif |
1118 | |
1195 | |
1119 | if (routing_mode == 0) |
1196 | if (routing_mode == 0) |
1120 | { |
1197 | { |
1121 | // normal highway routing |
1198 | // normal highway routing |
1122 | // sel=route_rect(4, &r.lu, &r.rl, 25, 0); |
1199 | // sel=route_rect(4, &r.lu, &r.rl, 25, 0); |
1123 | sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); |
1200 | sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); |
|
|
1201 | |
|
|
1202 | // the route selection rectangle will be extened further, to find all routes (by 25%) |
|
|
1203 | #ifdef HAVE_API_ANDROID |
|
|
1204 | if (global_show_route_rectangles) |
|
|
1205 | { |
|
|
1206 | send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 6 : 4); |
|
|
1207 | } |
|
|
1208 | #endif |
1124 | } |
1209 | } |
1125 | else if (routing_mode == 1) |
1210 | else if (routing_mode == 1) |
1126 | { |
1211 | { |
1127 | // normal roads routing (should take longer and use more roads) |
1212 | // normal roads routing (should take longer and use more roads) |
1128 | // sel=route_rect(6, &r.lu, &r.rl, 25, 0); |
1213 | // sel=route_rect(6, &r.lu, &r.rl, 25, 0); |
1129 | sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0); |
1214 | sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0); |
|
|
1215 | |
|
|
1216 | #ifdef HAVE_API_ANDROID |
|
|
1217 | if (global_show_route_rectangles) |
|
|
1218 | { |
|
|
1219 | send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 7 : 6); |
|
|
1220 | } |
|
|
1221 | #endif |
1130 | } |
1222 | } |
1131 | else |
1223 | else |
1132 | { |
1224 | { |
1133 | // DEFAULT setting |
1225 | // DEFAULT setting |
1134 | // normal highway routing |
1226 | // normal highway routing |
1135 | // sel=route_rect(4, &r.lu, &r.rl, 25, 0); |
1227 | // sel=route_rect(4, &r.lu, &r.rl, 25, 0); |
1136 | sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); |
1228 | sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0); |
|
|
1229 | |
|
|
1230 | // the route selection rectangle will be extened further, to find all routes (by 25%) |
|
|
1231 | #ifdef HAVE_API_ANDROID |
|
|
1232 | if (global_show_route_rectangles) |
|
|
1233 | { |
|
|
1234 | send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, try_harder ? 6 : 4); |
|
|
1235 | } |
|
|
1236 | #endif |
|
|
1237 | |
1137 | } |
1238 | } |
1138 | |
1239 | |
1139 | ret = sel; |
1240 | ret = sel; |
1140 | for (i = 0; i < count; i++) |
1241 | for (i = 0; i < count; i++) |
1141 | { |
1242 | { |
|
|
1243 | // make 2 rectangles around every waypoint |
|
|
1244 | // 1 rect small but with high detail (every small street) |
|
|
1245 | // 1 rect a bit bigger but with lower detail |
|
|
1246 | |
1142 | sel->next = route_rect(8, &c[i], &c[i], 0, 40000); |
1247 | sel->next = route_rect(8, &c[i], &c[i], 0, 40000); |
1143 | sel = sel->next; |
1248 | sel = sel->next; |
|
|
1249 | #ifdef HAVE_API_ANDROID |
|
|
1250 | if (global_show_route_rectangles) |
|
|
1251 | { |
|
|
1252 | send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, 8); |
|
|
1253 | } |
|
|
1254 | #endif |
|
|
1255 | |
1144 | sel->next = route_rect(18, &c[i], &c[i], 0, 10000); |
1256 | sel->next = route_rect(18, &c[i], &c[i], 0, 10000); |
1145 | sel = sel->next; |
1257 | sel = sel->next; |
|
|
1258 | #ifdef HAVE_API_ANDROID |
|
|
1259 | if (global_show_route_rectangles) |
|
|
1260 | { |
|
|
1261 | send_route_rect_to_java(sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y, 18); |
|
|
1262 | } |
|
|
1263 | #endif |
1146 | } |
1264 | } |
1147 | /* route_selection=ret; */ |
1265 | /* route_selection=ret; */ |
1148 | return ret; |
1266 | return ret; |
1149 | } |
1267 | } |
1150 | |
1268 | |
… | |
… | |
1202 | if (dst && count) |
1320 | if (dst && count) |
1203 | { |
1321 | { |
1204 | for (i = 0; i < count; i++) |
1322 | for (i = 0; i < count; i++) |
1205 | { |
1323 | { |
1206 | dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]); |
1324 | dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]); |
|
|
1325 | |
|
|
1326 | // try harder |
|
|
1327 | if (dsti == NULL) |
|
|
1328 | { |
|
|
1329 | dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[i], 16000); |
|
|
1330 | } |
|
|
1331 | |
1207 | if (dsti) |
1332 | if (dsti) |
1208 | { |
1333 | { |
|
|
1334 | |
1209 | //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y); |
1335 | //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y); |
1210 | //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y); |
1336 | //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y); |
|
|
1337 | //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y); |
1211 | route_info_distances(dsti, dst->pro); |
1338 | route_info_distances(dsti, dst->pro); |
1212 | this->destinations = g_list_append(this->destinations, dsti); |
1339 | this->destinations = g_list_append(this->destinations, dsti); |
1213 | } |
1340 | } |
1214 | } |
1341 | } |
1215 | route_status.u.num = route_status_destination_set; |
1342 | route_status.u.num = route_status_destination_set; |
1216 | } |
1343 | } |
1217 | else |
1344 | else |
1218 | { |
1345 | { |
1219 | route_status.u.num = route_status_no_destination; |
1346 | route_status.u.num = route_status_no_destination; |
1220 | } |
1347 | } |
|
|
1348 | |
1221 | callback_list_call_attr_1(this->cbl2, attr_destination, this); |
1349 | callback_list_call_attr_1(this->cbl2, attr_destination, this); |
1222 | route_set_attr(this, &route_status); |
1350 | route_set_attr(this, &route_status); |
1223 | //profile(1,"find_nearest_street"); |
1351 | //profile(1,"find_nearest_street"); |
1224 | |
1352 | |
1225 | /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */ |
1353 | /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */ |
… | |
… | |
1238 | struct attr route_status; |
1366 | struct attr route_status; |
1239 | struct route_info *dsti; |
1367 | struct route_info *dsti; |
1240 | route_status.type = attr_route_status; |
1368 | route_status.type = attr_route_status; |
1241 | |
1369 | |
1242 | dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]); |
1370 | dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]); |
|
|
1371 | |
|
|
1372 | // try harder |
|
|
1373 | if (dsti == NULL) |
|
|
1374 | { |
|
|
1375 | dsti = route_find_nearest_street_harder(this->vehicleprofile, this->ms, &dst[0], 16000); |
|
|
1376 | } |
|
|
1377 | |
1243 | if (dsti) |
1378 | if (dsti) |
1244 | { |
1379 | { |
1245 | //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y); |
1380 | //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y); |
1246 | //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y); |
1381 | //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y); |
|
|
1382 | //dbg(0, "3: x y: %i %i\n", dsti->lp.x, dsti->lp.y); |
1247 | |
1383 | |
1248 | route_info_distances(dsti, dst->pro); |
1384 | route_info_distances(dsti, dst->pro); |
1249 | this->destinations = g_list_append(this->destinations, dsti); |
1385 | this->destinations = g_list_append(this->destinations, dsti); |
1250 | |
1386 | |
1251 | route_status.u.num = route_status_destination_set; |
1387 | route_status.u.num = route_status_destination_set; |
… | |
… | |
1383 | |
1519 | |
1384 | int hashval; |
1520 | int hashval; |
1385 | struct route_graph_point *p; |
1521 | struct route_graph_point *p; |
1386 | |
1522 | |
1387 | hashval = HASHCOORD(f); |
1523 | hashval = HASHCOORD(f); |
1388 | if (debug_route) |
1524 | //if (debug_route) |
1389 | printf("p (0x%x,0x%x)\n", f->x, f->y); |
1525 | // printf("p (0x%x,0x%x)\n", f->x, f->y); |
1390 | |
1526 | |
1391 | p=g_slice_new0(struct route_graph_point); |
1527 | p=g_slice_new0(struct route_graph_point); |
|
|
1528 | //global_route_memory_size = global_route_memory_size + sizeof(struct route_graph_point); |
|
|
1529 | //dbg(0,"(A)route mem=%lu\n", global_route_memory_size); |
|
|
1530 | |
1392 | p->hash_next = this->hash[hashval]; |
1531 | p->hash_next = this->hash[hashval]; |
1393 | this->hash[hashval] = p; |
1532 | this->hash[hashval] = p; |
1394 | p->value = INT_MAX; |
1533 | p->value = INT_MAX; |
1395 | p->c = *f; |
1534 | p->c = *f; |
1396 | |
1535 | |
… | |
… | |
1436 | curr = this->hash[i]; |
1575 | curr = this->hash[i]; |
1437 | while (curr) |
1576 | while (curr) |
1438 | { |
1577 | { |
1439 | next = curr->hash_next; |
1578 | next = curr->hash_next; |
1440 | g_slice_free(struct route_graph_point, curr); |
1579 | g_slice_free(struct route_graph_point, curr); |
|
|
1580 | //global_route_memory_size = global_route_memory_size - sizeof(struct route_graph_point); |
|
|
1581 | //dbg(0,"(F)route mem=%lu\n", global_route_memory_size); |
|
|
1582 | |
1441 | curr = next; |
1583 | curr = next; |
1442 | } |
1584 | } |
1443 | this->hash[i] = NULL; |
1585 | this->hash[i] = NULL; |
1444 | } |
1586 | } |
1445 | } |
1587 | } |
… | |
… | |
1583 | int size; |
1725 | int size; |
1584 | |
1726 | |
1585 | size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(data->flags); |
1727 | size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(data->flags); |
1586 | |
1728 | |
1587 | s = g_slice_alloc0(size); |
1729 | s = g_slice_alloc0(size); |
|
|
1730 | //global_route_memory_size = global_route_memory_size + size; |
|
|
1731 | //dbg(0,"(A)route mem=%lu\n", global_route_memory_size); |
1588 | |
1732 | |
1589 | if (!s) |
1733 | if (!s) |
1590 | { |
1734 | { |
1591 | printf("%s:Out of memory\n", __FUNCTION__); |
1735 | printf("%s:Out of memory\n", __FUNCTION__); |
1592 | return; |
1736 | return; |
… | |
… | |
1616 | RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods; |
1760 | RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods; |
1617 | |
1761 | |
1618 | s->next = this->route_segments; |
1762 | s->next = this->route_segments; |
1619 | this->route_segments = s; |
1763 | this->route_segments = s; |
1620 | |
1764 | |
1621 | if (debug_route) |
1765 | //if (debug_route) |
1622 | { |
1766 | //{ |
1623 | printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y); |
1767 | // printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y); |
1624 | } |
1768 | //} |
1625 | } |
1769 | } |
1626 | |
1770 | |
1627 | /** |
1771 | /** |
1628 | * @brief Gets all the coordinates of an item |
1772 | * @brief Gets all the coordinates of an item |
1629 | * |
1773 | * |
1630 | * This will get all the coordinates of the item i and return them in c, |
1774 | * This will get all the coordinates of the item i and return them in c, |
1631 | * up to max coordinates. Additionally it is possible to limit the coordinates |
1775 | * up to max coordinates. Additionally it is possible to limit the coordinates |
1632 | * returned to all the coordinates of the item between the two coordinates |
1776 | * returned to all the coordinates of the item between the two coordinates |
1633 | * start end end. |
1777 | * "start" and "end". |
1634 | * |
1778 | * |
1635 | * @important Make sure that whatever c points to has enough memory allocated |
1779 | * @important Make sure that whatever c points to has enough memory allocated |
1636 | * @important to hold max coordinates! |
1780 | * @important to hold max coordinates! |
1637 | * |
1781 | * |
1638 | * @param i The item to get the coordinates of |
1782 | * @param i The item to get the coordinates of |
… | |
… | |
1751 | * @param end coordinate to add to the end of the item. If none should be added, make this NULL. |
1895 | * @param end coordinate to add to the end of the item. If none should be added, make this NULL. |
1752 | * @param len The length of the item |
1896 | * @param len The length of the item |
1753 | */ |
1897 | */ |
1754 | static void route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len) |
1898 | static void route_path_add_line(struct route_path *this, struct coord *start, struct coord *end, int len) |
1755 | { |
1899 | { |
1756 | //// dbg(0, "enter\n"); |
1900 | //dbg(0, "enter\n"); |
1757 | |
1901 | |
1758 | int ccnt = 2; |
1902 | int ccnt = 2; |
1759 | struct route_path_segment *segment; |
1903 | struct route_path_segment *segment; |
1760 | int seg_size, seg_dat_size; |
1904 | int seg_size, seg_dat_size; |
1761 | |
1905 | |
1762 | //dbg(1, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, |
1906 | //dbg(0, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x, end->y); |
1763 | // end->y); |
1907 | |
1764 | seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt; |
1908 | seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt; |
1765 | seg_dat_size = sizeof(struct route_segment_data); |
1909 | seg_dat_size = sizeof(struct route_segment_data); |
1766 | segment = g_malloc0(seg_size + seg_dat_size); |
1910 | segment = g_malloc0(seg_size + seg_dat_size); |
|
|
1911 | //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size; |
|
|
1912 | //dbg(0,"route mem=%lu\n", global_route_memory_size); |
|
|
1913 | |
1767 | segment->data = (struct route_segment_data *) ((char *) segment + seg_size); |
1914 | segment->data = (struct route_segment_data *) ((char *) segment + seg_size); |
1768 | segment->ncoords = ccnt; |
1915 | segment->ncoords = ccnt; |
1769 | segment->direction = 0; |
1916 | segment->direction = 0; |
1770 | segment->c[0] = *start; |
1917 | segment->c[0] = *start; |
1771 | segment->c[1] = *end; |
1918 | segment->c[1] = *end; |
… | |
… | |
1889 | c = ca; |
2036 | c = ca; |
1890 | } |
2037 | } |
1891 | seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra); |
2038 | seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra); |
1892 | seg_dat_size = route_segment_data_size(rgs->data.flags); |
2039 | seg_dat_size = route_segment_data_size(rgs->data.flags); |
1893 | segment = g_malloc0(seg_size + seg_dat_size); |
2040 | segment = g_malloc0(seg_size + seg_dat_size); |
|
|
2041 | //global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size; |
|
|
2042 | //dbg(0,"route mem=%lu\n", global_route_memory_size); |
|
|
2043 | |
1894 | segment->data = (struct route_segment_data *) ((char *) segment + seg_size); |
2044 | segment->data = (struct route_segment_data *) ((char *) segment + seg_size); |
1895 | segment->direction = dir; |
2045 | segment->direction = dir; |
1896 | cd = segment->c; |
2046 | cd = segment->c; |
1897 | if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y)) |
2047 | if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y)) |
1898 | *cd++ = pos->lp; |
2048 | *cd++ = pos->lp; |
… | |
… | |
1908 | *cd++ = dst->lp; |
2058 | *cd++ = dst->lp; |
1909 | segment->ncoords = cd - segment->c; |
2059 | segment->ncoords = cd - segment->c; |
1910 | if (segment->ncoords <= 1) |
2060 | if (segment->ncoords <= 1) |
1911 | { |
2061 | { |
1912 | g_free(segment); |
2062 | g_free(segment); |
|
|
2063 | // xxx |
1913 | return 1; |
2064 | return 1; |
1914 | } |
2065 | } |
1915 | |
2066 | |
1916 | /* We check if the route graph segment is part of a roundabout here, because this |
2067 | /* We check if the route graph segment is part of a roundabout here, because this |
1917 | * only matters for route graph segments which form parts of the route path */ |
2068 | * only matters for route graph segments which form parts of the route path */ |
… | |
… | |
1945 | while (curr) |
2096 | while (curr) |
1946 | { |
2097 | { |
1947 | next = curr->next; |
2098 | next = curr->next; |
1948 | size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(curr->data.flags); |
2099 | size = sizeof(struct route_graph_segment) - sizeof(struct route_segment_data) + route_segment_data_size(curr->data.flags); |
1949 | g_slice_free1(size, curr); |
2100 | g_slice_free1(size, curr); |
|
|
2101 | //global_route_memory_size = global_route_memory_size - size; |
|
|
2102 | //dbg(0,"(F)route mem=%lu\n", global_route_memory_size); |
1950 | curr = next; |
2103 | curr = next; |
1951 | } |
2104 | } |
1952 | this->route_segments = NULL; |
2105 | this->route_segments = NULL; |
1953 | } |
2106 | } |
1954 | |
2107 | |
… | |
… | |
2003 | if (dist && maxspeed > dist->maxspeed) |
2156 | if (dist && maxspeed > dist->maxspeed) |
2004 | maxspeed = dist->maxspeed; |
2157 | maxspeed = dist->maxspeed; |
2005 | if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed)) |
2158 | if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed < speed)) |
2006 | speed = maxspeed; |
2159 | speed = maxspeed; |
2007 | } |
2160 | } |
|
|
2161 | |
2008 | if (over->flags & AF_DANGEROUS_GOODS) |
2162 | if (over->flags & AF_DANGEROUS_GOODS) |
2009 | { |
2163 | { |
2010 | if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over)) |
2164 | if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over)) |
2011 | return 0; |
2165 | return 0; |
2012 | } |
2166 | } |
|
|
2167 | |
2013 | if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT) |
2168 | if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT) |
2014 | { |
2169 | { |
2015 | struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over); |
2170 | struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over); |
2016 | if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width) |
2171 | if (size_weight->width != -1 && profile->width != -1 && profile->width > size_weight->width) |
2017 | return 0; |
2172 | return 0; |
… | |
… | |
2121 | distp = &dist; |
2276 | distp = &dist; |
2122 | } |
2277 | } |
2123 | ret = route_time_seg(profile, &over->data, distp); |
2278 | ret = route_time_seg(profile, &over->data, distp); |
2124 | if (ret == INT_MAX) |
2279 | if (ret == INT_MAX) |
2125 | return ret; |
2280 | return ret; |
|
|
2281 | |
2126 | if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from->seg)) |
2282 | if (!route_through_traffic_allowed(profile, over) && from && route_through_traffic_allowed(profile, from->seg)) |
2127 | ret += profile->through_traffic_penalty; |
2283 | ret += profile->through_traffic_penalty; |
|
|
2284 | |
|
|
2285 | // calc delay from traffic lights |
|
|
2286 | if ((from) && (global_traffic_light_delay > 0)) |
|
|
2287 | { |
|
|
2288 | if (from->flags & RP_TRAFFIC_LIGHT) |
|
|
2289 | { |
|
|
2290 | // dbg(0, "traffic light delay:%d w/o:%d\n", (ret+global_traffic_light_delay), ret); |
|
|
2291 | // in 1/10 of a second !! |
|
|
2292 | ret += global_traffic_light_delay; |
|
|
2293 | } |
|
|
2294 | } |
|
|
2295 | |
2128 | return ret; |
2296 | return ret; |
2129 | } |
2297 | } |
2130 | |
2298 | |
|
|
2299 | |
|
|
2300 | |
|
|
2301 | |
|
|
2302 | |
2131 | /** |
2303 | /** |
2132 | * @brief Adds a route distortion item to the route graph |
2304 | * @brief Adds a traffic light item to the route graph |
2133 | * |
2305 | * |
2134 | * @param this The route graph to add to |
2306 | * @param this The route graph to add to |
2135 | * @param item The item to add |
2307 | * @param item The item to add |
2136 | */ |
2308 | */ |
2137 | static void route_process_traffic_distortion(struct route_graph *this, struct item *item) |
2309 | static void route_process_traffic_light(struct route_graph *this, struct item *item) |
2138 | { |
2310 | { |
2139 | // dbg(0, "enter\n"); |
|
|
2140 | |
|
|
2141 | struct route_graph_point *s_pnt, *e_pnt; |
2311 | struct route_graph_point *s_pnt, *e_pnt; |
2142 | struct coord c, l; |
2312 | struct coord l; |
2143 | struct attr delay_attr, maxspeed_attr; |
|
|
2144 | struct route_graph_segment_data data; |
2313 | struct route_graph_segment_data data; |
2145 | |
2314 | |
2146 | data.item = item; |
2315 | data.item = item; |
2147 | data.len = 0; |
2316 | data.len = 0; |
2148 | data.flags = 0; |
2317 | data.flags = 0; |
… | |
… | |
2150 | data.maxspeed = INT_MAX; |
2319 | data.maxspeed = INT_MAX; |
2151 | |
2320 | |
2152 | if (item_coord_get(item, &l, 1)) |
2321 | if (item_coord_get(item, &l, 1)) |
2153 | { |
2322 | { |
2154 | s_pnt = route_graph_add_point(this, &l); |
2323 | s_pnt = route_graph_add_point(this, &l); |
|
|
2324 | s_pnt->flags |= RP_TRAFFIC_LIGHT; |
|
|
2325 | } |
|
|
2326 | } |
|
|
2327 | |
|
|
2328 | |
|
|
2329 | |
|
|
2330 | |
|
|
2331 | |
|
|
2332 | /** |
|
|
2333 | * @brief Adds a route distortion item to the route graph |
|
|
2334 | * |
|
|
2335 | * @param this The route graph to add to |
|
|
2336 | * @param item The item to add |
|
|
2337 | */ |
|
|
2338 | static void route_process_traffic_distortion(struct route_graph *this, struct item *item) |
|
|
2339 | { |
|
|
2340 | // dbg(0, "enter\n"); |
|
|
2341 | |
|
|
2342 | struct route_graph_point *s_pnt, *e_pnt; |
|
|
2343 | struct coord c, l; |
|
|
2344 | struct attr delay_attr, maxspeed_attr; |
|
|
2345 | struct route_graph_segment_data data; |
|
|
2346 | |
|
|
2347 | data.item = item; |
|
|
2348 | data.len = 0; |
|
|
2349 | data.flags = 0; |
|
|
2350 | data.offset = 1; |
|
|
2351 | data.maxspeed = INT_MAX; |
|
|
2352 | |
|
|
2353 | if (item_coord_get(item, &l, 1)) |
|
|
2354 | { |
|
|
2355 | s_pnt = route_graph_add_point(this, &l); |
2155 | while (item_coord_get(item, &c, 1)) |
2356 | while (item_coord_get(item, &c, 1)) |
2156 | { |
2357 | { |
2157 | l = c; |
2358 | l = c; |
2158 | } |
2359 | } |
2159 | |
2360 | |
… | |
… | |
2173 | } |
2374 | } |
2174 | //dbg(0,"add traffic distortion segment, speed=%d\n", data.maxspeed); |
2375 | //dbg(0,"add traffic distortion segment, speed=%d\n", data.maxspeed); |
2175 | route_graph_add_segment(this, s_pnt, e_pnt, &data); |
2376 | route_graph_add_segment(this, s_pnt, e_pnt, &data); |
2176 | } |
2377 | } |
2177 | } |
2378 | } |
|
|
2379 | |
2178 | |
2380 | |
2179 | /** |
2381 | /** |
2180 | * @brief Adds a route distortion item to the route graph |
2382 | * @brief Adds a route distortion item to the route graph |
2181 | * |
2383 | * |
2182 | * @param this The route graph to add to |
2384 | * @param this The route graph to add to |
… | |
… | |
2258 | data.item = item; |
2460 | data.item = item; |
2259 | |
2461 | |
2260 | roadp = vehicleprofile_get_roadprofile(profile, item->type); |
2462 | roadp = vehicleprofile_get_roadprofile(profile, item->type); |
2261 | if (!roadp) |
2463 | if (!roadp) |
2262 | { |
2464 | { |
|
|
2465 | //dbg(0,"*[0]type=%s\n", item_to_name(item->type)); |
2263 | // Don't include any roads that don't have a road profile in our vehicle profile |
2466 | // Don't include any roads that don't have a road profile in our vehicle profile |
2264 | return; |
2467 | return; |
2265 | } |
2468 | } |
2266 | |
2469 | |
2267 | if (item_coord_get(item, &l, 1)) |
2470 | if (item_coord_get(item, &l, 1)) |
2268 | { |
2471 | { |
2269 | int *default_flags = item_get_default_flags(item->type); |
2472 | int *default_flags = item_get_default_flags(item->type); |
2270 | if (!default_flags) |
2473 | if (!default_flags) |
2271 | { |
2474 | { |
|
|
2475 | //dbg(0,"*[1]type=%s\n", item_to_name(item->type)); |
2272 | return; |
2476 | return; |
2273 | } |
2477 | } |
|
|
2478 | |
2274 | if (item_attr_get(item, attr_flags, &attr)) |
2479 | if (item_attr_get(item, attr_flags, &attr)) |
2275 | { |
2480 | { |
2276 | data.flags = attr.u.num; |
2481 | data.flags = attr.u.num; |
2277 | if (data.flags & AF_SEGMENTED) |
2482 | if (data.flags & AF_SEGMENTED) |
2278 | { |
2483 | { |
… | |
… | |
2420 | * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look |
2625 | * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look |
2421 | * at this algorithm. |
2626 | * at this algorithm. |
2422 | */ |
2627 | */ |
2423 | static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb) |
2628 | static void route_graph_flood(struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb) |
2424 | { |
2629 | { |
2425 | // dbg(0, "enter\n"); |
2630 | //dbg(0, "enter\n"); |
2426 | |
2631 | |
2427 | struct route_graph_point *p_min; |
2632 | struct route_graph_point *p_min; |
2428 | struct route_graph_segment *s = NULL; |
2633 | struct route_graph_segment *s = NULL; |
2429 | int min, new, old, val; |
2634 | int min, new, old, val; |
2430 | struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */ |
2635 | struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */ |
… | |
… | |
2461 | { |
2666 | { |
2462 | break; |
2667 | break; |
2463 | } |
2668 | } |
2464 | |
2669 | |
2465 | min = p_min->value; |
2670 | min = p_min->value; |
2466 | if (debug_route) |
2671 | //if (debug_route) |
2467 | { |
2672 | //{ |
2468 | printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y); |
2673 | // printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min, p_min->el, min, p_min->c.x, p_min->c.y); |
2469 | } |
2674 | //} |
2470 | |
2675 | |
2471 | p_min->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */ |
2676 | p_min->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */ |
2472 | |
2677 | |
2473 | s = p_min->start; |
2678 | s = p_min->start; |
2474 | |
2679 | |
… | |
… | |
2476 | { /* Iterating all the segments leading away from our point to update the points at their ends */ |
2681 | { /* Iterating all the segments leading away from our point to update the points at their ends */ |
2477 | val = route_value_seg(profile, p_min, s, -1); |
2682 | val = route_value_seg(profile, p_min, s, -1); |
2478 | if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item)) |
2683 | if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item)) |
2479 | { |
2684 | { |
2480 | new = min + val; |
2685 | new = min + val; |
2481 | if (debug_route) |
2686 | //if (debug_route) |
2482 | { |
2687 | //{ |
2483 | printf("begin %d len %d vs %d (0x%x,0x%x)\n", new, val, s->end->value, s->end->c.x, s->end->c.y); |
2688 | // printf("begin %d len %d vs %d (0x%x,0x%x)\n", new, val, s->end->value, s->end->c.x, s->end->c.y); |
2484 | } |
2689 | //} |
2485 | |
2690 | |
2486 | if (new < s->end->value) |
2691 | if (new < s->end->value) |
2487 | { /* We've found a less costly way to reach the end of s, update it */ |
2692 | { /* We've found a less costly way to reach the end of s, update it */ |
2488 | s->end->value = new; |
2693 | s->end->value = new; |
2489 | s->end->seg = s; |
2694 | s->end->seg = s; |
2490 | if (!s->end->el) |
2695 | if (!s->end->el) |
2491 | { |
2696 | { |
2492 | if (debug_route) |
2697 | //if (debug_route) |
2493 | { |
2698 | //{ |
2494 | printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value); |
2699 | // printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value); |
2495 | } |
2700 | //} |
2496 | |
2701 | |
2497 | s->end->el = fh_insertkey(heap, new, s->end); |
2702 | s->end->el = fh_insertkey(heap, new, s->end); |
2498 | |
2703 | |
2499 | if (debug_route) |
2704 | //if (debug_route) |
2500 | { |
2705 | //{ |
2501 | printf("el new=%p\n", s->end->el); |
2706 | // printf("el new=%p\n", s->end->el); |
2502 | } |
2707 | //} |
2503 | } |
2708 | } |
2504 | else |
2709 | else |
2505 | { |
2710 | { |
2506 | if (debug_route) |
2711 | //if (debug_route) |
2507 | { |
2712 | //{ |
2508 | printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value); |
2713 | // printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value); |
2509 | } |
2714 | //} |
2510 | fh_replacekey(heap, s->end->el, new); |
2715 | fh_replacekey(heap, s->end->el, new); |
2511 | } |
2716 | } |
2512 | } |
2717 | } |
2513 | |
2718 | |
2514 | if (debug_route) |
2719 | //if (debug_route) |
2515 | { |
2720 | //{ |
2516 | printf("\n"); |
2721 | // printf("\n"); |
2517 | } |
2722 | //} |
2518 | } |
2723 | } |
2519 | s = s->start_next; |
2724 | s = s->start_next; |
2520 | } |
2725 | } |
2521 | |
2726 | |
2522 | s = p_min->end; |
2727 | s = p_min->end; |
… | |
… | |
2525 | { /* Doing the same as above with the segments leading towards our point */ |
2730 | { /* Doing the same as above with the segments leading towards our point */ |
2526 | val = route_value_seg(profile, p_min, s, 1); |
2731 | val = route_value_seg(profile, p_min, s, 1); |
2527 | if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item)) |
2732 | if (val != INT_MAX && !item_is_equal(s->data.item, p_min->seg->data.item)) |
2528 | { |
2733 | { |
2529 | new = min + val; |
2734 | new = min + val; |
2530 | if (debug_route) |
2735 | //if (debug_route) |
2531 | { |
2736 | //{ |
2532 | printf("end %d len %d vs %d (0x%x,0x%x)\n", new, val, s->start->value, s->start->c.x, s->start->c.y); |
2737 | // printf("end %d len %d vs %d (0x%x,0x%x)\n", new, val, s->start->value, s->start->c.x, s->start->c.y); |
2533 | } |
2738 | //} |
2534 | |
2739 | |
2535 | if (new < s->start->value) |
2740 | if (new < s->start->value) |
2536 | { |
2741 | { |
2537 | old = s->start->value; |
2742 | old = s->start->value; |
2538 | s->start->value = new; |
2743 | s->start->value = new; |
2539 | s->start->seg = s; |
2744 | s->start->seg = s; |
2540 | if (!s->start->el) |
2745 | if (!s->start->el) |
2541 | { |
2746 | { |
2542 | if (debug_route) |
2747 | //if (debug_route) |
2543 | { |
2748 | //{ |
2544 | printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value); |
2749 | // printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value); |
2545 | } |
2750 | //} |
2546 | s->start->el = fh_insertkey(heap, new, s->start); |
2751 | s->start->el = fh_insertkey(heap, new, s->start); |
2547 | if (debug_route) |
2752 | //if (debug_route) |
2548 | { |
2753 | //{ |
2549 | printf("el new=%p\n", s->start->el); |
2754 | // printf("el new=%p\n", s->start->el); |
2550 | } |
2755 | //} |
2551 | } |
2756 | } |
2552 | else |
2757 | else |
2553 | { |
2758 | { |
2554 | if (debug_route) |
2759 | //if (debug_route) |
2555 | { |
2760 | //{ |
2556 | printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value); |
2761 | // printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value); |
2557 | } |
2762 | //} |
2558 | fh_replacekey(heap, s->start->el, new); |
2763 | fh_replacekey(heap, s->start->el, new); |
2559 | } |
2764 | } |
2560 | } |
2765 | } |
2561 | if (debug_route) |
2766 | //if (debug_route) |
2562 | { |
2767 | //{ |
2563 | printf("\n"); |
2768 | // printf("\n"); |
2564 | } |
2769 | //} |
2565 | } |
2770 | } |
2566 | s = s->end_next; |
2771 | s = s->end_next; |
2567 | } |
2772 | } |
2568 | } |
2773 | } |
2569 | |
2774 | |
… | |
… | |
2679 | * @return The new route path |
2884 | * @return The new route path |
2680 | */ |
2885 | */ |
2681 | static struct route_path * |
2886 | static struct route_path * |
2682 | route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile) |
2887 | route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile) |
2683 | { |
2888 | { |
2684 | // dbg(0, "enter\n"); |
2889 | //dbg(0, "enter\n"); |
2685 | |
2890 | |
2686 | struct route_graph_segment *first, *s = NULL, *s1 = NULL, *s2 = NULL; |
2891 | struct route_graph_segment *first, *s = NULL, *s1 = NULL, *s2 = NULL; |
2687 | struct route_graph_point *start; |
2892 | struct route_graph_point *start; |
2688 | struct route_info *posinfo, *dstinfo; |
2893 | struct route_info *posinfo, *dstinfo; |
2689 | int segs = 0; |
2894 | int segs = 0; |
… | |
… | |
2759 | ret->in_use = 1; |
2964 | ret->in_use = 1; |
2760 | ret->updated = 1; |
2965 | ret->updated = 1; |
2761 | |
2966 | |
2762 | if (pos->lenextra) |
2967 | if (pos->lenextra) |
2763 | { |
2968 | { |
|
|
2969 | //dbg(0,"l extra1=%d\n", pos->lenextra); |
2764 | route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra); |
2970 | route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra); |
2765 | } |
2971 | } |
2766 | |
2972 | |
2767 | ret->path_hash = item_hash_new(); |
2973 | ret->path_hash = item_hash_new(); |
2768 | dstinfo = NULL; |
2974 | dstinfo = NULL; |
2769 | posinfo = pos; |
2975 | posinfo = pos; |
2770 | first = s; |
2976 | first = s; |
2771 | |
|
|
2772 | |
|
|
2773 | |
2977 | |
2774 | // ------- build the real route here ------------------------ |
2978 | // ------- build the real route here ------------------------ |
2775 | // ------- build the real route here ------------------------ |
2979 | // ------- build the real route here ------------------------ |
2776 | while (s && !dstinfo) |
2980 | while (s && !dstinfo) |
2777 | { /* following start->seg, which indicates the least costly way to reach our destination */ |
2981 | { /* following start->seg, which indicates the least costly way to reach our destination */ |
… | |
… | |
2811 | // ------- build the real route here ------------------------ |
3015 | // ------- build the real route here ------------------------ |
2812 | // ------- build the real route here ------------------------ |
3016 | // ------- build the real route here ------------------------ |
2813 | |
3017 | |
2814 | if (dst->lenextra) |
3018 | if (dst->lenextra) |
2815 | { |
3019 | { |
|
|
3020 | //dbg(0,"l extra2=%d\n", dst->lenextra); |
2816 | route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra); |
3021 | route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra); |
2817 | } |
3022 | } |
2818 | |
3023 | |
2819 | //dbg(1, "%d segments\n", segs); |
3024 | //dbg(1, "%d segments\n", segs); |
2820 | return ret; |
3025 | return ret; |
… | |
… | |
2961 | return; |
3166 | return; |
2962 | } |
3167 | } |
2963 | route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY); |
3168 | route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY); |
2964 | } |
3169 | } |
2965 | |
3170 | |
2966 | |
|
|
2967 | tmp = p->start; |
3171 | tmp = p->start; |
2968 | while (tmp) |
3172 | while (tmp) |
2969 | { |
3173 | { |
2970 | if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s, tmp)) |
3174 | if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s, tmp)) |
2971 | { |
3175 | { |
… | |
… | |
2973 | //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type)); |
3177 | //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type)); |
2974 | } |
3178 | } |
2975 | tmp = tmp->start_next; |
3179 | tmp = tmp->start_next; |
2976 | } |
3180 | } |
2977 | |
3181 | |
2978 | |
|
|
2979 | tmp = p->end; |
3182 | tmp = p->end; |
2980 | while (tmp) |
3183 | while (tmp) |
2981 | { |
3184 | { |
2982 | if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp)) |
3185 | if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no && tmp->data.item.type != type_street_turn_restriction_only && !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp)) |
2983 | { |
3186 | { |
… | |
… | |
2985 | //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type)); |
3188 | //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type)); |
2986 | } |
3189 | } |
2987 | tmp = tmp->end_next; |
3190 | tmp = tmp->end_next; |
2988 | } |
3191 | } |
2989 | } |
3192 | } |
|
|
3193 | |
|
|
3194 | // -- UNUSED -- |
|
|
3195 | // -- UNUSED -- |
|
|
3196 | static void route_graph_process_traffic_light_segment(struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir) |
|
|
3197 | { |
|
|
3198 | //struct route_graph_segment *tmp; |
|
|
3199 | //s->data.len = s->data.len + global_traffic_light_delay; |
|
|
3200 | } |
|
|
3201 | |
2990 | |
3202 | |
2991 | static void route_graph_process_restriction_point(struct route_graph *this, struct route_graph_point *p) |
3203 | static void route_graph_process_restriction_point(struct route_graph *this, struct route_graph_point *p) |
2992 | { |
3204 | { |
2993 | // dbg(0, "enter\n"); |
3205 | // dbg(0, "enter\n"); |
2994 | |
3206 | |
… | |
… | |
3022 | } |
3234 | } |
3023 | |
3235 | |
3024 | p->flags |= RP_TURN_RESTRICTION_RESOLVED; |
3236 | p->flags |= RP_TURN_RESTRICTION_RESOLVED; |
3025 | } |
3237 | } |
3026 | |
3238 | |
|
|
3239 | // -- UNUSED -- |
|
|
3240 | // -- UNUSED -- |
|
|
3241 | static void route_graph_process_traffic_light_point(struct route_graph *this, struct route_graph_point *p) |
|
|
3242 | { |
|
|
3243 | // dbg(0, "enter\n"); |
|
|
3244 | |
|
|
3245 | struct route_graph_segment *tmp; |
|
|
3246 | |
|
|
3247 | // ------------------------------------------------------------- |
|
|
3248 | // p->start ==> a list of all streets that start from this point |
|
|
3249 | // ------------------------------------------------------------- |
|
|
3250 | tmp = p->start; |
|
|
3251 | while (tmp) |
|
|
3252 | { |
|
|
3253 | route_graph_process_traffic_light_segment(this, p, tmp, 1); |
|
|
3254 | tmp = tmp->start_next; |
|
|
3255 | } |
|
|
3256 | |
|
|
3257 | // ------------------------------------------------------------- |
|
|
3258 | // p->end ==> a list of all streets that end at this point |
|
|
3259 | // ------------------------------------------------------------- |
|
|
3260 | tmp = p->end; |
|
|
3261 | while (tmp) |
|
|
3262 | { |
|
|
3263 | route_graph_process_traffic_light_segment(this, p, tmp, -1); |
|
|
3264 | tmp = tmp->end_next; |
|
|
3265 | } |
|
|
3266 | |
|
|
3267 | // p->flags |= RP_TRAFFIC_LIGHT_RESOLVED; |
|
|
3268 | } |
|
|
3269 | |
|
|
3270 | |
3027 | static void route_graph_process_restrictions(struct route_graph *this) |
3271 | static void route_graph_process_restrictions(struct route_graph *this) |
3028 | { |
3272 | { |
3029 | // dbg(0, "enter\n"); |
3273 | // dbg(0, "enter\n"); |
3030 | |
3274 | |
3031 | struct route_graph_point *curr; |
3275 | struct route_graph_point *curr; |
… | |
… | |
3043 | curr = curr->hash_next; |
3287 | curr = curr->hash_next; |
3044 | } |
3288 | } |
3045 | } |
3289 | } |
3046 | } |
3290 | } |
3047 | |
3291 | |
|
|
3292 | // -- UNUSED -- |
|
|
3293 | // -- UNUSED -- |
|
|
3294 | static void route_graph_process_traffic_lights(struct route_graph *this) |
|
|
3295 | { |
|
|
3296 | // dbg(0, "enter\n"); |
|
|
3297 | |
|
|
3298 | // check if we should calc delay for traffic lights? |
|
|
3299 | if (global_traffic_light_delay > 0) |
|
|
3300 | { |
|
|
3301 | struct route_graph_point *curr; |
|
|
3302 | int i; |
|
|
3303 | //dbg(1, "enter\n"); |
|
|
3304 | for (i = 0; i < HASH_SIZE; i++) |
|
|
3305 | { |
|
|
3306 | curr = this->hash[i]; |
|
|
3307 | while (curr) |
|
|
3308 | { |
|
|
3309 | if (curr->flags & RP_TRAFFIC_LIGHT) |
|
|
3310 | { |
|
|
3311 | route_graph_process_traffic_light_point(this, curr); |
|
|
3312 | } |
|
|
3313 | curr = curr->hash_next; |
|
|
3314 | } |
|
|
3315 | } |
|
|
3316 | } |
|
|
3317 | } |
|
|
3318 | |
|
|
3319 | |
3048 | static void route_graph_build_done(struct route_graph *rg, int cancel) |
3320 | static void route_graph_build_done(struct route_graph *rg, int cancel) |
3049 | { |
3321 | { |
3050 | // dbg(0, "enter\n"); |
3322 | //dbg(0, "enter\n"); |
3051 | |
3323 | |
3052 | //dbg(1, "cancel=%d\n", cancel); |
3324 | //dbg(1, "cancel=%d\n", cancel); |
3053 | if (rg->idle_ev) |
3325 | if (rg->idle_ev) |
3054 | { |
3326 | { |
3055 | event_remove_idle(rg->idle_ev); |
3327 | event_remove_idle(rg->idle_ev); |
… | |
… | |
3070 | rg->sel = NULL; |
3342 | rg->sel = NULL; |
3071 | |
3343 | |
3072 | if (!cancel) |
3344 | if (!cancel) |
3073 | { |
3345 | { |
3074 | route_graph_process_restrictions(rg); |
3346 | route_graph_process_restrictions(rg); |
|
|
3347 | // --unused-- route_graph_process_traffic_lights(rg); |
3075 | //dbg(0, "callback\n"); |
3348 | //dbg(0, "callback\n"); |
3076 | callback_call_0(rg->done_cb); |
3349 | callback_call_0(rg->done_cb); |
3077 | } |
3350 | } |
3078 | |
3351 | |
3079 | rg->busy = 0; |
3352 | rg->busy = 0; |
… | |
… | |
3082 | // this function gets called in a loop until route is ready ---------- |
3355 | // this function gets called in a loop until route is ready ---------- |
3083 | // this function gets called in a loop until route is ready ---------- |
3356 | // this function gets called in a loop until route is ready ---------- |
3084 | // this function gets called in a loop until route is ready ---------- |
3357 | // this function gets called in a loop until route is ready ---------- |
3085 | static void route_graph_build_idle(struct route_graph *rg, struct vehicleprofile *profile) |
3358 | static void route_graph_build_idle(struct route_graph *rg, struct vehicleprofile *profile) |
3086 | { |
3359 | { |
3087 | // // dbg(0, "enter\n"); |
3360 | //dbg(0, "enter\n"); |
3088 | |
3361 | |
3089 | // int count = 1000; |
3362 | #ifdef DEBUG_GLIB_MEM_FUNCTIONS |
|
|
3363 | g_mem_profile(); |
|
|
3364 | #endif |
|
|
3365 | |
|
|
3366 | // int count = 1000; // *ORIG* value |
3090 | int count = 5000; // process 5000 items in one step |
3367 | int count = 5000; // process 5000 items in one step |
|
|
3368 | //int count = 15000; // process 15000 items in one step |
3091 | struct item *item; |
3369 | struct item *item; |
3092 | |
3370 | |
3093 | while (count > 0) |
3371 | while (count > 0) |
3094 | { |
3372 | { |
3095 | // loop until an item is found --------- |
3373 | // loop until an item is found --------- |
… | |
… | |
3112 | |
3390 | |
3113 | if (item->type == type_traffic_distortion) |
3391 | if (item->type == type_traffic_distortion) |
3114 | { |
3392 | { |
3115 | route_process_traffic_distortion(rg, item); |
3393 | route_process_traffic_distortion(rg, item); |
3116 | } |
3394 | } |
|
|
3395 | /* |
|
|
3396 | else if ( |
|
|
3397 | (item->type == type_street_2_city) || |
|
|
3398 | (item->type == type_street_3_city) || |
|
|
3399 | (item->type == type_street_4_city) || |
|
|
3400 | (item->type == type_highway_city) || |
|
|
3401 | (item->type == type_street_1_land) || |
|
|
3402 | (item->type == type_street_2_land) || |
|
|
3403 | (item->type == type_street_3_land) || |
|
|
3404 | (item->type == type_street_4_land) || |
|
|
3405 | (item->type == type_street_n_lanes) || |
|
|
3406 | (item->type == type_highway_land) || |
|
|
3407 | (item->type == type_ramp) || |
|
|
3408 | ) |
|
|
3409 | { |
|
|
3410 | */ |
|
|
3411 | /* |
|
|
3412 | ITEM(street_0) |
|
|
3413 | ITEM(street_1_city) |
|
|
3414 | ITEM(street_2_city) |
|
|
3415 | ITEM(street_3_city) |
|
|
3416 | ITEM(street_4_city) |
|
|
3417 | ITEM(highway_city) |
|
|
3418 | ITEM(street_1_land) |
|
|
3419 | ITEM(street_2_land) |
|
|
3420 | ITEM(street_3_land) |
|
|
3421 | ITEM(street_4_land) |
|
|
3422 | ITEM(street_n_lanes) |
|
|
3423 | ITEM(highway_land) |
|
|
3424 | ITEM(ramp) |
|
|
3425 | */ |
|
|
3426 | // route_process_sharp_turn(rg, item); |
|
|
3427 | // } |
|
|
3428 | else if (item->type == type_traffic_signals) |
|
|
3429 | { |
|
|
3430 | route_process_traffic_light(rg, item); |
|
|
3431 | } |
3117 | else if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only) |
3432 | else if (item->type == type_street_turn_restriction_no || item->type == type_street_turn_restriction_only) |
3118 | { |
3433 | { |
3119 | route_process_turn_restriction(rg, item); |
3434 | route_process_turn_restriction(rg, item); |
3120 | } |
3435 | } |
3121 | else |
3436 | else |
3122 | { |
3437 | { |
|
|
3438 | //dbg(0,"*[xx]type=%s\n", item_to_name(item->type)); |
3123 | route_process_street_graph(rg, item, profile); |
3439 | route_process_street_graph(rg, item, profile); |
3124 | } |
3440 | } |
3125 | |
3441 | |
3126 | count--; |
3442 | count--; |
3127 | } |
3443 | } |
|
|
3444 | |
|
|
3445 | //dbg(0,"leave\n"); |
3128 | } |
3446 | } |
3129 | |
3447 | |
3130 | /** |
3448 | /** |
3131 | * @brief Builds a new route graph from a mapset |
3449 | * @brief Builds a new route graph from a mapset |
3132 | * |
3450 | * |
… | |
… | |
3144 | * @return The new route graph. |
3462 | * @return The new route graph. |
3145 | */ |
3463 | */ |
3146 | static struct route_graph * |
3464 | static struct route_graph * |
3147 | route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile, int try_harder) |
3465 | route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile, int try_harder) |
3148 | { |
3466 | { |
3149 | // // dbg(0, "enter\n"); |
3467 | //dbg(0, "enter\n"); |
3150 | |
3468 | |
3151 | struct route_graph *ret=g_new0(struct route_graph, 1); |
3469 | struct route_graph *ret=g_new0(struct route_graph, 1); |
3152 | |
3470 | |
3153 | // // dbg(0, "enter\n"); |
|
|
3154 | |
|
|
3155 | ret->sel = route_calc_selection(c, count, try_harder); |
3471 | ret->sel = route_calc_selection(c, count, try_harder); |
|
|
3472 | |
3156 | ret->h = mapset_open(ms); |
3473 | ret->h = mapset_open(ms); |
3157 | ret->done_cb = done_cb; |
3474 | ret->done_cb = done_cb; |
3158 | ret->busy = 1; |
3475 | ret->busy = 1; |
3159 | |
3476 | |
3160 | if (route_graph_build_next_map(ret)) |
3477 | if (route_graph_build_next_map(ret)) |
… | |
… | |
3181 | return ret; |
3498 | return ret; |
3182 | } |
3499 | } |
3183 | |
3500 | |
3184 | static void route_graph_update_done(struct route *this, struct callback *cb) |
3501 | static void route_graph_update_done(struct route *this, struct callback *cb) |
3185 | { |
3502 | { |
3186 | // dbg(0, "enter\n"); |
3503 | //dbg(0, "enter\n"); |
3187 | |
|
|
3188 | route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb); |
3504 | route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb); |
3189 | } |
3505 | } |
3190 | |
3506 | |
3191 | /** |
3507 | /** |
3192 | * @brief Updates the route graph |
3508 | * @brief Updates the route graph |
… | |
… | |
3196 | * |
3512 | * |
3197 | * @param this The route to update the graph for |
3513 | * @param this The route to update the graph for |
3198 | */ |
3514 | */ |
3199 | static void route_graph_update(struct route *this, struct callback *cb, int async) |
3515 | static void route_graph_update(struct route *this, struct callback *cb, int async) |
3200 | { |
3516 | { |
3201 | // dbg(0, "enter\n"); |
3517 | //dbg(0, "enter\n"); |
3202 | |
3518 | |
3203 | struct attr route_status; |
3519 | struct attr route_status; |
3204 | struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this->destinations))); |
3520 | struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this->destinations))); |
3205 | int i = 0; |
3521 | int i = 0; |
3206 | GList *tmp; |
3522 | GList *tmp; |
… | |
… | |
3231 | while (this->graph->busy) |
3547 | while (this->graph->busy) |
3232 | { |
3548 | { |
3233 | route_graph_build_idle(this->graph, this->vehicleprofile); |
3549 | route_graph_build_idle(this->graph, this->vehicleprofile); |
3234 | } |
3550 | } |
3235 | } |
3551 | } |
|
|
3552 | |
|
|
3553 | //dbg(0,"leave\n"); |
3236 | } |
3554 | } |
3237 | |
3555 | |
3238 | /** |
3556 | /** |
3239 | * @brief Gets street data for an item |
3557 | * @brief Gets street data for an item |
3240 | * |
3558 | * |
… | |
… | |
3308 | |
3626 | |
3309 | struct street_data *ret; |
3627 | struct street_data *ret; |
3310 | int size = sizeof(struct street_data) + orig->count * sizeof(struct coord); |
3628 | int size = sizeof(struct street_data) + orig->count * sizeof(struct coord); |
3311 | |
3629 | |
3312 | ret = g_malloc(size); |
3630 | ret = g_malloc(size); |
|
|
3631 | // xxx global_route_memory_size = global_route_memory_size + seg_size + seg_dat_size; |
|
|
3632 | // xxx dbg(0,"route mem=%lu\n", global_route_memory_size); |
3313 | memcpy(ret, orig, size); |
3633 | memcpy(ret, orig, size); |
3314 | |
3634 | |
3315 | return ret; |
3635 | return ret; |
3316 | } |
3636 | } |
3317 | |
3637 | |
… | |
… | |
3326 | |
3646 | |
3327 | g_free(sd); |
3647 | g_free(sd); |
3328 | } |
3648 | } |
3329 | |
3649 | |
3330 | /** |
3650 | /** |
3331 | * @brief Finds the nearest street to a given coordinate |
3651 | * @brief Finds the nearest street to a given coordinate (result should be a road that is in vehicle profile for routing!) |
3332 | * |
3652 | * |
3333 | * @param ms The mapset to search in for the street |
3653 | * @param ms The mapset to search in for the street |
3334 | * @param pc The coordinate to find a street nearby |
3654 | * @param pc The coordinate to find a street nearby |
3335 | * @return The nearest street |
3655 | * @return The nearest street |
3336 | */ |
3656 | */ |
3337 | static struct route_info * |
3657 | static struct route_info * |
3338 | route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc) |
3658 | route_find_nearest_street(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc) |
3339 | { |
3659 | { |
3340 | // dbg(0, "enter\n"); |
3660 | //dbg(0, "enter\n"); |
3341 | |
3661 | |
3342 | struct route_info *ret = NULL; |
3662 | struct route_info *ret = NULL; |
3343 | int max_dist = 2000; // was 1000 originally!! |
3663 | int max_dist = 1000; // was 1000 originally!! |
3344 | struct map_selection *sel; |
3664 | struct map_selection *sel; |
3345 | int dist, mindist = 0, pos; |
3665 | int dist, mindist = 0, pos; |
3346 | struct mapset_handle *h; |
3666 | struct mapset_handle *h; |
3347 | struct map *m; |
3667 | struct map *m; |
3348 | struct map_rect *mr; |
3668 | struct map_rect *mr; |
… | |
… | |
3358 | h = mapset_open(ms); |
3678 | h = mapset_open(ms); |
3359 | while ((m = mapset_next(h, 2))) |
3679 | while ((m = mapset_next(h, 2))) |
3360 | { |
3680 | { |
3361 | c.x = pc->x; |
3681 | c.x = pc->x; |
3362 | c.y = pc->y; |
3682 | c.y = pc->y; |
|
|
3683 | |
3363 | if (map_projection(m) != pc->pro) |
3684 | if (map_projection(m) != pc->pro) |
3364 | { |
3685 | { |
3365 | transform_to_geo(pc->pro, &c, &g); |
3686 | transform_to_geo(pc->pro, &c, &g); |
3366 | transform_from_geo(map_projection(m), &g, &c); |
3687 | transform_from_geo(map_projection(m), &g, &c); |
3367 | } |
3688 | } |
|
|
3689 | |
3368 | sel = route_rect(18, &c, &c, 0, max_dist); |
3690 | sel = route_rect(18, &c, &c, 0, max_dist); |
|
|
3691 | |
3369 | if (!sel) |
3692 | if (!sel) |
|
|
3693 | { |
3370 | continue; |
3694 | continue; |
|
|
3695 | } |
|
|
3696 | |
3371 | mr = map_rect_new(m, sel); |
3697 | mr = map_rect_new(m, sel); |
|
|
3698 | //dbg(0, "sel lu=%d,%d rl=%d,%d\n", sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y); |
|
|
3699 | |
3372 | if (!mr) |
3700 | if (!mr) |
3373 | { |
3701 | { |
3374 | map_selection_destroy(sel); |
3702 | map_selection_destroy(sel); |
3375 | continue; |
3703 | continue; |
3376 | } |
3704 | } |
|
|
3705 | |
3377 | while ((item = map_rect_get_item(mr))) |
3706 | while ((item = map_rect_get_item(mr))) |
3378 | { |
3707 | { |
3379 | if (item_get_default_flags(item->type)) |
3708 | if (item_get_default_flags(item->type)) |
3380 | { |
3709 | { |
3381 | sd = street_get_data(item); |
3710 | sd = street_get_data(item); |
3382 | if (!sd) |
3711 | if (!sd) |
|
|
3712 | { |
3383 | continue; |
3713 | continue; |
|
|
3714 | } |
|
|
3715 | |
|
|
3716 | //dbg(0,"*type=%s\n", item_to_name(item->type)); |
|
|
3717 | |
3384 | dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos); |
3718 | dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos); |
|
|
3719 | |
3385 | if (dist < mindist && ((sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags || (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags)) |
3720 | if (dist < mindist && ((sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags || (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags)) |
3386 | { |
3721 | { |
3387 | mindist = dist; |
3722 | mindist = dist; |
3388 | if (ret->street) |
3723 | if (ret->street) |
3389 | { |
3724 | { |
… | |
… | |
3391 | } |
3726 | } |
3392 | ret->c = c; |
3727 | ret->c = c; |
3393 | ret->lp = lp; |
3728 | ret->lp = lp; |
3394 | ret->pos = pos; |
3729 | ret->pos = pos; |
3395 | ret->street = sd; |
3730 | ret->street = sd; |
|
|
3731 | |
|
|
3732 | //dbg(0,"*(N)type=%s\n", item_to_name(item->type)); |
|
|
3733 | /* |
|
|
3734 | struct attr street_name_attr; |
|
|
3735 | if (item_attr_get(item, attr_label, &street_name_attr)) |
|
|
3736 | { |
|
|
3737 | dbg(0, "*name=%s\n", street_name_attr.u.str); |
|
|
3738 | } |
|
|
3739 | else if (item_attr_get(item, attr_street_name, &street_name_attr)) |
|
|
3740 | { |
|
|
3741 | dbg(0, "*name=%s\n", street_name_attr.u.str); |
|
|
3742 | } |
|
|
3743 | */ |
3396 | //dbg(1, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, |
3744 | //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos); |
3397 | // item->id_lo, pos); |
|
|
3398 | } |
3745 | } |
3399 | else |
3746 | else |
3400 | { |
3747 | { |
3401 | street_data_free(sd); |
3748 | street_data_free(sd); |
3402 | } |
3749 | } |
… | |
… | |
3410 | if (!ret->street || mindist > max_dist * max_dist) |
3757 | if (!ret->street || mindist > max_dist * max_dist) |
3411 | { |
3758 | { |
3412 | if (ret->street) |
3759 | if (ret->street) |
3413 | { |
3760 | { |
3414 | street_data_free(ret->street); |
3761 | street_data_free(ret->street); |
3415 | // dbg(0, "Much too far %d > %d\n", mindist, max_dist); |
3762 | //dbg(0, "Much too far %d > %d\n", mindist, max_dist); |
3416 | } |
3763 | } |
|
|
3764 | |
|
|
3765 | //dbg(0,"return NULL\n"); |
|
|
3766 | |
3417 | g_free(ret); |
3767 | g_free(ret); |
3418 | ret = NULL; |
3768 | ret = NULL; |
3419 | } |
3769 | } |
3420 | |
3770 | |
3421 | return ret; |
3771 | return ret; |
3422 | } |
3772 | } |
|
|
3773 | |
|
|
3774 | |
|
|
3775 | |
|
|
3776 | static struct route_info * |
|
|
3777 | route_find_nearest_street_harder(struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc, int max_dist_wanted) |
|
|
3778 | { |
|
|
3779 | //dbg(0, "enter %d\n", max_dist_wanted); |
|
|
3780 | |
|
|
3781 | struct route_info *ret = NULL; |
|
|
3782 | int max_dist = max_dist_wanted; // was 1000 originally!! |
|
|
3783 | struct map_selection *sel; |
|
|
3784 | int dist, mindist = 0, pos; |
|
|
3785 | struct mapset_handle *h; |
|
|
3786 | struct map *m; |
|
|
3787 | struct map_rect *mr; |
|
|
3788 | struct item *item; |
|
|
3789 | struct coord lp; |
|
|
3790 | struct street_data *sd; |
|
|
3791 | struct coord c; |
|
|
3792 | struct coord_geo g; |
|
|
3793 | |
|
|
3794 | ret=g_new0(struct route_info, 1); |
|
|
3795 | mindist = INT_MAX; |
|
|
3796 | |
|
|
3797 | h = mapset_open(ms); |
|
|
3798 | while ((m = mapset_next(h, 2))) |
|
|
3799 | { |
|
|
3800 | c.x = pc->x; |
|
|
3801 | c.y = pc->y; |
|
|
3802 | |
|
|
3803 | if (map_projection(m) != pc->pro) |
|
|
3804 | { |
|
|
3805 | transform_to_geo(pc->pro, &c, &g); |
|
|
3806 | transform_from_geo(map_projection(m), &g, &c); |
|
|
3807 | } |
|
|
3808 | |
|
|
3809 | sel = route_rect(18, &c, &c, 0, max_dist); |
|
|
3810 | |
|
|
3811 | if (!sel) |
|
|
3812 | { |
|
|
3813 | continue; |
|
|
3814 | } |
|
|
3815 | |
|
|
3816 | //dbg(0, "sel lu=%d,%d rl=%d,%d\n", sel->u.c_rect.lu.x, sel->u.c_rect.lu.y, sel->u.c_rect.rl.x, sel->u.c_rect.rl.y); |
|
|
3817 | |
|
|
3818 | mr = map_rect_new(m, sel); |
|
|
3819 | |
|
|
3820 | if (!mr) |
|
|
3821 | { |
|
|
3822 | map_selection_destroy(sel); |
|
|
3823 | continue; |
|
|
3824 | } |
|
|
3825 | |
|
|
3826 | while ((item = map_rect_get_item(mr))) |
|
|
3827 | { |
|
|
3828 | if (item_get_default_flags(item->type)) |
|
|
3829 | { |
|
|
3830 | sd = street_get_data(item); |
|
|
3831 | if (!sd) |
|
|
3832 | { |
|
|
3833 | continue; |
|
|
3834 | } |
|
|
3835 | |
|
|
3836 | //dbg(0,"*type=%s\n", item_to_name(item->type)); |
|
|
3837 | |
|
|
3838 | dist = transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos); |
|
|
3839 | |
|
|
3840 | if (dist < mindist && ((sd->flags & vehicleprofile->flags_forward_mask) == vehicleprofile->flags || (sd->flags & vehicleprofile->flags_reverse_mask) == vehicleprofile->flags)) |
|
|
3841 | { |
|
|
3842 | mindist = dist; |
|
|
3843 | if (ret->street) |
|
|
3844 | { |
|
|
3845 | street_data_free(ret->street); |
|
|
3846 | } |
|
|
3847 | ret->c = c; |
|
|
3848 | ret->lp = lp; |
|
|
3849 | ret->pos = pos; |
|
|
3850 | ret->street = sd; |
|
|
3851 | |
|
|
3852 | /* |
|
|
3853 | dbg(0,"*(h)type=%s\n", item_to_name(item->type)); |
|
|
3854 | struct attr street_name_attr; |
|
|
3855 | if (item_attr_get(item, attr_label, &street_name_attr)) |
|
|
3856 | { |
|
|
3857 | dbg(0, "*name=%s\n", street_name_attr.u.str); |
|
|
3858 | } |
|
|
3859 | else if (item_attr_get(item, attr_street_name, &street_name_attr)) |
|
|
3860 | { |
|
|
3861 | dbg(0, "*name=%s\n", street_name_attr.u.str); |
|
|
3862 | } |
|
|
3863 | */ |
|
|
3864 | //dbg(0, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos); |
|
|
3865 | } |
|
|
3866 | else |
|
|
3867 | { |
|
|
3868 | street_data_free(sd); |
|
|
3869 | } |
|
|
3870 | } |
|
|
3871 | } |
|
|
3872 | map_selection_destroy(sel); |
|
|
3873 | map_rect_destroy(mr); |
|
|
3874 | } |
|
|
3875 | mapset_close(h); |
|
|
3876 | |
|
|
3877 | if (!ret->street || mindist > (max_dist * max_dist)) |
|
|
3878 | { |
|
|
3879 | |
|
|
3880 | //dbg(0,"no street found!\n"); |
|
|
3881 | |
|
|
3882 | if (ret->street) |
|
|
3883 | { |
|
|
3884 | street_data_free(ret->street); |
|
|
3885 | //dbg(0, "Much too far %d > %d\n", mindist, max_dist); |
|
|
3886 | } |
|
|
3887 | g_free(ret); |
|
|
3888 | ret = NULL; |
|
|
3889 | } |
|
|
3890 | |
|
|
3891 | return ret; |
|
|
3892 | } |
|
|
3893 | |
3423 | |
3894 | |
3424 | /** |
3895 | /** |
3425 | * @brief Destroys a route_info |
3896 | * @brief Destroys a route_info |
3426 | * |
3897 | * |
3427 | * @param info The route info to be destroyed |
3898 | * @param info The route info to be destroyed |
… | |
… | |
3919 | //// dbg(0, "enter\n"); |
4390 | //// dbg(0, "enter\n"); |
3920 | |
4391 | |
3921 | struct map_rect_priv * mr; |
4392 | struct map_rect_priv * mr; |
3922 | |
4393 | |
3923 | if (!priv->route->graph) |
4394 | if (!priv->route->graph) |
|
|
4395 | { |
|
|
4396 | return NULL; |
|
|
4397 | } |
|
|
4398 | |
3924 | return NULL;mr=g_new0(struct map_rect_priv, 1); |
4399 | mr=g_new0(struct map_rect_priv, 1); |
3925 | |
|
|
3926 | mr->mpriv = priv; |
4400 | mr->mpriv = priv; |
3927 | mr->item.priv_data = mr; |
4401 | mr->item.priv_data = mr; |
3928 | mr->item.type = type_rg_point; |
4402 | mr->item.type = type_rg_point; |
3929 | mr->item.meth = &methods_point_item; |
4403 | mr->item.meth = &methods_point_item; |
3930 | |
4404 | |
3931 | if (sel) |
4405 | if (sel) |
3932 | { |
4406 | { |
3933 | if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y == sel->u.c_rect.rl.y)) |
4407 | if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y == sel->u.c_rect.rl.y)) |
3934 | { |
4408 | { |
3935 | mr->coord_sel = g_malloc(sizeof(struct coord)); |
4409 | mr->coord_sel = g_malloc(sizeof(struct coord)); |
|
|
4410 | // xxx |
3936 | *(mr->coord_sel) = sel->u.c_rect.lu; |
4411 | *(mr->coord_sel) = sel->u.c_rect.lu; |
3937 | } |
4412 | } |
3938 | } |
4413 | } |
3939 | return mr; |
4414 | return mr; |
3940 | } |
4415 | } |