GDevelop
GDevelop copied to clipboard
4ian
[PathFinding] Add refined collision methods and isometric grid
An example with isometry (hitboxes are diamond) : https://games.gdevelop-app.com/game-4177b87c-89f1-41f7-a5a5-425af8ab639b/index.html
A comparison of the 3 collision methods: https://games.gdevelop-app.com/game-986b44e9-f0c7-412a-910b-fadacd114135/index.html
Mickael uses the refactored version of this PR on his game. A custom build can be found there: https://github.com/4ian/GDevelop/pull/2373
Interesting! Tag when when you think it's ready for review, unless it's already ready? :)
Can you also include the example project - as part of this PR? It will help with testing for regressions in the future
Can you also include the example project - as part of this PR? It will help with testing for regressions in the future
Should I put it in the tests subfolder? a zip or the project folder?
Can you also include the example project - as part of this PR? It will help with testing for regressions in the future
Should I put it in the tests subfolder? a zip or the project folder?
Put it in https://github.com/4ian/GDevelop/tree/master/newIDE/app/resources/examples 😄 Have a look at how other examples are added to that folder
Thanks for implementing this, looks cool
A suggestion on the example - can you remove the yellow tile under her feet, which moves with her? It misleads the player into thinking that the yellow tiles are walkable, when in fact they are walls
A suggestion on the example - can you remove the yellow tile under her feet, which moves with her? It misleads the player into thinking that the yellow tiles are walkable, when in fact they are walls
Might be a good idea indeed to use another color :)
The example is indeed very cool and serves both as an example for people exploring the possibilities of the behavior, and as a test case when we do changes later to this.
Put it in the newIDE/app/resources/examples. The name of the folder should be in kebab-case, and the name of the name kebab-case.json (same base name for both). Finally, add a README.md with a short (1-2 sentences) description.
I added the example. I made it a little less ugly: https://games.gdevelop-app.com/game-d44aeb68-2031-4ab5-b66b-fec3ccae27a6/index.html I'm note sure I can use Minda. How can I credit the author? You'll see I had to use a -8px margin. There is either an issue with assets or the code. I'll make more tests and probably end up with a big project not fit as an example but maybe useful for manual testing. What do you think about an hidden example list for devs?
What do you think about an hidden example list for devs?
You can put games used for feature testing in GDJS/tests/games, in a folder named after the name of the feature :) Or (actually, it's better!) in Extensions/PathfindingBehavior/tests/games (create a new folder for it). Second option is better because we keep test games close to the extension sources.
I'm note sure I can use Minda. How can I credit the author?
If it's included in GDevelop, you can use it freely :)
I push a version that doesn't rely of transformed shapes in the obstacles. It needs tests and polish, but it could be used as a discussion aid.
I did a comparison of the 3 collision methods so we can discuss about what behavior we want: https://games.gdevelop-app.com/game-986b44e9-f0c7-412a-910b-fadacd114135/index.html
We should probably have at some point some unit tests for this, to avoid obvious or not so obvious regression in edge cases.
I think so too because I have other ideas for this extension, it will save a lot of time. For future PR, I would like to add a step by step movement and an hexagonal grid because it will be useful for wargames.
We should probably support/force the sharing of the nodes between the objects, and have an option to memorize the nodes so that the "in memory map" is only created once. And then have methods to invalidate the nodes at some position. The idea is to avoid having to recompute the nodes everytime we search a path for an object. Useful if you have a large map but nothing is moving. If something moves, we would give an action to invalidate the nodes
Optimization will be very interesting. Quad tree may be useful.
This makes me think that there is a big flaw in the new implementation: the hitboxes at the start may to be representative to the ones on the way because of animation and rotation.
I think the stories could be:
- my object always keep the same hitboxes don't mess with it
- I don't care about overlapping, be permissive (use the intersection of every animations in every directions, so basically a inner disk)
- I don't want overlapping even if this close paths where the object could have actually go through (use the union of every animations in every directions, an outer disk).
Or maybe this is overthinking and people will have to choose their hitbox wisely... there is a change request for disk hitboxes right?
This makes me think that there is a big flaw in the new implementation: the hitboxes at the start may to be representative to the ones on the way because of animation and rotation.
That's something we don't really care about I would say, we assume that the user of the pathfinding will be aware that if a path is computed and the size/shape of the object if radically changed, it's not something solved by the pathfinding anymore.
Or maybe this is overthinking and people will have to choose their hitbox wisely... there is a change request for disk hitboxes right?
Yup I think it's overthinking, most people will use simple hitboxes. There is a request change for circle hitboxes, but they can be already appromixated... anyway I would rather ask users to be mindful of their hitboxes rather than implementing complex logic for this. Most users will be fine because the hitbox is staying the same for the object whatever its animation (even for the player, it's easier to have an object that does not change its "shape", and makes for better collision handling).
To come back to the PR:
- Thanks for the change to RBush! Actually will be very very useful because in the future I might factor all the RBushes into a "RBush" (or Quadtree etc...) provided by the game engine. So extensions could use it directly without each maintaining their own spatial data structure.
- Question: Is it working well? :) I don't anticipate much problems, but still because it's slightly different i wonder if you ran into edge cases?
- About the state of the PR:
- Thanks for the tests! 😍
- Do you think you could extract them + the RBush in a separate PR? That would be a much easier PR to review, and this one would become simpler (and safer if we add even more tests :))
EDIT: I see that you test all the "collision methods", so extracting the tests might need a bit of rework, but still worth it I think!
* Do you think you could extract them + the RBush in a separate PR? That would be a much easier PR to review, and this one would become simpler (and safer if we add even more tests :))
I'll continue to write tests and make the PR after that because I would like to split the test and the RBush in 2 commits to make it easier to run the tests on the untouched implementation.
I would like to split the test and the RBush in 2 commits to make it easier to run the tests on the untouched implementation.
Ok sounds good :) Tag me here when you have them ready or in another PR :)
Ok sounds good :) Tag me here when you have them ready or in another PR :)
@4ian, I extracted it here: https://github.com/4ian/GDevelop/pull/2315 The tests seem to run ok after and before the rbrush commit.
I removed the isometric angle setting, so the grid is set like the one from the scene editor. See https://github.com/4ian/GDevelop/pull/2445#issuecomment-802850667
I added grid offset properties. I didn't add action nor condition. I think actions and conditions for cell dimensions should be removed too. I don't see why a user would change the grid at run time and it may make the implementation more complex for no value. What is your view on this?
@4ian Is this PR left behind because its size makes it difficult to review? If you want, I can split it in 2:
- The collision methods (legacy, AABB and hitboxes)
- The isometric grid
Yes, that's pretty big to review so I've fallen behind this and I'm also worried of the long term maintainability of all these methods (though we can alleviate this problem with tests, but still), so it went off my radar.
What is the state of this PR? It can fix this issue: https://github.com/4ian/GDevelop/issues/2689
What is the state of this PR? It can fix this issue: #2689
I think I'll close it. It will be almost superseded by the NavMesh pathfinding: https://github.com/4ian/GDevelop/discussions/2787 The only cases that are not covered are the grid based movements. But for top-down, it can be done with the existing behavior and for isometry, hexagonal or anything else, the extension with linked objects can be used: https://github.com/GDevelopApp/GDevelop-extensions/issues/140
