3 ms·

An interesting application of A* in a game context was a programmer who was faced with making the Computer opponents of a game in the early 2000s and what he ca

by djmips 3y ago

An interesting application of A* in a game context was a programmer who was faced with making the Computer opponents of a game in the early 2000s and what he came up with was an abstraction of the options the AI had in the game and used A* to find the closest distance in the graph. I thought it was pretty cool because it wasn't using A* in the traditional way of pathfinding the world but instead pathfinding in a representation of choices the computer could make where the shortest path represented a possible best strategy.

programjames 3y ago
This is basically how you win every CodinGame Spring/Fall Challenge, though you check many paths in parallel (beam search) instead of a single at a time (A*).
adanto6840 3y ago
One of the more common approaches to AI in games is called GOAP [0][1] (Goal Oriented Action Planning), and it essentially "selects" which action set using the same concept -- graph searching (typically using A*) the available options. 0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-a-r-with-goal-oriented-action-planning https://www.gamedeveloper.com/design/building-the-ai-of-f-e-... 1 - https://web.archive.org/web/20230804100329/https://alumni.media.mit.edu/~jorkin/goap.html https://web.archive.org/web/20230804100329/https://alumni.me... See also (not mine): https://github.com/agoose77/goap-resources https://github.com/agoose77/goap-resources
throwaway17_17 3y ago
I think the ability to use similar ‘planning’ algorithms for walking through a room, choosing an option for attack/defend/use item, which enemy to target, may account for some of the attribution of intelligence to game AI. Humans seem to think they and other humans put as much thought and think in similar patterns about wildly dissimilar activities like planning a route or weighting risk/reward or planning an event 6 months out. So the ability to encode a wide variety of ‘search space’ into an appropriate graph for use with a common algorithm lends a perceived verisimilitude to the AI’s thoughtfulness and near-personhood when immersed in play.

by djmips 3y ago

programjames 3y ago

This is basically how you win every CodinGame Spring/Fall Challenge, though you check many paths in parallel (beam search) instead of a single at a time (A*).

adanto6840 3y ago

One of the more common approaches to AI in games is called GOAP [0][1] (Goal Oriented Action Planning), and it essentially "selects" which action set using the same concept -- graph searching (typically using A*) the available options. 0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-a-r-with-goal-oriented-action-planning https://www.gamedeveloper.com/design/building-the-ai-of-f-e-... 1 - https://web.archive.org/web/20230804100329/https://alumni.media.mit.edu/~jorkin/goap.html https://web.archive.org/web/20230804100329/https://alumni.me... See also (not mine): https://github.com/agoose77/goap-resources https://github.com/agoose77/goap-resources

throwaway17_17 3y ago

I think the ability to use similar ‘planning’ algorithms for walking through a room, choosing an option for attack/defend/use item, which enemy to target, may account for some of the attribution of intelligence to game AI. Humans seem to think they and other humans put as much thought and think in similar patterns about wildly dissimilar activities like planning a route or weighting risk/reward or planning an event 6 months out. So the ability to encode a wide variety of ‘search space’ into an appropriate graph for use with a common algorithm lends a perceived verisimilitude to the AI’s thoughtfulness and near-personhood when immersed in play.