Question about pick [sprite] vs tilemap

Get help using Construct 2

Post » Fri Feb 20, 2015 10:33 pm

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 :mrgreen: .
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 !
Last edited by Coin-coin le Canapin on Sat Feb 21, 2015 7:42 pm, edited 1 time in total.
B
12
S
7
G
7
Posts: 448
Reputation: 4,272

Post » Sat Feb 21, 2015 6:48 am

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.
B
89
S
30
G
95
Posts: 5,156
Reputation: 63,448

Post » Sat Feb 21, 2015 8:48 am

Thank you for your explanation :). I guess there is no way to store or organize sprites the same way to get them faster ?
B
12
S
7
G
7
Posts: 448
Reputation: 4,272

Post » Sat Feb 21, 2015 11:32 am

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.
B
89
S
30
G
95
Posts: 5,156
Reputation: 63,448

Post » Sat Feb 21, 2015 12:15 pm

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 ?
B
12
S
7
G
7
Posts: 448
Reputation: 4,272

Post » Sat Feb 21, 2015 3:50 pm

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.
B
44
S
11
G
2
Posts: 1,181
Reputation: 6,816

Post » Sat Feb 21, 2015 5:57 pm

Coin-coin le Canapin wrote: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:

Untitled.png


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)
You do not have the required permissions to view the files attached to this post.
B
27
S
12
G
1
Posts: 157
Reputation: 3,359

Post » Sat Feb 21, 2015 6:21 pm

@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) :
pick-a-boo.png

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 do not have the required permissions to view the files attached to this post.
B
12
S
7
G
7
Posts: 448
Reputation: 4,272

Post » Sat Feb 21, 2015 6:30 pm

You don't really need an array, your layout is an array.
You just need to optimise your picking
Image ImageImage
B
166
S
49
G
154
Posts: 8,103
Reputation: 100,227

Post » Sat Feb 21, 2015 7:12 pm

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 ?
B
12
S
7
G
7
Posts: 448
Reputation: 4,272

Next

Return to How do I....?

Who is online

Users browsing this forum: gianghl1983 and 7 guests