Creating a line on an hex grid.

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

Smurftra
 #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
 #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
 #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
 #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
 #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
 #6
I'm at work but will give this a look tonight to see if I can help.

Smurftra
 #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
 #8
just reposting the full source in a better format

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


 
Strict

Global Hexs:THex[10,10]
Global HexSize:Int = 20
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 360,250,0

SetColor 255,255,255

While not KeyHit(KEY_ESCAPE)
	Cls
	
	CheckKeys
	
	DrawHexs
	
	DrawText "SourceX = " + SourceX, 250,20
	DrawText "SourceY = " + SourceY, 250,30
	DrawText "DestX   = " + DestX, 250,40
	DrawText "DestY   = " + DestY, 250,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_C) Then
		Algorithm = 2
		ClearHexs
		
		FindPath_AlongLine2 SourceX, SourceY, DestX, DestY
	End If
	
	If KeyHit(KEY_SPACE) Then
		SourceX = Rnd(10)
		SourceY = Rnd(10)
		DestX = Rnd(10)
		DestY = Rnd(10)
		
		ClearHexs
		
		Select Algorithm
			Case 0
				FindPath_ByNearest SourceX, SourceY, DestX, DestY, SourceX, SourceY
			Case 1
				FindPath_AlongLine SourceX, SourceY, DestX, DestY
			Case 2
				FindPath_AlongLine2 SourceX, SourceY, DestX, DestY
		  	
		End Select
	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> -1 Then
		Select NextInput
			Case 0
				SourceX = KeyNb
			Case 1
				SourceY = KeyNb
			Case 2
				DestX = KeyNb
			Case 3
				DestY = KeyNb
				ClearHexs
				Select Algorithm
					Case 0
						FindPath_ByNearest SourceX, SourceY, DestX, DestY, SourceX, SourceY
					Case 1
						FindPath_AlongLine SourceX, SourceY, DestX, DestY
					Case 2
						FindPath_AlongLine2 SourceX, SourceY, DestX, DestY
				  	
				End Select
		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 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
			  	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


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


dynaman
 #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
 #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]