Storing unit locations in Hex/squ based games
Community Forums/Technical Discourse/Storing unit locations in Hex/squ based games
| ||
| 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 |
| ||
| 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 |
| ||
| 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. |
| ||
| 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 |
| ||
| 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. |
| ||
| 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... |
| ||
| Adam, your right, looks like a better version map_strength[x,y] map_unit[x,y] map_terrain[x,y] |
| ||
| 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. |
| ||
| If you need reminders... Use Const MAP_STRENGTH:int = 1 map[x,y, MAP_STRENGTH] = bla Bye Ron |
| ||
| 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 |
| ||
| 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 |
| ||
| 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 |
| ||
| 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 :) |
| ||
| 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 |
| ||
| 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. |
   |