Simple Unit Floating System v1.1

[Moderator]

19 Oct 2015 07:07
Bribe: I really like the smoothness of the floating and would be good to make a non-floating model into one that does float. A couple of things:

When I set the minimum height to 100, the unit would still touch the ground.

Turning on the loop trigger is only necessary if the floating unit count is equal to 1. That's why Purge and the others recommended using a FloatCount integer so you can keep track. This way, you don't have to use CountUnitsInGroup when you remove a unit from a group - just check if FloatCount is equal to 0.

old

20:55, 9th May 2013
PurgeandFire111:

The variables FU_MaxHeight and FU_MinHeight aren't needed. Just save the values of FU_MaxHeightSet and FU_MinHeightSet directly.

As Maker said, you shouldn't check if the group is empty every loop. It means an extra enumeration per loop (which is a drag on performance). I recommend using an integer variable -> increase it by 1 every time FU Event is ran, then decrease by 1 every time the unit is removed from the group. Then you can replace the condition for "<Unit Group> is empty" with "SomeInt Equal to 0".

 

[defskull]

Reserved.

 

[ILH]

Hmmm, looks very simple, I will test it

 

[defskull]

Please provide constructive feedback

 

[mckill2009]

its so funny man, anyway pls include the crow form in the system and making an index of an instance is faster than checking an empty group...
I suggest also to remove the global interval and put a periodic event...

 

[defskull]

pls include the crow form in the system

What do you mean by this ?

and making an index of an instance is faster than checking an empty group...

You mean to use Unit Indexer ?

I suggest also to remove the global interval and put a periodic event...

You mean I should just put 0.03 in the FU Loop trigger ?

 

[mckill2009]

instead of making a Simple Auto Fly System, put it in the event...

not Unit Indexer but make a global integer variable, when system runs, add an instance, then when it's cancelled reduce the instance, if it reaches zero off the FU_Loop trigger coz emptying a group in jass contains at least 8 lines of code...

You mean I should just put 0.03 in the FU Loop trigger ?

yes

 

[defskull]

Is checking isUnitInGroup is same (efficient-cost) as isUnitGroupEmpty ?
If it's the same, then no point.

Because if a unit is already affected by this system, and another function tries to insert that unit into this system once more, it will perform isUnitInGroup check to either add 1 of that global integer, or just do nothing to it.

 

[mckill2009]

IsUnitInGroup just checks a particular unit in group, while IsUnitGroupEmpty checks all units therefore making the latter slow, so it's not the same...
And you can perform such check and add the integer if the unit is NOT in group...

 

[Maker]

The least you can do is not to check if the group is empty during every loop, only when you remove a unit from it.

 

[Almia]

The system will be more quick if it uses Indexing by variable arrays or using Unit Indexer + Auto-Fly with variable arrays. Hashtables are slow.

Btw,you can replace the line is Alive with is Dead,because its much faster than is Alive.

 

[defskull]

Btw,you can replace the line is Alive with is Dead,because its much faster than is Alive.

If you are speedfreak, you'd use GetWidgetLife(u) < 0.405.

 

[Almia]

Nah. I will use GetUnitTypeId or IsUnitType XD

 

[Maker]

The system will be more quick if it uses Indexing by variable arrays or using Unit Indexer + Auto-Fly with variable arrays. Hashtables are slow.

The speed difference would me practically immeasurable. This system is not heavy in terms of save/load operations

 

[defskull]

Yay I love Maker

 

[Almia]

@Maker
Oh you beat me
Oh well,my coding knowledge is weak.

 

[Magtheridon96]

You can use the concept of the birthday attack to figure out the variation of the speed of a hashtable.

As more and more hash collisions occur, the hashtable gets slower and slower because the O(n)-complex component of the hash function would begin to emerge (A hashtable is implemented commonly as an array of lists or an array of arrays. An array of arrays is faster than an array of lists because an array of arrays avoids cache misses. Lists access memory addresses in no particular order as the nodes are all over the place in memory. When the arrays get larger and larger, a hashtable lookup starts to have O(n) complexity. This is when a Binary search tree with an algorithm that has O(log n) complexity becomes more advantageous. They could also be using a binary search tree of binary search trees, a binary search tree of arrays or a binary search tree of lists. I don't know what Blizzard does internally, but one of these is the ideal solution for a hashtable.)

Refer to this table from Wikipedia:

We can assume that their key space is 2^16 or 2^32. If their implementation is an array of something, then 2^16 is more likely because all keys can be assumed equi-probable, so logarithmic memory allocation is useless (This explains the 256 limit - too much memory required). If they're using an O(log n) search algorithm via a map for the hashtable, then they can use pretty much anything they want for the key space. In that case, 2^32 makes more sense. We can test for this by creating 255 hashtables and filling them with random data while monitoring memory usage. I have no idea about their implementation, but we can make a very good guess by looking at memory usage and speed variation of 1 hashtable with a ton of data vs. 255 hashtables with the same amount of data spread across. If their key space is 2^16, hashtables will only BEGIN to get slower at an ever increasing rate (still pretty low though) after about 500-600 storages. This is one of the reasons I suspect the 2^16 key space. People have reported different speeds all the time (2x slower, 4x slower, 16x slower, you name it)

 

[defskull]

This could be brought down to a debate contest, Mag.
Are you saying that Hashtable is slow no matter in what condition compared to Indexing ?
I'm just dazed seeing wall of texts @.@"

 

[zv27]

[It seems to me that this is about Formula 1[F1]. Everybody is talking about the speed hahahahaha I love F1]
just kidding

 

[mckill2009]

Mags, even without your explanation & wikipedia, we know already that HT is real slow from the looks of it vs arrays or indexes, but in any case, we cant really meassure the speed in WC3 environment...

 

[defskull]

but in any case, we cant really meassure the speed in WC3 environment...

Because the speed won't get noticed by human eyes, cmon guys ...

 

[Magtheridon96]

Under some conditions, we can measure the speed of a hashtable, but I'm not saying we're going to get accurate results

My point in the above post is that hashtables get slower as you add more values.
They are pretty fast at first, but after you start getting collisions, they only BEGIN to get slower. They're slow after you've put so much data, that there are hash collisions everywhere, and you'd still only notice this speed difference in time critical environments.

 

[defskull]

They're slow after you've put so much data

How much ?

And does this consist in a single hashtable, or hashtable with another hashtable ?

 

[Almia]

I think Mag is right. Since you are looking up the datas inside the hashtables one by one,just like how arrays are iterated. Hashtables are only good for finding values support ( O(1)).

Votes for revision to put indexing.

 

[mckill2009]

Votes for revision to put indexing.

Indexing is best although there's nothing wrong with HT for this...

 

[Almia]

We want speed.

 

[defskull]

mckill meant specifically for this system as it doesn't require overloads of data, you get it Almia ?
Mag said it himself, the hash loading will be slower and slower due to increasing amount of data, by the look of it, this system doesn't handle that kind of amount of data so it's fine.

 

[zv27]

I think the human eye simply has no ability to detect this kind of speed, so ... hmmm ... a waste of time.

 

[defskull]

^
But Mag has a point because in a long-run program (such as OS in Windows or any platform), the program needs to be as efficient as possible and tends to degrade linearly with the increasing time-usage.

But in this case, I could consider it as "negligible" case as it doesn't deal with massive amount of data so it'll be fine.

 

[zv27]

Yes, everything will be fine

 

[Magtheridon96]

How much ?

It will vary depending on how lucky you are and what indexes you're using, but on average, you can measure lookup times between 2 and 4 times slower
There exists a set of indexes that can be used so that the hashtable will be as fast as possible 100% of the time even as you add hundreds of thousands of values, but getting these would require a ton of work O:

 

[PurgeandFire]

Has this been updated for the changes I've suggested? I didn't check--i know you made changes after my post but the triggers in the text weren't changed. If you did update the map, then please update the triggers in the post when you can.

 

[defskull]

I don't update it yet, haha @@"
Later if I got time, I'll update it.
Usually I'll post the updates whenever I make the updates.
Will do in meantime

 

[defskull]

Updated to v1.1.

 

[Bribe]

@defskull, you may want to update your importing instructions now that Unit Indexer is a requirement

 

[defskull]

When I set the minimum height to 100, the unit would still touch the ground.

Been thinking about this before I posted the updated version, let me explain to you something.

When you descend by using a jetpack (assuming jetpack technology has arrived and pretty much can be explained mathematically logic to be done) and at altitude of 200m (moving at 200m/s), you press the "deceleration pedal" to land exactly on the ground with 0m/s (which thrust the jetpack upwards) and your deceleration is 50m/s-2, now let's calculate the distance traveled.

a = (vf^2 - vi^2) / 2s

Where,
a = deceleration
vf = final velocity
vi = initial velocity
s = distance traveled

-50 = (0 - 200^2) / 2s
-50 = -40000/ 2s
2s = 800
s = 400

In this case, you would need a 400m of distance to cover up before having your velocity reduced to 0m/s, so that's why you ended up hitting the ground.

BUT, the trigger does not stops there, the velocity will go back upwards after you have reached the point of nonnegative velocity (defined by calculating velocity per interval in the trigger) - then the unit will continue to float upwards, then the cycle continues.

This decision should be made by the coder themselves to determine which properties are suitable to be set for each variables, after all, we're dealing with physics formula - real life.

Or do you think I should put a SimError to warn the user (and possibly, terminate the Event creation) if they reach the limit when setting the variables ? I could do that, I guess.

 

[Bribe]

Maybe simplify it for laymen by just letting the user define min/max height and how long it takes to bounce, then you do that cool smoothness in the background.

 

[defskull]

The thing is, user is able to set both Speed and Boundary (Min/Max) - and this would actually affect the "unit hitting the ground" issue.

I can't take away those settings fron users as those variables are what the user would like to manipulate, not dictated by the system itself.

I'll do the "showing msg upon reaching limit" in the next version, something like:
"Given for all the variables that you have set, the minimum allowed value for FU_MinHeightSet is " + distanceTraveled + " .Else, your unit will hit the ground"

This way, users will be able to re-assess the values that they set and adjust accordingly.

 

[Bribe]

What about a wrapper that takes the height range and time it takes to bounce, then carves it up into the more advanced formulas before distributing them to the system? This way, you have your scholarly version and your layman version.

 

[defskull]

I... don't understand a thing.
Can you give me example ?

 

[Bribe]

I am trying to make a unit hover at 100 height, teetering between 75 and 125. You said that the speed is the amount traveled in seconds and the deceleration is how much the speed decelerates per second. What do I need to configure it to to make it take 2 seconds to go down and 2 seconds to go up? I've tried even setting the speed high and the decel to 0 and that made it extremely slow for some reason.