Array "Contains Value" Condition Question

What algorithm is applied to find a value in an array when the "contains value" condition is used?

Is it just a sequential search or something more efficient?

Wondering if I should just use this or roll my own.

Thanks,

Brian

It's a sequential search. Consider using Dictionary for O(log n) lookup performance.

This is binary tree O(log n) right?

I was wondering the speed of dictionary lately as I'm using it as a data state system for 4 GamePads. Knowing it's not sequential makes me feel a lot better.

So I have a question and this does side track the a little. If Dictionary is using a smarter algorithm. Why is collision detection using brute force and not a binary/qaud tree?

Dictionary uses raw javascript object properties, so it depends on the javascript engine - in some cases it's O(1) with a hash table implementation, but at worst should be something like O(log n). We've got improvements to the collision engine on our todo list, but it's tricky (not just a matter of swapping an array for something else).

I know the subject is Arrays but that collision improvement is so much needed for my game :( Just tell us if it is soon future or far in the horizon, ashley :)

-Also the regenerate partial obstacle map for pathfinding.

I know, I shouldn't have started with an RTS project... But it already happened so...

Windwalker - how do you know it's collisions that need improving? They're pretty fast for most games. Are you getting info that shows they're slow from the profiler?

Hey Ashley, thanks for giving a chance to share opinions.

I completely agree the current performance of the collision detection is enough for most of the games that comes to mind when using C2. However, I made the "mistake" on starting an rts game where I use collision detection for various events.

For everything below: I was monitoring the performance of collision detection via grouping the related events together and using debug layout.

I also know that the design is as important as the performance of the tools, if not more. And I am a newbie to C2, and relatively new to coding as all I know is some C# and XNA, in which I made a couple games.

In my current project, with just barebone elements like food and 1 type of neutral unit and some 1 enemy unit on a relatively large layout (22k x 22k) I can stress test up to 100 player units without any slowdowns (collision take 20 percent CPU, framerate stable —) and up to 300 units to playable levels. (collisions take 49 percent CPU, framrate stable —)

However when I introduce the opposing faction, 200 units each side trying to collision detect their enemies, as well as various resources on the board, it starts to show itself.(collisions take 90+percent cpu, framrate around 10) And due to the nature of my game, I would like to go up to 1000 units for each side. (units are not directly controllable, player creates units, creates groups from units, creates orders through map and attains groups to orders.)

As a sidenote, I am also using pathfinding behaviour which may add to low framerates somehow. But the CPU usage I detect from grouping the events and they don't include pathfinding events.

I tried several ways to remove collision detection from the design. Like I was using an invisible, LoS bubble sprite around units to find out if they have anything particular in their range, running collision checks with "collidables" family. I removed it for a simple, event driven distance check, which didn't improve performance much. Also currently my units are walking through eachother; with an improved collision detection it would be relatively easy (and admittedly lazy) way of doing something when they collide, like playing an animation at least. I also created a fog of war effect by using the flashlight method on shooter example, which was awesome!!! Units were leaving behind "destination out" circle "sight" sprites with fade when they the nearest "sight" sprite was at some distance. This meant all the player untis were checking distance for all the created "sight" sprites. Needless to say, even when I did this every .3 seconds, this reduced playability medium unit numbers. So I removed the fog of war.

I also tried to model the "spatial hashing collision detection method as described here via events and it actually reduced the performance. But it's possible that my events were just bad. I think "picking" itself is somehow costly.

And at some part of my game there are interiors, big caves or buildings where units can enter. At one point I thought I could use a side view here for interesting results, however I was scared of the platform behaviours need to collision check with platfrom objects for hundreds of units.

TLDR; I think not only for collision, but also for distance checks, and any behaviour that uses distance/collision, an aproach other than brute force could boost the power of C2 and open for more variation in gameplay made in games with it.

Whev. That was a lot. Thanks for everything already Ashley :)

Construct 2 already effectively has an extremely fast distance check: it rejects collision checks almost immediately via a bounding box check. (This also means trying to add distance checks yourself in events will likely only slow it down.) The only problem is the number of collision checks made. You really need a huge number of collisions for this bounding box check to start using lots of CPU. Often you can optimise this by filtering with conditions above the collision check. For example an 'Is moving' condition above a 'Is overlapping' condition will only collision check the moving objects, e.g. if you're checking for bumping in to other units, which can cut out the majority of the collision checks right away. And then you can reduce it by another 6x or so by checking every 0.1 seconds instead of every tick and so on.

We will eventually optimise it anyway... it is raised regularly on the forums so we're well aware of the need.

Thanks for the quick response.

I'm writing a word game and already have the word list load as a JSON file into a Dictionary object. When I've written this game in the past in other languages, I've implemented simple binary search to find a word in the list, which was fast enough for my needs. Looks like I don't even have to do that for the C2 version.

It appears the Dictionary search is only for the key value?

Right now I have sequential numbers as the keys (first word key is "0", value is word). It seems better to have the word as the key, which frees up the value for some word usage tracking I wabt to add anyway.