I'm trying to make AI for my 4-player party game. It's basically a series of minigames. You can see a preview of the gameplay here.

I've been tackling this problem for weeks, but it seems either there's very little information/technical guidance out there, or there's just generally no general solution. (I'm assuming the latter), I'll try to state my problem and the solutions I'm trying as briefly as I can.

The game uses box2d to simulate its physics, with slightly tweaked physics (for example I re-set the character's velocity every frame to apply my own universal friction independent of everything else)

The Problem

How do I implement efficient path finding in a game like this?

Attempt #1

My first attempt was to build a sort of "connectivity graph", given any walkable tile, what other walkable tiles the character can reach with one "step" (where step is defined as holding a specific set of keys for a certain time)

For example, you can see in the image below, he can either walk right, left or jump to these various tiles, or fall down.

Once that is good enough, it's trivial to run A* and come up with a path.

And it seems to work well in the general case:

However, this has a few problems.

Since all my nodes are "walkable" tiles. It can never jump up to hit a target in the air if it needed.

Since the nodes are all based on merely x and y (not taking into account acceleration and speed), it requires a lot of fudging to get it to work (for example, you can see it slows down between jumps, because it has to position itself correctly before making the jump).

It's pretty manual. I have to specify whether it can make the jump based on the tiles around it and whether there are any tiles that would block its path. The more restricting the checks are the more special cases it misses, and the more liberal it is the higher the risk it can get stuck.

It cannot make jumps like this:

Overall, it feels very restricted.

Attempt #2

So I took a look at the Mario AI and how it was done, since it seemed very similar to what I was trying to do.

It seems pretty solid, and the way he said it's made is that, instead of taking "steps" between tiles, it takes steps as in, what it should press the next frame, and where it will end up.

from this interview

So I did something like that, predicting the path given the current state and the key input

In this gif, it predicts the path if you keep the buttons pressed held

I thought I could then easily run this through an A*, and it will generate an awesome path.

I can't seem to figure out at all how to design the cost/heuristic for this. My heuristic is a simple euclidean distance of the node to the goal. As for the cost, I just made it a constant 1 for any and every stop, and this is what I'm getting:

This is the path generated by the A*, at every node it knows which key to press to reach the next one. It can jump on that pillar and get to the target. So far so good, works great! However...

It gets stuck for a really really long time. (This is stopped after a fixed time)

It would eventually find a path but the thing is, it's just searching way too many nodes. It keeps trying first to jump directly up, then to jump directly up, but just before hitting the tile, it goes right. That obviously doesn't work, it tries left, that doesn't work. It then tries 2 frames ago to do the same. It keeps doing this, so it never really reaches the goal.

Does anyone know where to go from here? How to fix this? How does Mario AI do it? Any insight there would be extremely helpful!

Thank you for your time and really sorry the post ended up being so long!

Hi, just give your path nodes attributes, like jump here, or walk here.

Also when controlling the character, make a position check and set back to the correct position instead of letting the character walk, like this :

if( x > node->x )x = node->x;

greetings, i hope this helps.

Since all my nodes are "walkable" tiles. It can never jump up to hit a target in the air if it needed.

Well, you dont need to handle every situation by the pathfinder. Eg if your entity is able to push an other object by jumping up to it, just determine the best jumping-start-tile, move to this tile by your pathfinder, and jump up to the object using the standard physics, then relocate to a close tile and continue like before.

Since the nodes are all based on merely x and y (not taking into account acceleration and speed), it requires a lot of fudging to get it to work (for example, you can see it slows down between jumps, because it has to position itself correctly before making the jump).

This is a problem of the entity controller you use, in other words, you control your entities by using forces/velocity (?) to move it around ? This is called dynamic controller. The alternative is a kinematic controller, which has better control and often uses the physics engine only for collision detection. Dynamic controllers are really hard to get right.

It cannot make jumps like this:

By the use of a kinematic controller (you code the movement path of the entity by hand) and adjustment to your waypoints (add extra edges for jumping left or right to an tile above) , you will be able to manage this too.

It gets stuck for a really really long time. (This is stopped after a fixed time)

Maybe it is not the best idea to use a physics engine to handle the collision between world and entity if you want to have these kind of special movement (jump up to a tile, but then do not fall through it). I would recomment to use the physic engine to help you to do the collision detection (check if entity at position X,Y collides with tile B), but to implement the collision response yourself, that is, use a kinematic controller and handle special movement actions yourself (eg. if jumping up, ignore tile A,B,C , until jump is completed etc.).

The first method you had really didn't look that bad. Sure some cases it didn't handle well, but do other people notice? As long as the AI can handle most of the cases, you might just shrug and say, "good enough". You could also cheat, and ensure that all levels work with the AI, ie, just get rid of the cases the AI can't do.

(I realize neither of those might be acceptable to you, but I think it's worthwhile to at least consider them, even if only briefly)

Ive seen this on a AAA project I was on once where there was a technical director of level design which was essentially a programmer affiliated with the gameplay progs. His job was to keep track of rules that limited what could abd could not be done within the game (safe distances between certain ingredients etc.)
He even updated gym level so all possibilities could be tested.
That being said, I am also curious as to whether this can be handled otherwise.

It looks like, for the first method, it might work if you just expanded the possible move set for the character to check, and perhaps widen the search a little. It gets a little specific, but it reminds me of games like Dawn of War \ Company of heroes, which basically have a set of moves that vehicles can make, like three point turns, and tries to overlay those over the tiles, and see which ones are valid to use or blocked, and then use the end position of the valid ones to continue the next search from.

EDIT: To expand further, for example, knowing all the methods of getting to a tile that is 2 tiles to the right, and 2 tiles up, just cycle through all the possible methods. So you end up with basically an array of moves for traveling from one tile to another, for each of the X tiles surrounding the jumper. Something like the surrounding 24 tiles. sort of vaguely similar to marco pinters 24 or 48 square directional search.

You might want to take a look at this answer:

http://gamedev.stackexchange.com/a/69929/16982

Thank you for the reply Ashaman! I hadn't thought about dynamic vs kinematic controllers. And I guess it just felt like the path finder had to control everything but yeah, it can just execute a direct action if the object it's chasing is within its vicinity, and otherwise it uses the path finder.

The first method you had really didn't look that bad. Sure some cases it didn't handle well, but do other people notice? As long as the AI can handle most of the cases, you might just shrug and say, "good enough". You could also cheat, and ensure that all levels work with the AI, ie, just get rid of the cases the AI can't do.

(I realize neither of those might be acceptable to you, but I think it's worthwhile to at least consider them, even if only briefly)

It looks like, for the first method, it might work if you just expanded the possible move set for the character to check, and perhaps widen the search a little. It gets a little specific, but it reminds me of games like Dawn of War \ Company of heroes, which basically have a set of moves that vehicles can make, like three point turns, and tries to overlay those over the tiles, and see which ones are valid to use or blocked, and then use the end position of the valid ones to continue the next search from.

EDIT: To expand further, for example, knowing all the methods of getting to a tile that is 2 tiles to the right, and 2 tiles up, just cycle through all the possible methods. So you end up with basically an array of moves for traveling from one tile to another, for each of the X tiles surrounding the jumper. Something like the surrounding 24 tiles. sort of vaguely similar to marco pinters 24 or 48 square directional search.

This confirms what I've had doubts about, that I was doing it too "manual" or hardcoded by giving it all these cases, but I guess it's a pretty legit method.

You might want to take a look at this answer:

http://gamedev.stackexchange.com/a/69929/16982

The answer basically says "Look at how Mario AI did it" and my question is, "I want to do it like Mario AI..how?"

I'm currently implementing the first method and it's actually playing well against a human player or against each other with a little tweaking. But I'm still thinking about doing something that searches steps in the future so it can allow for "unlimited interactivity in mid-air"

Maybe if instead of considering every possible step (left, right, up, up right, up left and no key) at each and every node. It just draws out a path from the current grid cell to the next. So it keeps left pressed until it passes 256 pixels, and same for other keys, and that would be the second node. This would VASTLY lower the search space, and of course lower its flexibility but I think by tweaking the grid size we may have something that would work great and be fast enough. Will have to experiment more with it.

Hi, someone has downvoted me without giving a reason, that is not nice.

Hi, someone has downvoted me without giving a reason, that is not nice.

That happens from time to time. It could be as easy as a misclick. The interface doesn't let you undo an upvote or downvote.

Just don't worry too much about the reputation system. It is broken, as evidenced by some awful members having decent scores.