Grid-based path detection?-VBForums
Results 1 to 27 of 27

Thread: Grid-based path detection?

  1. #1

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    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?

  2. #2
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    37,039

    Re: Grid-based path detection?

    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

  3. #3

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    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...

  4. #4
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    37,039

    Re: Grid-based path detection?

    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).

  5. #5
    Raging swede Atheist's Avatar
    Join Date
    Aug 2005
    Location
    Sweden
    Posts
    8,018

    Re: Grid-based path detection?

    Ive been reading about the A* algorithm in the artificial intelligence course at university these last months, and I second Si's suggestion.
    ---My Flickr photo (mostly screenshots these days!) stream. Have a look!

    Rate posts that helped you. I do not reply to PM's with coding questions.
    How to Get Your Questions Answered
    TCP client/server connection | Retrieving the EventHandler for any Event by code.
    Me on.. BitBucket, Google Code, Github (pretty empty)

  6. #6

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    Stay up a little later and we can pursue it together

  7. #7
    Raging swede Atheist's Avatar
    Join Date
    Aug 2005
    Location
    Sweden
    Posts
    8,018

    Re: Grid-based path detection?

    Deal!
    ---My Flickr photo (mostly screenshots these days!) stream. Have a look!

    Rate posts that helped you. I do not reply to PM's with coding questions.
    How to Get Your Questions Answered
    TCP client/server connection | Retrieving the EventHandler for any Event by code.
    Me on.. BitBucket, Google Code, Github (pretty empty)

  8. #8
    Not NoteMe SLH's Avatar
    Join Date
    Mar 2002
    Location
    192.168.0.1 Preferred Animal: Penguin Reason for errors: Line#38
    Posts
    3,051

    Re: Grid-based path detection?

    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).
    Last edited by SLH; Apr 13th, 2009 at 04:34 PM.
    Quotes:
    "I am getting better then you guys.." NoteMe, on his leet english skills.
    "And I am going to meat her again later on tonight." NoteMe
    "I think you should change your name to QuoteMe" Shaggy Hiker, regarding NoteMe
    "my sweet lord jesus. I've decided never to have breast implants" Tom Gibbons
    Have I helped you? Please Rate my posts.


  9. #9
    Stack Overflow mod​erator
    Join Date
    May 2008
    Location
    British Columbia, Canada
    Posts
    2,824

    Re: Grid-based path detection?

    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.

  10. #10

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    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.

  11. #11
    Stack Overflow mod​erator
    Join Date
    May 2008
    Location
    British Columbia, Canada
    Posts
    2,824

    Re: Grid-based path detection?

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

  12. #12
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

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

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  13. #13

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    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.

  14. #14
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    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
    Last edited by technorobbo; Apr 18th, 2009 at 12:19 PM.

  15. #15

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    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

  16. #16
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    I can post the executable if you want.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  17. #17
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    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
    Last edited by technorobbo; Apr 16th, 2009 at 10:23 PM.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  18. #18
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    Code Reposted - Had a typo
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  19. #19

    Thread Starter
    Banned timeshifter's Avatar
    Join Date
    Mar 2004
    Location
    at my desk
    Posts
    2,467

    Re: Grid-based path detection?

    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.

  20. #20
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

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

    Post Edit - fixed some transposed numbers on the logic table.
    Last edited by technorobbo; Apr 18th, 2009 at 12:15 PM.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  21. #21
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    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
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  22. #22
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    Algorithm refined to always travel shortest path and can efficiently manuever out of a dead end.
    http://www.vbforums.com/showthread.php?t=566060
    Last edited by technorobbo; Apr 20th, 2009 at 02:41 PM.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  23. #23
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

    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&#37; 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
    Last edited by technorobbo; Apr 19th, 2009 at 02:12 PM.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  24. #24
    Cyberman Lord Orwell's Avatar
    Join Date
    Feb 2001
    Location
    Elberfeld, IN
    Posts
    7,480

    Re: Grid-based path detection?

    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.
    John Lord, Evansville Indiana

  25. #25
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

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

    Orwell- I'm all for prealc.
    Have Fun,

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

  26. #26
    Cyberman Lord Orwell's Avatar
    Join Date
    Feb 2001
    Location
    Elberfeld, IN
    Posts
    7,480

    Re: Grid-based path detection?

    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.
    John Lord, Evansville Indiana

  27. #27
    Fanatic Member technorobbo's Avatar
    Join Date
    Dec 2008
    Location
    Chicago
    Posts
    864

    Re: Grid-based path detection?

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

    TR
    _____________________________
    Check out my Alpha DogFighter2D Game Demo and Source code. Direct Download:http://home.comcast.net/~technorobbo/Alpha.zip or Read about it in the forum:http://www.vbforums.com/showthread.php?t=551700. Now in 3D!!! http://home.comcast.net/~technorobbo/AlPha3D.zip or read about it in the forum: http://www.vbforums.com/showthread.php?goto=newpost&t=552560 and IChessChat3D internet chess game

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width

Survey posted by VBForums.