[Path finding] Bug or how would you solve it?

Get help using Construct 2

Post » Thu Oct 23, 2014 4:32 pm

Im aware that it topic is a bit weird as im not sure if it would be considered a bug or just a problem that should be solved, but its an issue that keeps coming back to annoy me, because I cant find a good way to solve it, and also i find it a weird way for the path finding behaviour to work.

I made a very simple program to illustrate the problem.

Image
The Green square is a unit with path finding and the big green square are the collision map (Tilemap). The Idea is to press any of the green squares on the tilemap and get the unit to move there.

Image
So if i press the left side it finds a path and move there like it should. (Purple square is just a cursor)

Image
However pressing the other side it fails to find a path. Same thing happens when you press a square in the bottom part.

Image

The problem seems to be that it doesn't see the empty spaces inside the green square as being blocked, so it select the closest cell that is not blocked, not taking into account whether it can actually reach it or not and then try to path find here, only to figure out that it cant. And without checking any other cell it conclude that no path could be found, even though there are several others that could be used.

Image
So if i block the white spaces it will work. However this is not a valid solution for me and to be honest im not sure how to solve it, or whether it should be considered a bug. Because as it calculate the best path to the target, it would be logic when it got to the green squares surrounding the inner white spaces that the cost to move through these squares should be impossible or at least a lot higher than if it moved below the target. However the path cost to move through the solids looks like its considered a better path than not to, even though it cant.

So i have tried several things to make it work, but none of them have resulted in anything i would consider a valid solution.
One thing i tried was to do it so if it fails to find a path it will just try another cell near the target. This will work in cases like the above example. But this is ofc not very performance friendly as it could result in having to do up to 9 path finds checks per unit if the first one fails.

Taking into consideration that you cant have more than 1 collision map, are there anyone that have experience this and found a good way to solve it?
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,828

Post » Thu Oct 23, 2014 5:24 pm

It would be best to provide a simplified capx that shows what you are doing.
As is there isn't enough information, and we can only guess.
Image ImageImage
B
168
S
50
G
164
Posts: 8,228
Reputation: 105,575

Post » Thu Oct 23, 2014 6:04 pm

newt wrote:It would be best to provide a simplified capx that shows what you are doing.
As is there isn't enough information, and we can only guess.

Didn't really think about it, as its really simple. But I understand what you mean. This is all the code and as you can see nothing special going on, just a standard path finding setup.

Image

CAPX:
https://dl.dropboxusercontent.com/u/109921357/Path%20problem/Path_problem.capx
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,828

Post » Thu Oct 23, 2014 6:52 pm

Its the behavior.
You want a grid type response, but its not a grid type movement.
On top of that you're asking it to find a path to a solid, rather than an empty cell.
Also, changing the tilemap at the same time is probably going to mess things up as well.
Image ImageImage
B
168
S
50
G
164
Posts: 8,228
Reputation: 105,575

Post » Thu Oct 23, 2014 7:04 pm

newt wrote:Its the behavior.
You want a grid type response, but its not a grid type movement.
On top of that you're asking it to find a path to a solid, rather than an empty cell.
Also, changing the tilemap at the same time is probably going to mess things up as well.

I don't necessarily want it to be a grid type response, not that it should matter, you could build the same shape with sprites if you wanted and it would end up having the same problem.

There are nothing wrong in telling it to move to a solid, it will just move as close to it as it can, if i fill the whole square with solid tiles and press in the middle of the square the unit will still try to move there and stop when it reach the solid.

Like this:
Image

Changing the tilemap wont have any effect and i could paint it whatever color i liked as long as i don't regenerate the collision map, it stay as it was when it was last generated which was at the start of layout.
There are nothing wrong in what im doing in the program it self, it rely totally on the path finding behaviour to find a path to there it is told.
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,828

Post » Thu Oct 23, 2014 9:11 pm

It can't find a path to a solid, it can only find a path to an empty cell.
The closest empty cell is within the square.
https://dl.dropboxusercontent.com/u/109 ... reen_3.jpg

Your solution is to find the closest empty cell that is not blocked off.
There are several ways to do that, but the simplest relies on the fact that you know the cells within the square can't be reached.
Which is essentially what you did when you filled the square.
Image ImageImage
B
168
S
50
G
164
Posts: 8,228
Reputation: 105,575

Post » Fri Oct 24, 2014 2:05 am

newt wrote:It can't find a path to a solid, it can only find a path to an empty cell.
The closest empty cell is within the square.
https://dl.dropboxusercontent.com/u/109 ... reen_3.jpg

Your solution is to find the closest empty cell that is not blocked off.
There are several ways to do that, but the simplest relies on the fact that you know the cells within the square can't be reached.
Which is essentially what you did when you filled the square.

I think we are talking a bit pass each other. The screenshot that you posted is the exact problem that im referring to. Normally or if you selected a tile on the other side or the top it would find a path there, so its not really normal as its failing is just as normal :D. But at least this is the same as what is stated in the manual.
If you ask the pathfinding behavior to pathfind to a destination inside an obstacle, it will simply find the nearest clear cell and pathfind to there instead.

The problem is that it doesn't seem to care whether that cell is actually reachable or not, it just select the nearest one. And since the unit is placed at the spot it is in the screenshot, the nearest cell when you select a top tile is also the cell above the selected tile and its the same if you select a tile on the left side. However when you select a tile on the right or bottom side, it find a cell inside the locked off square and then try to path find there. So it based on the units position compared to where it is told to move, so if I moved the unit somewhere below and to the right of the big square it would be able to find a path to a tile on the right side and on the bottom, but then the top and left side would just fail.

My point is that the path finding seems to work in a way , that if you had to travel somewhere for instant with a train and had several train stations from where a train might get you to your destination, just chose the nearest train station and went there to find out that no train could take you to where you wanted to go and then instead of checking the other train station just concluded that then there were no train stations at all that could get you there. But that is concluding something that you don't know and there is a good chance that you are wrong. At least to me it seems to work like that.

When the A* path finding tries to find a path, at least to the best of my knowledge it assign/calculate a path cost for each node or cell and based on these, it finds the best path to the destination. The reason I think or are uncertain whether its a bug or not is because in the situations like the one you posted as well, there are a path to the selected tile, its just that it for some reason when it calculate the path ignore the solid obstacles in the map or it just before it even tries to calculate a path have already selected the destination cell without taking into account whether that is even a reachable cell or not, something could suggest based on the quote that it just pre-select a destination cell if a solid is selected, without actually finding the best nearest cell. But im not sure if this is the case or maybe something else. But regardless of what it is, it for some reason think that the empty tile closest to the unit is just the best tile to go to. And that is what I don't understand, because as with the train stations example above, the purpose of path finding is to find something that is unknown not just assuming that something is just better than something else, and when that fails just conclude that then everything else must be even worse and that seems wrong to me.

This is from a site explaining how A* works, im not an expert in how it works, so there might be other ways that I don't know about. but this explain it quite good I think.
(In this case he is trying to find a path from the green square to the red.)
Image

Summary of the A* Method
Okay, now that you have gone through the explanation, let’s lay out the step-by-step method all in one place:
1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square …

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.


If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.


If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.


d) Stop when you:
•Add the target square to the closed list, in which case the path has been found (see note below), or
•Fail to find the target square, and the open list is empty. In this case, there is no path.

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.


What is interesting here is that he starts from the green square and values are calculated from here until it reach the red square and then Step 3, working backwards from the target square until it reach the starting square. But in "our" case it seems to never reach the target square so it wont be able to work backwards to find the path obviously. But how it even calculate the value of the tiles inside the Green square and decide that one of these are the best one, I don't understand according to what this guy is doing, if its the same approach that are used ofc, as he never calculate the solid (Blue squares), so if he had a box like in my example, the path finding would never add these tiles to the open list as he calls it.

You can read the whole thing in depth here if you want to know it in details. But hope that make my question a bit more clear :)
Path finding A*
http://www.policyalmanac.org/games/aStarTutorial.htm
B
44
S
11
G
2
Posts: 1,182
Reputation: 6,828


Return to How do I....?

Who is online

Users browsing this forum: No registered users and 8 guests