koobas.hobune.stream
Whats the best way to keep track of occupied spaces on a hex grid?
My game works on a hex grid that uses a 3-dimensional grid system. Right now I am just keeping a list of occupied hexes and each time something needs to move it checks every adjacent hex against every occupied hex to see if it is occupied. So instead of checking once, it checks once for every unit and building on the board (Hope that makes sense). I want to fix this but I'm unsure of how.
I could use a 2-dimensional array to keep track. The third dimension in my grid system is unnecessary, every space adds up to 0 so (5,-2,-3) would be the same as (5,-2) The reason I didn't use this from the beginning is since my board is hexagonal instead of a rectangle (or diamond as it would be here) the array would have a bunch of extra spaces I don't need to keep track of and I don't know enough about arrays to know how much that would effect it. Is that even a legitimate concern or is there some sort of array alternative (in C#) that would be better suited for what I am trying to do?
this questions is beco$$anonymous$$g a little discussy, because I get the feeling everyone has radically different pictures in their head of the nature of the game, and how many positions it has in each direction! (if they are discrete?)
So you have two choices really - the array you mention and a Dictionary. In the dictionary approach you select a key which is (at its best) a mathematical formula that yields a unique int for every combination of board position. The benefit of this approach is that you only store data when a cell is occupied, the downside is that you either need to check that the dictionary has a particular key or subclass it so you have a version that returns empty when the key is not found. Dictionary lookup is O(1) which is in the same class as an array lookup but it will be a bit slower.
The array will waste space, the question is do you care?
you care if the board is big
cells are sparsely populated
For memory sake you would probably use a 1d array and index into it using exactly the same formula as for the dictionary. Then your overhead will be to do with the number of unpopulated cells. Dictionaries will carry at the very least a 4 byte (size of an int) overhead for every cell compared to the array. So work out that unpopulated amount and figure it from there - it really depends on the size of the thing you are storing in the array or dictionary. If its a 128 byte sized struct then you will need a lot less sparsity for a dictionary to make sense compare to a 4 byte int or bool. if you are storing a class or other reference in there then the wasted space will be 4 bytes per empty entry and a population percentage approaching 50% would dictate an array.
If the board is small then just use the array - the wasted space won't count for much (again based on the size of the thing you are storing).
On reflection you can use a multi-dimensional array, but not a jagged one (to optimise memory usage).
On thinking about your question, the Dictionary approach is closest to your existing list, but for reference a list lookup is an O(n) operation - massively, game killingly worse than a dictionary.
Wow, you are awesome. This is the second answer I've gotten from you and both answered my question and explained exactly what I needed to know to decide on my solution. Thank you so much!
He is totally awesome!
this is the gentlest introduction to "sparse array" thought ever!
I just want to add something for you to think about, as Rodney Brooks points out, "Reality is its own best model". Don't forget you already have (in the game engine) and awesome structured set of data showing all the pieces (namely ...... the pieces!) You could, in fact, do what you say physically - using raycasting and so on.
So you have to program Bejewelled, when doing something like that 45 yrs ago on punchcards we''d use an array, but today you can do it behaviorally .. in a word, give the pieces a little AI of their own, that looks around and decides on things.
Interestingly, if your game is indeed really sparse, I dunno if it's immediately clear that using another data structure is actually faster than basically raycasting around all over the place (depending on the nature of your game, angles involved etc) -- the hex aspect sounds interesting to me, arrays naturally hate those). (For me, I'd choose to do it the "behaviorist" way ... purely because it's sheer fun.)
It's a very interesting insight (well to me anyway) that a typical modern game engine, with raycasting and so on, is in some ways a big solver for problems very analogous to sparse-array like problems.
(thus - there is already a staggering amount of awesome "physical" culling, quadtrees, spatial culling , etc doing on the in the game engine machinery, and funnily enough all those paradigms are exactly what you do when challenged by sparse situations!!)
There was book-length discussion about this here ...
http://answers.unity3d.com/questions/313280/how-to-check-if-3-objects-are-next-to-each-other.html
In summary, it would be INTERESTING to do it by giving each piece a $$anonymous$$d of it's own, enabled likely by raycasting or other physical techniques already available to you in the game engine, am agent or behaviorist approach. Enjoy!
This site is always fascinating for the different approaches it throws up. Personally I wouldn't use raycasting when the model can be represented more simply - there is no control over how the physics engine maps these things and we know that there are at least two methods: one for non-rigidbody colliders (which are probably space partioned) and one for those that are expected to move which are probably in some kind of list or perhaps block mapped space. So it would seem to me that raycasting is most likely to be at worst a O(log(n)) operation - if it is then it is significantly slower than the guaranteed O(1) array or dictionary lookup.
It does depend on your game - but I'd plump for my main game mechanic being under my control and modelled optimally. If there is an O(1) algorithm that models some part of my game I'd use that first and not take the chance. Also the complexities of choosing ray directions etc all take processing time and add to the code clutter.
Here's an analogy: if you have a bunch of related data structures that are huge the most obvious place to put them is in a database. A lot of people will tell you that the thousands of man years put into developing SQLServer, Oracle, $$anonymous$$ySQL etc etc mean that you should just use that database engine no matter what - it will be optimised better than anything you could write yourself.
But that avoids the design principle of RDB$$anonymous$$S systems which are to retrieve all of the items related to an individual quickly - that is totally crap for reporting, so along comes OLAP and that is totally crap for reports or queries that have many dimensions - so if you actually need to manipulate large groups of data (usually for statistical analysis) neither an RDB$$anonymous$$S or an OLAP will actually give you what you want and you are much better off actually writing the processing yourself - we are talking weeks of processing co$$anonymous$$g down to seconds - just down to technique and algorithm selection.
