• Create Account

# Hexagonal grid - Code review request

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1DavitosanX  Members   -  Reputation: 328

Like
1Likes
Like

Posted 10 July 2014 - 08:28 AM

Hello! I'm not sure if this belongs here, or in the beginners' section, so excuse me if this code is too bad, or too basic.

I had set a short term goal for myself as an amateur programmer: To implement a hexagonal grid, similar to the one found in the original Fallout. You should be able to move your mouse around and the hexagon that contains the mouse pointer should be highlighted. I thought it would be a good exercise, because unlike a square grid, determining which hexagon contains the mouse pointer is trickier.

I did finish the program, and it does exactly what I want, but I do tend to overcomplicate things and I would appreciate it if people with more  experienced took a look at it and gave me any tips. This was coded in python with pygame.

import pygame
import math

INITIAL_HEXAGON_VERTICES = ((-40,-40),(40,-40),(45,0),(40,40),(-40,40),(-45,0))
GRID_HEIGHT = 10
GRID_WIDTH = 10
VERTEX_COUNT = 6
X_ELEMENT = 0
Y_ELEMENT = 1
FIXED_ANGLE = 0.122 #7 degrees in radians
NOT_MOVING = (0,0)

def calculate_angle(fixed_point,var_point):

opposite = math.fabs(fixed_point[X_ELEMENT] - var_point[X_ELEMENT])

return angle

class Hexagon:

def __init__(self,num,ver):

self.number = num
self.vertices = ver

class InputManager:

def check_events(self):

for event in pygame.event.get():
if event.type == pygame.QUIT:
game.running = False

def mouse_in_grid(self,mouse_pos,hexagons):

result = 0

for counter,hexagon in enumerate(hexagons):

if (mouse_pos[X_ELEMENT] > hexagon.vertices[5][X_ELEMENT]
and mouse_pos[X_ELEMENT] < hexagon.vertices[2][X_ELEMENT]
and mouse_pos[Y_ELEMENT] >= hexagon.vertices[0][Y_ELEMENT]
and mouse_pos[Y_ELEMENT] < hexagon.vertices[3][Y_ELEMENT]):

result = hexagon.number

if (mouse_pos[X_ELEMENT] < hexagon.vertices[0][X_ELEMENT]
and mouse_pos[Y_ELEMENT] < hexagon.vertices[5][Y_ELEMENT]):

angle = calculate_angle(hexagon.vertices[0],mouse_pos)

if angle < FIXED_ANGLE:
result = hexagon.number

if (mouse_pos[X_ELEMENT] > hexagon.vertices[1][X_ELEMENT]
and mouse_pos[Y_ELEMENT] < hexagon.vertices[2][Y_ELEMENT]):

angle = calculate_angle(hexagon.vertices[1],mouse_pos)

if angle < FIXED_ANGLE:
result = hexagon.number

if (mouse_pos[X_ELEMENT] > hexagon.vertices[3][X_ELEMENT]
and mouse_pos[Y_ELEMENT] > hexagon.vertices[2][Y_ELEMENT]):

angle = calculate_angle(hexagon.vertices[3],mouse_pos)

if angle < FIXED_ANGLE:
result = hexagon.number

if (mouse_pos[X_ELEMENT] < hexagon.vertices[4][X_ELEMENT]
and mouse_pos[Y_ELEMENT] > hexagon.vertices[5][Y_ELEMENT]):

angle = calculate_angle(hexagon.vertices[4],mouse_pos)

if angle < FIXED_ANGLE:
result = hexagon.number

return result

class Game:

def __init__(self,resolution,caption):

self.screen = pygame.display.set_mode(resolution)
pygame.display.set_caption(caption)
self.clock = pygame.time.Clock()
self.running = True
self.gray = (220,220,220)
self.green = (50,240,50)
self.black = (0,0,0)
self.hexagons = []
self.current_hexagon = 0

def draw_screen(self):
self.screen.fill(self.gray)

if pygame.mouse.get_rel() != NOT_MOVING:
self.current_hexagon = input_manager.mouse_in_grid(pygame.mouse.get_pos(),self.hexagons)

pygame.draw.polygon(self.screen,self.green,self.hexagons[self.current_hexagon].vertices,3)

pygame.display.flip()

def calculate_grid_points(self):

number = 0

for column in range(GRID_WIDTH):

for row in range(GRID_HEIGHT):

points = []
lift_hexagon = 0

if column % 2 != 0:
lift_hexagon = 40

for point in range(VERTEX_COUNT):

points.append(  ((INITIAL_HEXAGON_VERTICES[point][X_ELEMENT] + (85 * column)),
((INITIAL_HEXAGON_VERTICES[point][Y_ELEMENT] + (80 * row))-lift_hexagon)  ) )

new_hexagon = Hexagon(number,points)
self.hexagons.append(new_hexagon)
number += 1

def main_loop(self,framerate):

self.calculate_grid_points()

while self.running:

self.clock.tick(framerate)
input_manager.check_events()

self.draw_screen()

pygame.quit()

input_manager = InputManager()
game = Game((800,600),"Game")
game.main_loop(60)


Starting out in game programming? Me too! Check out my blog, written by a newbie, for the newbies. http://myowngamejourney.blogspot.mx/

Also, if you don't mind a 5 seconds ad, here's a great free ebook for beginners on the subject of pygame: http://bit.ly/19Bem2q

### #2HappyCoder  Members   -  Reputation: 4418

Like
3Likes
Like

Posted 10 July 2014 - 03:52 PM

Good job on pushing yourself and completing what you set out to do. I do have some suggestions on how you can keep improving.

Anytime code relies on calculating and comparing angles it probably can be improved using vector math. In this case, if and only if a point is inside a hexagon, then the center of that hexagon will be the closer to the point than any other hexagon's center. This means instead of checking angles, you can find what center is closest to the point and that will be the hexagon the point is inside. The only caveat of this method is it will not tell you if the point is outside the map. I have an idea on how to fix this, but I don't want to take the fun away of having you solve that for yourself.

Also, I don't think that the logic for hexagon detection should be in the input manger. I think there should be a HexagonBoard class that contains the centers of all of the hexagons. It then should have a method where you pass in a point and it tells you what hexigon that point is inside.

EDIT: I realized that I assumed that your hexagons are regular. If they are stretched in anyway, then my suggested method would not work. However, there are ways to correct this.

Edited by HappyCoder, 10 July 2014 - 03:59 PM.

My current game project Platform RPG

### #3Thinias  Members   -  Reputation: 152

Like
3Likes
Like

Posted 11 July 2014 - 01:24 AM

I mirror HappyCoder's sentiment - good job on setting a goal and doing it!

I commend you on your general avoidance of "magic numbers".  The definitions at the top of this file are a great start.  You should look to find ways to remove all of the remaining "magic numbers" and replace them with constant definitions as well.

At first glance, I would make the following suggestion to your architecture: each individual grid unit should be responsible for determining whether a point is inside of it or not.  This coding practice is called Encapsulation, and would make it easier for other engineers to navigate your codebase should it get larger.  It would also allow you to, at some point in the future, modify your grid implementation to use any combination of geometric shapes you desire, rather than being locked into hexagons.  Your InputManager class then becomes a very simple loop that asks a Grid unit "is this point inside of you?"

Architecturally, I might also suggest moving the "calculate_grid_points" implementation into a separate utility executable, and performing the computation ahead of time.  Serialize the results to a file and simply load them back in when your application runs.  In the current implementation it will probably be more expensive to access disk than simply re-generate the data... but as the application scales, generating the data will begin to take longer and longer.  A pre-generated solution will prove superior by the time your game is done.

Like HappyCoder suggested, vector math is probably a better answer for the computation at the core of your algorithm.  The arc tangent function driving your current implementation evaluates to an approximation of an infinite Taylor Expansion (see Calculus); if the "infinite" wasn't a hint... this is expensive !  HappyCoder's suggestion is extremely efficient under the assumptions he made.  Given those same assumptions (regular, evenly distributed hexagons) I would have done the same thing.  Keep in mind if you do choose this approach that computing the absolute distance between two points requires you to take a square root; this square root also evaluates to an approximation of an infinite Taylor Series expansion, and is equally inefficient.  If you're going to do it this way, simply perform your comparisons against the squared values.  If a > 0, b > 0, and a < b, then a2 < b2.  Performing comparisons against squared results will yield the same answer, but much more quickly.

However, allow me to present a different approach which does not rely on these assumptions; there is an algorithm using cross products that will work for any convex, 2-dimensional shape.  Again, this implementation makes it easy to move your grid away from Hexagons at some point in the future if so desired... so long as the desired geometric structure is convex.  The algorithm is based on the following mathematical foundation:

1.  Take a line segment in a 2-dimensional plane denoted by endpoints [a,b].

2.  Take any point on the same 2-dimensional plane, denoted by z.

3.  Compute the cross product between vector [a,b] and vector [a,z], denoted by y.  ya*z - b*a.

4.  If y is positive, the vector [a,z] points to the right of vector [a,b].

5.  If y is negative, the vector [a,z] points to the left of vector [a,b].

With this information, you can compute whether a point is inside a convex polygon by wrapping around the polygon in a clockwise direction.  Compute the cross product for [a,b], [b,c], [c,d], ... etc until you come back to point a.  If [a,b] cross [a,z] is negative, all other cross products should also be <= 0.  If [a,b] cross [a,z] is positive, all other cross products should also be >= 0.  If you come across an inconsistency in this directionality, it means that either the polygon is not convex... or the point is outside of the polygon.  You can then implement this algorithm with a simple, roughly 10 line for loop.  This loop also gets rid of your current algorithm's dependence on magic numbers.

If you want to get serious about optimizations, a static Grid is also a great candidate for building Octrees (or, more appropriately in a 2-dimensional sense... QuadTrees).  The idea here is to simply partition your space such that a point doesn't have to be compared against each and every hexagon.  You break the space into 8 cubes (or 4 rectangles in 2 dimensions) and then test the point against each cube (or rectangle).  Once you know which cube the point is inside, you've eliminated 75% of the individual hexagons which need to be tested.  In general, you've also done so with a much cheaper computation than testing a single hexagon in the first place.  You need to build the partition data beforehand in order for this optimization to be effective... which can get messy if the objects in your partitions are moving (lookup Loose Octrees for a solution to that problem).  Depending on the size of your grid, you can accumulate further partitions within each partition as many times as necessary.

Keep pushing yourself.  This is great!

Edited by Thinias, 12 July 2014 - 05:40 PM.

### #4DavitosanX  Members   -  Reputation: 328

Like
0Likes
Like

Posted 11 July 2014 - 09:26 AM

Thank you both for the encouragement! I wil definitely take some time to really get into your answers. It may be evident now that my knowledge of vector math is poor, and I don't really know how to apply it. I'll read into that, as it seems it'll be far more useful than trigonometry for computer graphics.

About encapsulation, I'm still trying to get it right. I've struggled to grasp OO concepts, but it appears I'm not so far off now.

About optimization, well, I'll certainly take your suggestions into account. But maybe I'll wait a little before applying it, as it may turn a small concept program into a more complex, daunting task.

Thank you again!

Starting out in game programming? Me too! Check out my blog, written by a newbie, for the newbies. http://myowngamejourney.blogspot.mx/

Also, if you don't mind a 5 seconds ad, here's a great free ebook for beginners on the subject of pygame: http://bit.ly/19Bem2q

### #5aregee  Members   -  Reputation: 1072

Like
0Likes
Like

Posted 11 July 2014 - 02:26 PM

. This means instead of checking angles, you can find what center is closest to the point and that will be the hexagon the point is inside.

Won't this mean that you are basically treating the hexagons like circles when you check for boundaries?  How will this affect the corners?  Seems to be a possibility of error-tracking there to me, based on the "sort order" of those hexagons, but maybe it won't be much noticeable?

I am thinking if you are going for the circle method, that you can:

1. Check the closest centre.

2a. if it is inside a circumscribed circle of a hexagon, you are good.

2b. If it is between a circumscribed and inscribed circle of a hexagon, you are in the ambiguous zone and need to do some more calculations to know for sure that you are not actually in a neighbouring hexagon.

If you end up having to do vector math anyway to determine the point 2b, I would certainly go for that method, unless you need some form of optimisation, and point 1 actually will optimise.  Beware premature optimisation though.

Alternatively, you could just reject border cases, but players would probably like continuity, that the selected hexagon flows fluently between hexagons, not blinking on and off between them.

I would go for Thinias solution, as that is the way I have heard about in a distant past, it is exact, and should be fairly fast.

Optimisation possibility so you don't need to test all hexagons:

You do sort of have an estimate on where in your grid the mouse pointer is, just not the exact hexagon.  That means you should not need to search the whole map of hexagons, just a few inside an imagined square around the mouse pointer.  An exercise would be to find the right size of this "search"-square to be sure to find your hexagon.  I imagine you should be able to minimise the amount of hexagons that you need to test to about 9-16, depending on how clever you are about finding the optimum "search square".

Edit:

Just came up with a third method that will work, not exactly elegant, but quick to make, if you are not into vector and matrix math:

Treat each hexagon as a square (or rectangle).

If the mouse pointer is inside the square, then you need to test the diagonal areas to see which side you are.

To do this part of the test, you need to imagine four more squares that contain each diagonal only.

Now you test which of the four imagined squares you are inside.  Then you test if you are on the correct side of the diagonal inside that square.

You are done!  If you are on the correct side, you know the mouse pointer is inside that hexagon.  If it is on the wrong side, you need to test for another hexagon.

I see room for optimisations here too, like only testing two adjacent of those four imagined squares, since the other two will belong to one of the other hexagons anyway.

OR BETTER:  If you test one of the imagined squares, and find that you are outside of it, then you still know which hexagon you are in.  You are in the neighbouring hexagon of that square!

My idea that you do know the general area where the mouse pointer is, as mentioned above still applies, so you should still not need to test all hexagons on the map.

Talking about elegance, I don't think this last method is bad at all.  There are plenty of opportunities to bail out of testing early, and the tests you have to perform should be fast in themselves.

Edited by aregee, 11 July 2014 - 02:59 PM.

### #6HappyCoder  Members   -  Reputation: 4418

Like
1Likes
Like

Posted 11 July 2014 - 02:46 PM

. This means instead of checking angles, you can find what center is closest to the point and that will be the hexagon the point is inside.

Won't this mean that you are basically treating the hexagons like circles when you check for boundaries?  How will this affect the corners?  Seems to be a possibility of error-tracking there to me, based on the "sort order" of those hexagons, but maybe it won't be much noticeable?

It works. At its core, it is a voronoi pattern.

Here is a lengthy article that explains hexagonal grids. Look in point #2b in the Pixel to Hex section. It describes the method of finding the nearest center.

My current game project Platform RPG

### #7aregee  Members   -  Reputation: 1072

Like
0Likes
Like

Posted 11 July 2014 - 03:42 PM

It works. At its core, it is a voronoi pattern.

Here is a lengthy article that explains hexagonal grids. Look in point #2b in the Pixel to Hex section. It describes the method of finding the nearest center.

Ah that is a great article indeed!  Never thought about the connection between Voronoi and hexagonal grids before though.  I think I will make my own hexagonal implementation soon, it is about time, and hexagonals are fun, just need to finish my current project first!

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS