next »

[knight]

How would you dynamically find paths in a platform game. I saw this recently in Geti's wonderful RobotvRobot(http://1bardesign.steamwise.org/rvr/) and I was wondering how you would attempt that sort of thing.

[BorisTheBrave]

Nice.

The robots seem smart enough to know that jumping is required, so there could be some analysis going on. But if I were doing it, I'd see if I could get waypoints to work.

[AMT]

I've been interested in this as well. A* is simple enough to implement, but I always wondered how you would combine that with figuring out how to jump from ledge to ledge.

[Evan Balster]

I wrote a system once that broke block-based platforms into a series of connected walkable lines.  From there the plan was to find one-way nodes representing jumps off 'ledges', and after that a graph-search algorithm like Dijkstra's would be easy to do.

[st33d]

This is how I did it:

https://github.com/st33d/red-rogue/blob/master/src/com/robotacid/ai/DungeonGraph.as

Doesn't tackle jumping though. For that you would have to implement nodes with a property suggesting a jump action.

[bateleur]

For that you would have to implement nodes with a property suggesting a jump action.

Or you could maybe have a multi-phase approach which tries jumping exhaustively, making a note of any location from which jumping takes you to somewhere which is either distant or unreachable via walking alone, then add nodes and edges based on the results?

[Evan Balster]

I wrote that last bit while I was waaay too tired.  The system so far was only "break blocks into walkable lines"; at the time I had no idea what I was doing.

[dcarrigg]

There's no reason you can't add additional data to your connectivity graph that you're going to run A* on. I'd throw in a couple extra values having to deal with jumping.

The other way to think about it is that there may be one solution to figuring out how to get to a given location on the map, but another way to move there.

[Anicho]

Amazing article for AI: http://www.ai-blog.net/archives/2008_07.html should cover a few concepts of basic ai and pathfinding some pro tips you should be able to adapt for any platformer...

In this case I would recommend cheating, place objects at the end of ledges that the game agents can pick up on and react based on how you want. For instance if there is a ladder the game agent walks past the ladder collides with your object and something tells it that it can go up... or in this case objects near the ledge that tell the game agent that it can jump but may fall off etc....its not really cheating I am sure its more of tweaking a system specific for your games needs.... good luck

[Lon]

Infinite Mario may be relevant to your interests: http://www.youtube.com/watch?v=DlkMs4ZHHr8
It wan an AI Mario playing competition.  Source code and other interesting links are available in the video description.

[increpare]

Amazing article for AI: http://www.ai-blog.net/archives/2008_07.html should cover a few concepts of basic ai and pathfinding some pro tips you should be able to adapt for any platformer...

Completely irrelevant for 2d platformers though...

[PompiPompi]

I think there are two issues here.
First, finding the shortest path, which is what A* is used for. Second, making the AI capable of jumping onto higher grounds and ledges. Which is unrelated to A*.
The second issue is dependant on the physics of your game, if your physics don't have a random element, you should be able to analytically calculate if and how an NPC can jump someplace. Of course, there might be numerical errors that make this less accurate.

For the shortest path, including jumps, you "simpley" need to adjust A*. The normal tile based A* would just have one step to four or less tiles that havn't been visited before.
In the new A*, you would need each step of the A* to try and walk in four directions, but in addition to these four direction, you add a "jump direction", which is the same as the 4 directions, only it allows you to skip tiles with a distance weight of 1(for instance).
Another adjustment you need to make for this algorithm is that now you can visit more than once the same tile, if that tile's distance is greater than your current distance weight.
It makes the algorithm more complex with possible hazards(endless iterations etc).
This is something to let you think about, I never implemeted such a modified A*, so take my advice with a grain of salt.

[st33d]

It's fairly simple to adapt A* when thinking about it.

All nodes connect downwards (falling). But only some nodes connect upwards (the range of a jump). When ever the path tells you to move to the next node, that node's position compared to yours tells you exactly what to do.

Below? Same height? Walk on. Above? Jump.

So if you want a character to jump up and right, simply connect a node diagonally upwards.

[Lon]

I agree with the others, I would attempt to implement an A* search.  A* search is complete (as long as one is using a consistent or admissible heuristic) and should always find a goal within a finite amount of time if a goal exists and is reachable in a finite amount of time (provided you have enough memory).