How to get AI to recognise a hole or ledge
Author
I am making a 2D Super smash bros like game, and am ready to add AI. The AI is supposed to act like a player (eg, same abilities and moves), not like a drone (eg, walk left, then right, then left).
How do I allow the AI to recognise and avoid holes, or jump from platform to platform? I had a few ideas:
1. Have a hole definer on the level editor. When an AI collides with a hole's boundry object, it knows to jump. An extention of this would be to have each hole object associated with a number of landing nodes, so it knows where to jump to. The pros of this is that it would be easy and effective. The con is that it would take a lot of work on the level editing side of things.
2. The other way would be to have the AI able to figure out where a hole is. I would have it project a 45 degree ray downwards in front of it. If this collided with a platform, then it must be standing on one. If it didn't, then it is either in the air or standing on a ledge. It would then look for new platforms to jump to by projecting rays around, or by looking at the list of platforms to find a suitable one. The pros of this is that the AI will be able to automatically handle any level I make. The cons are that it is more difficult to implement and error prone.
Are there any other ways to handle this problem? It's easier for an AI to recongise the presence of something when it isn't defined by it's absense.
Those both sound good to me.
Alternatively, consider giving your AIs a form of "memory." As soon as the level is loaded, have them scan the floor they start on, looking for gaps. Then have them examine the data of the level to catalogue the location of platforms.
Have them store all this information within the object that embodies them. Then, whenever they're close to a ledge in their memory (whenever their AI processes "what to do next"), they can handle that - choosing to jump or stay on the platform they are.
Also, if they get sent flying, they can keep checking their memory, looking for the closest platform, and do whatever they can to try and make it there (so as not to fall off the level).
It's just what people do - look at the level when they start, to keep in mind what their environment is like. That way, they always know where the gaps and platforms are, and can react instantly to events with that knowledge already in hand.
If you have a small number of AIs in play at any given time (as I would expect for a Smash Bros type game), then this should be no problem.
Good luck!
Alternatively, consider giving your AIs a form of "memory." As soon as the level is loaded, have them scan the floor they start on, looking for gaps. Then have them examine the data of the level to catalogue the location of platforms.
Have them store all this information within the object that embodies them. Then, whenever they're close to a ledge in their memory (whenever their AI processes "what to do next"), they can handle that - choosing to jump or stay on the platform they are.
Also, if they get sent flying, they can keep checking their memory, looking for the closest platform, and do whatever they can to try and make it there (so as not to fall off the level).
It's just what people do - look at the level when they start, to keep in mind what their environment is like. That way, they always know where the gaps and platforms are, and can react instantly to events with that knowledge already in hand.
If you have a small number of AIs in play at any given time (as I would expect for a Smash Bros type game), then this should be no problem.
Good luck!
Quote:Original post by CIJolly
I am making a 2D Super smash bros like game, and am ready to add AI. The AI is supposed to act like a player (eg, same abilities and moves), not like a drone (eg, walk left, then right, then left).
How do I allow the AI to recognise and avoid holes, or jump from platform to platform? I had a few ideas:
1. Have a hole definer on the level editor. When an AI collides with a hole's boundry object, it knows to jump. An extention of this would be to have each hole object associated with a number of landing nodes, so it knows where to jump to. The pros of this is that it would be easy and effective. The con is that it would take a lot of work on the level editing side of things.
2. The other way would be to have the AI able to figure out where a hole is. I would have it project a 45 degree ray downwards in front of it. If this collided with a platform, then it must be standing on one. If it didn't, then it is either in the air or standing on a ledge. It would then look for new platforms to jump to by projecting rays around, or by looking at the list of platforms to find a suitable one. The pros of this is that the AI will be able to automatically handle any level I make. The cons are that it is more difficult to implement and error prone.
Are there any other ways to handle this problem? It's easier for an AI to recongise the presence of something when it isn't defined by it's absense.
What I would do is 1), but automatically pregenerated. Just run a simple terrain analysis algo that will find those "nodes" (often called navigation links), and allow the level editor to edit the generated content for tuning. Should be pretty easy, adding a node at each end of any ledge, and linking those that are close enough together. But 2) should be fine too, with the correct math.
My choice would strongly depends on the type of AI you want to use, specifically the temporal horizon of it.
Your 2d platformer is probably tile map based, why bother with a ray? If the tile in front of the character isn't solid, he's standing at a ledge. Keep checking the tiles until you find a solid one, then you know how far to jump. If you have some ledges that are allow to be walked off, then you can scan down, and if you don't find any solids, then you have a ledge. Also, if you want him to seem more human, add a random modifier to the jump distance, either shorter (rare) or more. That way, they can miss the jump sometimes, like a human player!
You could choose the platform within some distance of the character which is closest to their destination and then move or jump appropriately to try to reach it. Cover every platform with pathing nodes and use this list of nodes to find a spot to move towards. Spatial data structures could speed this up if necessary. Moving platforms are handled by moving the nodes with the platforms. It is easy to automatically generate these nodes for static geometry since they just go above every platform. Instead of trying to avoid holes, the AI simply goes towards platforms.
You have the issue of the traditional tradeoff between offline design then storage of the solution versus online computation. Memory vs CPU.
If the level is designed offline then I'd precompute the solution. It's more work initially, but will lead to substantially better in-game performance and requires very little memory (particularly if you use some smart storage methods).
If the level is generated on the fly, then you'll need to do a dynamic analysis of the terrain to determine which tiles are walkable and which are holes. When a hole is discovered, do a simple range search (find all objects of a certain type within a certain constraint... in this case, all landing tiles within the maximum jumping distance) and then choose one (at random, closest, farthest, etc.).
Cheers,
Timkin
If the level is designed offline then I'd precompute the solution. It's more work initially, but will lead to substantially better in-game performance and requires very little memory (particularly if you use some smart storage methods).
If the level is generated on the fly, then you'll need to do a dynamic analysis of the terrain to determine which tiles are walkable and which are holes. When a hole is discovered, do a simple range search (find all objects of a certain type within a certain constraint... in this case, all landing tiles within the maximum jumping distance) and then choose one (at random, closest, farthest, etc.).
Cheers,
Timkin
I would have to go with the pre-computed analysis in level design. Imagine that a level could be played over and over hundreds of times - why recalc the same analysis each time only to come up with the exact same data? One hybrid of this is to create a system that analyzes the designed level automatically (like a live-time system) but then STORES it during testing? Now your designers didn't have to do any extra work - an analysis algorithm did it for them when they saved the level.
As a caveat, one thing about precalcing landing points and jumpable gaps (either across or up) is that it doesn't allow for differing abilities of AI agents very well. i.e. If you say "this gap is jumpable", you make it that way for all AIs. What if one AI character doesn't jump well? You can pre-code distance and direction measurements instead of a yes/no solution, however. A character, knowing its own abilities, can check the precompilied map to see if a particular gap is in its range and to even be considered.
As a caveat, one thing about precalcing landing points and jumpable gaps (either across or up) is that it doesn't allow for differing abilities of AI agents very well. i.e. If you say "this gap is jumpable", you make it that way for all AIs. What if one AI character doesn't jump well? You can pre-code distance and direction measurements instead of a yes/no solution, however. A character, knowing its own abilities, can check the precompilied map to see if a particular gap is in its range and to even be considered.
Author
OK, it sounds like precalculating the nodes is the way to go, rather than having the ai "look" for holes.
The game isn't tile based, the levels are polygonal. One thing I was worried about was how to make the AI recognise it can jump on physically dynamic platforms (see-saws, hanging bridges, etc). It should be fairly easy to generate jumping nodes on the tops of those objects on the fly, and loop through the list every few frames to see which nodes can lead to each other.
Thanks for the input all!
The game isn't tile based, the levels are polygonal. One thing I was worried about was how to make the AI recognise it can jump on physically dynamic platforms (see-saws, hanging bridges, etc). It should be fairly easy to generate jumping nodes on the tops of those objects on the fly, and loop through the list every few frames to see which nodes can lead to each other.
Thanks for the input all!
I would use a Low tech solution: Your first idea.
Manually put a "this is a hole you can fit through" entity there. Easy. Extend this to computationally scanning for holes before the level is loaded. The ai then knows by the size of the hole, how far it has to jump, because the entity contains that data.
Manually put a "this is a hole you can fit through" entity there. Easy. Extend this to computationally scanning for holes before the level is loaded. The ai then knows by the size of the hole, how far it has to jump, because the entity contains that data.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
