• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
OmarShehata

2D Platformer Technique?

10 posts in this topic

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!

2

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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)

1

Share this post


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

Share this post


Link to post
Share on other sites

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.

Edited by ferrous
1

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0