func.calc_route() grinds the game into a halt, when player is in certain spots

[dille12]

The function does not work properly, since it finds infinite routes for some reason, so I just break the loop after certain amount of time. Usually it finds some route, but in certain spots (in Manufactory in top right corner) the zombies don't find any route so they try to calculate a new route every tick, grinding the game in to halt.

`def calc_route(start_pos, end_pos, NAV_MESH, walls): """ Calculates the shortest route to a point using the navmesh points """

if los.check_los(start_pos, end_pos, walls):
    return [end_pos]
dist_start = {}
dist_end = {}
for nav_point in NAV_MESH:
    point = nav_point["point"]
    if los.check_los(start_pos, point, walls):
        dist_start[los.get_dist_points(start_pos, point)] = nav_point
    if los.check_los(end_pos, point, walls):
        dist_end[los.get_dist_points(end_pos, point)] = nav_point
try:
    start_nav_point = dist_start[min(dist_start.keys())]
    end_nav_point = dist_end[min(dist_end.keys())]
except:
    return [end_pos]

complete_routes = []
routes = []
for conne in start_nav_point["connected"]:
    routes.append([start_nav_point["point"], conne])

while routes != []:
    if len(routes) > 200:   #sometimes continues infinetely, so the loop must be broken
        break
    route = routes[0]
    routes.remove(route)
    point = route[-1]
    point_2 = get_point_from_list(point, NAV_MESH)
    if end_nav_point["point"] in point_2["connected"]:
        route.append(end_nav_point["point"])
        complete_routes.append(route)

    else:
        for point_3 in point_2["connected"]:
            if point_3 in route:
                continue
            if route.copy() + [point_3] in routes:
                continue
            routes.append(route.copy() + [point_3])
shortest_route = {"dist" : 10000, "route" : []}

for route in complete_routes:
    route_ref = {"dist" : 0, "route" : route}
    last_pos = start_pos
    for point in route:
        route_ref["dist"] += los.get_dist_points(last_pos, point)

    if route_ref["dist"] < shortest_route["dist"]:
        shortest_route = route_ref

return shortest_route["route"]`

[mark-pippin]

I saw you pushed a temp fix. Will take a look. Had started to add some debug features to start isolating this issue.

[dille12]

The issue happens because over longer distances there are factorially more routes, and in certain starting conditions it couldn't find a route in time, so I just randomized the order of routes and made sure that it finds at least one route. The solution would be to add some algorithmic stuff to filter out some of the routes.

[dille12]

If you enable dev tools from settings and press middle mouse in game 4 times you can test out the navigation system

[mark-pippin]

nice - I have yet to investigate what that 'dev tools' option enables :D

[mark-pippin]

If this is sufficiently resolved for now [no longer game breaking] - I'll likely move on to something else.

[dille12]

Yeah I think it's enough