2D Platformer Technique?

Omar Shehata · 2014-07-15T04:13:48

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!