Algorithm for picking up items
Author
I'm working on another game. It's 2D and played from a top down perspective. When you kill enemies, they drop items, and what I want to do is have autonomous helpers that pick up items for the player, and I'm trying to figure out a clever algorithm to do so.
With one helper, the algorithm seems clear - continuously grab the closest item to the helper (assuming that the helper is agnostic to the value of items), and when full, or there are no more items, return to the player. I could make it a bit more clever by having it return to the player if its path comes near the player, but that seems secondary.
With multiple helpers, I want to divide them up so that they don't go after the same items. For example, if there was one clump of items at the top left of a square level, and one clump at the bottom right, one would go to each corner (even if each item in the one corner was closer than any item in the other).
Anyone done anything like this?
You might consider a simple blackboard system at the 'team' level. When a helper decides to collect an item, it writes this intention in the blackboard. This means that other helpers can check for this before making their own decisions, and if they see that an item is already going to be picked up by someone else, they can ignore that one and pick another.
Bonus points for going one step further and having the helpers negotiate over which item they should pick based on proximity etc.
Bonus points for going one step further and having the helpers negotiate over which item they should pick based on proximity etc.
Keeping it short... i hope you have path finding algorithm. Just assign the items as so:
equation assignment for each npc: # % (# of items free to pick left)
Optimize by assigning the closest one (distance wise). Better but more costly would be to have a a predictive path finding (walk the path) and shortest path is assigned to npc.
Good Luck
equation assignment for each npc: # % (# of items free to pick left)
Optimize by assigning the closest one (distance wise). Better but more costly would be to have a a predictive path finding (walk the path) and shortest path is assigned to npc.
Good Luck
Author
Quote:Original post by Kylotan
You might consider a simple blackboard system at the 'team' level. When a helper decides to collect an item, it writes this intention in the blackboard. This means that other helpers can check for this before making their own decisions, and if they see that an item is already going to be picked up by someone else, they can ignore that one and pick another.
Bonus points for going one step further and having the helpers negotiate over which item they should pick based on proximity etc.
Well, the problem was that I wanted them to go after different clumps of items, not just other items. The more I think about it, the more I'm convinced that the optimal solution to this is NP-Complete.
However, I misread blackboard in your post as checkerboard, and here's what I did:
The level is divided up into a grid, each grid is aware of which items are on it. Helpers mark a checkerboard as theirs (along with all of the items on it). Each helper finds its own checkerboard, taking an empty one (or the one with the most items on it per helper assigned if there are more helpers than squares with items on them. This way, in the example case, the helpers should go to opposite ends of the map (I think I'll make it more intelligent and have it consider the adjacent squares as well).
When you're deciding which item to aim for, perhaps you could take into account not only proximity to your agent, but proximity to the destinations of other agents. That is, when assessing merit, you penalise items that are within whatever range of another agent's destination.
Author
Quote:Original post by jack_1313
When you're deciding which item to aim for, perhaps you could take into account not only proximity to your agent, but proximity to the destinations of other agents. That is, when assessing merit, you penalise items that are within whatever range of another agent's destination.
That's a really good idea too! It could be more ad-hoc this way - "closest" defined now by distance less penalties.
These bots could be the coolest part of the game! :)
Think in terms of multi-layered influence maps. I see 3 layers.
Bonus for proximity radiating out from starting location.
Squares with items have a pull.
Squares "claimed" by the other bot(s) have a push
Lay them out in that order. Remember that you only need do the first and second plys once. The first step can apply to both bots. The second needs to be on respective copies of the map so that each bot has its own version of this map.
Then, you have them take turns claiming a square, rerunning the 3rd ply between each claim. You don't need to rerun the entire map, just the squares affected by a claim... that is, you simply propagate that "push" in the claimed square and others around it to whatever radius you are using. The claim for each bot each turn will be the next-highest rated, unclaimed square. Notice how the highest rated square per turn will be a combination of the squares with items, that are closest, but also farthest away from where the other bot is claiming.
The result will be that the 2 (or more) bots will diverge from the starting location.
You can push the squares onto a queue in the order you claim them (and process them in that order) or you can just reevaluate when you get to each square and pick up items there.
Bonus for proximity radiating out from starting location.
Squares with items have a pull.
Squares "claimed" by the other bot(s) have a push
Lay them out in that order. Remember that you only need do the first and second plys once. The first step can apply to both bots. The second needs to be on respective copies of the map so that each bot has its own version of this map.
Then, you have them take turns claiming a square, rerunning the 3rd ply between each claim. You don't need to rerun the entire map, just the squares affected by a claim... that is, you simply propagate that "push" in the claimed square and others around it to whatever radius you are using. The claim for each bot each turn will be the next-highest rated, unclaimed square. Notice how the highest rated square per turn will be a combination of the squares with items, that are closest, but also farthest away from where the other bot is claiming.
The result will be that the 2 (or more) bots will diverge from the starting location.
You can push the squares onto a queue in the order you claim them (and process them in that order) or you can just reevaluate when you get to each square and pick up items there.
Dave, I would like to politely challenge your suggestion.
I'm think influence maps might be overcomplicating the problem. In this case we're only interested in the squares that contain items. At that, we are really only interested in the locations of the items, and working with them in grid square cells is probably an unnecessary abstraction in the first place. Creating and annotating an influence map seems like a waste of time because most of the information will go unused. We're not performing any sort of tactical reasoning or weighted path finding here. We want to make comparisons between the locations of items only, and not every area on the playing field.
Instead, I think it is probably better just to loop through the items and assign each one a value based on the ideas presented above (trying to get to the closest items while avoiding proximity to other agents' targets), and choosing the best one as such. This is would serve the same task as an influence map, without the unnecessary processing of places that we don't actually care about.
I am open to discussion if you think I am mistaken.
I'm think influence maps might be overcomplicating the problem. In this case we're only interested in the squares that contain items. At that, we are really only interested in the locations of the items, and working with them in grid square cells is probably an unnecessary abstraction in the first place. Creating and annotating an influence map seems like a waste of time because most of the information will go unused. We're not performing any sort of tactical reasoning or weighted path finding here. We want to make comparisons between the locations of items only, and not every area on the playing field.
Instead, I think it is probably better just to loop through the items and assign each one a value based on the ideas presented above (trying to get to the closest items while avoiding proximity to other agents' targets), and choosing the best one as such. This is would serve the same task as an influence map, without the unnecessary processing of places that we don't actually care about.
I am open to discussion if you think I am mistaken.
Sure... overall a full influence map is overkill. I was adapting a method for doing exploration of unknown area. In this case, as you mentioned, you only need annotate the actual items.
That's what I get for posting off the cuff on a long weekend. I was honestly trying to do something other than work on my slides for my GDC AI Summit lecture. *sigh* The funny thing is, the panel I'm on is about choosing the right tool for the job. Hehe... Guess that's what we're doing, eh?
That's what I get for posting off the cuff on a long weekend. I was honestly trying to do something other than work on my slides for my GDC AI Summit lecture. *sigh* The funny thing is, the panel I'm on is about choosing the right tool for the job. Hehe... Guess that's what we're doing, eh?
Quote:Original post by mdkessQuote:Original post by Kylotan
You might consider a simple blackboard system at the 'team' level. When a helper decides to collect an item, it writes this intention in the blackboard. This means that other helpers can check for this before making their own decisions, and if they see that an item is already going to be picked up by someone else, they can ignore that one and pick another.
Bonus points for going one step further and having the helpers negotiate over which item they should pick based on proximity etc.
Well, the problem was that I wanted them to go after different clumps of items, not just other items. The more I think about it, the more I'm convinced that the optimal solution to this is NP-Complete.
Use something like k-means to cluster the items into one clump per helper.
Then have the helpers claim one clump each.
Each helper can use a simple greedy algorithm to collect the items within the clumps.
I think this will work fine.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement