Jump to content
  • Advertisement
Sign in to follow this  
Angelic Ice

Ordered Dictionary/Hash Map?

This topic is 677 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello forum!

 

I'm looking for a solution of the following problem in Lua:

 

I calculate the a collision between a mouse click and a tile within a grid.

Now, I can calculate the grid coordinates, but I would like to look it up and access directly.

However, my current implementation is a simple table list, that goes up from object 0  to object n. Like an array.

Therefore, I would have to iterate over all of them in order to find the right object.

 

Now, I thought about implementing a dictionary/hash map. Sadly, this approach kills the possibility to iterate in an ordered manner, which I need for drawing.

 

Am I overlooking a possibility? Any suggestions?

Share this post


Link to post
Share on other sites
Advertisement

No, you're not overlooking something, Lua has no ordered thingies, other than arrays-ish tables. (Edit: and Lua starts at 1, not at 0 !)

 

Simplest solution is to keep an array and an unordered map alongside each other, and use the map for lookup, and the array for drawing.

Note that "alongside" can also be in that array itself, although I don't like that kind of mixing numbers with entries. No idea what that does for iteration speed though.

Edited by Alberth

Share this post


Link to post
Share on other sites

(Edit: and Lua starts at 1, not at 0 !)

True! I forgot about that x (

 

Simplest solution is to keep an array and an unordered map alongside each other, and use the map for lookup, and the array for drawing. Note that "alongside" can also be in that array itself, although I don't like that kind of mixing numbers with entries. No idea what that does for iteration speed though.

I would rather separate them.

I will probably do the following: One array-ish approach, on which Lua makes sure that it is actually iterating in an ordered manner through it.

Additionally, there will be a key-word/hash map-ish approach, that will simply own the references to the array objects.

 

Only one more question, if I would save both approaches. Would they still work? Or would Lua fill in whole objects in my hash-map?

Otherwise, I can hardly imagine how it will preserve the hash-map.

I just want to avoid duplicates in the save-game. Though, it would not matter that much, I guess.

Share this post


Link to post
Share on other sites

Only one more question, if I would save both approaches. Would they still work? Or would Lua fill in whole objects in my hash-map? Otherwise, I can hardly imagine how it will preserve the hash-map. I just want to avoid duplicates in the save-game. Though, it would not matter that much, I guess.
Both the array and the hashmap only have references to the (same) objects, it is not as in C/C++ where a variable represents storage for objects. It's more like Java where a variable is a reference to data (for the non-primitive types), as in "public MyClass c = new MyClass();".

The "value" field of both the array and the map just refer to the same object.

 

One thing I mostly expect to work but I don't know for sure, is preservation of sharing. After save+load, you want that the array and the map still point to the same objects. If that is not the case, an update from the map is not displayed when you access an object from the array.

The simplest way to verify is to do a quick test, I think. Add the map, save, load, and then check if the array and the map still point to shared objects.

Share this post


Link to post
Share on other sites
Both the array and the hashmap only have references to the (same) objects, it is not as in C/C++ where a variable represents storage for objects. It's more like Java where a variable is a reference to data (for the non-primitive types), as in "public MyClass c = new MyClass();". The "value" field of both the array and the map just refer to the same object.

Yes, but upon serialising, I will have to serialise the actual values.

If I do this for the hash table too, I would have duplicates. That is what I'm worrying about - well, it is rather premature optimising. I know this is a bad habit, just curious whether there is a slicker way.

Even if I could store the address of the allocated memory... once GC or the application is being restarted, the address is worthless.

 

Any ideas for this? I could of course iterate once through the array-table in order to create the hash one.

Edited by Angelic Ice

Share this post


Link to post
Share on other sites

Yes, but upon serialising, I will have to serialise the actual values. If I do this for the hash table too, I would have duplicates. That is what I'm worrying about - well, it is rather premature optimising.
Right, so sharing won't survive serialization? I would call that a very limited form of serialization for a language where references is one of the core foundations.

 

Unless you never ever modify the objects, things will break.

 

 

Options that you have are either extend the serialization, or delete the map just before saving and rebuilding it again after loading.

Share this post


Link to post
Share on other sites

Hello forum!

 

I'm looking for a solution of the following problem in Lua:

 

I calculate the a collision between a mouse click and a tile within a grid.

Now, I can calculate the grid coordinates, but I would like to look it up and access directly.

However, my current implementation is a simple table list, that goes up from object 0  to object n. Like an array.

Therefore, I would have to iterate over all of them in order to find the right object.

 

Now, I thought about implementing a dictionary/hash map. Sadly, this approach kills the possibility to iterate in an ordered manner, which I need for drawing.

 

Am I overlooking a possibility? Any suggestions?

The solution is quite simple, you need to de/encode the grid position to the map index for direct access, typically like this:

function grid2Index(x,y)
  return x + y * map_width + 1
end
function index2Grid( i)
  return (i-1)%map_width, math.floor((i-1)/map_width)
end

Share this post


Link to post
Share on other sites
How do you serialise the data? It's definitely possible to serialise a bag of multiply referenced interconnected tables while preserving those reference semantics instead of turning them into duplicate values.

Share this post


Link to post
Share on other sites

I'm saving them as Lua tables.

 

Hodgman, do you mean something like this?

array_approach = {
	[1] = {
		["value"] = 1;
	};
}

hash_approach = {
	["key"] = array_approach[1];
}

This could indeed work.

Share this post


Link to post
Share on other sites

I'm saving them as Lua tables.

 

Hodgman, do you mean something like this?

array_approach = {
	[1] = {
		["value"] = 1;
	};
}

hash_approach = {
	["key"] = array_approach[1];
}

This could indeed work.

You can remove multiple references to the same table (which results in more serialization/deserialisation overhead) simply by refering the index instead of the table:

array_approach = {
	[1] = {
		["value"] = 1,
	},
}

hash_approach = {
	["key"] = 1,
}

-- return nil if the key is unknown
function getTileByKey( _key) 
  local i = hash_approach[_key]
  if i~=nil then
    return array_approach[i]
  end
end


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!