Sign in to follow this  

An easy approach to platformer pathfinding

This topic is 1111 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a platformer game right now where I wanted enemies to really feel like the computer was trying to kill you. Not like, "oh, you went too far away or you climbed on that moving thing I don't know how to use, later..." I had some complicated ideas about fitting a curve to a weighted space, but didn't want to spend a large chunk of development time on research. The method I implemented to get the human-like AI I needed is as follows (also, I should mention, if you're interested, the game is called Nomera: we have a website www.dotstarmoney.com and a twitter @DotStarMoney):

 

As a preamble, the game uses a custom physics engine and all surfaces are represented by circles or line segments. Moving platforms can either rotate at a speed following a periodic function, follow a periodic path, or be toggle-able via switch.

 

1) The engine splits the level up into "nodes," or, a surface that an AI could visit in its entirety just by walking. These constitute flat static surfaces that could have slopes but no breaks or (all of) moving platforms, this is done when a map is loaded.

 

2) If in recording mode (press a key, 'M' in this case), the game tracks the node that you stand on. AS SOON AS you jump, or fall off of a static surface, the engine starts recording your keypresses. In recording mode, the players object properties are set to those of the enemy paths you wish to record (so in my case, I want to record soldier movement, so the engine sets my mass, collision shape, friction, etc... to that of the soldier). AS SOON AS you land on a STATIC surface, the recording is finished and the engine stores the path between the two static surfaces and the recorded per-frame key presses.

 

For moving objects, the game also records the cyclic_time of the object, that is, the point in its periodic movement (or start point/end point if a toggle) of the moving platform. The path will only be recorded if the moving platforms traversed have periods that are a small (< 4) integer multiple of each other.

 

As a developer, its my job to jump around for a bit, record some good paths, delete some if they're bad (these realtime functionality to do this), and make sure the enemy has options.

 

9JQtXym.png?1

A screenshot of some recorded paths(edges).

 

3) With a whole bunch of stored pathing (this works as you record too!), if an enemy needs to get from point A, to B, where B can be you/close enough to you to shoot/something to investigate/a switch for a moving platform, he runs Djikstra's algorithm on the node graph, keeping track of where he ends up on the node after each edge to ensure he takes the fastest of the possible edges where two nodes have multiple connecting edges. For the easier enemies, they're barred from taking paths where sprinting is involved or random weights are distributed during the graph routing.

 

4) With the path in hand, an enemy will alternate, walking/running along a node to reach the start of the edge he must take, if he needs a running start, he'll instead try to get to a point where he can build up the correct speed. Once an edge is reached at the proper position/velocity (within a teeny tolerance, about half of one pixel for position and half of pixel/second for veloctiy), the enemy snaps his position/velocity to the edges start position/velocity and as I like to call it, runs "Jesus take the wheel." The recorded inputs take over and move the enemy to the next node to repeat the process.

 

In the case where an enemy must take a moving platform, he'll stand at the node waiting for the cyclic_time of the platform to line up to the recording (this is why multiple platforms must have periods that are multiples of one another) before he takes the edge, handing control over to the recorded edge movement.

 

5) Thats it! This logic is packed into a few routines and they're used by the enemy logic for the fun programming (actual behavior). Heres a gif of some pathing in action:

 

Ynhun7J.gif

These dipsticks were set to "hug" mode, where they

must reach the target and get real close at all costs.

 

I can make a more interesting vid if desired, this is just what I created from a level I'm working with right now. Thanks for reading!

Edited by DotStarMoney

Share this post


Link to post
Share on other sites

It reminds me of how some bots (quake bots ?) work. They build up a level waypoint graph by analsying the player's movement/action. A good idea would be to merge nodes and refine the graph with each play through. Instead of using Djikstra for pathfinding, I would recommend to use A*, if you need to get from A to B.

 

Nevertheless good work, keep it up smile.png

Share this post


Link to post
Share on other sites

Thanks, I'm tryin'!

 

Yeah, the idea here was to avoid set "waypoints," or work in such a way that AI navigation wasn't limited to places you had been before. Player recordings are only taken between platforms the engine deems "too tricky to automatically path to"

 

In this case actually merging nodes would defeat the purpose of them, as their "traversable in their entirety by just mosying left and right" property keeps the code for the algorithm pretty simple and gives the illusion of completely autonomous movement; graph refinement might actually make the pathing worse! If by A* you mean I should include a heuristic to the pathfinding algorithm, then I do. It explores paths "in the direction" of the target first, which in affect behaves like a priority queue would. Really the search runs so comically fast given the pitance of nodes (medium sized maps tend to have around 40) that I can't imagine A* would offer much in the way of an improvement.

Share this post


Link to post
Share on other sites

This topic is 1111 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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