Storing unit locations in Hex/squ based games

Community Forums/Technical Discourse/Storing unit locations in Hex/squ based games

cps(Posted 2017) [#1]
A little itch I keep scratching at, Iím sure that some of you must have come across the question during the game design phase; Where do I store unit location?
Take a typical game using hexís/squares that has a number of units that may inhabit those hexes. A typical setup may contain two extended types;
1. Type AllHexs (methods for manipulating the map) extending Type Hex with data fields
.HexX (top left x co-ord) .HexY (top left y co-ord) .HexType (terrain type, hill, forest etc) etc
2. Type AllUnits (methods for manipulating the units) extending Type Unit with data fields
.UnitOwner (who owns it) .UnitType (Tank, art, inf etc) .UnitMoral (unit's moral) etc
For unit location, I could put a field in Type Hex called .UnitNumber (unit number or say 255 if empty), or a field in Type Unit called .UnitLocaton ( hex number the unit inhabits or 9999 if unit destroyed)

Running my games reveals that it is more likely that I will need a function that has a hex number as a starting point than a unit number, at about 50:1. A routine embedded in a few of my games, reveals that the user is more likely to initiate a change with a known hex number than a known unit number (100:1, yes this is becoming a real niggle). This would indicate that I should use .UnitNumber in the type Hex.
However as games increase in size and complexity more changes to the board based on unit number are occurring and more space is wasted storing effectively zero. Not a problem on boards in the low hundreds of hexes but across a thousand hexes with say 60 units ? And of course starting with unit number and requiring a unitís location from this requires a trawl through all the hexís looking for that number.

To avoid wasting memory and the Hex trawl, I tried .UnitLocation in the Type Units, this produces acres more code as I am continually having to start at a hex location and trawl through Units.UnitLocation to derive a unit number in that location. Note this is a much shorter trawl as there are many fewer units than hexís. I have just tried doing both at once, that is storing the same data in two fields, Hex.UnitNumber and Unit.HexNumber, this not only looks bad but feels bad. (Itís easy to alter a unitís location in one field and forget to alter it in the other field).
This has led me to write common functions that alter both fields to get around programming errors and this has brought the following solution to mind.

A super type dependant on Type AllHexs and Type AllUnits and declared after them called say BodgeIt that extends the Type UnitPos with fields .HexNumber and possible some others etc
Thus (mouse) eventX and eventY are sent to a method in Bodgeit which converts to hex number via a method in AllHexs
And a quick trawl through Bodgeit.HexNumber to derive a unit number (if any) and then manipulate based on the data in AllHexs and AllUnits.

I am simply asking which method the people at the top of the hill found most effective. IE The people who sit supping nectar and munching ambrosia before leaping from peak to peak without oxygen mask or fur coat, while I sit wrapped in furs at base camp wondering which way to hold the ice pick. Not that Iím grovelling.. Hope you can follow this and that Iíve not been too verbose, any input welcome. Have fun cps


Mainsworthy(Posted 2017) [#2]
I cant say I like struggling with complexity, but all I do is I have x and y to represent hex location, then I have a loop to display a window of the map offset by x and y, so as you move around the map by adding or subtractin x and y.

then I have a grid like map[100,100,50] so the window would display
map[x+windowx,y+windowy,1] = unit number
map[x+windowx,y+windowy,2] = terrain number
map[x+windowx,y+windowy,3] = strength

etc filling with all the info on a unit, if you had 2 units in the same hex then keep filling the map[x+windowx,y+windowy,20] = unit number

then when a unit moves you need a loop to move all
map[x+windowx,y+windowy,z] to new destination on the map and delete old map info

also when you come to save a game you just dump the map[] to a file easy peasy.

I don't know if this helps, its as simple as I can make it, it may not be best but it works for me


zzz(Posted 2017) [#3]
I think a quadtree or similar data structure should work well here? Keep your units in a list or something, and use the tree to quickly search for units based on position. This lets you reduce memory footprint by not having to store unit references in your map data, and coordinate-based unit search should be a lot quicker then just looking through your whole list of units every time.


Derron(Posted 2017) [#4]
THexMap - Manager / Controller of THexTile
-> manipulates the map, contains "offsets" (camera)

THexTile
-> "Type Hex"

TUnit
-> a unit on the hex map


To avoid "cross linking" you mustn't have THexTile contain links to the units _and_ the units to have links to the tile they are on now. (if you do so, and delete eg. the hexTile and the unit without resetting their individual links, they will stay in memory forever -> memleak)

But what is possible, is a "soft link". This means you eg. store the "id" (or another unique identifier) of the hext tile in the unit.
If the hex tiles have coordinates, you could store the "tileX,tileY" in the units. When a unit then needs to access certain data of the tile, it could ask the "THexMap" to give it the corresponding tile.
Of course this adds some overhead and it is slower than a direct reference.

On the other hand you could have a list of "currently owning units" for each THexTile.
Using this approach eases the pain for "drawing visible tiles + drawing visible units" (visible units are either "flying" or are attached to a tile).



@ trawls
This happens as soon as you have to decouple things. Indirection and the likes are the result. In my game I use "base types" which could be used by other types (import filex.bmx) without knowing about the "extended type" which does the real work (eg.the extended type could use the "base type" of another object kind without "cyclic dependency").


@ hexnumber, unitnumber
The problem here is "they are numbers". So if you change A you need to change B too.
If you use "objects", you reference them.

So this auto-handles changes (bad example, as it contains a cyclic dependency - car needs to know about wheels and vice versa):

Type TWheel
  Field parentCar:TCar
End Type

Type TCar
  Field name:string
  Field wheels:TWheel[4]
End Type

global car:TCar = new TCar
car.wheels[0] = new TWheel
car.wheels[0].parentCar = car

car.wheels[0].name = "testcar"
print car.name




Back to the question of "who needs what kind of information". Imho you should go from "Map -> Tile -> Unit". Another approach is to have "Map -> Tile" and "Map -> Unit" - with Unit storing the ID of the tile it is on, so it could ask "Map" to get additional information about the tile. If it is allowed to retrieve them - eg possible Movement directions - then this decouples "tile" from "unit", a unit just needs to know whether it could move, not at which location (x,y) or in which animation state a tile is. So a Map is telling a unit if it could move right or left or which tile types are in range.

But let's wait what others think of it.



bye
Ron


Matty(Posted 2017) [#5]
In games I have written that use a map and a set of units, such as an rts I simply store the location reference (x/y coords) in the unit. The map is checked against with a lookup using a grid array (grid array element index = x + y * maxx) when I need to know various qualities about the map.


AdamStrange(Posted 2017) [#6]
My thoughts would be these:
1. using oop types can make thing look simple if you have that training.
2. mainsworthy's map[100,100,50] method may seem inelegant and simplistic, but can also be the best approach where speed and efficiency are required
3. a variation of Mainsworthys would be separate map[x,y] for each 'thing. E.G.
map_strength[x,y]
map_unit[x,y]
map_terrain[x,y]

Of course it would also be simpler to use a type as well
type MyMap
Field stength:int
Field unit:int
Field Terrian:int
end type

map[x,y]:MyMap

The best would be to use the method you are most comfortable with. The problems come when you need to share this code with others...


Mainsworthy(Posted 2017) [#7]
Adam, your right, looks like a better version

map_strength[x,y]
map_unit[x,y]
map_terrain[x,y]


Mainsworthy(Posted 2017) [#8]
This map having all the info is easer for A.I. I think, and having different storage like map_strength[x,y] map_unit[x,y] map_terrain[x,y] is a lot of checks, if its all in map[] the tests for a situation are easier to copy and paste eg if map[x,y,1] > 0 then map[x,y,20] = map[x,y,20] -1 , its better than having a different name for each element of info, but having different elements means you wont get mixed up as to what your checking, but a snippet of text reminder is all that's needed.


Derron(Posted 2017) [#9]
If you need reminders... Use

Const MAP_STRENGTH:int = 1
map[x,y, MAP_STRENGTH] = bla


Bye
Ron


cps(Posted 2017) [#10]
Thanks to all for your input, a variety of ideas and some new concepts that I will have to digest. I may not have made my point clearly enough so an example using 1000 hexes and 100 units.
Creating an array with everything in it based on EventX, EventY converted to suit the arrays dimensions (x=0-25, y=0-40) gives quick and easy access to all data from any event initiated by a mouse click on the board.

What about events that need to change/interact with the array that are triggered by an off board button. Such as, click this to illuminate all units that are out of ammunition?
Or (by the game code) at the start of your turn the code tries to remove the disrupted flag from all your disrupted units. Such events donít have an X,Y value.

The only way to derive the X,Y value (on which all on board drawing and data manipulation is based) would be to trawl (iterate) through a thousand bits of data until you found the unit/units and derive the X,Y from that.
IE Trawl through the supply fields until you find supply=zero, find X,Y of that cell, Use X,Y to draw the 'out of ammo' symbol on the unit.
IE Trawl through the disrupted fields find a set disrupted flag, find X,Y of that cell, use X,Y to obtain data that affects recovery from disruption, depending on result redraw unit with/without disrupted symbol.

The same problem arises if I create two arrays one for unit data and one for terrain data, the advantage being that I only have to move one piece of data (a unit number) when moving from Hex to Hex and I donít have 900 empty data blocks (every block containing a cell for each byte of unit info) in my terrain/board array. The same problems apply to my application of the method of putting data into one or more types.

Of course I may be missing something fundamental, if so please excuse my stupidity. Thank you all again for your ideas, next time we meet I may be holding the ice pick at the correct end. Have fun cps


Henri(Posted 2017) [#11]
Hi,

TLists are quite fast to iterate and under 1000 objects is nothing.
It takes 1 millisec to iterate ten thousand objects on my computer:
Local units:TList = New TList

For Local i:Int = 1 To 10000
	units.addlast( "Unit " + String(i) )
Next

Local start:Int = MilliSecs()

For Local s:String = EachIn units
	If Not s Then Print "Simulating a condition."
Next

Print "Iterating units took " + (MilliSecs() - start) + " msecs."


I would probably use similar approuch as Derron with TUnits to store all data conserning units and just iterate through them. But, as of course programmers always want to optimize even when its not necessary, I'd probably use other lists for units that have special conditions just so that if you want reduce seeking time (even when it's totally unnecessary :-).

-Henri


Derron(Posted 2017) [#12]
I would do like henri suggested.

In my game i have a list/map to store all entries of a specific type. Then I have lists for "filtered" collections of that type. So they contain only available ones or only ones having children (parents) and so on.

In your case a unit which gets out of supply will get added to an outOfSupply-List (if not contained already... For maps the key makes sure already of duplicates avoidance).
Once you restock the supply you remove it from the list again.

I my game I sometimes just invalidate such lists on changes and recreate them on the fly via a getMyList:Tlist() getter.


A unit does not matter what processing power tbe map needs to return the requested information but of course you could cache information like the current hex tile (or indirect with xy or a guid).


Bye
Ron


Mainsworthy(Posted 2017) [#13]
Derron I like that CONST , I never bothered to use any,It wasn't because I didn't know about them,thats a great example. but I shall use them now :)


Mainsworthy(Posted 2017) [#14]
even if you want to not look at all the zero entries, the app will still have to check in someway for all the data, so even if you cut memory storage for not having a data entry, the program still has to ask. so if you build a list of units with no ammo you would still have to check it wont just be no ammo, or you would need to check for ammo, all the data has to be trawled / stored in some way. the thing your looking for is to check only the units on the map not all the empty hexes. but the units live by the map, they coexist with terrain and supply chains. if no unit is found at a hex you don't check all the data at that hex, so your only trawling the data if a unit exists at that hex, and to be honest computers are great at numbercrunching so don't worry, and you have gigabytes now not 64kb

off board stuff happens by trawling, but you only see the window, the window to the map is for us humans, the computer dosnt care about sight, it calculates


cps(Posted 2017) [#15]
So what has scratching this itch taught me?
There are as many methods as there are coders. Some of the methods I have tried and discarded could be of use with a few variations that I hadnít thought of. 'quadtreeí is out there and needs some serious study.
A reminder that cpu cycles and memory worries are things of the past and that my question has more to do with aesthetics than programming.
It has also got me to examine some of the routines in my bag of tricks, most of which were created on the hoof and as they work I have never gone back to them.
Thanks to some of the ideas raised I can see a better (more pleasing) way of doing things and as an extra morsel, a nice usage of the constant variable to label fields in an array.

Iíve decided to try TLists for disposable data and soft-linking (yes a light bulb went on somewhere), both of which have cropped up in my programs but for some reason not as an answer to my question.
Could it be that thinking and keyboard tapping at one in the morning are incompatible?
So my future output should have fewer discordant bits and Iíll be a happy little bunny strolling through my netherworld of code. Many thanks to you all for your input have fun cps.