next »

[indie11]

I am making a waypoint based isometric puzzle game which requires path finding. The game has some static levels in which the movement paths remain the same. The dynamic levels have moving platforms and bridges that connect/disconnect two Islands.So if the bridge is connected the player can move from Island A to Island B.If it’s not, the player cannot move.

Which path finding algorithm fits perfectly for dynamic levels?

[Dacke]

Most common path finding algorithms will work. The standard choice would be to use A*, since it's:

• relatively easy to implement
• will work for you
• runs really fast

If the platsforms/bridges change all the time, you can recalculate the path every move. If the bridges don't change that often, you can update the path whenever a bridge/platform changes position.

[indie11]

Most common path finding algorithms will work. The standard choice would be to use A*, since it's:

• relatively easy to implement
• will work for you
• runs really fast

If the platsforms/bridges change all the time, you can recalculate the path every move. If the bridges don't change that often, you can update the path whenever a bridge/platform changes position.

So I just need to update the connection of the nodes every time they move?
Just for a reference I want the movement to be like this( NOT THE GAMEPLAY ) just the click to move on flat and inclined tiles

[Dacke]

I'm not sure if I fully understand your question.

If something changes you need to update the grid/graph so that the pathfinding-algorithm knows how the world looks now.

When something changes, you need to calculate the path again to find out if you should take a new path.

[indie11]

I'm not sure if I fully understand your question.

If something changes you need to update the grid/graph so that the pathfinding-algorithm knows how the world looks now.

When something changes, you need to calculate the path again to find out if you should take a new path.

Wouldn't it be costly to calculate path again and again if something keeps on changing?
What If we keep checking if CURRENT_NODE is connected to NEXT_NODE. If it is, the user can move on else it stops.

[oahda]

Depends on what changes, I suppose. You can mark specific things only. You wouldn't necessarily have to update the path if another character moves, for example; just let your path-following NPC slide against other characters if they happen to bump into them, so that they can get past them even if they're in the path. Stuff like that.

If they need to avoid a character, I suppose you can recalculate very short paths at a time since they'll most likely change before they've reached the end anyway. Just a couple of steps rather than an entire escape plan.

[Dacke]

If you just have a small grid (which I think you said in the other thread) it should be perfectly possible to recalculate the path often. It isn't that expensive, really.

If it does turns out to be too CPU intensive (which I don't think it will be), there are plenty of optimizations you can do. You just have to decide what drawbacks you can live with.

• Use a weighted heuristic in A*. Makes the path-finding go much faster (in most cases) but doesn't give you the optimal path.
  
• Only calculate a new path if the old one stops working (your suggestion). Will save lots of path-recalculations, but the AI will look really stupid since it will make up a perfect plan and then follow it blindly until it runs into a wall.
• Check the integrity of the path every time something changes. If a bridge/platform moves, check if this breaks the path. If it does, recalculate the path. This is an improved version of your suggestion. The drawback is that the AI won't make use of new (and sometimes obvious) shortcuts, but instead follow the pre-calculated path.
• Only calculate a part of the path (Prinsessa's suggestion). This is greedy algorithm; it will be much faster but won't give you the optimal path and will get stuck if it ever has to move backwards too far in order to get to the goal.

Depending on what your world looks like, there are more optimizations that may be possible. For example:

• JPS (no drawbacks)
• Depending on your level design, you can calculate waypoints/paths for static sections of the level and treat those sections as one node in the path finding algorithm (no drawbacks)
• If you have multiple agents that are trying to reach the same goal, you may be better off with a flowfield of some kind

Basically, it all depends on what your game looks like and what you want. But I think it should work fine if you just run a new A* on every change.

[oodavid]

I am making a waypoint based isometric puzzle game which requires path finding. The game has some static levels in which the movement paths remain the same. The dynamic levels have moving platforms and bridges that connect/disconnect two Islands.So if the bridge is connected the player can move from Island A to Island B.If it’s not, the player cannot move.

Am I right in thinking you don't need to know what the path actually is, just that it's possible to move between islands? If so that would be a VERY lightweight algorithm.

Regarding moving platforms, as long as you know the waypoints, you can effectively treat this as a normal connection.

Edit - @Dacke that jump point algorithm is beautiful!

[indie11]

If you just have a small grid (which I think you said in the other thread) it should be perfectly possible to recalculate the path often. It isn't that expensive, really.

If it does turns out to be too CPU intensive (which I don't think it will be), there are plenty of optimizations you can do. You just have to decide what drawbacks you can live with.

• Use a weighted heuristic in A*. Makes the path-finding go much faster (in most cases) but doesn't give you the optimal path.
  
• Only calculate a new path if the old one stops working (your suggestion). Will save lots of path-recalculations, but the AI will look really stupid since it will make up a perfect plan and then follow it blindly until it runs into a wall.
• Check the integrity of the path every time something changes. If a bridge/platform moves, check if this breaks the path. If it does, recalculate the path. This is an improved version of your suggestion. The drawback is that the AI won't make use of new (and sometimes obvious) shortcuts, but instead follow the pre-calculated path.
• Only calculate a part of the path (Prinsessa's suggestion). This is greedy algorithm; it will be much faster but won't give you the optimal path and will get stuck if it ever has to move backwards too far in order to get to the goal.

Depending on what your world looks like, there are more optimizations that may be possible. For example:

• JPS (no drawbacks)
• Depending on your level design, you can calculate waypoints/paths for static sections of the level and treat those sections as one node in the path finding algorithm (no drawbacks)
• If you have multiple agents that are trying to reach the same goal, you may be better off with a flowfield of some kind

Basically, it all depends on what your game looks like and what you want. But I think it should work fine if you just run a new A* on every change.

A Level on average will have 150-200 Nodes and at max 300-350

The game has puzzles(traps etc) and a few NPC so it wont be CPU intensive.

I am making a waypoint based isometric puzzle game which requires path finding. The game has some static levels in which the movement paths remain the same. The dynamic levels have moving platforms and bridges that connect/disconnect two Islands.So if the bridge is connected the player can move from Island A to Island B.If it’s not, the player cannot move.

Am I right in thinking you don't need to know what the path actually is, just that it's possible to move between islands? If so that would be a VERY lightweight algorithm.

Regarding moving platforms, as long as you know the waypoints, you can effectively treat this as a normal connection.

Edit - @Dacke that jump point algorithm is beautiful!

The island example is just a small part of a level, there are going to be many similar obstacles and puzzles in a single level with multiple paths.

[Dacke]

A Level on average will have 150-200 Nodes and at max 300-350

That's almost nothing in this context. I'd consider anything below 10,000 nodes to be a small world.

[Denor-DiskFunkt]

This is the closest lead so far.