H2I/GetHandleId, Hashtables in SC2

[maskedpoptart]

Okay so we can use arrays in sc2. Great. But are there any data structures that do the equivalently opposite thing? For example, I have an array of regions. When a unit enters one of these regions, I want to use the entered region to figure out what index of the array that region belongs to (in less than O(n) time). I think Data Tables might do the trick, but the keys have to be strings. Of course, you can convert integers to strings, but I have found no way to get the "handle id" or address of any types. Does anyone know how to do this?

 

[Mooglefrooglian]

Use the O(n) search. It's the only way I've been able to determine.

And I mean gosh, it's not like it's that horrible for processing time unless you have hundreds of regions.

It should be possible to generate a unique integer for a region though - you have its center point and size after all. No other region will have those exact same values. And I'm sure someone has already created a hashtable system by now. I thought I heard geX did all the basic container types for Andromeda, perhaps you could look into it on SC2Mod.

I could probably create a hashtable system myself with some time.

 

[Dr Super Good]

Hashtables are easy to produce, however generating the hashes can be harder.

The easiest way currently I guess would have to be converting the midpoint and size of region to a string and then using that in a data table.

 

[mrzwach]

Sadly, I don't think there is any function that can get a handle yet. I've been using things like custom value for units though, ie the custom value = position array. Dialog items can also use their current value to store information, which helps for having lots of buttons.

Also, you can just define a region using its center and radius (or length/width for rects). However, this won't work for non-regular regions (ie ones that are multipel regions combined) so meh.

 

[maskedpoptart]

Well that is unfortunate. I guess I'll just have to wait and pray that Blizzard fixes this fail... It would really suck if we remain forced to create a different hash function for each type...

 

[Mooglefrooglian]

Andromeda will probably have hashes as part of most type's enrichments anyways, so I dont think you have to worry about that.

The only thing I'm concerned about is making a hash for a unit; theres nothing unique about two units of the same type, so it is impossible. The most you could do is give each unit a unique id in its unit data array I guess.

 

[Dr Super Good]

You clearly have no idea how hashtable systems work. They use a hash for the appriximation of the index the item should be stored at but ultimatly then have to revert to checking weather one item is truly what they are after.

What I am more concerned about is efficency of this. Yes it is doable but not even the average guys behind those save compile extensions will be able to make them ultra efficenctly.

 

[Mooglefrooglian]

You clearly have no idea how hashtable systems work. They use a hash for the appriximation of the index the item should be stored at but ultimatly then have to revert to checking weather one item is truly what they are after.

What I am more concerned about is efficency of this. Yes it is doable but not even the average guys behind those save compile extensions will be able to make them ultra efficenctly.

Emphasis mine. You need to start with a hash to get anywhere. There is no way to get a unique id for any unit as of this time. That means you are going to have to set a constant number to be the hash, or else string hash their unit type. If you do this, then you are going to start getting hash conflicts like crazy, and O(n) time is going to start resulting. The point of using a hashtable is to avoid that.

 

[BlinkBoy]

You clearly have no idea how hashtable systems work. They use a hash for the appriximation of the index the item should be stored at but ultimatly then have to revert to checking weather one item is truly what they are after.

What I am more concerned about is efficency of this. Yes it is doable but not even the average guys behind those save compile extensions will be able to make them ultra efficenctly.

you also forgot to mention that they use linked-lists to avoid collisions and as we know, we haven't any CDT that could actually work like a linked list.

Anyways, I remember there was a way to attach data through behaviors, you should look around sc2mapster to find such tutorial.

 

[Dr Super Good]

The appriximation can be done in a variety of ways with varing degrees of usefullness. If your units never change type you could use that as part of the hash. With buildings that cant move you can use their positions. Etc

Yes however, O(n) efficency is probable at the moment.

I only hope the restrictions currently applied were cause some features were unsafe/unfinished at the time of the beta editor launch.

 

[WanderingPeanut]

I'm not exactly sure what O(n) and all this efficiency business means (so I apologize if this isn't helpful) but couldn't you do:

While
RegionArray[Integer] =! Triggering Region
Set Integer = Integer + 1

I don't think this is particularly efficient but it will get the index of the region, hope I've helped.

 

[Dr Super Good]

Yes but its load can vary. For very small scale tasks its perfectly fine to use but for larger scope sizes you have to use a more direct method of finding the right data.

 

[mrzwach]

O(n) means cycling through each value in an array until you find the correct one.

It works, but if you have a very large array it is inefficient.

 

[Dr Super Good]

Yes but that is worsecase only. The actual load should average at O(n/2) as it should only have to cycle through half (as it stops looping once found). Ofcourse looking for something not in the system would be the full O(n) which is where problems can start efficency wise.

 

[maskedpoptart]

you also forgot to mention that they use linked-lists to avoid collisions and as we know, we haven't any CDT that could actually work like a linked list.

Recall that Jass did not have structs, and thus did not have linked lists. BUT through vJass's use of arrays, it was able to give us structs that could function like linked lists. There is no reason why we can't create something similar to that in Galaxy (since Galaxy structs don't work atm). If Blizzard does not make structs usable by release, I'm sure someone else will through the use of a precompiler.

P.S. I'd prefer that this thread not turn into a tutorial on efficiency and big O notation...