Pathfinding...
Blitz3D Forums/Blitz3D Beginners Area/Pathfinding...
| ||
| So im basically looking for help with a 3d pathfinding system and help with how i would go about storing nodes and their properties eg, parent, h, g, f values |
| ||
About the storage of nodes: user-types are here for that reason.Type pathNODE Field pivot% Field h%,g%,f% Field parent.pathNODE Field children.pathNODE[100] End TypeYou can learn more about Types by: - Looking in the Blitz3D documentation for the keyword "Type"; - Searching these forums; - At the Blitz3D tutorials section; - Reading online articles about the subject (blitzCoder and jNoodle). You should use Types to encapsulate and organize almost everything, all kinds of data your game may have - "if you can store it inside a Type, then you should". EDIT: General Blitz Basic tutorials that may be useful for you - http://www.krylarskreations.com/bc/ Last edited 2012 |
| ||
| wow, sometimes the most simple things pass under radar lol. i know a fair amount about types but i have a few specific questions that you may be able to answer so i do not have to delve into far more reading than i need to. first, simple question im sure i actually know the answer (its been awhile) why the "%" after the pivot and the values. and then what the effect of the period is in between the lower fields. thank you much! |
| ||
| The % indicates that these fields are integer values. Some people put them there to make it clear what type of variable it is, but for integers, it can be ignored as integer is the default type if it's not specified. So "pivot%" is the same as "pivot", they both hold integer values. The period in between indicate these fields hold a reference to another type-instance (in this case, the "pathnode" type). So one pathnode instance holds a reference to another pathnode instance, where the reference is stored in the field "parent". Also, the lowest is an array which holds up to 100 references to 100 instances of "pathnode". Last edited 2012 |
| ||
| Those suffixes are how you declare a variable's data-type. In Blitz3D you use symbols to declare a variable's data-type: "%" for Int, "$" for String and "#" for Float. If you don't use any suffix, Blitz3D will consider by default the variable to be of Integer type, but for readibility's sake you should always declare Int variables the same way as the others - use the "%" symbol. When dealing with Types, you need to use the "dot + TypeName" suffix for declaring variables that will hold user-types. If I create a variable like this: "Local myPlayer.playerType", this variable will only be able to hold instances of the "playerType" value. Those last two fields relate to node hierarchy. They'll hold 'pathNODE' values and as such are declared that way. EDIT: Ninja'd by PowerPC603! x) Last edited 2012 |
| ||
| so first off, in your example you have made it assume 100 nodes have been created? and would i not need to define parent and children in the fields? eg Type pathNODE Field pivot% Field h%,g%,f% Field parent Field children Field parent.pathNODE Field children.pathNODE[100] End Type also thank you for holding in here i know i can be a bother badgering people for help lol |
| ||
| It's kinda complicated. Standard Blitz3D arrays are created with the Dim command. "Dim myArray(499) ;Array with 500 slots." (The number inside parenthesis is the index of the last slot, rather than the total amount of slots, so going from 0 to 499 you have 500 total.) But if you want to have arrays inside an user-type you can only use Blitz-Array arrays, which are different. They're declared with brackets: Type myType Field myArray#[100] ;Blitz-Array of 101 slots. End Type BlitzArrays can't be resized, so you always need to specify the total amount of slots at first. They can also be used outside types - Read more here. I chose 101 because it's a safe number: thinking of a random navigational map, it'd be hard for a single node to have more than 101 children. It's speculatory of course. As you build your game, get your worst case scenario (the one node with most children, in all of the levels), and use that as your max, fixed value, so you know you're safe for all other nodes. Even if other nodes have like, one or even zero children, the redundant memory cost is negligible. |
| ||
| would my max amount of children not be 8 though? (assuming we are using grid based nodes i guess) regardless i shall study up on arrays and things of the sort. OH wait the 100 is the max amount of nodes (IDs) that i would allow in said map pathing Last edited 2012 |
| ||
| I didn't know about this site "blitzcoder". I post a link here to access the articles : http://membres.multimania.fr/blitzcoder/articles.shtml |
| ||
| Psychicbottle>> Here is an example of how i store the infos about the nodes, the links, the paths (for a grid system or for a nodes around obstacles system) In my code each node is child of a room so that i can calculate a path in a room with only some nodes of the level/area const RoomsMaxCount% = 100 ; this is the number of Rooms per level/area const NodesPerRoomMaxCount% = 400 ; you may want to change this value depending on the number of cells or of nodes per obstacle Dim NodesCount%(RoomsMaxCount) ; number of nodes in this room Dim NodeOrigine(RoomsMaxCount,NodesPerRoomMaxCount) ; pivot representing the node, (of course you can replace this by X,Z coordinates) Dim NodeLinkToNode%(RoomsMaxCount,NodesPerRoomMaxCount,20) ; 20 links max per node, these links are precalculated, (if you use a grid system, there will be only 4 or 8 links per node) Dim NodeFDistance#(RoomsMaxCount,NodesPerRoomMaxCount) ; This is used to store the FDistance (= Distance from Character to this node + Distance from this node to Target) Dim NodeState%(RoomsMaxCount,NodesPerRoomMaxCount) ; this is to store the state of the node, to know if this node as already been processed in the pathcalculation routine) Then for each character, i store the last calculated path : PathsMaxCount% = CharactersMaxCount ; each path is associated to a character who has the same id PathNodesList%(PathsMaxCount,100) ; 100 nodes max in a path PathState%(PathsMaxCount) ; this is to store the state of the path, if it has been completed or not. PathNodeS%(PathsMaxCount) ; this is to store the id of the NodeStart (the nearest node from the character) PathNodeE%(PathsMaxCount) ; this is to store the id of the NodeEnd (the nearest node from the target) PathNodeT%(PathsMaxCount) ; this is to store the id of the NodeTarget (the node where the character has to turn and to move towards) I haven't finished to code all my routines but i think it will be functional. Maybe it can give you some ideas. Last edited 2012 |
| ||
| well, iv'e obviously got some studying to do here, thanks for all your help. if anybody is interested in guiding me on how to make a semi-good pathfinding system then please let me know or if you find anything related to pathfinding with blitz then post a link, thanks! :) also if anyone has the zip file used in the A* tut on the link from earlier i would appreciate a look at it as the download on the website is no more :) Last edited 2012 |
| ||
| @Kryzon How are ou able to create an array inside a type without a dim statement |
| ||
| How are ou able to create an array inside a type without a dim statement There are two different and unrelated kinds of array in B3D, as Kryzon touches on in post #7 but doesn't explain fully. "Dim", or BASIC-style, arrays are always global and unique, cannot be treated as value objects in their own right, can be resized at any time, can have as many dimensions as you like, are declared with the special "Dim" keyword, and their values are accessed with parentheses:
Dim myArray(10, 2) ;Declaration
myArray(1, 1) = 123 ;Element set
Local foo = myArray(1, 1) ;Element get
For foo = 1 to 5
Dim myArray(10, foo) ;Dynamic resize
Next
f()
Function f()
Print myArray(3, 0) ;Global access, OK
Dim myArray2(10) ;Error, myArray2 was never declared in a global context (scoped Dim statements can only be a resize)
End FunctionThe other kind, "Blitz arrays", or C-style, have a different set of advantages and disadvantages: They are declared the same way as variables, but with a size instead of an initial value (and locals have to be declared explicitly); they can have any of the three variable scopes (local, global or field); they can be passed as parameters, meaning you can use them as value objects (although not put in other variables or returned); they can only have one dimension; they can not be resized (and the size is considered part of the array type); and their values are accessed with square brackets: Global myArray1[10] ;Declaration
Local myArray2[10]
Type Foo
Field myMemberArray[10]
End Type
myArray1[5] = 15 ;Element set
Local n = myArray1[5] ;Element get
Function arrScopeTest()
Print myArray1[5] ;Accessing a global, OK
Print myArray2[5] ;Error: no local by that name exists in this scope
End Function
Function arrFunc(arr[10]) ;Array parameter
Print arr[3] ;Localised access through parameter
End Function
arrFunc(myArray1) ;Pass in an array
arrFunc(myArray2)
Local f.Foo = New Foo
arrFunc(f\myMemberArray) ;Pass an array field like any other field value
Local myArray3[15]
arrFunc(myArray3) ;Error, myArray3 is of type %[15] and we can only pass type %[10]Both kinds of array can hold values of any type: int, float, string, and objects. Last edited 2012 |
| ||
ok, i have created a grid (im using a grid if you didn't know) that you can size, actually its kinda hard to explain... i didn't want to do this cause my messy coding is embarrassing but im in dire need of help.Global G_grid_cell_size# = 1.0
Graphics3D 600, 600, 0, 2
SeedRnd MilliSecs()
Global CamPivot = CreatePivot( ) ;create camera pivot
Global camera = CreateCamera( ) ;create camera with CamPivot as parent
MoveEntity CamPivot,0,30,0 ;Move camera above terrain
RotateEntity camera ,90,0,0
EntityType CamPivot, 1
EntityRadius CamPivot, 1.5
EntityType camera, 1
EntityRadius camera, 1.5
Global G_light = CreateLight()
Global R# = 255
Global G# = 255
Global B# = 255
Global t$
Global PN = 0
Global G_cube = CreateCube()
ScaleMesh G_cube, 0.5, 0.5, 0.5
PositionMesh G_cube, 0.5, 0.5, 0.5
EntityColor G_cube,80,0,255
EntityAlpha G_cube ,.4
Global G_picked_entity
Global G_grid = CreateGrid()
EntityPickMode G_grid, 2
nodeprecounter = 0
Type node
Field model
Field x,z,id,u,d,r,l
Field parent
End Type
nodegridsize = 10
For mw = 1 To nodegridsize
For mz = 1 To nodegridsize
nodeprecounter = nodeprecounter + 1
n.node = New node ;create a new badguy
n\model = CopyEntity(g_cube)
EntityColor n\model,255,255,255
EntityAlpha n\model ,1
n\x = mz
n\z = -mw
n\id = nodeprecounter
n\u = n\id - 10
n\d = n\id + 10
n\r = n\id + 1
n\l = n\id - 1
PositionEntity n\model ,n\x,-1.01,n\z
Next
Next
SetBuffer BackBuffer()
Type cubetype
Field entityhandle
Field top
End Type
cyl=CreateCylinder()
cub=CreateCube()
HideEntity cub
HideEntity cyl
cube = cub
PositionMesh cub, 1, 1, 1
PositionMesh cyl, 1, 1, 1
EntityType cube, CUBE_COL ;set up collision type for the badguy
EntityRadius cube, .5, .95 ;set up collision radius for the badguy (1.9 meters tall, .6 meters wide)
HideEntity cube ;this will also exclude them from collisions
ScaleEntity cub,.5,.5,.5
ScaleEntity cyl,.5,.5,.5
;MAIN LOOP+++++++++++++++++++++++++++++++++++
While Not KeyHit( 1 )
MoveEntity campivot,0,-MouseZSpeed()*5,0
If KeyDown(42)
If MouseHit(1)
MoveMouse GraphicsWidth()/2, GraphicsHeight()/2 ;move mouse pointer to center of screen
EndIf
If MouseDown(1)
HidePointer
MoveEntity campivot,-MouseXSpeed()/5,0,MouseYSpeed()/5
Else
ShowPointer
EndIf
EndIf
UpdateWorld
PositionEntity Camera, EntityX#( CamPivot ), EntityY#( CamPivot ), EntityZ#( CamPivot )
RenderWorld
Text 0,20,"Picked : "+t$
Text 0,50,"node_id# : "+id#
Text 0,100,"U : "+node_above
Text 0,150,"D : "+node_down
Text 0,200,"R : "+node_right
Text 0,250,"L : "+node_left
Flip
Delay( 1 )
G_picked_entity = CameraPick( camera, MouseX(), MouseY() )
If G_picked_entity
x# = Floor ( PickedX() / G_grid_cell_size# ) * G_grid_cell_size#
z# = Floor ( PickedZ() / G_grid_cell_size# ) * G_grid_cell_size#
y# = Floor ( PickedY() / G_grid_cell_size# ) * G_grid_cell_size#
PositionEntity G_cube, x#, -1, z#
EndIf
For n.node = Each node
If n\x = x# And n\z = z#
id# = n\id
node_above = n\u
node_down = n\d
node_right = n\r
node_left = n\l
EndIf
Next
Wend
End
Function CreateGrid()
; -- Create grid texture.
Local i, x, y
Local grid_2d_tex = CreateTexture ( 256, 256, 11 )
SetBuffer TextureBuffer ( grid_2d_tex )
For i = 0 To 4
Rect i, i, 256 - i - i, 256 - i - i, False
Next
For y = 5 To 250
For x = 5 To 250
WritePixel x, y, 0
Next
Next
;^^^^^^
; -- Create 2D grid.
Local grid_2D = CreatePlane ()
EntityTexture grid_2D, grid_2d_tex
EntityFX grid_2D, 9
;^^^^^^
Return grid_2D
End FunctionSo im having trouble making a way to sense which nodes are touching other ones the method im currently using is flawed massively,,,, Last edited 2012 Last edited 2012 |
| ||
| ok so i tried putting this in there to see if i could fin surrounding nodes this way... figured it wouldnt work but gave it a shot... For n.node = Each node If n\x = x# And n\z = z# id# = n\id node_above = n\u node_down = n\d node_right = n\r node_left = n\l If EntityDistance(n\model,n\model) < 1 Then EntityColor n\model,0,255,0 EndIf Next |
| ||
| im not trying to bug... but im very lost, help? :D |
| ||
| Psychicbottle>> There are several ways to create links between 2 nodes on a grid. You can use a 2 dimensions array in order to set and store the parameters of the cells. for example : ;each cell can be of one of this kind Const Empty% = 0 ; (not walkable) Const Ground% = 1 (walkable) Const Wall% = 2 (not walkable) Const Obstacle% = 3 (not walkable or crossable with a specific move) Dim NodeKind%(99,99) ;this is a 2 dimensions array to store each cell kind depending on its X,Z coordinates, this array can store 100*100 cells, from 0X,0Z to 99X,99Z You can use a custom level editor or the pixels of an image to define the kind of each cell. Once you have done that, you can either keep your 2 dimensions array and create links between some cells or you can create nodes at the center of walkable cells and then create links between nodes that are next to each other. For the first solution, for each cell, you can check what is the kind of the cell at back (X,Z-1), at front (X,Z+1), at left (X-1,Z), at right (X+1,Z) and see if a link is possible or not between this cell and the other cell. (if the other cell is walkable or not) For the second solution, for each node, you can check which other node is at a distance of less than 1.001 (if you use a 1 unit grid system) and see if a link is possible or not between this node and the other node. (if the other node is near enough or not) If you don't understand these explanations, maybe you can study some examples in the code archives : you can type this in bing or google : astar site:blitzbasic.com Last edited 2012 |
| ||
| GAH! thank you so much, i think i'm on to a method for my madness ;) ill go out and smash on the keyboard for a few hours now, thank you much. |
| ||
| so.. they dont have a ton of information on these x,y arrays, how would i assign them to a node and then call upon it later for use? sorry not trying to nag, just get some information |
| ||
| ;this is a 2 dimensions array to store each cell kind depending on its X,Z coordinates, this array can store 100*100 cells, from 0X,0Z to 99X,99Z This means : the infos of the cell who has the coordinates 0X,0Y,0Z can be set/retrieved by using Cell(0,0) the infos of the cell who has the coordinates 99X,0Y,99Z can be set/retrieved by using Cell(99,99) the infos of the cell who has the coordinates 10X,0Y,5Z can be set/retrieved by using Cell(10,5) For the first solution, for each cell, you can check what is the kind of the cell at back (X,Z-1), at front (X,Z+1), at left (X-1,Z), at right (X+1,Z) and see if a link is possible or not between this cell and the other cell. (if the other cell is walkable or not) This means : For X% = 0 to 99 For Z% = 0 to 99 ;The current Cell is Cell(X,Z) ;The cell at back of this cell is Cell(X,Z-1) ;The cell at front of this cell is Cell(X,Z+1) ;The cell at left of this cell is Cell(X-1,Z) ;The cell at right of this cell is Cell(X+1,Z) Next Next you can either keep your 2 dimensions array and create links between some cells or you can create nodes at the center of walkable cells and then create links between nodes that are next to each other. This means : You can either create links between some cells or create nodes on some cells (and delete the array of the cells once you have your nodes) For 3D games where you can't fly, a node can be stored by creating a pivot or by storing its X,Z coordinates. You can use arrays or types for this. Study, study, study, study, study. http://www.youtube.com/watch?v=HCi_vMQBUls Last edited 2012 |
| ||
| thank you much, will do : |
| ||
we.. ive been studying and yet i am still having problems with my code, im getting head aches and no results... if anybody can help crack this one i would appreciate it cause im just not grasping this well i guess....Global G_grid_cell_size# = 1.0 Graphics3D 600, 600, 0, 2 SeedRnd MilliSecs() Global CamPivot = CreatePivot( ) ;create camera pivot Global camera = CreateCamera( ) ;create camera with CamPivot as parent Global calcnodex Global calcnodey MoveEntity CamPivot,0,30,0 ;Move camera above terrain RotateEntity camera ,90,0,0 EntityType CamPivot, 1 EntityRadius CamPivot, 1.5 EntityType camera, 1 EntityRadius camera, 1.5 Global G_light = CreateLight() Global R# = 255 Global G# = 255 Global B# = 255 Global t$ Global PN = 0 Global G_cube = CreateCube() ScaleMesh G_cube, 0.5, 0.5, 0.5 PositionMesh G_cube, 0.5, 0.5, 0.5 EntityColor G_cube,80,0,255 EntityAlpha G_cube ,.4 Global G_picked_entity Global G_grid = CreateGrid() EntityPickMode G_grid, 2 nodeprecounter = 0 Type node Field model Field x,z,id,u,d,r,l Field parent Field nx,ny,children[3] End Type Global array[3] nodegridsize = 10 For mw = 1 To nodegridsize For mz = 1 To nodegridsize nodeprecounter = nodeprecounter + 1 n.node = New node ;create a new badguy n\model = CopyEntity(g_cube) EntityColor n\model,255,255,255 EntityAlpha n\model ,1 n\x = mz n\z = -mw n\id = nodeprecounter n\u = n\id - 10 n\d = n\id + 10 n\r = n\id + 1 n\l = n\id - 1 n\nx = mz n\ny = mw PositionEntity n\model ,n\x,-1.01,n\z Next Next SetBuffer BackBuffer() Type cubetype Field entityhandle Field top End Type cyl=CreateCylinder() cub=CreateCube() HideEntity cub HideEntity cyl cube = cub PositionMesh cub, 1, 1, 1 PositionMesh cyl, 1, 1, 1 EntityType cube, CUBE_COL ;set up collision type for the badguy EntityRadius cube, .5, .95 ;set up collision radius for the badguy (1.9 meters tall, .6 meters wide) HideEntity cube ;this will also exclude them from collisions ScaleEntity cub,.5,.5,.5 ScaleEntity cyl,.5,.5,.5 ;MAIN LOOP+++++++++++++++++++++++++++++++++++ While Not KeyHit( 1 ) MoveEntity campivot,0,-MouseZSpeed()*5,0 If KeyDown(42) If MouseHit(1) MoveMouse GraphicsWidth()/2, GraphicsHeight()/2 ;move mouse pointer to center of screen EndIf If MouseDown(1) HidePointer MoveEntity campivot,-MouseXSpeed()/5,0,MouseYSpeed()/5 Else ShowPointer EndIf EndIf UpdateWorld PositionEntity Camera, EntityX#( CamPivot ), EntityY#( CamPivot ), EntityZ#( CamPivot ) RenderWorld Text 0,20,"Picked : "+t$ Text 0,50,"node_id# : "+id# Text 0,100,"U : "+node_above Text 0,150,"D : "+node_down Text 0,200,"R : "+node_right Text 0,250,"L : "+node_left Text 0,300,"n\x : "+ x# Text 0,350,"n\y : "+ z# G_picked_entity = CameraPick( camera, MouseX(), MouseY() ) If G_picked_entity x# = Floor ( PickedX() / G_grid_cell_size# ) * G_grid_cell_size# z# = Floor ( PickedZ() / G_grid_cell_size# ) * G_grid_cell_size# y# = Floor ( PickedY() / G_grid_cell_size# ) * G_grid_cell_size# PositionEntity G_cube, x#, -1, z# EndIf For n.node = Each node If n\x = x# And n\z = z# id# = n\id node_above = n\u node_down = n\d node_right = n\r node_left = n\l calcnodex = n\nx calcnodey = n\ny FindChilder() n\children[0] = f n\children[1] = g n\children[2] = h n\children[3] = j EndIf Next Flip Delay( 1 ) Wend End Function CreateGrid() ; -- Create grid texture. Local i, x, y Local grid_2d_tex = CreateTexture ( 256, 256, 11 ) SetBuffer TextureBuffer ( grid_2d_tex ) For i = 0 To 4 Rect i, i, 256 - i - i, 256 - i - i, False Next For y = 5 To 250 For x = 5 To 250 WritePixel x, y, 0 Next Next ;^^^^^^ ; -- Create 2D grid. Local grid_2D = CreatePlane () EntityTexture grid_2D, grid_2d_tex EntityFX grid_2D, 9 ;^^^^^^ Return grid_2D End Function Function findchildren(n.node) For i = 0 To 3 n\children[i] = Rnd(100) Next End Function Function FindChilder() For n.node = Each node For i = 0 To 3 If n\nx = calcnodex+1 And n\ny = calcnodey EntityColor n\model ,0,255,0 an = n\id Else If n\nx = calcnodex-1 And n\ny = calcnodey EntityColor n\model ,0,255,0 bn = n\id Else If n\nx = calcnodex And n\ny = calcnodey-1 EntityColor n\model ,0,255,0 cn = n\id Else If n\nx = calcnodex And n\ny = calcnodey+1 EntityColor n\model ,0,255,0 dn = n\id Else EntityColor n\model ,255,200,255 an = 0 bn = 0 cn = 0 dn = 0 EndIf Text 0,470, "child1: "+an Text 10,460,"child1: "+bn Text 20,450,"child1: "+cn Text 30,440,"child1: "+dn Next Next End Function |
| ||
| im having trouble transferring the node ids to the parent node's child list. |
   |