-
Apr 13th, 2009, 09:12 AM
#1
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?
-
Apr 13th, 2009, 11:11 AM
#2
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
-
Apr 13th, 2009, 12:04 PM
#3
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...
-
Apr 13th, 2009, 01:38 PM
#4
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).
-
Apr 13th, 2009, 01:38 PM
#5
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.
-
Apr 13th, 2009, 01:52 PM
#6
Re: Grid-based path detection?
Stay up a little later and we can pursue it together
-
Apr 13th, 2009, 01:52 PM
#7
Re: Grid-based path detection?
-
Apr 13th, 2009, 04:30 PM
#8
Not NoteMe
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.
-
Apr 15th, 2009, 01:07 PM
#9
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.
-
Apr 15th, 2009, 02:10 PM
#10
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.
-
Apr 15th, 2009, 02:27 PM
#11
Re: Grid-based path detection?
Well, that was meant to be grid-based, unless I'm totally misunderstanding what you mean by that.
-
Apr 16th, 2009, 11:47 AM
#12
Fanatic Member
Re: Grid-based path detection?
Actually navigating hex lattices is easy - I'll post an example tonight.
-
Apr 16th, 2009, 12:13 PM
#13
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.
-
Apr 16th, 2009, 09:55 PM
#14
Fanatic Member
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.
-
Apr 16th, 2009, 10:05 PM
#15
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
-
Apr 16th, 2009, 10:09 PM
#16
Fanatic Member
Re: Grid-based path detection?
I can post the executable if you want.
-
Apr 16th, 2009, 10:14 PM
#17
Fanatic Member
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.
-
Apr 17th, 2009, 05:13 AM
#18
Fanatic Member
Re: Grid-based path detection?
Code Reposted - Had a typo
-
Apr 17th, 2009, 02:09 PM
#19
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.
-
Apr 17th, 2009, 08:11 PM
#20
Fanatic Member
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.
-
Apr 18th, 2009, 12:18 PM
#21
Fanatic Member
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
-
Apr 19th, 2009, 11:24 AM
#22
Fanatic Member
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.
-
Apr 19th, 2009, 12:34 PM
#23
Fanatic Member
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% 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.
-
Apr 19th, 2009, 01:18 PM
#24
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.
-
Apr 19th, 2009, 02:02 PM
#25
Fanatic Member
Re: Grid-based path detection?
Post Edited for Dead End Tracking - it was on my to do list.
Orwell- I'm all for prealc.
-
Apr 20th, 2009, 05:06 PM
#26
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.
-
Apr 20th, 2009, 08:21 PM
#27
Fanatic Member
Re: Grid-based path detection?
I's pretty quick - if you shut off the delay it's there right away.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|