ATM. every npc has a list with all nodes within the distance of the npc to the target(player).
Sorted that list on distance, so closest is first. Well this is where my understanding of grabbing those items ends.
At this point the npc follows last entry in list to the closest node near player list.pop(-1), then to player itself. But it goes trough every node within that distance, while i want it to follow the shortest path to the player with those nodelist.
Mine is grid based so it’s a little different (plus it’s still a WIP), but here’s how I do.
Get list of adjacent tiles
Loop thru the list, get distance to starting point and goal
Build a dict. reach = {“nodes”:list of tiles,“dist”: list of tuples (dist1,dist2) }
Pass the dict to a function that determines which point is closer.
#(...)
index_min = min(range(len(reach["dist"])), key=reach["dist"].__getitem__)
nearest_point = reach["nodes"][index_min]
nearest_dist = reach["dist"][index_min]
i = 0
#-------
for point in reach["nodes"]:
node,dist = reach["nodes"][i],reach["dist"][i]
#-------
# dist[0] = distance to start. dist[1] = distance to goal
# I initially got which tuple the sum of is a smaller number
# for now I check if another node is closer to the end
# absolutely **not** optimal in some situations involving obstacles,
# working on a better solution at the moment.
if (dist[1] < nearest_dist[1]):
nearest_point = node
nearest_dist = dist
#-------
i += 1
return nearest_point
Repeat until we find a path to the goal or realize the goal is unreachable (but that’s another story c:)
Thing you could try with nodes, is linking them together – e.g., node A to B, C to B, B to AC.
So then you can build path out of a list of neighboring nodes.
Tricky part might be building this list programmatically; unless you use meshes.
Then you can just check if two vertices share the same coordinates and be done with it.
How BPR manages to pull off that sweet black magic is anyone’s guess c:
There’s a whole lot more going on with my code (setting up the grid, evaluating whether a path is viable, excluding tiles that lead to dead ends, aborting the search if there’s no way to reach the end goal, etc), I had to simplify the example quite a bit.
The pathfinding itself is just around 150~ lines total, but since it’s dependent on other systems (and written with those systems in mind) it’d take some rewriting to make it work on a different environment, so I just shared the basic idea behind it. I can send you the whole thing later if you want to take a look at it anyway.
i got stuck figuring out how to even find the closest point. Now if i am right i can just implement the suggestion you said with the distances, and calculate the shortest path, because i already got all the nodes between the start- and endpoint.
And that is exactly what i needed. If i try to hard i get tunnel vision and getting stuck on a few ways and always end up the same. This example let me look at it from a different way then i was trying.
