Hello all,
Has anyone else encountered this issue with spatial partitioning (I think its called that?)
What happens is, instead of this working on the entire map, it only works one one grid block (random one I think) and the surrounding ones, the rest of the objects that are not in this 3x3 block area are ignored and their collisions dont count.
code
Grid system off
Grid system on
Well, you donât pick a specific Gunslinger in your last âFor each Bulletâ-Event.
So each Bullet grid value minus the grid value of your first created Gunslinger gets compared to <= 1.1, which totally depends on which Gunslinger is Gunslinger[0], and the chosen size of your grid. This leads appearently to the resulting explosions in the lower half.
What do you want to do and what is your issue?
If you simply want to only pick all Gubslingers in the same cell, as each Bullet, you should do (careful, freestyle syntax incoming):
For each Bullet
Pick Gunslinger with GridX/Y = Bullet.GridX/Y
And check collision.
That way you decrease the number of collision checks based on your grids cell-size.
What I didnât include there, was the neighbouring cells. So if an objects collision mask overlaps into a cell, but its center point is not, then this object would not be checked for collision. That might be okay, for your small looking sprites, since it is only edge cases. But you can ofcourse add the edge neighbors (5 cells total) or even the ones at the corner (9 cells total).
The implementation could be to also include Gunslingers with GridX/Y of -1,0,+1 for each direction respectively (conditions coupled by OR)
Repeats can become inefficient with large number of objects.
The repeats you have are unnecessary. The first 2 events do not need a repeat for each object. You can just use an unconditional event with the actions to calculate gridx and gridy. The values calculated for each object will be based on only that objectâs position.
For the collisions, you also do not need to do a repeat for each object. So event with:
Variable Grid is false
Bullet is in collision with Gunslinger
will only select the bullets and gunslingers that collide with each other. Thereâs no need to repeat.
Just because youâre using a grid doesnât make the problem you encounter an issue with spatial partitioning. If GDevelop is using spatial partitioning for collision detection, itâll be doing it for each object it works with, not your grid.
Because spatial partitioning is a way of dividing up space into smaller regions so that objects only need to deal with nearby objects instead of everything at once.
As for why only a block of bullets explode, realise floor returns an integer, and the difference between integers will be another integer. So the gridx and gridy values will be 0, 1, 2, 3⌠Checking whether itâs less than or equal to 1.1 is pointless. Those differences will only be 0, 1, 2, 3 etc.
So it could just be coincidental that the girdx & gridy differences do not meet the threshold.
For example, say the grid was 64x64, and Gunslinger.CenterX()=127 and Bullet.CenterX()=128 and the condition is Gunslinger.gridx-Bullet.gridx < 1.
They are right next to each other, but the gunslinger.gridx = 1 and bullet.gridx = 2, and the condition wonât be met.
Yet if Gunslinger.CenterX() = 64 and Bullet.CenterX()=127, then they both have a gridx value of 1, even though theyâre nearly a whole grid size apart.
So for that last event,you may be better off using a standard event with the 2 conditions:
Bullet is in collision with Gunslinger
abs(Bullet.CenterX() - Gunslinger.CenterX()) < grid.size * 1.1
That may solve your problem.
And get rid of all those repeats.
You are right, that the conditions should not be inside the repeats. But âCreate Explosion at each collided Bullet centerâ-action still needs to cycle through each instance of bullets, that collided, right?
Hello all,
Apologies for the late reply.
the 1.1 should have been a â1â I added the 0.1 out of desperation basicallyâŚyou know, just in case.
I have to keep the âif less than 1â to make sure it checks if the objects are in the same grid block or an adjacent ones, I cannot just check if its in the same block because then neighboring blocks will not be checked.
The current issue, as pointed out by you also, is that I have no way of letting Gdevelop know that it has to check all gunslingersâŚ
Any idea how to do that without a âfor each gunslingerâ inside âfor each bulletâ?
It will do all gunslingers if theyâre in the scene.
If you use a normal event with the condition "Gunslinger in collision with Bullet", then the actions will only be applied to the Gunslinger and Bullet objects that meet the condition. No need to iterate for each bullet and then for each gunslinger.
If youâre still having trouble, you could zip up your project, put it on a shared drive and share the link to it. Then Iâll have a look into it later in the evening. Share the link in this thread or PM me.
Hello again,
Thanks for your time!
Heres the project
The thing is that, it doesnât seem to cycle through all the gunslingers currently.
Iâm assuming it only happens for the first created one? And the the explosions happen only in 3x3 block area around that one.
each block is 200 pixels, it is set in a global variable in case youâd want to change that one as well
There are some other stuff in there too, Iâve been tryingâŚ
So, the issue appeared to be the order of conditions:
These events:
Create these explosions:
Shifting 1 condition like this:
Resulted in:
Resulting in:
Further suggestions:
Remove these 2 events - they are getting run every game frame, which is pointless unless:
And add the actions here instead, which is a much better solution:
Well, useless to continously update the grid, until your objects are moving. Because then they might move from one grid cell to another one. Then you will need to update the gridX/Y. But still not every frame and not all of them.
Hello all!
Once again apologies for late reply and thank you for giving this some extra thought.
The issue I find with this:
Is that the grid check must be FIRST since its much CHEAPER (less lag) than a collision check. If I put the collision check first, the there is really no point in checking coordinates.
Thank you for also checking the rest of the game, but its really just a demonstration game, Iâm mainly looking to minimize lag as much as possible, and thought this grid system would be easy to implement, but it doesnât seem soâŚ
Gdevelopâs collision checks are very efficient. Assuming that is an FPS meter at the top, it looks like your problem was the misuse of âFor eachâ, since after MrMen corrected it the FPS went from 28 to 55.
A grid system could potentially be more efficient, but you would want to avoid all on-the-fly calculations. Youâre just calculating grid positions based on CenterX/Y every frame which is sort of eliminating the advantage of a grid in the first place. It should either be an array with references to objects, or grid positions stored in the objects that only get updated when the object changes position. Then you would use object filtering (not for each) to pick them - but since youâd be comparing up to four values (since object can overlap four grid spaces max), it might not save you any processing in the end. Iâm not really sure because I havenât tried this myself.
An actual grid, where objects can only move by one whole space, would definitely be more efficient as you would always have discrete grid values for everything
No, itâs not cheaper. GDevelopâs collision process will be optimised as much as possible. What you are doing is going over every gunslinger instance for every bullet instance and checking the variable values, rather than a subset of gunslingers.
Say there are 100 bullets and 100 gunslingers.
Your method checks every bullet against every gunslinger, and then performs two variable checks on each pair. Thatâs: 100 Ă 100 Ă 2 = 20,000 checks per frame.
My method flips the order. I run the collision test first, which usually narrows the field to just one or two gunslingers. Then I do the variable checks: 100 Ă 2 Ă 2 = 400 checks per frame.
So the difference is dramaticâa reduction of roughly 1/50th, or 19,600 fewer checks every single frame.
Yeah, that happens sometimes. You try something but itâs slower and more cumbersome than an already a more efficient method.
And thatâs the crux of being a developer - trying something out to see what the results are. You may not always be right in your initial assumptions, but there will be times when you do uncover something better.
Hi
Yes, if you like programming or development, youâve got to be able to rack your brains when it comes to solving problems.
Because itâs quite rare for it to work on the first try.
It can also be pleasant or funny to optimize your code.
A+
Xierra
Thank you all for your help and time!
I will continue to try and optimize fps in other ways!
I was really under the impression that comparing numbers is cheaper (lag wise) than collision checks, even when we consider that we would need to check twice, both X and Y.
In any case, this one didnât work outâŚIâll keep looking!
Thank you al!
Spatial positioning still has its place in performance tuning. Itâs just not well suited for moving objects, unless you can implement rules that restrict your constant question of âin which cell am Iâ.
I used it for example for an huge open world simulation, where every newly sprouded plant would be stored in an already existing grid structure. Since the plants donât move, the calculation was only done once per plant (not every frame, once per game). When I wanted to pick a plant based on coordinates, it made sense to only distance check the plants of one specific cell instead of every plant in the whole game. But thats a completely different scenario then moving Gunslingers and moving Bullets.
