Pathfinding experiences

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

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?

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.

—

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.

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

—

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.

<img src="http://i.imgur.com/W1ikCg9.png" border="0" />

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"

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.

dl.dropboxusercontent.com/s/wdp3ihkz79subg9/pathfinding_problems.capx

I tried my best.

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

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