Looting Policy using Dijkstra.

Hello everybody! So, my suggestion is:

I don't know if you already use it, but as long as I could observe I think you are using a greedy approach (like the closest body) to select what body the bot should go loot. Since the bot usually don't have more than 10 bodies in it looting queue I think Dijkstra would work pretty fast and you always be sure that the bot is walking the best way it could. If you want we can study this case together @Lucas Terra.

Att. Gabriel

It actually makes a balance between distance and loot value. But it doesn't seem to be working very well. I'll redesign it...

Oh boy, it is definitly not using closest body, and sometimes i think it would be better.

to be honest my only dobut is wtf is Dijkstra


Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

@Wesker lets say bodies are the nodes and the distance between bodies are the edges of your graph, we can use dijkstra's algorithm to find the best looting order.
@Lucas Terra alright, thanks!

@Architect

I don't Dijkstra is exactly what we're looking forward to here. Dijkstra is meant to find the shortest path between 2 nodes. We want to find the shortest path that gets to all the nodes, which is what we'd call the Traveling Salesman Problem, which is NP-hard and doesn't really have a great solution. But ye, it can be solved fairly easily for the amount of nodes we usually have.

And yes, I obviously agree the way it is now is pretty stupid. I've actually been meaning to make a request like this for months.

Quote:

---

Originally Posted by Raphael

@Architect

I don't Dijkstra is exactly what we're looking forward to here. Dijkstra is meant to find the shortest path between 2 nodes. We want to find the shortest path that gets to all the nodes, which is what we'd call the Traveling Salesman Problem, which is NP-hard and doesn't really have a great solution. But ye, it can be solved fairly easily for the amount of nodes we usually have.

And yes, I obviously agree the way it is now is pretty stupid. I've actually been meaning to make a request like this for months.

---

A* is the canonical algorithm for finding the shortest path between two nodes, Dijkstra finds the shortest path from one node to every other node. Solving a TSP, while easily tractable at these problem sizes, is likely overkill since you're likely to be interrupted before completing the path. Either Dijkstra or a heuristic TSP solver would be a good starting point for designing a looting algorithm, but there should be looting modes that prioritizes high value corpses.

Quote:

---

Originally Posted by Raphael

@Architect

I don't Dijkstra is exactly what we're looking forward to here. Dijkstra is meant to find the shortest path between 2 nodes. We want to find the shortest path that gets to all the nodes, which is what we'd call the Traveling Salesman Problem, which is NP-hard and doesn't really have a great solution. But ye, it can be solved fairly easily for the amount of nodes we usually have.

And yes, I obviously agree the way it is now is pretty stupid. I've actually been meaning to make a request like this for months.

---

You right!? I forgot you must visit every node! xD I was thinking about 2 nodes, where you are right now and where is the next waypoint you should go. between it the position of loot bodies.

PS: omg, you guys have a TS? let me enjoy you, pls! I love computer stuff! xD