Jump to content
  • Advertisement
Sign in to follow this  
CIJolly

How to get AI to recognise a hole or ledge

This topic is 4148 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!