Signup Now
Results 1 to 8 of 8
  1. #1
    Free User Architect's Avatar
    Join Date
    Feb 2017
    Posts
    36
    Reputation
    10
    Rep Power
    0

    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

  2. #2
    Administrator Lucas Terra's Avatar
    Join Date
    Dec 2013
    Location
    Brazil
    Posts
    2,202
    Reputation
    141
    Rep Power
    10
    It actually makes a balance between distance and loot value. But it doesn't seem to be working very well. I'll redesign it...

  3. #3
    Wind Tester
    Join Date
    Dec 2013
    Location
    Warsaw, Poland
    Posts
    2,578
    Reputation
    149
    Rep Power
    27
    Oh boy, it is definitly not using closest body, and sometimes i think it would be better.

  4. #4
    Free User Wesker's Avatar
    Join Date
    Dec 2013
    Posts
    462
    Reputation
    -65
    Rep Power
    0
    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.

  5. #5
    Free User Architect's Avatar
    Join Date
    Feb 2017
    Posts
    36
    Reputation
    10
    Rep Power
    0
    @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!
    Last edited by Architect; 02-17-2017 at 12:27 AM.

  6. #6
    Moderator Raphael's Avatar
    Join Date
    Dec 2013
    Location
    raphseller.com
    Posts
    2,440
    Reputation
    283
    Rep Power
    27
    @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.
    Last edited by Raphael; 02-18-2017 at 02:40 PM.
    RaphSeller
    PayPal Instantaneous Reseller


    raphseller.com

  7. #7
    Free User shAdOwArt's Avatar
    Join Date
    Apr 2015
    Location
    Kharos
    Posts
    189
    Reputation
    151
    Rep Power
    19
    Quote Originally Posted by Raphael View Post
    @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.

  8. #8
    Free User Architect's Avatar
    Join Date
    Feb 2017
    Posts
    36
    Reputation
    10
    Rep Power
    0
    Quote Originally Posted by Raphael View Post
    @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
    Last edited by Architect; 02-19-2017 at 04:26 AM.

 

 

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •