Pathfinding
Blitz3D Forums/Blitz3D Programming/Pathfinding
| ||
| I've been attempting this for a bit now and read all the posts from doing a Pathfinding search, but I'm still a bit at a loss. Its a 3d world with a T.ED terrain. Here is my ideas on making this work. Right now, I've attempted many renditions and variations, but starting over (again) Im looking to see what others are doing or have done. The A* beginning tut code is a little complex for me, but I keep referring to it anyways. I will hopefully update this post as info or breathroughs happen. The code displayed is contained in my pathfinding.bb program that I intend to include in my game. 1 - Create Grid Create a 2d Grid that stores Cell info based on a flat representation of the 3d world. Use Array to store data or Custom Type. Store ID, CellX, CellY, Walkable, ParentCell, Fcost, Gcost, Hcost of each cell. Iterate through each cell based on maps overall dimensions initializing the cells values, leave Fcost, Gcost, Hcost, Parent and Walkable zero, they will get values when I look for the path. (Stevie G enlighted me on using a custom type array, which was perfect for this)
Type Cell
Field ID
Field X
Field Z
Field FVal
Field GVal
Field HVal
Field Walkable
Field Parent
End Type
Global GridX = 200
Global GridZ = 200
Global TotCells = (GridX+1) * (GridZ+1)
Dim Grid.Cell(TotCells) ;The Custom Type and Array was exampled by Stevie G, Awesome!
Global StartCell ;Stores the number of the Current Cell
Dim OpenList(10000)
Dim ClosedList(10000)
;----------------------------------------------------------------------------------
Function CreateGrid(X,Z)
;X and Z are map dimensions passed in, It will create a 2d grid containing (X+1 * Z+1) number
;of cells. The +1 is for adding the 0 column and 0 row.
A = 1
CellX = (GridX/2) * -1
CellZ = (GridZ/2) * -1
While A < TotCells+1
If CellX < (GridX/2)+1
Grid(A) = New Cell
Grid(A)\ID = A
Grid(A)\X = CellX
Grid(A)\Z = CellZ
Grid(A)\FVal = 0
Grid(A)\GVal = 0
Grid(A)\HVal = 0
SelEnt = LinePick(CellX, 200, CellZ, 0, -1000, 0)
If SelEnt > 0
SelName$ = EntityName(PickedEntity())
If SelName$ = "Ground"
Grid(A)\Walkable = 1
Else
Grid(A)\Walkable = 0
EndIf
EndIf
Grid(A)\Parent = 0
CellX = CellX + 1
A = A + 1
Else
CellX = (GridX/2) * -1
CellZ = CellZ + 1
End If
Wend
A = 1
;;Save info To check it
FileOut = WriteFile("Nodeinfo.dat")
WriteLine(FileOut,"Total Cells= " +TotCells)
While A < TotCells+1
WriteLine(FileOut, Grid(A)\ID+", "+Grid(A)\X+", "+Grid(A)\Z+", "+Grid(A)\Walkable+", "+Grid(A)\Parent)
A = A + 1
Wend
CloseFile FileOut
End Function
;----------------------------------------------------------------------------------
2 - Find Path Using Player position, do a path search as explained in http://www.policyalmanac.org/games/aStarTutorial.htm 1 - Move Character to nearest Cells Coordinates, if not there already 2 - Put Start Cell in Closed list 3 - Check each adjecent cells Fcost value, Fill in the Cells Fcost, Gcost, Hcost, Walkable, Parent Values here. 4 - Add each adject cell to open list 5 - Pick the cell with lowest FCost 6 - Make that Cell the new Start Cell 7 - Repeat 2 - 7 until Target Cell is added to closed list
;----------------------------------------------------------------------------------
Function FindPath(StartX,StartZ,EndX,EndZ)
;1 - Move Char to nearest cell coords, if not there already
A = 1
While A < TotCells+1
;If Grid(A)\X < StartX + 5 And Grid(A)\X > StartX - 5
If Grid(A)\X = StartX And Grid(A)\X = StartX
;If Grid(A)\Z < StartZ + 5 And Grid(A)\Z > StartZ - 5
If Grid(A)\Z = StartZ And Grid(A)\Z = StartZ
;The Character is within Grid(A)'s coords, Make this Cell, the Start Cell
StartCell = A
Grid(A)\Parent = A
Exit
End If
End If
A = A + 1
Wend
;;Save info To check it
FileOut = WriteFile("PathInfo.dat")
If StartCell > 0
;WriteLine(FileOut,Grid(StartCell)\ID+", "+Grid(StartCell)\X+", "+Grid(StartCell)\Z+", "+Grid(StartCell)\Walkable+", "+Grid(StartCell)\Parent)
WriteLine(FileOut,StartCell)
EndIf
CloseFile FileOut
End Function
;----------------------------------------------------------------------------------
3 - Save Path Work backwards from the stored path to create a path from beginning pos to target position. 4 - Move Player Move the player entity using the stored path procedure. again, any help would be greatly appreciated!! |
| ||
| If you have the memory, I would try and hold a weighted map of the terrain for each different type of movement that any units have, that is walking, tracked wheeled etc. Also, again dep on memory, try to precalculate some routes before hand, (say across bridges etc), then when your pathfinding get to a node at either end of these, it knows to just follow them. If you are moveing groups of units, add weight to "secondary" routes based on how far that route is from the mian route, so as to avoid "wandering units" |
| ||
| So you would basically preplot movable areas of a unit by say coloring a terrain map, like drawing roads for wheeled vehicles and such? Can you give an example of this method? Like... Make a map for Tanks, Color Tank Roads yellow on a map of the terrain. In Code, if a tank is selected to move, use readpixel to find out if target position is yellow? Thanks for the help. |
| ||
| Did you see Kevin8084's new code entries here? http://www.blitzmax.com/codearcs/codearcs.php?cat=2 |
| ||
| Thanks MarkD, I looked it over and it does add to the A* Beginners tut, but alot of it is the same explanation. Kevins Code is pretty good, but a wee bit higher level than I was looking for, using heaps and math. I will look at it some more. Thank you. I updated the original post adding some comments to the make grid and changed start search to find path with more comments. |
| ||
| 2 - Find Path Using Player position, do a path search as explained in www.policyalmanac.org/games/aStarTutorial.htm 1 - Move Character to nearest Cells Coordinates, if not there already 2 - Put Start Cell in Closed list 3 - Check each adjecent cells Fcost value, Fill in the Cells Fcost, Gcost, Hcost, Walkable, Parent Values here. 4 - Add each adject cell to open list 5 - Pick the cell with lowest FCost 6 - Make that Cell the new Start Cell 7 - Repeat 2 - 7 until Target Cell is added to closed list Try: 1. Move Character to current Node 2. Place current Node on closed list 3. Check adjacent nodes 4. If adjacent node is walkable (i.e, yellow on map) and not on open list then place on open list and calculate costs. 5. If adjacent node is already on open list then calculate if shorter path through current Node. If shorter path then make current Node the parent and calculate costs for child node, else ignore the node. 6. Take node with lowest FCost and place on closed list. Make this node the current node. 7. repeat from step 3 until current Node = target Node or until there are no more nodes on open list (in which case there IS no path) |
| ||
| Thanks for the info Kevin8084. Before I start smacking the keyboard to try and futher my understanding of this, I need to ask, The open list is a list of available Cells to look at, to determine if they are the actual cell that leads to the target? The Closed list is a list of cells that have been looked at, they are the cells that make up the actual path? I am attempting to use the above psuedo to make a Pathfinding program that I understand 100% and can incorporate into my ongoing adventure, lol. Thank you. I also updated the Create Grid part, I added the code I am attempting to use to create a grid based on map dimensions I also added the beginning part of the Find Path, It locates the current cell in the Grid Container based on players position. |
| ||
| The open list is a list of children cells (cells adjacent to the current cell). The closed list is a list of cells that have been looked at already (they are not necessarily part of the actual path)...take into account the parent pointer to get your actual return path. Sorry for the delay...been playing GuildWars NightFall :) |
| ||
| "been playing GuildWars NightFall :)" Me too :) :) great game ! |
   |