The hunt for the ULTIMATE PLATFORMER AI!

Chat about anything not covered in these forums, but keep it civil!

Post » Tue Apr 15, 2008 10:46 pm

Hi! In the planning of my adventure platformer i've been looking around for various types of plattformer AI methods. I've learned one thing all really good plattformer AI's have in common. They don't exsist. Let me explain futurer.

What is a really good platformer AI to me? Well, the ultimate AI is an enemy with editable running speed and jump strength that you can put into a level, tell it where to go, and it will find the fastest way to get there. If you can acomplish that it will be easy to expand the AI to whatever you want it to be.

An AI usually works with different "routines". One routine would for example be "Idle" Where the enemy is just standing still. Common in platformers is to have an Idle routine, and when the player is in the line of sight you activate the Walking routine to chase the player. Well, if this ultimate AI was created we could have routines like

:D ON GUARD: The enemy is searching for clues of where the player might be (for example the sount of the player landing on the ground with a certain speed) and when he get one the "go-to spot" is set to that position!

:D SEARCHING: The go-to spot is set at random positions close to where the AI saw/heard the person for the last time.

:D HUNTING: The enemy is hunting the player, allways setting the Go-to to where he last time saw the player. If the player disappears behind something, the enemy moves to that spot and then switch to searching to explore the area futhurer.

It would also be possible to for example make the enemies able to call for backup. The go-to points of all enemies in a large area would be set to where the first enemy is. Or instead of calling for help the enemie could run to the closest friend before he tries to attack you. It's lika a clich in "Game-making-idea-talk" but THE POSSIBILITIES ARE ENDLESS!!!

I've looked arount for different methods, and the closest one so far was using nodes. Little clues that are spread around the level to help the AI's to find it's way. That however is not really what i'm looking for, since it requires lots and lots of time, and whenever you change anything in the level you have to replace the nodes.

I have some ideas that theoreticaly should be possible, but before i start my explanation i would like to hear your thoughts about this. Does anybody know a good method to create the ultimate platformer AI? Have you seen any articles/tutorials on the subject (not just AI, but this kind of AI)? Do you have any ideas how to solve it?

Every help in the hunt for the ultimate platformer AI is appreciated!

Attan
B
8
S
2
G
5
Posts: 744
Reputation: 3,288

Post » Tue Apr 15, 2008 11:00 pm

I've never come up with my own engine, but an idea: I think nodes are the way to go. If you don't want to go round placing nodes at the edges of all your platforms, then come up with a way of automatically detecting platform edges: place a detector on the floor in front of the object in the direction its heading. When this detector is NOT overlapping anything solid, you must have come to the edge of a platform - so you can set off a jump. This would allow your AI to jump over gaps instead of dumbly charing off the edge in to the abyss, and it's node-free.
Scirra Founder
B
359
S
214
G
72
Posts: 22,946
Reputation: 178,468

Post » Tue Apr 15, 2008 11:10 pm

Well, that's a small step in the right direction, but what i'm thinking of is something far more complex.

Imagine a scenario like this:



The enemy (red) should be able to find it's way to the player, not just running in the direction of the player. Also, the computer should be able to figure out that the blue path is not the best way, since it not the shortest.
B
8
S
2
G
5
Posts: 744
Reputation: 3,288

Post » Tue Apr 15, 2008 11:39 pm

The biggest, baddest supercomputer in the world would have trouble figuring that out. Even things like Darpa vehicles with AI pathfinding algorithms to avoid obstacles are still programmed with GPS coordinates and detailed map routes.

Computers are stupid. You need to tell them what to do. Basically, you need those nodes, or pre-mapped routes, or whatever. All game AI is a cheat. So just cheat.
Moderator
B
5
S
2
G
6
Posts: 4,348
Reputation: 10,971

Post » Wed Apr 16, 2008 12:59 am

Well.. That's a little pessimistic i think. Her's what i'm thinking.


When I first encountered the problem I didnt really knew how I should think. I had seen examples before, but they all looked so complicated and illogical. I thought How would I do in that situation? I imagined myself In a room with ledges and obstacles, and a goal I had to reach. Well, I would start looking for a way to get up on one of the ledges. If I saw somewhere where I could climb up I would look if it was possible to continue from that position. I would keep exploring the environment with my eyes until I found a path leading all the way, then I would try to make it through that path.

Ok, to make the computer do this we would need something that is the computers "Imaginary self" running through the level searching for paths. So every second or so the computer spit out two of these:

The purple things are what's going to be detectors, carefully placed and stretched depending on the players jump strenght, max speed and current speed, checking for every posibility to jump up on something, down to something, or over something. This little dude is run with the same platform movement engine as the actual enemy, only it is run by loops, in infinite speed.

So what happends now. Take a look at this picture.


At first, the enemy send one helper in each direction. The helper to the left run straight into the wall, and is destroyed (1). The second one is looped forward until its detectors tell him there is a ledge in front of him, low enough to reach (2). Now the helper clone himself, and the new helper jump up on the ledge. The second one keeps running forward and is destroyed by the wall.
The only helper left now is the one on the top of the first little hill (3). He's now detecting one ledge on each side of him, and he duplicates himself two times sending one in each direction. He keeps running forward, and crashes into the wall (4). The helper going left finds another platform to the right of him, clones himself and runs forward (5). All helpers leave a trace behind them, so when When he comes close to the ground (6) he finds the trace of another helper. That means someone has allready been there, so the helper is destroyed. The one who survived by going right finds a new ledge to the left and sends one of his clones up there (7). As he continue going forward he will collide with a helper who's parents went right at number 3 (8). They will both be destroyed since they know both paths have been explored by the other one. One thing i can't really imagine though is how it would be possible to detect situations like the one at number 9. maybe he could like "throw " detectors in diferent speeds and see if anyone of them collide with something. In this situation he would find him anyways by just running forward.

Well, we finally found him!

For this to work, this whole process of finding the player should be one big loop that should run once every second or so without ever being noticed, allways updating the best path to the player. The information about which path is best should be stored somewhere, and the enemy should just have to take the exact same way as the one succesfull helper.

It would be one hell of a challange, but it has never been done before, so it would be an absolute revolusion to the platform games!
B
8
S
2
G
5
Posts: 744
Reputation: 3,288

Post » Wed Apr 16, 2008 1:05 am

I think you could actually calculate the direct, quickest route to the player from anywhere with any configuration of platforms using a modified version of the A* pathfinding algorithm. It'd definitely be tricky, but by setting cells which you cannot reach by jumping to an infinitely high "cost" to traverse (ie. impassble), generating special one-way cells for jumping off ledges etc, you could return a list of nodes that lead to the player. The next challenge would be to make the player jump and run accurately through all these nodes...

Definitely to go in a behavior! That'd be tricky to event.
Scirra Founder
B
359
S
214
G
72
Posts: 22,946
Reputation: 178,468

Post » Wed Apr 16, 2008 1:15 am

The point of this is not to find the quickest way. It is that the helper is actually preforming each jump with the same platform movement engine as the enemy. If then the enemy does exactly the same in the same position he will be guaranteed to make it. The helpers would have their detectors positions calculated from the enemies jump strenght and speed, to be sure the jump is preformed successfully.
B
8
S
2
G
5
Posts: 744
Reputation: 3,288

Post » Wed Apr 16, 2008 8:59 am

[quote="Ashley":1bolpumt]
Definitely to go in a behavior! That'd be tricky to event.[/quote:1bolpumt]

Wait a minute... are you seriously going to put this into a behavior :shock:
B
8
S
2
G
5
Posts: 744
Reputation: 3,288

Post » Wed Apr 16, 2008 4:03 pm

A* path finding is definatly the way to go. I think I have thought of a way this can be tackled as well, will try and demonstrate it when I get home today.
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,887

Post » Sat Apr 19, 2008 7:39 pm

I found a flash game which makes enemies jump on platforms to arrive to the player.

http://www.newgrounds.com/portal/view/323678

You could contact the creator.
B
2
S
2
G
5
Posts: 512
Reputation: 2,674

Next

Return to Open Topic

Who is online

Users browsing this forum: No registered users and 3 guests