0
\$\begingroup\$

I want to be able to modify the A* pathfinding in a way that I can get my NPC from his current position to any point that's within reach. The tricky part is that this takes place in a side-scrolling world where gravity is an issue. There's workarounds to that. My goal is to not only make the pathfinding clean, but be able to add other obstacles and movement aiding objects like jump pads.

enter image description here

In that image I have my NPC and his target position. Between them is a jump pad. When stepping on a jump pad, it launches him into the air high enough to reach his goal. This is what it looks like with a relatively unmodified A* script:

enter image description here

and that's how it should look. But that's just lucky jump pad placement. The NPC doesn't perceive it in any way. Here it looks a lot different just by having the starting position changed:

enter image description here

what I'm trying to do is have a way for the NPC to recognize that the jump pad will take him to his target. Or on the other hand:

enter image description here

What if the best way to get up there is a different jump pad on the opposite side?

Or if the best way is to go down then back up

enter image description here

and would it be any more difficult to add them back to back?

enter image description here

I watched the brackey's video so I know about making a "custom" A* script. I just can't find anywhere how I'd introduce both gravity to it, and my jump pads. Any help is MASSIVELY appreciated.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ A* is a directed-graph algorithm. So you just need to turn your world into a directed graph. If you can reach one node from another (either by walking, or falling, or jumping, or bouncing), connect them. \$\endgroup\$ Jul 10, 2021 at 1:58

1 Answer 1

2
\$\begingroup\$

A* is very smart but also very dumb. It is a graph search algorithm; that means that A* assumes that any two connected points in the graph are reachable without checking back into the game itself to verify your NPC could reach any of those points. It will just search through connected points in the graph to find the most efficient path between them. It seems like your path-finding script is using the wrong type of graph to represent the places your NPC can reach. Imagine this was a top-down game where your NPC could move up, down, left, and right all the same. The green path would be totally acceptable in that case and the blue path would be very, very far out of the way.

beeline

There are a couple of things you can do here.

Create a Navmesh

You need to see what A* sees; find a way to display the graph it searches through and you will see the problem right away; then you can alter that graph so it more naturally represents what your NPC can do. By fixing the input, you will fix the output. Thus, i would recommend you explicitly create a navmesh that naturally represents the places your NPC sprite can move between and how it moves between them (by hand or by algorithm); it might look like this:

example navmesh from a 2d platformer

The different connection colors represent different types of movement (jumping versus just walking for example). Generating a navmesh can be pretty hard, but there are lots of resources that should get you started. Once you have your navmesh, getting your NPC to the goal would probably look something like this:

  1. Request a path from your pathserver/a* search
  2. Iterate through the waypoints on the path
    1. Depending on the type of connection between the waypoints, take a certain action: I.E. walk, jump, or use a door or object
    2. once the action is complete, advance to the next waypoint
  3. Arrive at the goal

Treat your NPC like a robot

Note, this is usually not a good approach for games, I'm just including it to hopefully help you understand why a navmesh is useful.

Suppose your NPC was a robot: it would probably have a set of controls. The controls would be something like:

  1. Walk with velocity x
  2. Jump with velocity x,y

Your NPC would also have a state. That state could be:

  1. Position x,y
  2. Energy e

If you applied a control to a state, you would get a new state, perhaps with a different energy and position.

You want to plan in terms of these controls instead of the states those controls result in, which is the source of the disconnect you have in your game currently. You can modify the A* algorithm to accomplish this surprisingly easily: when you expand the children of your current node, instead of finding the neighbor nodes, you sample a set of controls, resolve each of those controls into new child states, and then proceed as usual with your A* algorithm. You can find an example of this approach that I implemented here.

The point of a navmesh is to encode this sort information directly into the graph so it can be computed exactly once. However, if you have a sufficiently complicated model for your NPC, you might need to explore robotics approaches like the one described here.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .