Question about pick [sprite] vs tilemap

Hi.

In had a project with about 4000 sprites named "block". They were spawned automatically with events.

I had multiple nested loops with "pick by comparison" or "pick by evaluate" on "blocks"

Like :

pick blocks by…

foreach block

-> function "search"

function search : "pick blocks by evaluate"

On my first loop : no problem

Second nested loop : no problem

Third and last nested loop : micro-freeze during this loop, which was just a simple "pick by comparison".

So I thought one tick was not enough to do something like : search for theses blocks inside 4000 blocks. Among these found blocks, for each of them, test for surrounding blocks inside 4000 blocks… etc.

So I guess it was pretty normal if it was kinda slow.

However, I modified my events to replace my blocks by tiles from a tileset object (same number of tiles as blocks : about 4000).

It appeared that nested loops to search specific tiles was a lot faster.

I discussed it with a programmer friend. I have some basic programming knowledge but he's more skilled than me so I listened to him .

Basically, he said that picking some objects by an evaluation or comparison among a lot of objects can be slow or fast, depending of how they are "organized" (not sure if it's the right word, my english isn't as good I'd like). If the objects are sorted in an array with for example their coordinates, well, looking for one object among 50000 other ones will be very fast.

In Construct 2, my nested loops with sprites were slow.

Same loops with tiles were very fast.

So I supposed that it was because the tiles are sorted in an array, somewhat as a grid, so looking for one or more specific tiles is very fast.

Is that right ? Could you explain the fundamental differences between tiles and sprite regarding performances and how Construct 2 gets access to them ?

I hope my message is understandable. Hard to explain technical things with my english !

Picking with sprites has to check all the currently picked sprites. Tilemap tiles on the other hand aren't picked, you select them directly based on tile location.

I don't quite follow your description but if you have a "for each" which calls a "for each" with no "pick by evaluate" and 4000 instances you'll get 4000*4000 iterations. With picking you'll get much less depending on what's picked. On another note picking is run over all the picked instances so an event by itself that uses "pick by comparison" will have to run the comparison on all 4000 instances, and since functions reset picking, each time it's run 4000 comparisons will have to be made. So again a total of 4000*4000 comparisons.

Tilemaps don't do picking on tile. Checking any tile only takes 1 check. It can be refered to as a spacial hash.

overall sprites can be anywhere so you need to loop over all of them to find one in a specific spot.

Tiles are in specific spots so you can just check that spot to find the tile.

Thank you for your explanation . I guess there is no way to store or organize sprites the same way to get them faster ?

Pick by uid is a direct way to pick a particular instance. You could use a 2d array and store the uids of the objects on the respective grid. That way you can have the same advantage as a tilemap.

Basically you can organize them any way you want and store them in an array for quicker access.

Ah ! This is indeed good to know.

So If I understand well your message I can do something like this :

Create a two dimensional array with a width about 100 and a height about 60, then I fill this array with my block X and Y coordinates and I set the block UID at this index.

Then I can do : block pick by UID = (array.at(someX,someY)) ?

And that would work with the expected performances ?

[quote:25tdsuvr]And that would work with the expected performances ?

You would most likely get a bit of performance increase I would guess. But still your program would have to keep track of all the objects.

With a tilemap you are working on 1 object containing a lot of tiles, but it is still one object and the benefit of that, is that you can assign a tile graphic which can be a lot smaller than the actual tile object. Meaning that you could make a tile object be 5000px x 5000px with 500x500 tiles of 10 by 10 pixels. And still maintain a near zero performance impact, due to the graphic it self not being more than an 1024x1024 image, and reused for all the tiles.

However the more loops you use to go through the tilemap will ofc have an impact as its still a lot of tiles. But comparing the tilemap in this case, which would be 250000 tiles all in 1 object, to have 250000 objects, which C2 would have to keep track of, the tilemap solution would work, where as the object solution would most likely kill your program performance. So I think regardless of how you organise your objects, you will never get the same performance as with a tilemap. And the more things you do that involve your objects the worse the performance, which I would guess will decrease rapidly, ofc depending on the amount of objects.

In my game Dragonhelm I think it uses a tilemap with around 70000 tiles for the world map which I do some generating stuff for at the beginning of the game, but its almost don't instantly and have near zero performance impact on the game it self afterwards, since its just 1 object and I don't have to loop through it all the time.

So If I understand well your message I can do something like this :

Create a two dimensional array with a width about 100 and a height about 60, then I fill this array with my block X and Y coordinates and I set the block UID at this index.

Then I can do : block pick by UID = (array.at(someX,someY)) ?

And that would work with the expected performances ?

You only need to fill the array with the block UIDs. You choose which array element to set according to the blocks xy position, using something like this:

[attachment=0:znm5miv9][/attachment:znm5miv9]

For performance, as rojo explained you eliminate the need for many (many as in 16 million ) comparisons. Providing this is a desktop game you should be fine, mobiles maybe not.

So it'd be just like working with a tilemap & you'd be using equivalent expressions to tilemap's 'tileToPositionX/Y' & 'positionToTileX/Y'.

tileToPositionX's equivalent would be something like: (array.x * gridsize) + (gridsize/2)

positionToTileX would be like in the image above: floor(block.x/gridsize)

nimos100 : thank you for this in-depth explanation

mattb : As you speak about it, it's exactly what I tried after Rojo's last reply . It took some time because my events are a mess and I wanted to know if there was an obvious reply to my question before spending two or three hours (I need at least that, I always get lost in the X and Y kingdom…) to try it.

That said, it seems to work so far.

Here a partial screenshot of my last nested function (the part that caused my computer to stop for ¼ second) :

[attachment=0:w5uxjhr4][/attachment:w5uxjhr4]

Laggy : System | Pick block by evaluating block.X = x*size & block.Y = y*size

Instant : Block | Pick instance with UID grid.At(x,y)

Hooray !

You don't really need an array, your layout is an array.

You just need to optimise your picking

If the only way to pick a sprite without iterating over all the other sprites is pick by UID, how do you return a sprite instance given this XY coordinates without storing its data in an array ?

Its not the only way, theres like dozens.

You need to say what you want to do, not postulate how you think you should go about it.

We have no idea why you need to pick the object, so we can't give you a better way to go about it.

Associating a object by its position is a bad way to go unless you are dealing in absolute positions. As in not using sub-pixel coordinates, or decimals.

You have to say something like "how do I pick this object when its close to this other object?", or something like that.

My question was more in a general way about how to efficiently pick some objects among a lot of instances and the array thing seems to suit me well.

That said, this is what I want to achieve :

I have a level made by from lot of violet squares as sprites.

When we click somewhere, it destroys some blocks in a given radius (a slope is just a different frame from the same sprite) :

[attachment=2:zlaz61oa]hole1.png[/attachment:zlaz61oa]

I want my hole to have slopes on each "corners" :

[attachment=1:zlaz61oa]hole2.png[/attachment:zlaz61oa]

And this for any given radius or shape. A bigger hole would make this (I did it manually) :

[attachment=0:zlaz61oa]bighole.png[/attachment:zlaz61oa]

Plus, when a player creates a hole, the hole regenerates hitself somewhat square by square :

You can try it here : http://canapin.com/construct/tolilo/06/ (arrow keys, left click)

For each square regenerated, it needs to scan surrounding blocks to know which frame must be set at the current square (frame 0 : full square, frame 1 : top left slope, frame 2 : top right slope etc…).

Yeah, theres a bunch of ways to do that.

If it were with the tilemap object checking xy's would have been ok.

Here your quickest dirtiest method would to use a dummy object, and check if the invisible dummy object was overlapping the tiles.

I managed to achieve what I wanted : http://canapin.com/construct/tolilo/07/

I noticed the game slows down when there are many projectiles on the screen.

My guess is that the event "projectile on collision with block" (where block is a sprite) iterates over all the block sprites, which are still about 4000. So, if there are 10 projectiles on screen, it iterates over 10*4000 tiles on a tick. Is that right ?

So I guess I'll going back to tiles and find a way to manage stuff like timer regeneration for reach tile.

I managed to achieve what I wanted : http://canapin.com/construct/tolilo/07/

I noticed the game slows down when there are many projectiles on the screen.

My guess is that the event "projectile on collision with block" (where block is a sprite) iterates over all the block sprites, which are still about 4000. So, if there are 10 projectiles on screen, it iterates over 10*4000 tiles on a tick. Is that right ?

So I guess I'll going back to tiles and find a way to manage stuff like timer regeneration for reach tile.

You will eventually kill your program when using so many objects, because the moment you have to check vs any of them, it will add a lot of tests, which will rapidly build up.

Also the way you do collision check is of great important when it comes to performance, which you wouldn't think. I did some testing of this some time ago and here is two examples. They are exactly the same, only the way collision is handled is different.

The first one uses "is overlapping" including some optimization that I added. The second one uses "on collision".

If you try them don't press the "1. Spawn objects" more than 2-3 times, the program will kill your browser, as its was created to test performance when doing collisions.

After you have done that just press "2. Remove overlaps" and then "3. Increase speed by 25" to increase the speed of the objects. (The program was made as a test so, don't spawn objects while its running, there are no error handling in the program so it might crash or bug <img src="{SMILIES_PATH}/icon_e_smile.gif" alt=":)" title="Smile">)

Personally I test it in chrome, since my internet explorer is causing problems all the time, reducing performance in general.

"Is overlapping with optimization"

https://dl.dropboxusercontent.com/u/109921357/Performance%20Test%201/index.html

"On collision"

https://dl.dropboxusercontent.com/u/109921357/Performance%20Test%202/index.html

So as you can see there is a quite huge difference between how you implement collision in C2, a general rule is to never use "On collision" it will always give poor performance, compared to "Is overlapping" and with optimization you can improve the "Is overlapping" which is impossible with "On collision".