I am trying to make triangular grid for pathfinding but it is kinda difficult to generate it.
What I have is:
1) Node
type Nodes
ID as integer
fill as integer `0 passable, 1 obstacled
x as float
y as float
z as float
c1 as integer `6 connections- no arrays allowed in DBP type :(
c2 as integer
c3 as integer
c4 as integer
c5 as integer
c6 as integer
prevNode as integer `node from which this node was reached
cover as vector6 `this has no effect now
endtype
` c6 c1
`c5 ID c2
` c4 c3
2) not working properly grid generator
function MakePathfindingGrid(ni as integer, nj as integer, nodeLenght as float)
NodesNumber=ni*nj
global dim Node(NodesNumber) as nodes
n=0
for i=1 to ni
for j=1 to nj
inc n,1
node(n).ID=n
node(n).fill=0
node(n).x=(i+ 0.5*(j mod 2))*nodeLenght
node(n).z=(j*sin(60))*nodeLenght
node(n).y= get terrain ground height (1, node(n).x, node(n).z)
if i<ni then node(n).c2=nj*(j-1)+i+1
if i>1 then node(n).c5=nj*(j-1)+i-1
if j mod 2 = 0 `second row specific
node(n).c6=nj*(j-2)+i
if i<ni then node(n).c1=nj*(j-2)+i+1
if j<nj
if i<ni then node(n).c3=nj*j+i+1
node(n).c4=nj*j+i
endif
else `first row specific
if j>1
if i>1 then node(n).c6=nj*(j-2)+i-1
if i<ni then node(n).c1=nj*(j-2)+i
endif
if j<nj
if i<ni then node(n).c3=nj*j+i
node(n).c4=nj*j+i-1
endif
endif
make object sphere 1000+n,1
position object 1000+n,node(n).x,node(n).y+1, node(n).z
next j
next i
endfunction
3)pathfinding algorithm
function findPath(obj)
col=1 `=sc_raycast(0, object position x(obj), object position y(obj), object position z(obj), unit(objecttoUnit(obj)).dx, unit(objecttoUnit(obj)).dy+5, unit(objecttoUnit(obj)).dz, 1)
if col=0
addwarning("no collision",1)
unit(objecttoUnit(obj)).nx=unit(objecttoUnit(obj)).dx
unit(objecttoUnit(obj)).nz=unit(objecttoUnit(obj)).dz
else
`addwarning(str$(col),2)
n1=nearestNode(obj) `node A
color object 1000+n1, rgb(0,0,255)
text 200,100, "Start node "+str$(n1)
n2=nearestNodeCoord(unit(objecttoUnit(obj)).dx,unit(objecttoUnit(obj)).dz) `node B
color object 1000+n2, rgb(0,255,0)
text 200,120, "End node "+str$(n2)
empty array SearchList(0)
add to stack SearchList(0) `list of nodes to be searched
SearchList(0)=n1
checkNum as integer =0 `count search steps to do limited lenght search
found as boolean =0
while array index valid(SearchList(0))&& checkNum<10 && found<1
sms("Check Num "+str$(checkNum)) `stop program and wait key pressed ( debugging utility ;D )
inc checkNum,1
if node(SearchList(0)).ID>0
if SearchList(0)=n2 then found=1 `if current node is node B
if node(SearchList(0)).c1>0 `if connection has value
node(node(SearchList(0)).c1).prevNode=SearchList(0) `connected node can be accessed from current node
add to stack SearchList(0) `add connected node into search list
SearchList(0)=node(SearchList(0)).c1
color object 1000+node(SearchList(0)).c1, rgb(0,255,100)
endif
if node(SearchList(0)).c2>0
node(node(SearchList(0)).c2).prevNode=SearchList(0)
add to stack SearchList(0)
SearchList(0)=node(SearchList(0)).c2
color object 1000+node(SearchList(0)).c2, rgb(0,255,100)
endif
if node(SearchList(0)).c3>0
node(node(SearchList(0)).c3).prevNode=SearchList(0)
add to stack SearchList(0)
SearchList(0)=node(SearchList(0)).c3
color object 1000+node(SearchList(0)).c3, rgb(0,255,100)
endif
if node(SearchList(0)).c4>0
node(node(SearchList(0)).c4).prevNode=SearchList(0)
add to stack SearchList(0)
SearchList(0)=node(SearchList(0)).c4
color object 1000+node(SearchList(0)).c4, rgb(0,255,100)
endif
if node(SearchList(0)).c5>0
node(node(SearchList(0)).c5).prevNode=SearchList(0)
add to stack SearchList(0)
SearchList(0)=node(SearchList(0)).c5
color object 1000+node(SearchList(0)).c5, rgb(0,255,100)
endif
if node(SearchList(0)).c6>0
node(node(SearchList(0)).c6).prevNode=SearchList(0)
add to stack SearchList(0)
SearchList(0)=node(SearchList(0)).c6
color object 1000+node(SearchList(0)).c6, rgb(0,255,100)
endif
color object 1000+SearchList(0), rgb(250,100,100)
remove from stack SearchList(0) `remove checked node from list
endif
endwhile
endif
if found `trace nodes back from B to A
empty array Path(0)
while n2<>n1
add to queue Path(0)
Path(0)=node(n2).prevNode
n2=node(n2).prevNode
endwhile
endif
endfunction found
Algorithm works like this:
1) start node is put into search list
2) while search list isn't empty, limit og steps isn't reached or end node wasn't found
every nodes in search list every connection is checked and if not already searched and walkable it is added into search list (stack)
3) if end node reached, from it algorithm traces previuos nodes back to start node and puts into queue.
problem is that I can't calculate connections. I though at first my nodes are placed in shifted lines
1 2 3 4
_5 6 7 8
9...
but it came out that they are placed in two rows
1 3 5
_2 4 6
7 9 11
_8 10 ...
It took long time to write algorithm to connect nodes in shifted rows... I don't know if it is possible to write it for rows of two shifted rows
Looks like a hard candy. Anyone will help with that?
Any advice appreciated
PS If You try running program:
select unit/make it move with mouse
move camera with arrows/wasd
rotate camera- hold middle mouse button and move around
red nodes are obstacled or already checked
green are in earch list
You will need to press any key to advance because I put some stop functions to see step by step process of pathfinding
sms(string) and smsf(float) prints text and waits key
because connections are set not to adjacent nodes, random nodes are added into search list. Green nodes should spread like a ring around unit.
Join The dark Side! We have cookies
