From 269be26f06ff9506cf33da603342bb0963a3339c Mon Sep 17 00:00:00 2001 From: Aldrik Ramaekers Date: Mon, 25 Nov 2024 13:44:21 +0100 Subject: pathfinding improvement. close #9 --- src/world.c | 68 +++++++++++++++++++++---------------------------------------- 1 file changed, 23 insertions(+), 45 deletions(-) diff --git a/src/world.c b/src/world.c index 02563ec..db8ce7d 100644 --- a/src/world.c +++ b/src/world.c @@ -624,53 +624,31 @@ bool job_offer_has_ship_day(job_offer* offer, weekday day_to_find) static void world_find_location_deep(s32 depth, world_location* source, array* buf) { - world_location* current_source = source; - while (buf->length < depth) { - world_location* best_match = 0; - s32 attempt = 0; - - try_again: - best_match = 0; - attempt++; - s32 rand_conn = get_random_number(0, current_source->connections.length); - world_location* connection = *(world_location**)array_at(¤t_source->connections, rand_conn); - - bool already_in_path = false; - for (s32 c = 0; c < buf->length; c++) { - if (*(world_location**)array_at(buf, c) == connection) already_in_path = true; - } - - if (already_in_path && attempt < current_source->connections.length) { - goto try_again; - } - best_match = already_in_path ? 0 : connection; + retry:; - #if 1 - double best_match_distance = 0; - - for (s32 i = 0; i < current_source->connections.length; i++) { - world_location* connection = *(world_location**)array_at(¤t_source->connections, i); - if (connection == source) continue; - - bool already_in_path = false; - for (s32 c = 0; c < buf->length; c++) { - if (*(world_location**)array_at(buf, c) == connection) already_in_path = true; - } + double current_furthest_point = 0.0; + world_location* current_source = source; + for (int d = 0; d < depth; d++) + { + for (int i = 0; i < current_source->connections.length; i++) + { + s32 rand_conn = get_random_number(0, current_source->connections.length); + world_location* connection = *(world_location**)array_at(¤t_source->connections, rand_conn); + double dist = distance_between_location(connection, source); + if (dist < current_furthest_point) continue; - if (!already_in_path) { - double total_distance = fabs(connection->latitude - current_source->latitude) + fabs(connection->longitude - current_source->longitude); + current_furthest_point = dist; + current_source = connection; - if (!best_match || best_match_distance < total_distance) { - best_match_distance = total_distance; - best_match = connection; - } - } + array_push(buf, &connection); + break; } - #endif + } - if (!best_match) break; - array_push(buf, &best_match); - current_source = best_match; + if (depth != buf->length) { + buf->length = 0; + array_push(buf, &source); + goto retry; } } @@ -714,10 +692,10 @@ static void world_assign_new_job_offers(world* world) total_dist += distance_between_location(source, dest); } new_offer.total_distance = total_dist; - new_offer.reward = (u32)((JOB_OFFER_REWARD_PER_CONNECTION * location->reliability) * amount_of_connections-1); // -1 because source is is connection list. + new_offer.reward = (u32)(new_offer.total_distance * 2.1); // -1 because source is is connection list. - // lest assume most experienced drivers drive at 95km/h - double min_duration_hours = (new_offer.total_distance/95.0); + // lets assume most experienced drivers drive at 90km/h + double min_duration_hours = (new_offer.total_distance/90.0); double max_diration_hours = min_duration_hours * SHIPTIME_DURATION_MULTIPLIER_MIN; new_offer.duration_sec_min = (time_t)(min_duration_hours * 60 * 60); -- cgit v1.2.3-70-g09d2