Pathfinding..yet again :)

Have really struggled with the pathfinding behavior and its giving me a lot of problems. So i decided to make a small example and hopefully someone can clarify or maybe it will help push for some improvement with this behavior. But i really don't understand what is going on in this example as it doesn't really act as it should according to the manual.

Some basic info

• All sprites are 32, 32 px using a cell size of 32 pixel with cell border - 1.

• Red sprite have the pathfinding behavior.

• Green and purple sprites have solid behavior.

• Blue sprite is simply used as primary target for the red sprite.

Code

Screenshot 1

The test

The red square will try to find a path to the blue square, which will fail as it cant get there, as it fail it will then find a path to a Green sprite which is nearest to it self (The Red sprite).

from the manual:

[quote:1fpisgiz]Note it may be impossible to find a path, such as trying to navigate to a destination inside a ring of obstacles. In this case, On failed to find path will be triggered instead of On path found.

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.

So based on this it looks pretty straight forward, as i know that it will trigger "On failed to find path" and then ill tell it to go to the nearest green tile, which clearly ain't blocked. However in screenshot 1 if i press the button nothing happens.

However if i switch a green square with a purple and press the button. It works fine as according to the manual. (Screenshot 2)

Screenshot 2

A third test i moved the red square down 96 pixel and left the purple "Barrier" where it was normally and pressed the button again. And it seems to work as well.

Screenshot 3

Screenshot 4

I have also tried to make the pathfinding behavior using the standard 30 cell size. And then none of the examples work. So what exactly is going on with this behavior how are you suppose to work with it, when it seems so unstable that it will simply stop working based on where objects are placed in relations to each other, the cell sizes and so on?

I really hope that this behavior can get an overhaul as its so essential for so many games, and if its not reliable troubleshooting problems with it will be near impossible.

If you tell it to go to a green square, it can't because they are solid. So it looks for an empty square beside the green square. Now that empty square might be inside the box or it might be outside. In your first screenshot it's probably inside so there's no way to get to it.

I bet if you took away the purple squares and just told it to find a path to the nearest green, it would be trying to move to a square on the inside.

[attachment=1:34y6gp0c][/attachment:34y6gp0c]

[attachment=0:34y6gp0c][/attachment:34y6gp0c]

[quote:2547yadq]I bet if you took away the purple squares and just told it to find a path to the nearest green, it would be trying to move to a square on the inside.

Yeah that would work as well, but then I could also just remove all the solids and then it would be able to find a path to the blue square. I don't say that to provoke you , but merely point out the initial problem.

In most games where you want to use path finding the path it finds are calculated in real time, so you as programmer will not know where blocks/units will be at a given time.

If we imagine that the example above illustrate a base of some kind that the player have build to keep out zombies and all the green and purple squares are barricades or fences, it wouldn't work very well if the zombies aint able to attack the walls if they cant reach the player inside.

So the real problem comes as you can place the units in design time and then test it, and everything seems to work. But then as you run the program suddenly the units are in such positions that it cant figure out how to do it, and then you will have a lot of problems trying to figure out why it doesn't work. And then you will end up with the same problem as I showed in the first screenshots.

To me it seems like the pathfinding behavior might not be 100% correctly implemented and seems to lack some features that would make it very good.

1. The path calculated shouldnt place the nearest empty cell the furthest away from the unit using the pathfinding behavior. Based on the A* algorithm it seems to be wrong, as the cost to move there would be higher than the tile nearest to the unit with pathfinding behavior. And the fact that the pathfinding unit cant even reach that tile, so makes little sense why it then marks this as being the cell to go to.

2. There should be two different mode to the pathfinding behavior, "Tilemap" or "Standard". Where "Standard" would be roughly as it is now. The "Tilemap" mode would be used for turn based games. If you use tilemaps with pathfinding in a strategic game where units move one tile at the time. The pathfinding wont work correctly with directional movement as it will see tiles next to it as blocking the path.

Instead it will calculate a path all around them.

Other solution would be to do it so if directional movement is enabled it should be able to move directional near other units,

3. There should be a trigger for Regenerated obstacle map, just as an "on path found" it could be "On obstacle map regenerated". For a lot of games this would be very useful, but in general it would be a good feature to be able to track when the obstacle map is generated.

Looking at screenshot 3

The logic nearest empty cell would be something like this, indicated with the green line and not the red line which is what it chooses:

[quote:3qld29iy]I bet if you took away the purple squares and just told it to find a path to the nearest green, it would be trying to move to a square on the inside.

Yeah that would work as well, but then I could also just remove all the solids and then it would be able to find a path to the blue square. I don't say that to provoke you , but merely point out the initial problem.

I wasn't offering that as a solution. Just a test you could do to see where it's trying to find a path to. If it's trying to get to the inside then that would explain why it won't move when the wall is there.

[quote:3qld29iy]

1. The path calculated shouldnt place the nearest empty cell the furthest away from the unit using the pathfinding behavior. Based on the A* algorithm it seems to be wrong, as the cost to move there would be higher than the tile nearest to the unit with pathfinding behavior. And the fact that the pathfinding unit cant even reach that tile, so makes little sense why it then marks this as being the cell to go to.

It chooses the empty cell closest to the destination. It's not going to use A* to find which empty cell is closest to the player because then it would have to pathfind to every cell on the map and that would take forever. And even that would be no use because the cell right next to the player would be the nearest.

[quote:l51e2o7m]It chooses the empty cell closest to the destination. It's not going to use A* to find which empty cell is closest to the player because then it would have to pathfind to every cell on the map and that would take forever. And even that would be no use because the cell right next to the player would be the nearest.

Agree with what you are saying and it might be a huge flaw in the behavior that in the end breaks it. Because if it just picks the nearest random cell to where its trying to go, there are no certainty that it will work and it will be completely random when it does and doesn't. However this is what my tests pretty much shows, but this also means that the behavior is so broken that it need to be fixed as its simply not working.

From testing it seems that the pathfinding will always go to the cell below the cell being blocked. Which explain why it doesn't work in screenshot 1

Rough distance check.

However this kind of falls apart.

As then this one should fail as well, but it doesn't. It actually moves to the top. And if I block all surrounding cells and just leave top open it works.

However if I do the same but with the side it doesn't work.

So I added so I can see the actual collision cells and then align the sprites to exactly overlap the collision cells. Which improve the path finding a lot.

And it will be able to find path to both top and side.

But further testing seems to cause the same problem.

As it can be seen the tile right of the green tile is clearly not blocked, but still it ain't able to find a path.

However moving the green tile 32 px up and then it works again.

And again you are left exactly as the initial problem.

[quote:l51e2o7m]..It's not going to use A* to find which empty cell is closest to the player because then it would have to pathfind to every cell on the map and that would take forever.

Not necessarily, it could work its way out from the initial target. And stop at the first cell it encounters that it can actually reach. It would require more path finding calculations. But if the alternative is that it doesn't work, then I would consider it a better solution.

Further more it have already calculated the values for the fastest/effective path to the initial destination.

This is a screenshot from another site about A*.

If we assume that the cell I have marked blue is blocked. it could move to the cell indicated by the arrow, and still make use of all the "path cost" information. And it could do that for each surrounding cell. And move backwards based on either condition being the primary one. Either find the nearest tile to the initial goal, no matter how far away it is from the path finding unit.

Which is what I use in my game:

As seen the enemies surround the target.

This could be extended, so it would also value the distance the enemy would have to travel, in comparison to how close the tile is to the original target.

How it works in my game, is that if an enemy fails to find a path to a target, ill calculate a distance to each tile from the initial target and the one with the lowest value will be the new goal for the enemy, as I use an functionality to average the distance all tiles in the same range from the initial target will have the same distance. So all tiles that are 2 tiles from the initial target might have a value of 60 and those at 3 tiles away have a value of 90, which is because there are no difference in my game whether you move directional or horizontal/vertical. But could change it by adding in some weight to how far this goal is from the enemy start position as well.

Yes, sounds like a good idea. Maybe in combination with the current method. If the cell is blocked, choose the nearest empty cell (because that would be much faster in many scenarios). If A* can't reach that one then get the nearest reachable cell (cell with the lowest H value from the closed list?).

Yes, sounds like a good idea. Maybe in combination with the current method. If the cell is blocked, choose the nearest empty cell (because that would be much faster in many scenarios). If A* can't reach that one then get the nearest reachable cell (cell with the lowest H value from the closed list?).

Yeah exactly. Because it seems that it doesn't really care at all whether the cell it pick as the nearest is actually reachable or not, before deciding whether that's the best alternative, and therefore it doesn't check any other cells surrounding the goal. But just keeps checking the same cell and failing to find path to it.

But whether its the best method I don't know. But it make sense that if it fails to find a path, that the best alternative cells to move to instead would be one nearest to the last nodes on the closed list. Meaning the cells that got it closest to its initial target, before figuring out that it couldn't reach it.

This is another problem, which I still haven't figured out why happens and is harder to recreate.

In the image the yellow squares shows the actual path of the enemy on tile (4,7) these are based on the nodes that the path finding behavior have found to be valid. As seen it actually think that the tile at (4,4) is a good place to go, even though its blocked. The obstacle map have been regenerated at this point and printing the collision cells the same way as I did in the above example shows that this tile is in fact marked as a collision cell. But doesn't seem to have any effect for when its tries to find a path. The actual goal for the enemy is to reach tile (4,3) left of the character.

So to make it work I had to add my own path finding correction code, that manipulate or fix the path for mistakes like this.

But each time you have to make correctional code like this, it complicates things a lot and you don't really know if this solves all problems that can happen. But as I said I have no clue why it ignore some of the collision cells.