Hi! can anyone help me find a good path finding algorithm for a side scroller game? Can I use the A* algorithm? I can already implement A* on a tile based game but do not know how to implement it in a side scroller. How do I factor the gravity, current speed, acceleration etc? For example, an enemy wants to follow the player. How do I know where the nodes should be and what nodes are connected to each other (based on enemy's current speed, jump forc etc)

Thanks!

Is this a platform-style game?

Yes. It is like Super Mario and the enemy will follow you.

You could mark edges in your path graph as "jump here". After that it boils down to A* again.
You can probably auto find the edges that'll need the jump. Just look for edges that has "emptiness" under some or all of them.

-Morten-

There was a contest involving writing an AI to play Infinite Mario, I believe the source code for the entries is available. Those might give you some nifty ideas if you feel like digging through someone else's code.

Just an idea could be, if it is following the player at the exact spot/time (kinda like one of the last Rayman levels) then make your game remember the path the player took, and make the enemy do the same :) But I guess that only works if the enemy has to work like that :)

@MortenB
Are the "jump here" nodes already defined in the level? Can you please explain further your solution. I think your solution will work but I am having a hard time visualizing it. Thanks!

What I did was just A* as normal, with a "jump" flag on some node transitions (not the node itself but the edge between two nodes).
When the path came back, some had the jump flag set. When those were traversed I made the AI execute a jump.
I used a nav mesh and made the artists flag the jump nodes for me. They can be hard to detect with code.

For a Mario type game I expect you use points for nodes, connected by lines for edges. All you'd need to do is to have a flag for every line, and mark all the lines going up, or over holes with the jump flag.

-Morten-

@MortenB

How do you know where to put the nodes? Are they pre defined when the map loads? I think that the nodes will only be created when the enemy starts to think of a path towards the player. The first node will be the current position of the enemy and the end node will be the player's position. Given the source and destination, how do I create nodes in between? Thanks for helping!

The whole graph was pre-made by the artists in 3DSMax as a way to say "you can go here".
Some nodes were added that were marked as "when you get here jump" by the artists.

It looks something like this :

where the red rectangle is marked for jump, and the green/blue is the result from the pathfinder. When I get to the blue bit of the path, I make the AI execute a jump command.
Design/art were responsible for making sure that the AI could reach across and not fall off the edge.

-Morten-