Efficiency of Pick by UID

Hi there,

My Question Short Version:

What's the efficiency of using "Pick instance with UID"? Does "Pick instance with UID" simply access in to an array with an index of UID, or does it do some kind of searching?

Long Version:

I'm trying to make a simple mmorpg with Construct 2. The problem I am facing is that when the server (written in construct 2) broadcasts a position of a monster, the client has to find the same monster on the client side and update the client monster's position.

Now I first tried doing this simply by assigning an instance variable called "UniqueMonsterId" that is the same in all clients (but of course UID may not be, depending on the order that monsters are created in), but the problem with this was that I had to look through all the monsters on each update to check if the monster's UniqueMonsterId was the same as the one broadcast by the server, and if it was update it. This gives me an O(n^2) complexity.

I tried to improve it by creating a relational array which linked the UniqueMonsterId to a particular UID, so now I can use a "Pick instance with UID" to find my monster (instead of searching through all the monsters). However the efficiency doesn't appear to have improved.

My question is, does "Pick instance with UID" simply access in to an array with an index of UID, or does it do some kind of searching? Because if it just accesses an array this would reduce the complexity down to O(1) which would be a great improvement!

Please let me know if anyone can shed some light on to this. Without being able to figure this out, my game won't be able to have more than 10 monsters at a time without maxing out one of my CPUs!

Thanks for your help! Cheers!

Dengke / ValkyrieGames

Pick by UID is O(n). It searches through all instances. However, it can be made O(1) if needs be - but even so it sounds like it should be fine with 10 monsters. Have you profiled using Chrome's dev tools and proven that the bottleneck is the pick by UID condition? It could be something else.

Hi Ashley, thanks for your reply. Actually you're right, there were some other bottle necks which I've fixed up now and the performance has improved dramatically (I can get about 200 monsters now by straining 1 cpu). However, would it be possible to put the efficiency improvement of Pick by UID on to the development TODO list to be done eventually? Because I think for games which require a large number of enemies, using Pick by UID is almost unavoidable! Thanks Ashley!

Sure, but I'd prioritise it higher if you could prove it was the bottleneck (try running a profile in Chrome).

Hi Ashley,

I ran a profile in Chrome like you suggested, and it appears that pickByUID wasn't run that much at all and only took 0.04% of CPU time. It appears that the bottleneck was actually in a plugin - Rex_SocketIO. I'll see what I can do about that.

Thanks for your time!