flood-fill and path-finding

Get help using Construct 2

Post » Thu Mar 24, 2016 4:23 am

After searching for simplest algorithm to perform pathfinding over tiles, came the solution: flood-find_path.capx

Image
Note that the logic was build from scratch not using existing pathfinding behavior.

An article which gave me the concept: http://www.gamasutra.com/blogs/AdamSalt ... rtists.php
ImageImage
B
115
S
51
G
24
Posts: 790
Reputation: 23,505

Post » Thu Mar 24, 2016 5:38 am

Hey alextro, :)

Just in case you're interested, a while back I found a really cool interactive demo of various path finding algorithms.
https://qiao.github.io/PathFinding.js/visual/
At the site listed above, I believe the "breadth-first-search" algorithm is equivalent to the "flood-fill-search" algorithm. (3rd in the list.)
Construct 2's built in path-finding algorithm is A*, (which is pronounced "A Star"). (1st in the list.)


One other special case path finding solution that can be handy is "Goal-Based" path-finding. This one is usually only good when you want to have a massive number of objects path their way to a single goal location.
This is a video that does a nice job of explaining it.
https://www.youtube.com/watch?v=Bspb9g9nTto
B
28
S
18
G
8
Posts: 333
Reputation: 6,193

Post » Thu Mar 24, 2016 6:49 am

@fisholith
Great references you got there. Interactive demo from Pathfinding.js sure teach a lot with various algorithms.
And cool video demonstrates alternative method to achieve it.

I am about to implement the case for existing flood-fill range demo: https://dl.orangedox.com/UkkZMMQmTfgSKdbeYx
Actually that would be first part of tutorial (perhaps in future).
ImageImage
B
115
S
51
G
24
Posts: 790
Reputation: 23,505

Post » Tue Apr 05, 2016 3:34 am

I would like to improve the searching time by implement bidirectional search with dual floodfill.

Say A is starting point and B is the goal. Both point will flooding their neighbour until they flooded certain point that will act as an intersection, let's call it "C". Then The result is path cost/step to reach C for both that bring us to total cost by sum up them:

Total_cost = A_cost + B_cost

Image

Now we just need to traceback from A. However the traces from B need to be converted to cost "how far them from A". We need to write new value from existing b_cost towards the goal.

Total_cost-B_cost = A_cost

So now early traces from B got an A_cost in correct order to complete entire node path. That should relatively fast in theory.
Time to implement the idea.
ImageImage
B
115
S
51
G
24
Posts: 790
Reputation: 23,505

Post » Tue Apr 05, 2016 9:31 pm

It's tricky to improve performance with events. In my experience simpler is better and when doing something more complex to improve performance you also get more event and picking overhead which reduces overall improvement.

That said you'll probably want to measure it with wallclocktime to get a good idea if you're getting any improvements. "best first" might be a better choice than bi-directional or even going full A* might reduce the amount of cells to search through.

There are other things you can do too. One I tried is to not use the overlapping condition. Instead i populated an array with uid's so I could pick the neighbors directly so it wouldn't have to check all the instances if they're overlapping. That roughly made it twice as fast. I say roughly because it would take anywhere from 0.01 to 0.05, whereas before it was 0.03 to 0.08 seconds with my test. I can provide that capx if you'd like.

A next iteration could be to do all of it in an array and do no picking. That would give further improvements but would be harder to read. I'd imagine you may be able to half the time again, but that's just a guess. The only problem is it's less visual and more abstract at that point and if you change the tiles around you'd need to update the arrays accordingly.

The ultimate for speed would be to use js for most of it. Basically send the array or tile positions to some js code, then tell it a start and end tile. This is by far the most awkward and least flexible, but the performance improvement of calculating the path itself will be around 10x faster, or more with more tuning on the js side. This can be done with the browser object, since making a plugin would require a good design idea and take longer.

Another thing i've done elsewhere is to not do it in just one frame, but instead do it over multiple frames so it doesn't affect the framerate.
B
94
S
33
G
118
Posts: 5,396
Reputation: 75,853

Post » Wed Apr 06, 2016 5:37 am

Thanks @R0J0hound for cover every possibility with it's pros and cons. A* seems fair enough for fixed same distance (grid). I always think there must be other way than using overlapping test. Since JS not my thing, I'd like to see an example that utilizing array like you said.
ImageImage
B
115
S
51
G
24
Posts: 790
Reputation: 23,505

Post » Thu Apr 07, 2016 5:54 pm

@alextro
That's probably not every possibility. Here's three different ways:

This uses normal pick logics:
https://dl.dropboxusercontent.com/u/542 ... kstra.capx
This does it all in an array:
https://dl.dropboxusercontent.com/u/542 ... array.capx
This does the same as above but in js. There is some overhead of copying the map to and from js, and likely something more efficient could be done on the js side.
https://dl.dropboxusercontent.com/u/542 ... ra_js.capx
B
94
S
33
G
118
Posts: 5,396
Reputation: 75,853

Post » Fri Apr 08, 2016 12:52 pm

That's a lot of example R0J0. I think I need extra time to understand them. I red that dijkstra algorithm is the most shortest possible route calculation.
ImageImage
B
115
S
51
G
24
Posts: 790
Reputation: 23,505

Post » Fri Apr 08, 2016 8:18 pm

@alextro
The dijkstra algorithm is what your capx is doing and is the algorithm used it the article you referenced.
B
94
S
33
G
118
Posts: 5,396
Reputation: 75,853

Post » Fri Apr 08, 2016 10:12 pm

With this, i just marked the this treath for future reference, now i can find it back. Sort to disturb.
B
33
S
18
G
28
Posts: 2,493
Reputation: 20,950

Next

Return to How do I....?

Who is online

Users browsing this forum: blackhornet, dop2000, Lancifer and 31 guests