0 Favourites

How do I make a pathfinding routine (no action)

  • Hi. I'm projecting a builder game of sorts, and I'm having doubts on the core pathfinding function. Lemme explain:

    I have an environment defined by an array with two Z levels. The first one is for tiles (1 or 0), the other one is for entities (by ID).

    The environment is defined by either 4x4 rooms, 2x4 corridors, or 3x3 corners. All connections are on a grid.

    I want an entity to first scan for points where it wants to go and then plot possible paths to said destinations. Once it has done that, decide for the shortest path (eg, "I'm at 3,5, there's a point at 10,6 and another one at 6,10, which one is the shortest accounting for the shape of the playing field?).

    The pathfinding function included in construct2 is not really cutting it for me, because it moves the sprite along a grid. What I want is to run it for every possible destination, and return a length in tiles *before* moving it, as the game will be rendering every .3 seconds and I need the entities to move one tile every time the game renders. I would also need to be able to stop it and re-run it if the path became obstructed while the entity is on the move.

    Really filthy casual developer here, so any pointers would be appreciated.

    Thanks.

  • Construct 3

    Buy Construct 3

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

    Buy Now Construct 3 users don't see these ads
  • Well, if the build in plugins/behaviours give you doubts, then there are still excellent 3th party plugin/behaviours that might make you shiver.

    Here is a (close to complete) list: c2-plugins-and-behaviors-list_t65170

    If you work in C3, that list is close to non existing yet, today.

    If not one plugin/behaviour does the job for you, then there are 3 scenarios.

    You have outgrown Construct 2 (marketed as an easy drag and drop development environment) .....

    You make your own plugin/behaviour, or modify an existing one (that is way above my talents)

    You ask your friend Google to look up algorithms and then just script it in events.

    In your case that can be https://www.google.be/search?q=dijkstra+algorithms

    Here is a something close to Dijkstra, adapted to your needs, path distances in tile counts.

    https://www.dropbox.com/s/mhv1lz2vwazx3 ... .capx?dl=0

    Yes that performance is just bad. But it has a lot of 'debug things' running to show you what it is doing. When i kill those, it runs at a nice pace.

    https://www.dropbox.com/s/mxtj4f0rsgcsr ... .capx?dl=0

    So, it all depends on your perseverance, and on how hard you wanna learn. Hope this brings you somewhere.

    Capx depends on behavior-moveto_t63156

  • Hi. I'm projecting a builder game of sorts, and I'm having doubts on the core pathfinding function. Lemme explain:

    I have an environment defined by an array with two Z levels. The first one is for tiles (1 or 0), the other one is for entities (by ID).

    The environment is defined by either 4x4 rooms, 2x4 corridors, or 3x3 corners. All connections are on a grid.

    I want an entity to first scan for points where it wants to go and then plot possible paths to said destinations. Once it has done that, decide for the shortest path (eg, "I'm at 3,5, there's a point at 10,6 and another one at 6,10, which one is the shortest accounting for the shape of the playing field?).

    The pathfinding function included in construct2 is not really cutting it for me, because it moves the sprite along a grid. What I want is to run it for every possible destination, and return a length in tiles *before* moving it, as the game will be rendering every .3 seconds and I need the entities to move one tile every time the game renders. I would also need to be able to stop it and re-run it if the path became obstructed while the entity is on the move.

    Really filthy casual developer here, so any pointers would be appreciated.

    Thanks.

    It sounds like you need "pathfinding", but do not want the stock "path following" behavior. I am in the same boat.

    I first looked at implementing A* purely in events. There are lots of good tutorials on this, just google "a star pathfinding". I was about ready to start coding it into events when I ran across Magistross excellent "easystar" plugin designed for tilemaps.

    All you have to do is put in a tilemap and it will quickly determine paths in realtime. You can even optimize it for compute time vs accuracy. In my case, I was looking to find not necessarily the absolute shortest path, but one that minimizes CPU load because I have lots of 3D physics going on already in the game.

    I am working in Q3D, so I have to implement my own movement system. Easystar is perfect for this.

    Here is a demo:

    https://www.scirra.com/forum/behavior-easystar-js-pathfinding-for-tilemap_t129056?&hilit=easystar

  • Thanks, guys. It's taken me the better part of a week, but I just made a decent A* function by scanning adjacents and then backtracking the same exact way. I dunno how efficient that'll be when more entities come into play, but at least it's reasonably solid with a start and destination point. Thanks again.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)
Similar Topics Posts Views Last Post
Unread hot topic
167 14,499
DMT2005's avatar
DMT2005
Unread sticky
1 Favourites
C2 Games made with CocoonIO
136 89,826
minhcuong's avatar
minhcuong
Unread hot topic
99 10,139
karshinkoff's avatar
karshinkoff