15

I've been looking for a robust method of pathfinding for a platformer based game I'm developing and A* looks like it's the best method available. I noticed there is a demo for the AStar implementation in Godot. However, it is written for a grid/tile based game and I'm having trouble adapting that to a platformer where the Y axis is limited by gravity.

I found a really good answer that describes how A* can be applied to platformers in Unity. My question is... Is it possible to use AStar in Godot to achieve the same thing described in the above answer? Is it possible this could be done better without using the built in AStar framework? What is a really simple example of how it would work (with or without AStar) in GDscript?

Though I have already posted a 100 point bounty (and it has expired), I would still be willing to post another 100 point bounty and award it, pending an answer to this question.

E_net4
  • 27,810
  • 13
  • 101
  • 139
Matthew
  • 768
  • 1
  • 11
  • 25
  • 1
    I'm not sure what details you want that the thread you linked to doesn't already give. It describes how the Astar algorithm works; it's not Unity specific. The tricky part about using Astar with a non-tile game is building up the node graph with appropriate movement costs. – Andrew Hows Nov 05 '18 at 04:46
  • You answered your first statement with your final statement. I would like to see how this is implemented in a platform style game, specifically, using Godot's GDscript. That's something that is definitely not present in the links I posted. – Matthew Nov 06 '18 at 23:53
  • were you able to find an acceptable solution for this? I'm about to tackle this same problem. – Logain Mar 30 '19 at 18:48
  • I am not sure if this is what you are looking for but how about the [Navigation](https://docs.godotengine.org/en/3.2/classes/class_navigation.html) class. – Anutrix Apr 02 '20 at 11:05
  • I wish. None of the built in functions / classes do what I need. Everything seems to be geared toward unrestricted x/y movement (overhead/isometric view). What I need is something that will work for a platform game, where Y axis is restricted by gravity. – Matthew Apr 04 '20 at 16:57

1 Answers1

1

you could repurpose the Navigation2D node for platformer purposes. The picture below shows an example usage. The Navigation2D node makes it possible to navigate the shortest path between two point that lie within the combined navigation polygon (this is the union of all NavigationPolygonInstances).

You can use the get_simple_path method to get a vector2 array that describes the points your agent/character should try to reach (or get close to, by using some predefined margin) in sequence. Place each point in a queue, and move the character towards the different points by moving it horizontally. Whenever your agent's next point in the queue is too high up to reach, then you can make the agent jump.

I hope this makes sense!

Godot engine Navigation2D example

The grey/dark-blue rectangles are platforms with collision whereas the green shapes are NavigationPolygonInstance nodes

This approach is by no means perfect. If you were to implement slopes into your game then the agent may jump up the slope instead of ascending it normally. It is also pretty tedious to create all the shapes needed.

A more robust solution would be to have a custom graph system that you could place in the scene and position its vertices. This opens up the possibility to make one-way paths and have certain edges/connections between vertices marked as "jumpable" only. This is a lot more work though if you can not find any such solution online.

J. van Mourik
  • 58
  • 1
  • 7