Hex Grid mechanics/logic


(Monster) #2

Just some thoughts while analyzing your file. It might appear a little bit chaotic and it is. It follows the steps I did (at least the major steps).

Brush builds your grid?

In that case I suggest to change the name of the function to “buildGrid”, “makeMap” or something like that as this is what it is doing. As this is a major function (at least a function a reader will be interested in) I suggest to place it at the top of the code rather than at the end.

I would go a step deeper and rename the module from “drawGrid” to lets say “grid” as it represents grid(s) not just drawing it.

So you can get “grid.build”.

When you move the classes and internals to a separate module, lets say board.py you can move the bge callable function from mOver.py to grid.py. When you rename it from go() to something more expressive e.g. selectTile() [I guess it selects the tile under the cursor), it would look a bit more helpful.

Just now I do not know what part of your code handles your blast. There is too less information to quickly identify it.

Lets start at mOver.py. I guessed it selects a tile. You placed your blast when selecting. So there must be a relationship.


it sets

core['board'].targetHex = ...

I know from drawGrid that core[‘board’] is you current grid
so I assume targetHex is the selected tile.

So lets see what happens with that…

  • it is assumed to be a list
  • it is checked in “main” [whatever main means ;)]
    –> it is used to get A
  • it is checked again in “main”
    –> it is used to set the position of target
    –> there it is —> cube_areaDraw()

lets follow cube_areaDraw().

The name is fine. It is a bit hidden under the lots of over code.

I assume h means tile … no it is Cube which contains coordinates.
A bit confusing … you override h with a complete different datatype.
First it is a Tile (why is a tile called h?).
Then it is a Cube (why is a cube called h?).

I guess r= radius (as it is used as argument I suggest to use the real name rather than a abbreviation).

You do a nested loop => two dimensional processing. This looks like the are blast/area code we are looking for.

Cause:
You always create a full set of Cubes.
Expectation:
At the border I would expect a smaller set as the “out-of-bounds” Cubes should not be in results.
Solution:
So I think you are missing some limit checks either in the loops range (more efficient) or when creating/appending the results.

Finally you managed to display the result “wrapped” otherwise you would see the “out-of-bounds” Cubes being out of the grid.
I think showing the incorrect Cubes might be incorrect too.

Lets see where the results end in real objects. … back to the caller of cube_areaDraw() [which does not draw anything, but creates the Cubes of an area] -> “main”

Here is a loop that adds the objects. I guess this is the “real” areaDraw() -> may be encapsulate in “drawCubes”?

I do not see an obvious wrapping.

… cube_to_hex() we convert the cube back … .ah there is a Hex type … what is the difference to Tile?

Means my above statement is not good. “h” for hex is fine (but “h” for Cube is still not).

You place the “brush” ( I guess it acts as cursor) at the location taken of the map and add a new object. I assume “out-of-bound” coordinate would fail the map access.

Here it is, your try: except statement catches that at least it is supposed to do this. Yes, it is a valid bounds check (but I think it might be a little late).

Hint:

  • an except statement should always have an explicit expected error type. Otherwise you hide any unexpected errors and you get no idea why your code behaves like an idiot if it fails ;).
  • keep the try block with less statements as possible. Otherwise you might catch errors from irrelevant code. In your situation you can simply skip the current iteration:

for cube in self.areaHexes:
    hex = cube_to_hex(cube)
    try:					
        self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    except KeyError:
        continue
    pip = logic.getCurrentScene().addObject('LINE', self.brush)
    self.areaHexPips.append(pip)

I just recognize you constantly rebuild the area. This is not really efficient :wink: and is really disturbing on debugging (via print statements).

Ok now I see. Your “self.map” is not a map/dict.
It is a list. Python lists deal with “out-of-bounds” values by wrapping the indices. -> This is your problem.

Solutions:
Either you say this is fine (it is a valid behavior),
or you do a different limit check than try…except.

Be aware this cures the symptom not the cause (see above)


(Nines) #3

Thank you for the insight, Monster!

Yes, I am aware that the code in that file is a ****ing mess! It is a first prototype I’ve put together, a sort of ‘get it working’ approach. I have methods which begin as doing one task, but eventually get migrated into doing a different task, without me changing the name of the method (bad!) It will certainly be split out into modules, cleaned up, made more efficient, and everything else.

But, here is the code which finds the area around a hex: I did clean it up a bit to make it less confusing:


def cube_areaDraw(h,r):      #find hexes within 'r' steps of hex 'h' and return as a list
	c = hex_to_cube(h)
	results = []
	for dx in range(c.x-r, c.x+r+1):
		for dy in range(max(c.y-r, c.y-dx-r),min(c.y+r, -c.y-dx+r)+1):
			dz = -dx-dy
                        #below is my hack to cut corners out of the rhombus
			h1 = cube_to_hex(Cube(dx,dy,dz))
			h2 = cube_to_hex(c)
			if abs(h2.r-h1.r) <= r:
				results.append(Cube(dx,dy,dz))	
	return results

Without the last lines there, you get a ‘rhombus’ shape rather than a ‘circle’. The “if abs(h2.r-h1.r) <= r:” just cuts the corners off the rhombus to make it a circle (or rather, a hexagon). The original code I got this from did not need to do this, so this has me confused a little…
Although I have a good feeling it’s how I’m storing the map (it’s generating a ‘square’ against the map array, which is translating into a slanted rhombus in the hex grid).


So how would I prevent my lists from wrapping out-of-bounds indices?


This is the particular issue which is causing me grief.

Here is the process for getting to where I’m at, concerning the ‘blast radius’:

-“Board” holds info for the map as a whole, in its main-loop it checks for targetHex (where/if the blue marker is placed). If so, it runs cube_areaDraw().
-Board has two sets of lists, areaHexes which just holds generic Cube objects to store coordinates. areaHexPips holds the KX_Gameobjects which represents those areaHexes coordinates in the view. The code for this is like so (in Board.main()):


for pip in self.areaHexPips:
	pip.endObject()
self.areaHexPips = []
self.areaHexes = cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3)
for cube in self.areaHexes:
	hex = cube_to_hex(cube)
	self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
	pip = logic.getCurrentScene().addObject('LINE', self.brush)
	self.areaHexPips.append(pip)

Where would I want to put the check to squelch out-of-bounds entries into areaHexes?


(iamthwee) #4

Can’t you just write a check bounds function? I mean it’s pretty simple coding 101 :wink:


(Nines) #5

Too simple to warrant an example/explanation, I guess?

My guess is that the areaHex coords are giving self.map negative indices, resulting in the ‘wrapping’ it’s doing (and hence why it’s not wrapping from the end of the list back to the beginning).

So maybe, something like:


for cube in self.areaHexes:
    hex = cube_to_hex(cube)
   <i><b> if self.map[hex.q] &gt;= 0 and self.map[hex.r+hex.q//2] &gt;= 0:</b></i>
         self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
         pip = logic.getCurrentScene().addObject('LINE', self.brush)
         self.areaHexPips.append(pip)

I will play with that and see what happens. If this isn’t what you mean by a ‘check bounds function’, please enlighten me.

EDIT: That doesn’t work. Still stumped.


(iamthwee) #6

Just think of it like a 2d array where each element is a coordinate.

You should be able to code up a check bounds function. That’s all it is really. Then you use a nested for loop to block in the hexagons. Why not try a simple ascii program first? Unless I’m missing something patently obvious?


(agoose77) #7

Well that was fun!

The hex grid mathematics are interesting, I’d not really given much thought into different grid structures before.

Your problem stems from the fact that you permit negative coordinates within a list structure, which wraps around negative indices. Switching to a dictionary based lookup can fix this issue. You could also shift your indices to fix this, but that may be more problematic than not.

I also took the liberty of removing the logic from the tiles (that will quickly become a bottleneck, due to each tile performing a raycast), and a little bit of code cleanup (i’m fussy).

hex_tests.blend (555 KB)


(Smoking_mirror) #8

When I saw the title of the thread I was going to link to that article, but you found it already. :slight_smile:
I think as Agoose says, dictionary structure will work better than arrays/lists.

Have fun! I’ve never finished a hex based prototype before…


(Nines) #9

Thank you all for your help! Using a dictionary instead of a list to store the map is something that never occured to me. The site I linked mentioned something about ‘shifting the indices’ but I could not quite wrap my head around the concept (as simple as it seems to be).

A new, optimized version of this is already in the works. I will post it when it’s ready to go.

More than likely, more issues will arise, so I may keep this as a running thread for future issues (directional LOS, pathfinding, etc etc). I’ve played around a lot with square grid systems like this, so I figured hex grids would be fun! How much more difficult could it be? :smiley:


(Monster) #10

I think that this is a good idea.

cube_areaDraw() runs on an infinity grid. Therefore it produces valid Cubes only.
You apply the “areaCubes” by


self.areaHexes = cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3)

Now the cubes have a relation to the board and can be verified against the board’s limits.

There are some options:

A) Assign valid cubes only (your original approach)
cube_areaDraw() remains unattached and creates all area cubes in an endless world.
When applying it to the Board you do the validity check and skip all invalid objects via a validation method. [You implicitly did that with the try…except clause - but this did not work as expected]


def isValidCube(self, cube):
   # check cube against map limits

so you can replace


hex = cube_to_hex(cube)
try:
    self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    pip = logic.getCurrentScene().addObject('LINE', self.brush)
    self.areaHexPips.append(pip)
except:
    pass

with


if self.isValidCube(cube):
    hex = cube_to_hex(cube) 
    self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    pip = logic.getCurrentScene().addObject('LINE', self.brush)
    self.areaHexPips.append(pip)

Your original approach did not remove the invalid cubes. They still exist in self.areaHexes (which are Cubes btw ;)). It might have been a good idea to store them in a local variable rather than a member variable.
self.areaHexPips should be valid (when the check works as expected).

B) operate on Board and use factory method
You integrate cube_areaDraw() into Board, and let it operate on the map. This way you can skip any outside cubes before you even create them.
The code stays pretty much the same except the Cube creation. You replace them with a factory method


def cube_areaDraw(self, h,r):
    ...
    # old code: results.append(Cube(dx,dy,dz))
    cube = self.createCube(dx,dy,dz)
    if cube:
        result.append(cube)

...
def createCube(self, x,y,z):
    if self.isValidPosition(x,y,z):
        cube = Cube(x,y,z)
        return cube
    else:
        return None
...
self.areaHexes = self.cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3)

C) Use a factory
You tell cube_areaDraw() who creates cubes


def cube_areaDraw(h,r, cubeFactory):
    ...
    # old code: results.append(Cube(dx,dy,dz))
    cube = cubeFactory.createCube(dx,dy,dz)
    if cube:
        result.append(cube)

...
# Board can be the factory 
def createCube(self, x,y,z):
    if self.isValidPosition(x,y,z):
        cube = Cube(x,y,z)
        return cube
    else:
        return None

...
self.areaHexes = cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3, self) # self = factory = Board

D) use a factory funtion
you tell cube_areaDraw() how to create cubes


def cube_areaDraw(h,r, createCube):
    ...
    # old code: results.append(Cube(dx,dy,dz))
    cube = createCube(dx,dy,dz)
    if cube:
        result.append(cube)

...
def createCube(x,y,z):
    
# Board can be the factory as above
def createCube(self, x,y,z):
    if self.isValidPosition(x,y,z):
        cube = Cube(x,y,z)
        return cube
    else:
        return None

...
self.areaHexes = cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3, self.createCube) # self.createCube = factory function

Operate on Hex rather than Cube
A further alternative would be validate the Hex while creating - as this is what you are using. The cubes are just input and you throw them away after you got the Hex.

I think it sounds more logically this way.

Line
Before I forget, the same principle belongs to line. You do not see a problem right now as you currently can’t create invalid Cubes/Hex. But what if your Board is not convex anymore?

Messy code
Btw. My code looks messy at the beginning too. So do not worry about your code :smiley:


(Monster) #11

Another hint:

You create a lot of Hex at different places:


for cube in self.lineHexes:
    hex = cube_to_hex(cube)
    self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    tile = logic.getCurrentScene().addObject('LINE', self.brush)
    self.lineHexPips.append(tile)

....
for cube in self.areaHexes:
    hex = cube_to_hex(cube)
    self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    pip = logic.getCurrentScene().addObject('LINE', self.brush)
    self.areaHexPips.append(pip)

This is pretty much the same code. Just the input varies.

I suggest to encapsulate the inner block into a function e.g. createPip()


def createPip(self, cube):
    hex = cube_to_hex(cube)
    self.brush.worldPosition = self.map[hex.q][hex.r+hex.q//2].pip.worldPosition
    return logic.getCurrentScene().addObject('LINE', self.brush)

which reduces the above code to:


for cube in self.lineHexes:
     self.lineHexPips.append(self.createPip(cube))
...
for cube in self.areaHexes:
    self.areaHexPips.append(self.createPip(cube))

or even further


self.lineHexes = self.createPips(cube_lineDraw(A,B))
...
self.areaHexPips = self.createPips(cube_areaDraw(Hex(self.targetHex[0],self.targetHex[1]), 3))

...
def createPips(self, cubes):
    return [self.createPip(cube) for cube in cubes]

Here you might see you do not need self.lineHexes and self.areaHexes

[Edit]
This would fit very well with the validation mentioned in post#10:


def createPips(self, cubes):
    return [self.createPip(cube) for cube in cubes if self.isValidCube(cube)]


(Nines) #12

hex_tests2.zip (98.1 KB)

An update (done before Monster’s two posts immediately above, a lot of good ideas there!).

The script has been overhauled, converted to external modules, and greatly cleaned up. Hopefully this is a little easier code to work with.

You can now use the up/down arrow keys to increase/decrease the radius of the area drawn.

Something is going funky with the line drawing now, though. Something got off on the way to converting from the old script to the new. I’m pretty certain it’s a silly error/typo on my part, but I can’t hunt it down for the life of me…


(Monster) #13

Second Version
It seems to work. Looks better now.

Line Draw
I guess there is some mixed coordinate on the line calculation. (I will have a look later at that topic).

Default value
Hint: You can give a property a default value when reading. So in listen.py you can replace


prefix = ""
if 'prefix' in own:
    prefix = own['prefix']

with


prefix = own.get('prefix', "")

Hiding values
(listen.py)
You successfully retrieve the body from the message. Unfortunately you still set the text if there is none. This clears out the text you set before.

This is pretty simple to solve.
Replace


if incoming.positive:
    body = incoming.bodies[0]
own.text = prefix+body+suffix

with


[if incoming.positive:
    body = incoming.bodies[0]
    own.text = prefix+body+suffix # --&gt; just moved into the sensor.positive block

This is the reason why most of my BGE callable functions start with “if not allSensorsPositive(): return”

[edit]
Printing class instances
The default printing only tells you what class the object is and what internal id is has. So not really something useful.

But your both classes Cube and Hex have some more interesting information: the coordinates

For easier printing of your classes to the console I strongly suggest to override the default output.
Example:


class Hex:
	# better use doc strings to describe your class
	"""A generic Hex object w/ axial coordinates"""
...
	def __repr__(self):
                return "Hex({},{})".format(
                        self.p, self.q)

class Cube:
	"""A generic Cube object w/ cubic coordinates"""
...
	def __repr__(self):
                return "Cube({},{},{})".format(
                        self.x, self.y, self.z)

a cube would look like this:


Cube(3,-6,3)

Efficiency
As I wrote earlier the constantly running code is really disturbing when debugging. When adding print statements the console is flooded with output. As this is not necessary I strongly suggest to review your sensor settings.

Brush
Always with [True Level Trigger]. There is no need to run the “goGo” all the time. Run it once to create the grid and that is all -> rename it to “on creation”, switch off [True Level Trigger].

Message incoming - is fine. But here I would enable [True Level Trigger] as consecutive messages needs to be processed too. Btw. What is this message telling?

Mouse MouseOver. Activate [Pulse] that it updates when the mouse over detects a different HEX. I suggest to name the sensor “over HEX” - reads -> Mouse over Hex

Mouse MouseClick. Why tap? that is useless here … deactivate it. The controller gets triggered when you press or release the button. I’m sure you only need the “just pressed” event. I suggest to call this sensor “set area” to express this event sets the area.

With this changes (mainly the change at the Always) it is possible to produce better output in your console. As positive side effect, it runs much faster.

Example output (printing the results of cube_line):


Blender Game Engine Started
[]
[]
[]
[]
[]
[]
[]
[]
[]
[]
[]
[]
[]
[]
[Cube(3,-6,3)]
[Cube(3,-6,3)]
[Cube(3,-6,3)]
[Cube(3,-5,2)]
[Cube(3,-5,2)]
[Cube(3,-5,2)]
[Cube(4,-6,2), Cube(3,-6,3)]
[Cube(4,-6,2), Cube(3,-6,3)]
[Cube(4,-6,2), Cube(3,-6,3)]
[Cube(4,-6,2), Cube(3,-6,3)]
[Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(5,-6,1), Cube(4,-6,2), Cube(3,-6,3)]
[Cube(6,-7,1), Cube(5,-7,2), Cube(4,-7,3), Cube(3,-6,3)]
[Cube(6,-7,1), Cube(5,-7,2), Cube(4,-7,3), Cube(3,-6,3)]

there are still repetitions, but much better than before.


(Monster) #14

I can tell the distance calculation between the cubes is not correct.

e.g. you get a distance of 1 between 5|4 and 3|5 but the you need at least two steps to get there. Therefore your draw_line skips one tile.

I’m sure this is not the only issue. If you look you get additional tiles when the line is drawn from downwards/to the left and you miss tiles at the other directions.


(Nines) #15

Following more of Monster’s sage advice (object.get() is a trick I always forget about!). Lines are only being calculated when a new hex is moused over, and drawing a line prints out a comprehensive list of axial coordinates (q/r) of all hexes in the line. According to my output, no hexes are being duplicated in lineHexes (perhaps not having board.main on true trigger pulse fixed that?)

The problems persist though, and it behaves the same (albiet a bit faster now :wink: ), so not much to see in this update…
hex_test3.zip (97.9 KB)

There is a pattern to the error in the line. I can see it. An experiment:

-Select the top-left hex (0,8). Now move the mouse down along the ‘southeast’ hex side to (9,3) and watch how the line ‘shifts’ between columns. It appears correct if you’re over an odd column, and shifts odd-columned hexes up one when over an even column

-Now select map hex (1,7) and do the same thing. Mouse over to (9,3) and watch how the line remains ‘true’ no matter which column you’re mousing over.
-Going from the bottom-left to top-right looks like it gives the same pattern.

-Now select a map on the bottom right and mouse toward the upper-left. There is still a pattern, but it’s different. You see no-hex, hex, no-hex, hex, hex, no-hex, hex…

-if you go top-right to bottom-left, the line almost looks right, but you get these little ‘nubbies’ where they shouldn’t be, about every other column (the odd columns!)

-If you try drawing any lines straight up-down, or straight left-right (as well as you can do that anyway) it appears you always get a clean line.


(Nines) #16

I will try to explain what I did, before I forgot what I did :wink:

-The root of the problem went way back to when buildGrid is defining new coordinates for the ‘0,0’ coordinates given to the default Tiles when the map is first defined.


tile.hex.q = x
tile.hex.r = y

should be


tile.hex.q = x
tile.hex.r = y-x//2

(this was in the original script, and was incorrectly re-typed by Nines in the new script.:o)

Now, Board has a method:


def getMapTile(self,q,r):
    return self.map[q][r+q//2]

Which takes the off-set coordinates defined in the Tile, and ‘on-sets’ them? Anyway, when you want to refer to a Tile on Board’s map, use board’s .getMapTile(column, row). The line in findLine() which sets the brush’s position for marker spawning has been changed to:


self.brush.worldPosition = self.getMapTile(hex.q,hex.r).pip.worldPosition

There may have been a few other tweaks here and there to get it working (I had nearly gotten to the point of randomly mixing up variables just to see if I could fix it by mistake).

EDIT: real-time area radius changes can be enabled by noodling the keyboard sensors to the Go.go controller.

Attachments

hex_test_line_area.zip (98 KB)


(agoose77) #17

As you’ve discovered, it was an artifact of using the x, y coordinates for q, r coordinates.
It took me a little longer to find that, as I didn’t compare your older file until a while later.

Besides making that change, I also:

  • Switched you over to an Axial / Cubic arrangement, and added a Cubic display option. I did this in order to better see how your graph should look, compared with the reference.
  • Removed most of the utility logic and added it directly to the Hex / Cube classes, as well as removed the duplicate types.
  • Accounted for an artifact that can occur on diagonals, moving the e displacement to the end points.
  • Added an alternative, single definition of Cube/ Hex as they essentially views of the same data.

hex_view.zip (88 KB)
normal_hex.zip (88.1 KB)


(Nines) #18

Good stuff!
I’ve been having issues with my computer the last few days, and haven’t had much of a chance to play with this.
Things are (mostly) in working order now.

Agoose’s scripts look great! I will work on integrating some of the changes I made in mine to his, and probably be using that from now on. Thanks, Agoose!

Next I will probably be working on trying to put units on the board. Controls to move/rotate them and move them alone cleanly and easily along the grid. Should be straight-forward (although we all know that these things rarely are :wink: )

One thing I’ve been trying to ponder is how to calculate the ‘arc of fire’. Say something like this:


With some playing around, I came up with this idea, although it seems kind of inefficient…
-March one hex ‘forward’ and calculate the area from there with radius 1. Append those hexes to an ‘arc’ list
-Now, as an algorithm, march 2 hexes forward, increase the radius by +1, and append those hexes (ignoring ‘overlaps’)
-Keep doing this until no valid hexes are found in an findArea call.

But, I am probably getting ahead of myself here. There are other things which need to be tackled before this can even be tested.

There is a link to this demo which does pretty much what I want (although with a wider angle). It appears it does something like ‘sweeping’ a line between two angles relative to the player’s facing. I’ve taken a look at the source for that, but it is in Java which is kind of greek to me.


(agoose77) #19

It looks like two line traces and the area between filled


(Nines) #20

Alright. I’ve got basic unit spawning and control working. It will have to be expanded soon to handle multiple units. A unit can change its facing and move forward and backward, without any ‘cross-chatter’ between turning and walking. Declaring movement (for now) should be a nice smooth, methodical turn turn walk walk turn walk walk Go. Functionality should be put in place for undo/restarting movement as well.
The ‘unit’ you control now will probably be a ‘ghost unit’ which is used to declare movement. The actual Unit (whatever it gets called…the one with weapons and stats and all that jazz), will then follow the path of the ghost once a move has been finalized.
I also added a camera rotation/movement control (or, hijacked the camera system from NSoO) so you can make large boards and navigate around them.

As far as finding firing arcs, we could skip trying to find every hex within the arc, and just test vectors to other units and see if they lie within the arc. That coupled with a LOS/range check can declare if a unit is a viable target or not.

I will post an updated package soon. I want to go through the new unit code first and make do some general clean-up of the project.
While I’m at it, I might as well put together a thread in the WIP forum, as this is surely to that point.


(Algaris) #21

@Nines

I’m absolutely loving this thread, its a great resource for em as I’ve got a similar project I’m working on. I’m wondering if you ever got around to finishing this. Can you post an update?