How do I make a pathfinding routine (no action)

Get help using Construct 2

Post » Sat Jun 17, 2017 11:21 pm

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.
B
7
S
1
Posts: 11
Reputation: 574

Post » Sun Jun 18, 2017 7:58 pm

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
B
33
S
18
G
28
Posts: 2,493
Reputation: 20,950

Post » Sun Jun 18, 2017 9:03 pm

Ottomic wrote: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
www.simbucket.com - HTML5 Science Simulations / https://www.airconsole.com/#!play=com.n ... obotrumble - Robot Rumble on AirConsole
B
47
S
13
G
20
Posts: 371
Reputation: 14,445

Post » Sun Jun 25, 2017 5:19 pm

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.
B
7
S
1
Posts: 11
Reputation: 574


Return to How do I....?

Who is online

Users browsing this forum: plinkie, rayolf, SashikLV and 9 guests