Jump to content

  • Log In with Google      Sign In   
  • Create Account

OmarShehata

Member Since 09 Feb 2012
Offline Last Active Aug 14 2014 08:46 AM

#5165557 2D Platformer Technique?

Posted by OmarShehata on 08 July 2014 - 09:20 AM

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. 

 

4070ad6f93.png

 

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:

 

Path-Finding.gif

 

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:

 

93e63aa017.png

 

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.

 

InfiniteMarioAI_Algorithm.large.png

 

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

 

5feda5f952.gif

 

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:

 

f26c0d01c0.png

 

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...

 

16583a09ab.png

 

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!




#4915400 Organizing and managing code?

Posted by OmarShehata on 21 February 2012 - 10:05 PM

Can't tell if you're being sarcastic here or not. But yes they are very valuable. An "assert(this);" can save you hours of debugging by simply pointing out that "this was null". An assert is not for USER ERROR, it is for the things that you are assuming are true. I.e. if you have a function that takes a string and the string must never be null... assert(string != null); can save you from going "FUUUUU". Especially since it tends to give you a nice stack trace, so you can find exactly where it's being called.


I was genuinely being grateful! I apologize if I came off as sarcastic.

Uh, asset tracking is rarely associated with the visibility of the asset, just its existence. When exiting your application you should attempt to do as little work as you have to, preferring just to clean up what needs to be cleaned up (i.e. resetting the resolution to default, maybe closing sockets, and saving any open files), and then just exit. Windows will tend to handle the rest.


That's actually a relief, so I don't need to remove every single variable and every single asset when closing.

Again, thanks for the speedy replies Washu! If you or anyone else still has any debugging and/or optimization "Gotcha's", feel free to post! Maybe others will benefit as well.


PARTNERS