2 replies to this topic

[@Alex@]

So as a little bit of challenge I was set I have to create a small game where balls bounce around passing information to each other with each collision, easy enough but I'm also not allowed to use instances. To this effect i've set up a system where each ball as a bunch of variables held in an array of all the balls. This allowed me to loop through each ball and check for a collision with every other ball. This worked fine for a small number of balls , somewhere in the region 50-75 it became really slow. So what I am asking here is what is the most efficient way I round handle the collisions here. I've been thinking about dumping all the balls into a ds_map with one of the co-ordinates as the key and checking the collisions up until one that is to far away for a possible collision but I'm not sure how much speed I would gain from this and don't want to spend to much time on it if there is a better approach I'm unaware of. I'm looking to get the number of balls I can run without dropping my framerate up to around 400 so I can have a sort of gradual progression with my levels failing that I'll have to come up with a new idea for how the levels progress.

[paul23]

Well only solution I can think of is spatial hashing. However that really works best on large maps, with a large number of balls (like 100+ you'll start seeing the difference).
Very simplistic overview of the algorithm


But I'm surprised the game slows down for collision checking, already at 50 objects. - As this would in a naive implementation only do 2500 point-distance functions. Are you really sure collision checking is the problem? - Aren't you under the hood doing some inefficient array dimension changing / things such as swapping lines?

[@Alex@]

I don't really do anything other than checking the collisions and updating the already present array values, well and drawing the circles. It could be a bit of script overhead since collision checking is spilt into about 3 scripts. It works fine a 50 balls by the way it starts to drop frames somewhere between there and 75 (I haven't pinned it down to a more exact number), it's halfed by 100 and at 300 I get 1 or 2 frames per second. I'll look into Spatial Hashing, thanks for the link.