A* pathfinding....

Blitz3D Forums/Blitz3D Programming/A* pathfinding....

psychicbottle

(Posted 2012) [#1]

so i tried this on another forum but i think i did not place it well so i will try it here.
I am having trouble with my A* code, ive basically written it from scratch but am at a dead halt now cause im having trouble finding then storing the child nodes to the parent nodes. heres my code,

 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

Last edited 2012

RemiD

(Posted 2012) [#2]

I don't know how to achieve the same results with "Type" but maybe this will give you some ideas :

I don't understand what you mean by node childs.
There are nodes, and there are links between some nodes and some others nodes.

If you use a grid based system, there are maximum 4 links per node to others nodes.

I store the others nodes Id like this :
NodeLinkToNode(NodeId%,LinkId%) ;NodeId% is the id of this node, LinkId% is the id of this link (from 0 to 4 links per node in this case), and the stored value is the ONodeId% the id of the other node.

Now see why i use Dim instead of Type to store my nodes :
This is my function to create the links between nodes for a grid system :

Function LinksCreate(ZId%)
 For NId% = 1 To NodesCount(ZId)
  For ONId% = 1 To NodesCount(ZId)
   If(ONId <> NId)
    VLength# = VLength2D#(NodeX(ZId,NId),NodeZ(ZId,NId),NodeX(ZId,ONId),NodeZ(ZId,ONId))
    If(VLength# < 1.001)
     NodeLinksCount(ZId,NId) = NodeLinksCount(ZId,NId) + 1
     LId% = NodeLinksCount(ZId,NId)
     NodeLinkToNode(ZId,NId,LId) = ONId     
    EndIf
   EndIf
  Next
 Next
End Function

Don't worry about ZId%, you can remove them if you want, this is to store Nodes per Zone instead of having all the Nodes of the Level involved in the path calculation.

For a system with nodes not positionned on a grid, you want to increase the distance check and add a linepick or moving collider check between the Node and the ONode in order to check if a path is possible.

Then when you use the AStar routine, you need to retrieve the ONodes connected to the current Node.
You can do it like this :

NId% = 3 ; the id of this node
For LId% = 1 to NodeLinksCount(ZId,NId)
 ONId% = NodeLinkToNode(ZId,NId,LId) ; With this you get the Id of the ONode connected to this node
 Distance# = VLength2D#(NodeX(ZId,NId),NodeZ(ZId,NId),NodeX(ZId,ONId),NodeZ(ZId,ONId)) ; With this you have the distance from Node to ONode
 ;Then you need to calculate the distance from ONode to Target
 ;Then you need to add the 2 previous distances and to compare it with the others distances calculated with the others nodes connected to this node.
 ;Then you know which other node connected to this node is the nearest from this node and to the Target
Next

Last edited 2012

psychicbottle

(Posted 2012) [#3]

thank you so much, RemiD.
i haven't gotten a chance to throuroughly look through this yet but from what i have seen it looks understandable and useful. i'll let you know if i have any problems with it if you dont mind.
cheers

psychicbottle

(Posted 2012) [#4]

i did want to ask your opinion on this http://www.blitzbasic.com/Community/posts.php?topic=39354#440007

it mentions the use of banks since they use minimal memory and a very fast, would you think this is a viable option? maybe not for a beginner but just in general blitz3d pathfinding.

RemiD

(Posted 2012) [#5]

I think you can use Dim arrays or Types to store the infos of your nodes.

What is important is to organize your code in a way that it doesn't have to search one node in a list with all nodes.

In the example above, for each Node, i store the possible links from this node to others nodes.

Then when i need to retrieve the infos of another node connected to this node, i only have to search a list of 4 nodes instead of a list of 10x10 nodes or 100x100 nodes (depending on your grid size.)

Another advantage of nodes compared to using Cell(X,Z) is that once you have created the walls, the doors, the columns, the furnitures, the plants, the rocks, you can create nodes only where the cells are empty, so even if you have a 100x100 grid, you will have less than 100x100 nodes. Hence, the list will be smaller.

If you want to go one step further, you forget about the grid based pathfinding, and you use a "node around obstacles" pathfinding which is, in my opinion, more realistic and faster. (there are nodes only around obstacles, and up to x links from each node to others nodes)