0 Favourites

Grid based path finding

  • Hey there, I am having trouble coming up with a grid-based pathfinding system.

    The game would be seen from top-down and the AI couldn't go in "straight" diagonals (say if they wanted to go up & right they would have to first go up and then right).

    I first tried like this: If the ai position is 0, 0 and the destination is 3, 3 , the ai would go 3 squares down and then 3 to the right. But then they would bump into obstacles (that are user-placed) and they would get stuck. I could then say: is obstacle up, go right and so on, but then they would feel less like real people and more like roomba's...

    Do you have any ideas on how to do this more realistically or if there are any pluggins for this?

    Thanks!

  • search for Dijkstra, A* or easystar in plugin section, there are plenty of plugins for it

  • What is the difference between easystar and astar? The built in pathfinding plugin already uses a* right?

  • the easystar is also an A* algorithm but it is far better implemented then the built in behaviour, you can implement algorithms naivly or in some clever way, the scirra one is a naively implemented one, you can see by the resources (CPU time) it eats. The easystar plugin uses a fraction of that resources.

  • scirra.com/forum/behavior-easystar-js-pathfinding-for-tilemap_t129056

    I tried to install the plugin, but C2 doesn't recognize it...

    Also, sorry for the late reply =D

  • Construct 3

    Buy Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Buy Now Construct 3 users don't see these ads
  • Make sure it's in the right folder, it's a behaviour not a plugin.

  • Make sure it's in the right folder, it's a behaviour not a plugin.

    Oh, thanks =D

  • the easystar is also an A* algorithm but it is far better implemented then the built in behaviour, you can implement algorithms naivly or in some clever way, the scirra one is a naively implemented one, you can see by the resources (CPU time) it eats. The easystar plugin uses a fraction of that resources.

    Is there any particular reason why the built-in algo is worse than easystar?

  • pretty sure the algorithm is the same (A*), the implementation of it is what is different. Read the wikipedia article about A* and then think about how to implement it, im sure you will come up with more then one way, but not every way thats possible is effective. Btw the two behaviours are too completely different, while the built in behaviour also moves the objects the easystar will only calculate the path. You should try both, far better then me explaining the difference.

  • pretty sure the algorithm is the same (A*), the implementation of it is what is different. Read the wikipedia article about A* and then think about how to implement it, im sure you will come up with more then one way, but not every way thats possible is effective. Btw the two behaviours are too completely different, while the built in behaviour also moves the objects the easystar will only calculate the path. You should try both, far better then me explaining the difference.

    Yeah, I often wonder how a* performance could be improved, if at all.

  • I'm no expert, but rather than the pathfinding algorithm itself that is improved, I believe the gain is from the control you get over how the movement is implemented.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)