Pathfinding experiences

Discussion and feedback on Construct 2

Post » Mon Apr 01, 2013 4:42 pm

Hey guys,

I am working on a tower defence game for android-devices. I am very thankfull for the pathfinding functions, but there were a few things I had to work around. Maybe someone noticed the same problems or has any advice.
Here are my experiences and maybe suggestions for Scirra-Team:

1. It would be nice to be able to find just one way through a maze and then send several enemies on that path. Right now each enemy has to find its own. I don't need that for my game and I would like to save those operations. The Pathfinding-Plugin had this option but I just want to use the included functions. Due to the fact that I am building for mobile devices I want to avoid any waste of cpu because I also need turret-behavior and a lot of colision detections.I am happy about any extra fps ;-)

2. I had big problems with the obstical-map. In my game the player is going to be able to set extra blocks to increase the path length for enemies. I dont mind that the action takes a bit, but it would be nice to have a trigger like "on obstical-map recalculated" Right now I am giving it a buffer of serveral seconds to get sure that its done. On my Android device I had problems with less than 3 seconds. Enemies were walking through new blocks (= map wasnt updated fast enough).

cheers Marco
Last edited by MACPK on Sun Aug 31, 2014 7:01 am, edited 1 time in total.
B
32
S
9
G
3
Posts: 204
Reputation: 7,787

Post » Mon Apr 01, 2013 5:42 pm

1. If you want multiple enemies to follow the same path, you could calculate the path once, save all the path nodes to an array, and have each enemy move along that same path using the bullet behavior.

2. I don't think I'm following exactly what's causing the enemies to walk through new blocks. Is it due to the time needed to recalculate their path after a new block is placed?
B
44
S
13
G
7
Posts: 338
Reputation: 10,389

Post » Tue Apr 02, 2013 5:46 pm

1. How do u do that? I can't find that action like "save path to array" and "load path from array".

2. Yes, I think so. That's why I am asking for a trigger when it's done recalculating.
B
32
S
9
G
3
Posts: 204
Reputation: 7,787

Post » Wed Apr 03, 2013 5:28 pm

@MACPK

1. There are expressions to find the coordinates of nodes for an object's path. You can loop through each node, and save them to an array. Keep in mind, you'd only need to save them to an array if you want to save the path for some other purpose.

Here's an example of using the bullet behavior to replace the "move along path" action. The capx actually has 2 examples. One is moving an object along its own path. The other is saving an object's path to an array, and then moving along the coordinates stored in the array. The second option would be handy to use when you want more than one object to follow the same path.

Demo
Capx

2. I still don't think I'm following. I'm not sure what the difference between a trigger for "recalculating done", and a trigger of "on path found" is. If you're still having an issue, could you post a capx demonstrating the issue.zatyka2013-04-03 18:24:31
B
44
S
13
G
7
Posts: 338
Reputation: 10,389

Post » Thu Apr 04, 2013 9:16 am

@zatyka:

1. Omg, It took me a while to understand those expressions and to integrate it into my game, but it works perfectly. That's exactly what I needed. Now, I can even send diffrent enemy types along the saved path. Thx a lot .

2. Those are two diffrent options. Here is the example capx to show it:


http://burpsgames.com/shared_capx/pathf ... blems.capx
Last edited by MACPK on Sun Aug 31, 2014 7:00 am, edited 1 time in total.
B
32
S
9
G
3
Posts: 204
Reputation: 7,787

Post » Fri Apr 05, 2013 1:34 pm

@MACPK

Ah, understood regarding the 2nd issue. You'd probably be better off regenerating the obstacle map whenever it changes instead of right before finding a path.



Granted, it's more labor intensive due to the frequent recalculations, but it's probably the best solution at the moment. Now that I understand the situation, I agree that it would be handy to have the "On Obstacle Map Regenerate Finished"zatyka2013-04-05 13:43:01
B
44
S
13
G
7
Posts: 338
Reputation: 10,389

Post » Sat Aug 17, 2013 9:47 pm

@Zatyka

Thanks for the capx with your examples on moving an object or series of objects through an array. I implemented your design into my tower defense game as well, however, since I am new to construct 2 and programming in general, how do I call other objects to follow the saved path? Say you wanted hero1 and hero2 to both follow the path, but only hero1 to find the path. Do I copy all the events and just change hero1 to hero2? or is there an easier way. Any input or an example capx would be helpful. Thanks in advance.
B
6
S
1
Posts: 11
Reputation: 597

Post » Sun Aug 18, 2013 12:34 am

https://dl.dropboxusercontent.com/s/wdp3ihkz79subg9/pathfinding_problems.capx?token_hash=AAFLVAImUVq9m61VWALLyEOzdPZejiKVPu3wOtN0_jpn0w&dl=1

I tried my best.
B
9
S
2
G
1
Posts: 97
Reputation: 1,931

Post » Sun Aug 18, 2013 1:43 am

@Potzero

I just copied the code that moves the Hero Sprite along the saved path, and changed it's references to the Hero2 Object. I also delayed their the pathfinding of the Hero2 Object so they don't end up on top of each other.

There are many ways to improve upon this model. For example, if you're having multiple objects/instances follow the same path, it would be wise to loop through them to set their movement as opposed to having to copy the same code for each one. The important thing is that you save the path to something that other objects can reference and follow using whatever method you choose.

Capx
Last edited by zatyka on Sun Aug 31, 2014 4:58 am, edited 1 time in total.
B
44
S
13
G
7
Posts: 338
Reputation: 10,389

Post » Sun Aug 31, 2014 3:58 am

That's a very useful thread it seems first, since I also thought, it obviously could save cpu.

But...

... I did a stress-test with both solutions, as follows:
(Galaxy SIII - dead same conditions, besides described below)

Test A
- 8 Spawning points (for Heroes)
- each spawning Heroes every 2s (8 at once)
- each of them with their own path finding detection at "created" (no map regenerating/registering new obstacles/costs, only FindPath command, rotate object on)
- going to the same goal

Test B
- 1 Spawning point (for one hero at once)
- Spawning point finds path on start and saves it in an array to share with spawned heroes (exactly as in zatyka's capx)
- Spawning point spawning 1 Hero at a time, every 0.5s
- Hero has bullet-behavior and follows path (exactly as in zatyka's capx)


A vs. B

Sum of Heroes on Map / FPS (average)
A: 0/21; 25/20; 50/18; 100/15; 150/14; 200/12; 250/11; 300/10; 350/9; 400/8; 500/7; 600/6;
B: 0/21; 25/18; 50/16; 100/14; 150/12; 200/10; 250/9; 300/7; 350/6; 400/6; 500/6; 600/5;


I also have to note, I tested it first in my desktop browser - same tendency, though it spreads way more, so "A" has a bigger advantage
A: dropping below 60 fps only above 500 heroes on map and 56 fps when 850
B: dropping already after 250 heroes on map below 60 fps and 56 fps when 425

Since "move along path" does also rotate/turn my heroes smoothly around corners - whereas bullet-behavior does not (it is possible of course, but why bother, it surely won't make it faster) - I am not sure it makes any sense to substitute the path-finding-behavior.

Feel free to correct me, if I'm wrong, since I am really keen to find a faster solution than path-finding (especially on mobiles).
This thread is a bit older, maybe path-finding got better meanwhile? Or bullet-behavior worse ;)

Any explanation? For me it does not really make sense, since the path objects have to move and rotate too in addition to generating the path.. how can that be faster, right? But the numbers :(
B
8
S
3
Posts: 197
Reputation: 1,207

Next

Return to Construct 2 General

Who is online

Users browsing this forum: pablo7, Yahoo [Bot] and 14 guests