NewsForumsCodeLogsGallerySpecsSearch

Creating a line on an hex grid.

BlitzMax Forums/BlitzMax Programming/Creating a line on an hex grid.

Smurftra(Posted 2006) [#1]
I've been looking all over the web to find a way to create a line between two hexes in an hex grid. The only working implementations i found are unpracticale for me giving the coordinate system they use.

I work with a 2d array, and i offset every Odd column by half my hex's height.

So my array looks like this:



Now i've tried several approaches and all of them fail at some point.

here are the approaches i tried:




1) Shortest distance

Start from Source Hex.
Compare the graphical distance between each of the adjacent hex and the Destination Hex.
Move to the Hex with the smallest distance.
Loop until i reach Destination Hex.

This works in a way that it will find the shortest path between both hexs (in terms of number of hexes), but it doesnt give a nice 'straight' line.



An example of a bad result it gives is this:
(Green = Start, Blue = End, Red = Path)



but this is what i want (a straighter looking line)




2) Moving along a line

I use the X,Y coords of my Array (not the graphical representation)
I change Y so Y = Y * 2 + (X mod 2)

so basicaly, it means that my Y value is in steps of 2, and every odd column is shifted by one

So Hex(2,2) is in fact (2,4)
and hex (3,1) is in fact (3,3)

This way i take into account the shifting on the graphical representation of the array


Now, i find out which is bigger: The differencebetween Source X and Destination X or Source Y and Dest Y.

So lets say i want to go from (2,2) to (7,6) (which translates to 7,13)
DistX = 7-2 = 5
DistY = 13-2 = 11

So DistY > DistX

Now, i move along my X axies by increments of DistX/DistY and on Y axies by increments of 1

For i = 1 to DistY
NewX = SourceX + (i*5/11)
NewY = SourceY + i
Next i

So then i have the coords of the hexs that cross the line

But it gives weird results like:

a gap:



too much hexes:





**** Right now my test project is in VB as it was faster/easier for me to test the algorithm. I'll translate it to blitzmax and post it later on.


This has been bugging and blocking me for a while now any help will be extremely appreciated, be sure of that.

Smurftra


dynaman(Posted 2006) [#2]
Try getting the angle from each hex to the target hex.

If it is 331 to 29 go up
if it is 31 to 89 go up and right
if it is 91 to 149 go down and right
if it is 151 to 209 go down
if it is 211 to 269 go down and left
if it is 271 to 329 go up and left

if it is 30, 90, 150,210,270, or 330 then you have a choice of either of the adjacent hexes.


dynaman(Posted 2006) [#3]
I thought some more and it won't work correctly.

But a kind soul has put Bresenham's line algorithm in the archives, modifying this and treating each hex as 2 pixels across (with Odd x values meaning the Y is adjusted accordingly) may work. so hex 0,0 and 0,1 would be "pixels"
0,0 0,1
1,0 1,1 1,2 1,3
2,2 2,3

(I may be pointing you in a bad direction here...)

http://www.blitzbasic.com/codearcs/codearcs.php?code=1465


Smurftra(Posted 2006) [#4]
Well, i'm gonna try that, but curiously enough, i ported my code to bmax and now the Line algorithm works. The Nearest one doesnt tho.

I dont know what caused the breaks in the lines in VB, but i think it has to do with the Round function.


Im not sure how you guys post code so it appears in a nice box, so i'm gonna post it straight as:

How to use: Hit Keys:

A = Switch to nearest hex graphically algorithm
B = Switch to hexes along a line algorithm

0-9 = Set SourceX, SourceY, DestX, DestY

(It will set the values in that order, meaning if you press 4,5,6,7, it will set SourceX to 4, SourceY to 5, DestX to 6, DestY to 7. When it sets DestY it calls the pathfinding algorithm selected via A or B)

Btw, i appreciate any comments on code structure, optimisation, other ways to implement this, etc...

I was also wondering if we can change KeyHit(Key) by something like Key = TheKeyThatWasHit()

So i could do If Key >= 0 and Key <=9

known issue: In the line algorithm, if you make a line alongside the edges, it might put every 2 hexs outside the limits therefor not drawing them. Fortunatly for my usage its a case that wont happen.

Strict

Global Hexs:THex[10,10]
Global HexSize:Int = 17
Global HexOffset:Int = 20
Global MovX:Int[6] 'How to find the adjacent hexs, 0 = North, 1 = North East, 2 = South East, 3 = South, 4 = South West, 5 = North West
Global MovY:Int[6,2]

Global Algorithm:Int = 0
Global NextInput:Int = 0

Global SourceX:Int, SourceY:Int, DestX:Int, DestY:Int

Local i:Int, j:Int

MovX[0] = 0
MovX[1] = 1
MovX[2] = 1
MovX[3] = 0
MovX[4] = -1
MovX[5] = -1

MovY[0, 0] = -1
MovY[0, 1] = -1
MovY[1, 0] = -1
MovY[1, 1] = 0
MovY[2, 0] = 0
MovY[2, 1] = 1
MovY[3, 0] = 1
MovY[3, 1] = 1
MovY[4, 0] = 0
MovY[4, 1] = 1
MovY[5, 0] = -1
MovY[5, 1] = 0

For i = 0 To 9
For j = 0 To 9
Hexs[j,i] = New THex
Hexs[j,i].x = HexOffset + j * HexSize

Hexs[j,i].y =( HexOffset + i * HexSize) + ((HexSize / 2) * (j mod 2))
Next
Next

'Runs the example by nearest graphical position
'FindPath_ByNearest 1, 1, 7, 7, 1, 1

'FindPath_AlongLine 2, 4, 6, 7
FindPath_AlongLine 2, 7, 5, 3


graphics 640,480,0

SetColor 255,255,255

While not KeyHit(KEY_ESCAPE)
Cls

CheckKeys

DrawHexs

DrawText "SourceX = " + SourceX, 400,20
DrawText "SourceY = " + SourceY, 400,30
DrawText "DestX = " + DestX, 400,40
DrawText "DestY = " + DestY, 400,50

Flip
Wend

Private Function CheckKeys()
Local KeyNb:Int = -1
If KeyHit(KEY_A) Then
Algorithm = 0
ClearHexs

FindPath_ByNearest SourceX, SourceY, DestX, DestY, SourceX, SourceY
End If

If KeyHit(KEY_B) Then
Algorithm = 1
ClearHexs

FindPath_AlongLine SourceX, SourceY, DestX, DestY
End If

If KeyHit(KEY_0) Then
KeyNb = 0
End If
If KeyHit(KEY_1) Then
KeyNb = 1
End If
If KeyHit(KEY_2) Then
KeyNb = 2
End If
If KeyHit(KEY_3) Then
KeyNb = 3
End If
If KeyHit(KEY_4) Then
KeyNb = 4
End If
If KeyHit(KEY_5) Then
KeyNb = 5
End If
If KeyHit(KEY_6) Then
KeyNb = 6
End If
If KeyHit(KEY_7) Then
KeyNb = 7
End If
If KeyHit(KEY_8) Then
KeyNb = 8
End If
If KeyHit(KEY_9) Then
KeyNb = 9
End If

If KeyNb> 0 Then
Select NextInput
Case 0
SourceX = KeyNb
Case 1
SourceY = KeyNb
Case 2
DestX = KeyNb
Case 3
DestY = KeyNb
ClearHexs
If Algorithm = 0 Then
FindPath_ByNearest SourceX, SourceY, DestX, DestY, SourceX, SourceY
Else
FindPath_AlongLine SourceX, SourceY, DestX, DestY
End If
End Select

NextInput:+1
NextInput = NextInput Mod 4
End If

End Function


Private Function FindPath_ByNearest(X1, Y1, X2, Y2, OX, OY)
Local i:Int
Local x:Int
Local y:Int
Local ClosestDist:Int
Local TmpDist:Int
Local TmpDist2:Int
Local ClosestHex:Int
Local ClosestX:Int
Local ClosestY:Int

Hexs[OX,OY].Selected = 1 'Set as source

'See the ID of the closest hex to -1 (Not found
ClosestHex = -1

'Make sure the starting ClosestDist is big enough that any distances between two hexes is smaller
ClosestDist = 2000000000


'Loop All hexs around current hex
For i = 0 To 5
x = X1 + MovX[i]
y = Y1 + MovY[i, X1 Mod 2]

'if its within range of the grid
If x > -1 and x < 10 and y > -1 and y < 10 Then

'Check the distance between our hex and the destination hex
TmpDist = (Hexs[x2,y2].x - Hexs[x,y].x) ^ 2 + (Hexs[x2,y2].y - Hexs[x,y].y) ^ 2

If TmpDist = ClosestDist Then
'if its equal to another hex, check the distance between our hex and source hex)

'Distance of current hex to source hex
TmpDist = (Hexs[OX,OY].x - Hexs[x,y].x) ^ 2 + (Hexs[OX,OY].y - Hexs[x,y].y) ^ 2

'Distance of the closest x to source hex
TmpDist2 = (Hexs[OX,OY].x - Hexs[ClosestX,ClosestY].x) ^ 2 + (Hexs[OX,OY].y - Hexs[ClosestX,ClosestY].y) ^ 2

'If the new hex distance its smaller we use the new hex
If TmpDist < TmpDist2 Then
ClosestDist = TmpDist
ClosestHex = i
ClosestX = x
ClosestY = y
End If
Else
'if its not equal we check if its smaller
If TmpDist < ClosestDist Then
ClosestDist = TmpDist
ClosestHex = i
ClosestX = x
ClosestY = y
End If
End If
End If

Next

'if we found one
If ClosestHex <> -1 Then
'If its the destination
If ClosestX = X2 and ClosestY = Y2 Then
Hexs[ClosestX,ClosestY].Selected = 3 'Set as destination
Else
Hexs[ClosestX,ClosestY].Selected = 2 'Set as path
'Recursive FindNext
FindPath_ByNearest ClosestX, ClosestY, X2, Y2, OX, OY
End If
End If
End Function

Private Function FindPath_AlongLine(X1, Y1, X2, Y2)

Local DistanceX:Double
Local DistanceY:Double
Local NbSteps:Double
Local AdjustedY1:Int
Local AdjustedY2:Int
Local AdjustedDistanceY:Int
Local IncrementX:Double
Local IncrementY:Double
Local NewX:Int
Local NewY:Int
Local i:Int



AdjustedY1 = Y1 * 2 + (X1 Mod 2)
AdjustedY2 = Y2 * 2 + (X2 Mod 2)

DistanceX = X2 - X1
DistanceY = AdjustedY2 - AdjustedY1

'Find the increments and nbsteps to do lines
'DebugStop
If Abs(DistanceX) > Abs(DistanceY) Then
NbSteps = Abs(DistanceX)

AdjustedDistanceY = AdjustedY2 - AdjustedY1

IncrementY = AdjustedDistanceY / NbSteps
IncrementX = DistanceX / Abs(DistanceX)

Else
NbSteps = Abs(DistanceY)
AdjustedY1 = Y1 * 2 + (X1 Mod 2)
AdjustedY2 = Y2 * 2 + (X2 Mod 2)

AdjustedDistanceY = AdjustedY2 - AdjustedY1

IncrementY = AdjustedDistanceY / Abs(AdjustedDistanceY)
IncrementX = DistanceX / NbSteps
End If

For i = 1 To NbSteps

NewX = X1 + Round((i * IncrementX))
NewY = AdjustedY1 + Round((i * IncrementY))

'change frmo adjusted to real Y
NewY = Round((NewY - (NewX Mod 2)) / 2)

If NewX > -1 and NewX < 10 and NewY > -1 and NewY < 10 Then
Hexs[NewX,NewY].Selected = 2
End If
Next

Hexs[X1,Y1].Selected = 1 'set source
Hexs[X2,Y2].Selected = 3 'set dest
End Function


Function DrawHexs()
Local i:Int
Local j:Int

For i = 0 To 9
For j = 0 To 9
Select Hexs[i,j].Selected
Case 1
SetColor 0,255,0
DrawRect Hexs[i,j].x, Hexs[i,j].y, HexSize, HexSize
SetColor 255,255,255
Case 2
SetColor 255,0,0
DrawRect Hexs[i,j].x, Hexs[i,j].y, HexSize, HexSize
SetColor 255,255,255
Case 3
SetColor 0,0,255
DrawRect Hexs[i,j].x, Hexs[i,j].y, HexSize, HexSize
SetColor 255,255,255
End Select

DrawRectOutline Hexs[i,j].x, Hexs[i,j].y, HexSize, HexSize
Next
Next
End Function

Function ClearHexs()
Local i:Int
Local j:Int

For i = 0 To 9
For j = 0 To 9
Hexs[i,j].Selected = 0
Next
Next
End Function

Function DrawRectOutline(x,y,w,h)
'trim
w = w-1
h = h-1
DrawLine(x,y,x+w,y,0)
DrawLine(x+w,y,x+w,y+h,0)
DrawLine(x+w,y+h,x,y+h,0)
DrawLine(x,y+h,x,y,0)
End Function

Function Round:Double(x:Double)
Return Int(x + (Sgn(x) * 0.5))
End Function

Type THex
Field x:Int
Field y:Int
Field Selected:Int

End Type

anyways, heres the code:


Smurftra(Posted 2006) [#5]
I tested the line algorithm alot and it stills does weird things

if you try it with lines

0,1 - 2,7
8,3 - 5,2

you will see

I'm gonna try working on that Bresenham's line algorithm


dynaman(Posted 2006) [#6]
I'm at work but will give this a look tonight to see if I can help.


Smurftra(Posted 2006) [#7]
heres the modified line algorithm to work with the link you given me. It does give a good looking line but still has some exceptions (some lines that go from bottom left to upper right start by going down before going up. I've tried working around it using Floor/Ceil but it doesnt always work).

try (7,5) - (0,7) to see what i mean

Function FindPath_AlongLine(X1:Int,Y1:Int,X2:Int,Y2:Int)
'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
Local OldX1:Int = X1
Local OldX2:Int = X2
Local AdjY1:Int = Y1 * 2 + (X1 Mod 2)
Local AdjY2:Int = Y2 * 2 + (X2 Mod 2)

Local Steep:Int=Abs(AdjY2-AdjY1) > Abs(X2-X1) 'Boolean
If Steep
Local Temp:Int=X1; X1=AdjY1; AdjY1=Temp 'Swap X1,Y1
Temp=X2; X2=AdjY2; AdjY2=Temp 'Swap X2,Y2
EndIf
Local DeltaX:Int=Abs(X2-X1) 'X Difference
Local DeltaY:Int=Abs(AdjY2-AdjY1) 'Y Difference
Local error:Int=0 'Overflow counter
Local DeltaError:Int=DeltaY 'Counter adder
Local x:Int=X1 'Start at X1,Y1
Local y:Int=AdjY1
Local XStep:Int
Local YStep:Int
Local RY:Int

If X1<X2 Then XStep=1 Else XStep=-1 'Direction
If AdjY1<AdjY2 Then YStep=1 Else YStep=-1 'Direction
If Steep Then

If x > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(x) - (Double(y) Mod 2)) / 2)
Else
RY = Ceil((Double(x) - (Double(y) Mod 2)) / 2)
End If
Hexs[y,RY].Selected = 2
Else
'Draw
If y > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(y) - (Double(x) Mod 2)) / 2)
Else
RY = Ceil((Double(y) - (Double(x) Mod 2)) / 2)
End If

Hexs[x,ry].Selected = 2
End If
While x<>X2
x:+XStep 'Move in X
error:+DeltaError 'Add to counter
If (error Shl 1)>DeltaX 'Would it overflow?
y:+YStep 'Move in Y
error=error-DeltaX 'Overflow/wrap the counter
EndIf
If Steep Then
If x > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(x) - (Double(y) Mod 2)) / 2)
Else
RY = Ceil((Double(x) - (Double(y) Mod 2)) / 2)
End If
Hexs[y,ry].Selected = 2
Else
If y > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(y) - (Double(x) Mod 2)) / 2)
Else
RY = Ceil((Double(y) - (Double(x) Mod 2)) / 2)
End If
Hexs[x,ry].Selected = 2
End If
Wend

Hexs[oldX1,Y1].Selected = 1 'set source
Hexs[oldX2,Y2].Selected = 3 'set dest
End Function


Smurftra(Posted 2006) [#8]
just reposting the full source in a better format

now pressing A = Nearest Algorithm, B = my line algorthm, C = Bresenham's line algorithm





dynaman(Posted 2006) [#9]
I tried working on this last night, my results were even worse, the "line" going up then down when it should have gone left or right, etc...

I did find a web page with logic to look at though.

http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html

(tooo much to go through right now, but item 5 on that page seems to be what you are after)


Smurftra(Posted 2006) [#10]
I pursued the Breseham algorithm and figured i had just to 'fix' the part where i need to chose between CEIL Or FLOOR depending on the slope.


here's the fixed algorithm that works (needs the full source that s 2 posts above, remember to press C to be using the correct algorithm):

(Side note: I just made it work, didnt optimize it or clean up the code)





[CodeBox]
Function FindPath_AlongLine2(X1:Int,Y1:Int,X2:Int,Y2:Int)
'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
Local OldX1:Int = X1
Local OldX2:Int = X2
Local AdjY1:Int = Y1 * 2 + (X1 Mod 2)
Local AdjY2:Int = Y2 * 2 + (X2 Mod 2)

Local Steep:Int=Abs(AdjY2-AdjY1) > Abs(X2-X1) 'Boolean
If Steep
Local Temp:Int=X1; X1=AdjY1; AdjY1=Temp 'Swap X1,Y1
Temp=X2; X2=AdjY2; AdjY2=Temp 'Swap X2,Y2
EndIf
Local DeltaX:Int=Abs(X2-X1) 'X Difference
Local DeltaY:Int=Abs(AdjY2-AdjY1) 'Y Difference
Local error:Int=0 'Overflow counter
Local DeltaError:Int=DeltaY 'Counter adder
Local x:Int=X1 'Start at X1,Y1
Local y:Int=AdjY1
Local XStep:Int
Local YStep:Int
Local RY:Int

If X1<X2 Then XStep=1 Else XStep=-1 'Direction
If AdjY1<AdjY2 Then YStep=1 Else YStep=-1 'Direction
If Steep Then

If x > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(x) - (Double(y) Mod 2)) / 2)
Else
RY = Ceil((Double(x) - (Double(y) Mod 2)) / 2)
End If
Hexs[y,RY].Selected = 2
Else
'Draw
If y > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(y) - (Double(x) Mod 2)) / 2)
Else
RY = Ceil((Double(y) - (Double(x) Mod 2)) / 2)
End If

Hexs[x,ry].Selected = 2
End If

While x<>X2
'DebugStop
x:+XStep 'Move in X
error:+DeltaError 'Add to counter
If (error Shl 1)>DeltaX 'Would it overflow?
y:+YStep 'Move in Y
error=error-DeltaX 'Overflow/wrap the counter
EndIf
If Steep Then

If x = (Y2* 2 + (x2 Mod 2)) Then
If XStep < 0 Then
RY = Ceil((Double(x) - (Double(y) Mod 2)) / 2)
Else
RY = Floor((Double(x) - (Double(y) Mod 2)) / 2)
End If
Else
If x > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(x) - (Double(y) Mod 2)) / 2)
Else
RY = Ceil((Double(x) - (Double(y) Mod 2)) / 2)
End If
End If
If ry>9 Then ry=9
If ry<0 Then ry=0
Hexs[y,ry].Selected = 2
Else
If y = (Y2* 2 + (x2 Mod 2)) Then
If YStep < 0 Then
RY = Ceil((Double(y) - (Double(x) Mod 2)) / 2)
Else
RY = Floor((Double(y) - (Double(x) Mod 2)) / 2)
End If
Else
If y > (Y2* 2 + (x2 Mod 2)) Then
RY = Floor((Double(y) - (Double(x) Mod 2)) / 2)
Else
RY = Ceil((Double(y) - (Double(x) Mod 2)) / 2)
End If
End If
If ry>9 Then ry=9
If ry<0 Then ry=0
Hexs[x,ry].Selected = 2
End If
Wend

Hexs[oldX1,Y1].Selected = 1 'set source
Hexs[oldX2,Y2].Selected = 3 'set dest
End Function
[/CodeBox]