Grid-based path detection?

So there are two goals here... the first one is for me to learn the best way to determine the shortest grid distance between two points, taking obstacles into account. The second is to translate that knowledge onto a hexagonal grid, instead of squares. So we should probably start with the basics... I'm thinking a recursive approach would work, but that would get considerably slower, the larger the map... and I'm hoping for some fairly big maps in the end... where should I start?

A* is a popular algorithm for pathfinding, and from what I remember it is pretty good (but with some room for improvement).

I don't know what language you are using for this, but a quick search found a C++ example that apparently deals with hexagons:
http://www.grinninglizard.com/MicroPather/readme.htm

That does look like a pretty diverse solution, albeit a little more than I need... also, I'd like to actually learn the process of determining the shortest path, not just use code that someone else wrote. I'm doing this in C#, btw. If I was allowed to use MSN at work, I'd just hit up Wossy, but that's out of the question...

From what I remember (albeit about 10 years ago) it is a fairly simple algorithm to understand and implement, and there are many explanations of it out there that you could work from - including a couple linked from the article I referred to before.

The amount of complexity can be reduced to whatever you circumstances are - so if each square/hexagon can only be usable or not (so no variation in difficulty of usable areas), you simply count the number of the usable areas on that path (rather than assigning various costs for each type of terrain, and totalling them).

Ive been reading about the A* algorithm in the artificial intelligence course at university these last months, and I second Si's suggestion.

Stay up a little later and we can pursue it together ;)

Deal!

Did a quick search for pathfinding to find some old threads, it's a common topic in Games & Graphics!

A game i made in VB6 ages ago, which preprocesses the map making for instant evaluations when moving objects (at a cost to memory).
http://www.vbforums.com/showthread.p...hreadid=253989

In Post 6 in this thread i talk a bit about it
http://www.vbforums.com/showthread.p...ht=pathfinding

One optimization i did do that i'm not sure would work for a hexagonal grid was removing redundent nodes, e.g. in a straight path with walls above and below there's no need to treat each tile as a node, you could replace it with nodes only at each end. I did something similar with open spaces, only placing nodes at corners and calculating the distances within those simply as width+height (since you'd still have to move up then across, or visaversa in an open space).

Only an idea, but...
1. Find the shortest path between two points, just by calculating the line (which should be easy, depending on how you want it.)
2. If there are any obstacles on that line, then, for each obstacle on the line:
2.1: If it is a diagonal line that had to be evened out, look to the side opposite of the
lean.
2.2: Otherwise, look to the left of the obstacle. If there is an obstacle there, look to
the right. If there's still an obstacle, look 2 to the left, calculate the next line,
and so on...

.. and that should be it. Hope that helps a bit.

Well yeah, that's how proper path detection works... but this is grid-based. The rules change slightly, as a straight line from start to end is NOT the ideal path... unless you can find a way to quickly calculate every cell occupied by that line.

Well, that was meant to be grid-based, unless I'm totally misunderstanding what you mean by that.

Actually navigating hex lattices is easy - I'll post an example tonight.

I have a system right now that can indeed find a path if one exists... but it doesn't do much to find the ideal path... not sure where I'm going wrong... can't wait to see what you've got and hopefully learn from it.

Hopefully you'll find this helpful (it's VB6).
Put the code below in a form and run it. Instructions will be at the top of the form. It works by setting up regions for each hex and translating cartesian coordinates to Hex coordinate then it uses recursive evasion techniques to find the end point. Hex coordinates are an even/odd wiggle that occurs on the Y axis. Cartesian has 8 possible paths hex has six so it uses a prioritizing technique in translating to a hex path, starting with the path direction and works itself backwards.
http://http://www.vbforums.com/showthread.php?t=566060

Ick... I don't even have a VB6 install lying around anywhere... hopefully I'll get bored enough this weekend to convert it to C#... thanks for the start, though :wave:

I can post the executable if you want.

BTW - it randomizes the terrain everytime you start the program and it uses gettickcount to slow itself down cause it's too damn fast.

It can get stuck - but it usually takes some goofy bottled neck terrain. For most games the algorithm works pretty good

Code Reposted - Had a typo

Exe's will get removed by the mods... forum policy, although I would like to see it in action. If you could email it to me, that'd be great. I'm bored at work, so I'm gonna try to convert as much of it into C# as I can... if I achieve success, I'll be sure to post it so you have a good .Net version. Thanks again.

Bug Fix:
http://www.vbforums.com/showthread.php?t=566060

Post Edit - fixed some transposed numbers on the logic table.

I've figured out a fix for bottlenecks where the AI has to go backwards to find the solution. Scramble it's Logic! And let it find it's way back.
http://www.vbforums.com/showthread.php?t=566060

Algorithm refined to always travel shortest path and can efficiently manuever out of a dead end.
http://www.vbforums.com/showthread.php?t=566060

Timeshifter,

As per our PM here is how the algorithm works:
Declarations:

Standard API declares for RECT's and Regions, Poly's and Fill are used and supporting types and constants. The only custom declaration is the Enum for the loop logic.

Code:

---

Enum Logic
    Origin = 1
    Target = 2
    Victory = 3
    Idle = 4
    Init = 5
    quit = 6
    Defeat = 7
    Lattice = 8
End Enum

---

This is a mini scritpting system that controls the sequence of events.

The Variables

• hRgn() - All hexes are defined as regions
• Think - Token using logic enum for flow control
• FindPath - Stores beginning and end coords in RECT structure
• GameOn - boolean that keeps loop looping
• LastPath - see next comment
• TailCount - keeps track of last 100 locations for backing out of dead ends and stops endless loops - increase this for larger grids!
• Tailend stores end of path for restoring
• DeadEnds - tracks dead ends

Making the Lattice

• PI = Atn(1) * 4 = best way to define PI in VB
• NumCoords = 6 - It' a hex
• hexrad = Me.ScaleWidth / 25 - and it's 25 across
• INC = pi / 3 - the equivalent to 60 degrees
• latX = Cos(INC) * hexrad - convert 60 degrees to x and y
• latY = Sin(INC) * hexrad - " "

Create regions in windows for hex:

Code:

---

ReDim hRgn(0 To Me.ScaleWidth / 50, 0 To Me.ScaleHeight / hexrad)

---

Draw hexes on screen - mostly brown and some green randomnly:

Code:

---

For y = 0 To Me.ScaleHeight / hexrad
    For x = 0 To Me.ScaleWidth / 50
        For j = 1 To 6
            i = j * INC
            poly(j).x = Cos(i) * hexrad + latX * x + hexrad * x
            poly(j).y = Sin(i) * hexrad + latY * (x And 1) + y * latY * 2
        Next
        Me.FillColor = Choose(Int(Rnd() * 4) + 1, RGB(192, 192, 0), _
                RGB(64, 255, 64), RGB(192, 192, 0), RGB(192, 192, 0))
        Polygon Me.hdc, poly(1), NumCoords
        hRgn(x, y) = CreatePolygonRgn(poly(1), NumCoords, ALTERNATE)
    Next
Next

---

The y axis wobble is created by offsetting the 60 degrees for even and odd hexes in this part of the routine

Code:

---

latY * (x And 1) + y

---

*Note that regions have to be deleted before redraing the Lattice.


Navigation Algorithm

There are 2 Key routines that support the path finding logic:

1. The Cartesian 2 hex translation - I believe in precomputing as much as possible for speed. OE is the odd even bit used to translate the y axis wobble.

Code:

---

Private Function NPair(OE As Integer, ByVal nav As Integer) As COORD
'LATTICE lOGIC
        NPair.x = Choose(nav, -1, 0, -1, 1, 0, 1)
        NPair.y = Choose(nav, -1 + OE, -1, 0 + OE, -1 + OE, 1, 0 + OE)
End Function

---

2. Check block colors for collision- yes it's an archaic throwback to the commodore 64 but it works. Using GetRgnBox and finding the center pixel color. I am also checking check for boundaries. If your filling your hexes with graphics and not colors - keep refence array for this type of collision detection.

Note that the LastPath and borders are also checked.

Code:

---

Function CheckBlock(ByVal x1 As Integer, ByVal y1 As Integer) As Boolean
Dim box As RECT, color As Long
If x1 < 0 Or x1 > UBound(hRgn, 1) Then
    CheckBlock = False
    Exit Function
ElseIf y1 < 0 Or y1 > UBound(hRgn, 2) Then
    CheckBlock = False
    Exit Function
ElseIf DeadEnds(x1, y1) Then
    CheckBlock = False
    Exit Function
ElseIf LastPath(x1, y1) Then
    CheckBlock = False
    Exit Function
End If
GetRgnBox hRgn(x1, y1), box
color = GetPixel(Me.hdc, (box.Left + box.Right) / 2, (box.Top + box.Bottom) / 2)
If color = RGB(192, 192, 0) Then
    CheckBlock = True
Else
    CheckBlock = False
End If
End Function

---

Now for the main AI routine PlotPath. I'm going to explain it little by little since it is kind of complex


Necessary Evils:
Note we're setting up to sort and paint

Code:

---

Sub plotpath()
Dim DONE As Boolean, PlotX As Integer, Ploty As Integer
Dim hbrush As Long, pause As Long, x1 As Integer, y1 As Integer
Dim x As Single, OE As Integer, i As Integer, lost As Boolean
Dim Sort(1 To 6, 0 To 1) As Single, sTmp As COORD, tmp As Single

---

Contstants for sorting array

Code:

---

Const Index = 0
Const Dist = 1

---

Initialize the path history with current location

Code:

---

Erase LastPath
ReDim LastPath(0 To UBound(hRgn, 1), 0 To UBound(hRgn, 2))
Erase DeadEnds
ReDim DeadEnds(0 To UBound(hRgn, 1), 0 To UBound(hRgn, 2))

LastPath(FindPath.Left, FindPath.Top) = True

TailCount = 0
Tailend.x = FindPath.Left
Tailend.y = FindPath.Top

---

start pathfinding loop and set up a drawing delay that's easy on the eyes.

Code:

---

Do While Not DONE
    'sell the drama -LET'S SLOW IT DOWN
    pause = GetTickCount + 50
    While pause > GetTickCount
        DoEvents
    Wend

---

check if your at your destination - you can also use abs()
set the flag and end the loop if you are.

Code:

---


  'get bearings
    PlotX = Sgn(FindPath.Right - FindPath.Left)
    Ploty = Sgn(FindPath.Bottom - FindPath.Top)
    OE = FindPath.Left And 1
    'think
    'Check Arrive
    If PlotX = 0 And Ploty = 0 Then
        Think = Victory
        DONE = True

---

If your not start the logic as if your lost - which you are.
Scan all hexes around your current location and use the Pythagorean theorem to determine their distance to the destination. If the hex you check is out of bound store a really far distance.

I all hexes are out of bounds the lost flag remains true. If you do have a spot to move to then it becomes false.

Code:

---

  Else
        lost = True
        For i = 1 To 6
          If CheckBlock(NPair(OE, i).x + FindPath.Left, _
              NPair(OE, i).y + FindPath.Top) Then
              sTmp.x = FindPath.Left + NPair(OE, i).x
              sTmp.y = FindPath.Top + NPair(OE, i).y
              x = Sqr((FindPath.Right - sTmp.x) ^ 2 + (FindPath.Bottom - sTmp.y) ^ 2)
              Sort(i, Index) = i
              Sort(i, Dist) = x
              lost = False
          Else
              Sort(i, Index) = i
              Sort(i, Dist) = 65535
          End If
        Next

---

Are we lost??? If we are that means we've hit a dead end so clear the path history mark your current location, that way you will back out of the dead end. Keep Track of dead ends, but don't erase them.

Code:

---

      If lost Then
            Erase LastPath
            ReDim LastPath(0 To UBound(hRgn, 1), 0 To UBound(hRgn, 2))
            LastPath(FindPath.Left, FindPath.Top) = True
            DeadEnds(FindPath.Left, FindPath.Top) = True
        Else

---

Not lost - sort the hexes around you to see which is closest to your destination cause that's where your going.

Code:

---


            'sort
            i = 1
            While i < 7
                If i = 1 Then
                    i = i + 1
                ElseIf Sort(i - 1, Dist) <= Sort(i, Dist) Then
                    i = i + 1
                Else
                    tmp = Sort(i, Dist): Sort(i, Dist) = Sort(i - 1, Dist): Sort(i - 1, Dist) = tmp
                    tmp = Sort(i, Index): Sort(i, Index) = Sort(i - 1, Index): Sort(i - 1, Index) = tmp
                    i = i - 1
                End If
            Wend

---

Now go there! Don't forget your path history. I've limit it to 100 but you can make it bigger for bigger boards with larger bottlenecks and dead ends. I used 15% of the board - that seems to work good.

Code:

---

          'use closest
            FindPath.Left = FindPath.Left + NPair(OE, Sort(1, Index)).x
            FindPath.Top = FindPath.Top + NPair(OE, Sort(1, Index)).y
           
            LastPath(FindPath.Left, FindPath.Top) = True
            TailCount = (TailCount + 1) Mod 100
            If TailCount = 0 Then
                LastPath(Tailend.x, Tailend.y) = False
                Tailend.x = FindPath.Right
                Tailend.y = FindPath.Bottom
            End If
        End If
    End If

---

Draw the graphics - its time

Code:

---


  If Not DONE Then
        Me.Cls
        hbrush = CreateSolidBrush(RGB(255, 0, 0))
        x1 = FindPath.Left
        y1 = FindPath.Top
        FillRgn Me.hdc, hRgn(x1, y1), hbrush
        DeleteObject hbrush
    End If

---

Viola! Loop 'til your there or you want to escape!

Code:

---

    If Think = quit Or Think = Init Then DONE = True
Loop
End Sub

---

i was working on something like this once when i was tinkering with a 2d rpg. It was going to be like ultima - monsters on map. I had a second array with terrain movement plotted out ahead of time. If i can find my old work, i'll tell you more. I just seem to remember that it was 4x the size of the terrain grid. And i was able to do this by breaking the large area into manageable smaller ones. It did screen switching like the first zelda. However that can be applied to huge maps as well because you most likely won't have the entire map in memory at once. I mainly plotted it all out ahead of time so monsters could chase me based on my destination square and possibly intercept me. There was only one path calculation this way instead of one for each creature on the screen.

Post Edited for Dead End Tracking - it was on my to do list.

Orwell- I'm all for prealc.

actually it's starting to come back to me. In my grid, i was doing a recursive path search. every square that had already been stepped in by one of the various checked paths had a value stored in it equal to how far it was from the End. When one of the paths finds the Beginning, i then started at the beginning and went square by square forwards along the path and checked the value of steps from end on each surrounding square, and moved onto the square wth the lowest number. I did this with a single thread but i would be willing to bet it would be almost instant on a fast computer because you are only doing two checks on every node on screen. That's really not that many. And actually if the origin is hit early, there are less checks.

I's pretty quick - if you shut off the delay it's there right away.