[Path finding r182] Ignore collision settings

Problem Description

Path finding is not working correctly, seems to ignore all other objects collision settings besides the first added object to the project that uses the behaviour.

Attach a Capx

Description of Capx

Move two objects from there starting position to a X,Y coordinate. And on the way they have to move around some obstacles.

Steps to Reproduce Bug

Full description of the problem can be found here - https://www.scirra.com/forum/viewtopic.php?f=147&t=117025&p=842288#p842288

Its not easy to explain without adding a lot of screenshots. Which are already added in the forum topic.

Observed Result

Ignore all other path finding objects collision settings, and uses the settings for the first added object to the project that uses path finding.

Expected Result

That each object would use its own collision settings.

Affected Browsers

Not browers specific.

Operating System and Service Pack

Windows 7

Construct 2 Version ID

r182

The problem is there is only one global obstacle map used for the pathfinding behavior. Everything pathfinds on the same map. So if you have object A with two obstacle types, and object B with no obstacle types, you have a conflict: should the one global map have those objects as obstacles, or not? In this case it happens to pick the global map where no obstacle types are defined. If you delete the red object there's no conflict any more and it uses the right obstacles.

I'm not sure how to resolve this - having multiple maps becomes memory inefficient and possibly slower, but on the other hand perhaps the obstacle types should be global as well to avoid this situation... the easiest thing to do is to make sure you have the same obstacles added for every object using the pathfinding behavior.

The problem is there is only one global obstacle map used for the pathfinding behavior. Everything pathfinds on the same map. So if you have object A with two obstacle types, and object B with no obstacle types, you have a conflict: should the one global map have those objects as obstacles, or not? In this case it happens to pick the global map where no obstacle types are defined. If you delete the red object there's no conflict any more and it uses the right obstacles.

I'm not sure how to resolve this - having multiple maps becomes memory inefficient and possibly slower, but on the other hand perhaps the obstacle types should be global as well to avoid this situation... the easiest thing to do is to make sure you have the same obstacles added for every object using the pathfinding behavior.

I can see why it would be memory inefficient, but as it is now the purpose of using custom obstacles kind of vanish as the benefit of using them, rather than just making objects solid was so you would be able to control obstacle settings for individual objects more specific I guess?

But the moment you have 2 or more different types of objects, the behaviour will bug, for instant a game where you have two units using pathfinding, a "Ship" and a "Tank" and for the ship you want the land area to be the obstacle and for the tanks the water area. Then there are no way of using pathfinding as it is now, as i see it? Im actually working on a game which uses both ships and land units, and what made me notice this problem in the first place.

Im by no means an expert in pathfinding, so might not be a huge help in finding a solution, but I did search around a bit for things, and I found something called Navmesh, whether its useful or not I have no clue.

[quote:2q7bd8gr]

From the second link

Benefits of a Navigation Mesh over pathnodes:

Reduction in node density

Since with a mesh we can represent a large area with a single polygon, overall graph density goes down. This is a win for many reasons:

Memory footprint is reduced with the decrease in nodes being stored.

Pathfinding times go down as the density of the graph being searched shrinks.

Less nodes means less time fixing up cross-level pathing information

A* with NavMesh Detailed

Navigation Mesh Reference

Edit:

Another way that might work, could be if you could create obstacle maps kind of like you would a layer. So as you add them you would be able to choose which obstacle map an object would use in the properties panel just like with layers. And maybe be able to switch them around during runtime and so on. But don't know If that would cause memory problems as well.

[quote:15e9geye]Edit:

Another way that might work, could be if you could create obstacle maps kind of like you would a layer. So as you add them you would be able to choose which obstacle map an object would use in the properties panel just like with layers. And maybe be able to switch them around during runtime and so on. But don't know If that would cause memory problems as well.

I think this should be enough. For instance on isometric game where you would have multiple floors kind of like old X-Com games. When changing floor you could switch obstacle map to "Floor2" and maybe for add obstacle you would have new setting for what obstacle map you would like to add that.

Would it still be too much if instead of using own map for every instance you would use predefined amount? For instance on this RTS example there would be 2 (air units probably don't need one), on old X-com there is 4 and on X-Com: Apocalypse there is 9 etc.

[quote:205wgrcy]

Would it still be too much if instead of using own map for every instance you would use predefined amount? For instance on this RTS example there would be 2 (air units probably don't need one), on old X-com there is 4 and on X-Com: Apocalypse there is 9 etc.

Using one for each instance I think would create some serious performance issues, and would probably be a bit overkill. If you should do it like this, I would prefer there not to be any redefine amounts of obstacle layers. People should instead just be aware that adding to many of these would hurt performance, just like if you add to many collision points to an object in the editor it gives you a warning. But as you wrote that would be the overall idea to do it like that.

Having only one global obstacle map is a serious limitation, and given the way they are actually configurable in the editor, this is a bug.

It avoids to have ground and air units for instance.

It avoids to have obstacles traversable by only one kind of units (private gates).

...

A pathfinding behavior shoud be connected to a given obstacle map, that can be shared with some other pathfinding behaviors for performance.

nimos100 mentioned to use layers to store these obstacle maps which may be a good idea.

Ashley, do you plan to fix this?

LOL LOL LOL

Just fiddling into the source code to see that :

var cellkey = "" + this.cellSize + "," + this.cellBorder;

So there is ALREADY multiple obstacle maps. It suffices to add to this key a simple variable from pathfinding behavior config to have multiple obstacle maps.

For the actual users, just adjust slightly cellSize or cellBorder to have multiple obstacle maps.

For instance one with cellBorder -1 and one with -2.

Please implement such simple modification to pathfinding behavior.

Wouldn't it be possible to have one obstacle map with different values like this

The ship has value 1 as obstacle and the tank value 2 and 3

1=land

2=water

3=building

Or isn't that already possible if you use path cost ?

ship path cost for land = positive infinity

tank path coast for water and building = positive infinity

but i dont know if that would be efficient or not

Wouldn't it be possible to have one obstacle map with different values like this

The ship has value 1 as obstacle and the tank value 2 and 3

1=land

2=water

3=building

Or isn't that already possible if you use path cost ?

ship path cost for land = positive infinity

tank path coast for water and building = positive infinity

but i dont know if that would be efficient or not

It was kind of the same solution as I suggest as far as I remember except that you would be able to assign units/objects to an obstacle map like you would a layer.

Thrust me I have tried pretty much anything to make the path finding work and your suggestion about adding different costs was also one of them.

But its makes no different, to the units/objects there are only one map, so if you for instant have 3 different types of units, it doesn't matter which of them you add a cost to, it applies to all of them. The path finding is bullet proof when it comes to being broken it seems

nimos100 You are right. Did a test and it didn't work.

The only thing that worked is what Turing was mentioning befor with the different cell or border sizes.